Abstract
This paper presents a survey and comparison of significant diversity measures in the genetic programming literature. This study builds on previous work by the authors to gain a deeper understanding of the conditions under which genetic programming evolution is successful. Three benchmark problems (Artificial Ant, Symbolic Regression and Even-5-Parity) are used to illustrate different diversity measures and to analyse their correlation with performance. Results show that measures of population diversity based on edit distances and phenotypic diversity suggest that successful evolution occurs when populations converge to a similar structure but with high fitness diversity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. F. McPhee and N. J. Hopper. Analysis of genetic diversity through population history. In W. Banzhaf et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference, Florida, USA, 1999. Morgan Kaufmann.
C. Ryan. Pygmies and civil servants. In K. E. Kinnear, Jr., editor, Advances in Genetic Programming, chapter 11, pages 243–263. MIT Press, 1994.
A. Ekárt and S. Z. Németh. A metric for genetic programs and fitness sharing. In R. Poli et al., editors, Proceedings of the European Conference on Genetic Programming, volume 1802 of LNCS, pages 259–270, Edinburgh, 15–16 April 2000. Springer-Verlag.
R. I. McKay. Fitness sharing in genetic programming. In D. Whitley et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference, pages 435–442, Las Vegas, Nevada, USA, 10–12 July 2000. Morgan Kaufmann.
J. P. Rosca. Entropy-driven adaptive representation. In J. P. Rosca, editor, Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, pages 23–32, Tahoe City, California, USA, 9 July 1995.
J. P. Rosca. Genetic programming exploratory power and the discovery of functions. In J. R. McDonnell et al., editors, Proceedings of the Fourth Conference on Evolutionary Programming, pages 719–736, San Diego, CA, 1995. MIT Press.
W. B. Langdon. Evolution of genetic programming populations. Research Note RN/96/125, University College London, Gower Street, London WC1E 6BT, UK, 1996.
E. D. de Jong, R. A. Watson, and J. B. Pollack. Reducing bloat and promoting diversity using multi-objective methods. In L. Spector et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco, CA, 7–11 July 2001. Morgan Kaufmann.
R. I. McKay and H. A. Abbass. Anticorrelation measures in genetic programming. In Australasia-Japan Workshop on Intelligent and Evolutionary Systems, 2001.
M. Keijzer. Efficiently representing populations in genetic programming. In P. J. Angeline and K. E. Kinnear, Jr., editors, Advances in Genetic Programming 2, chapter 13, pages 259–278. MIT Press, Cambridge, MA, USA, 1996.
P. D'haeseleer. Context preserving crossover in genetic programming. In Proceedings of the 1994 IEEE World Congress on Computational Intelligence, volume 1, pages 256–261, Orlando, FL, USA, June 1994. IEEE Press.
E. Burke, S. Gustafson, and G. Kendall. Survey and analysis of diversity measures in genetic programming. In (Accepted as a full paper) Proceedings of the Genetic and Evolutionary Computation Conference, 2002.
J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.
W. A. Tackett. Recombination, Selection, and the Genetic Construction of Computer Programs. PhD thesis, University of Southern California, Department of Electrical Engineering Systems, USA, 1994.
L. J. Eshelman and J. D. Schaffer. Crossover’s niche. In S. Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms, pages 9–14, San Mateo, CA, 1993. Morgan Kaufman.
K. Deb and D. E. Goldberg. An investigation of niche and species formation in genetic function optimization. In J. D. Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms, Washington DC, 1989.
T. F. Bersano-Begey. Controlling exploration, diversity and escaping local optima in GP. In J. R. Koza, editor, Late Breaking Papers at the Genetic Programming Conference, Stanford University, CA, July 1997.
S. Siegel. Nonparametric Statistics for the Behavioral Sciences. McGraw-Hill Book Company, Inc., 1956.
S. Luke. ECJ: A java-based evolutionary comp-utation and genetic programming system, 2002. http://www.cs.umd.edu/projects/plus/ecj/.
S.-H. Nienhuys-Cheng. Distance between Herbrand interpretations: a measure for approximations to a target concept. In N. Lavraĉ and S. Džeroski, editors, Proceedings of the 7th Internations Workshop on Inductive Logic Programming. Springer-Verlag, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Burke, E., Gustafson, S., Kendall, G., Krasnogor, N. (2002). Advanced Population Diversity Measures in Genetic Programming. In: Guervós, J.J.M., Adamidis, P., Beyer, HG., Schwefel, HP., Fernández-Villacañas, JL. (eds) Parallel Problem Solving from Nature — PPSN VII. PPSN 2002. Lecture Notes in Computer Science, vol 2439. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45712-7_33
Download citation
DOI: https://doi.org/10.1007/3-540-45712-7_33
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44139-7
Online ISBN: 978-3-540-45712-1
eBook Packages: Springer Book Archive