Using quotient graphs to model neutrality in evolutionary search

ABSTRACT

We introduce quotient graphs for modeling neutrality in evolutionary search. We demonstrate that for a variety of evolutionary computing problems, search can be characterized by grouping genes with similar fitness and search behavior into quotient sets. These sets can potentially reduce the degrees of freedom needed for modeling evolutionary behavior without any loss of accuracy in such models. Quotients sets, which are also shown to be Markov models, aid in understanding the nature of search. We explain how to calculate Fitness Distance Correlation (FDC) through quotient graphs, and why different problems can have the same FDC but have different dynamics. Quotient models also allow visualization of correlated evolutionary drives.

References

1. D. Cvetkovic, P. Rowlinson, and C. Simic, Eigenspaces of Graphs. Encyclopedia of Mathematics and its Applications, Vol. 66, Cambridge University Press, 1997.
2. P.F. Stadler, and G. Tinhofer, .Equitable partitions, coherent algebras, and random walks: applications to the correlation structure of landscapes, MATCH 40 pp.215--261, 2000.
3. C. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, NY. 1993.
4. M. Shpak, P. F. Stadler, G. P. Wagner, and J. Hermisson. .Aggregation of variables and system decomposition: application to fittness landscape analysis, Theory in Biosciences 123: 33--68, 2004.
5. T. Jones and S. Forrest .Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms, Proceedings of the Sixth International Conference on Genetic Algorithms. pp. 184--192, 1995.
6. T. Jones.: Evolutionary Algorithms, Fitness Landscapes and Search. PhD thesis, University of New Mexico, Albuquerque (1995).
7. R. Poli and E. Galvan .On the Effects of Bit-Wise Neutrality on Fitness Distance Correlation, Phenotypic Mutation Rates and Problem Hardness, FOGA 2007.
8. Tomassini, M., Vanneschi, L., Collard, P., Clergue, M.: A study of fitness distance correlation as a difficulty measure in genetic programming. Evolutionary Computation 13(2), 213--239, 2005.
9. B. Naudts and L. Kalle .A comparison of predictive measures of problem difficulty in evolutionary algorithms. IEEE Transactions Evolutionary Computation 4(1), 1--15, 2000.
10. L. Altenberg, .Fitness distance correlation analysis: An instructive counterexample, Proceedings of the Seventh International Conference on Genetic Algorithms, San Francisco, CA, USA, 1997, pp. 57--64. Morgan Kaufmann Publishers Inc. San Francisco, 1997.
11. R. Thomason and T. Soule .Redundant genes and the evolution of robustness., Proceedings of the 8th annual conference on Genetic and evolutionary computation. Seattle, Washington, USA pp. 959 -- 960, 2006.
12. N. Richter, J. Paxton and A. Wright. EA Models and Population Fixed-Points Versus Mutation Rates for Functions of Unitation. GECCO 2005, Genetic and Evolutionary Computation Conference. June 2005.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Philosophical/theoretical foundations of artificial intelligence