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.
- D. Cvetkovic, P. Rowlinson, and C. Simic, Eigenspaces of Graphs. Encyclopedia of Mathematics and its Applications, Vol. 66, Cambridge University Press, 1997.Google Scholar
- 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.Google Scholar
- C. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, NY. 1993.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- T. Jones.: Evolutionary Algorithms, Fitness Landscapes and Search. PhD thesis, University of New Mexico, Albuquerque (1995).Google Scholar
- R. Poli and E. Galvan .On the Effects of Bit-Wise Neutrality on Fitness Distance Correlation, Phenotypic Mutation Rates and Problem Hardness, FOGA 2007. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- Using quotient graphs to model neutrality in evolutionary search
Recommendations
Fitness distance correlation and mixed search strategy for differential evolution
AbstractThe fitness landscape is a theory applied to the evolutionary dynamics of biological evolution to explain the behavior of evolutionary algorithms in the solution of optimization problems. With the continuous advancement of evolutionary ...
NK landscapes, problem difficulty, and hybrid evolutionary algorithms
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computationThis paper presents an experimental study of NK landscapes with the main focus on the relationship between (1) problem parameters, (2) various measures of problem difficulty of fitness landscapes, and (3) performance of hybrid evolutionary algorithms. ...
Fitness landscapes and evolvability
In this paper, we develop techniques based on evolvability statistics of the fitness landscape surrounding sampled solutions. Averaging the measures over a sample of equal fitness solutions allows us to build up fitness evolvability portraits of the ...
Comments