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: Terry Jones , Stephanie Forrest, Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms, Proceedings of the 6th International Conference on Genetic Algorithms, p.184-192, July 15-19, 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: Marco Tomassini , Leonardo Vanneschi , Philippe Collard , Manuel Clergue, A Study of Fitness Distance Correlation as a Difficulty Measure in Genetic Programming, Evolutionary Computation, v.13 n.2, p.213-239, June 2005 [doi>10.1162/1063656054088549]
• 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: Russell Thomason , Terence Soule, Redundant genes and the evolution of robustness, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144169]
• 12: J. Neal Richter , John Paxton , Alden Wright, EA models and population fixed-points versus mutation rates for functions of unitation, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068211]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Measurement, Theory

Keywords:
degenerate code, fitness distance correlation, neutral evolution, quotient sets