creators_name: Whitacre, James M
creators_name: Sarker, Ruhul A
creators_name: Pham, Q. Tuan
type: journalp
datestamp: 2009-07-06 09:41:58
lastmod: 2011-03-11 08:57:23
metadata_visibility: show
title: Making and breaking power laws in evolutionary algorithm population dynamics
ispublished: pub
subjects: comp-sci-art-intel
full_text_status: public
keywords: Evolutionary algorithms; Population dynamics; Genealogical graphs; Population topology; Historical coupling; Optimization; Algorithm analysis
abstract: Deepening our understanding of the characteristics and behaviors of population-based search algorithms remains an important ongoing challenge in Evolutionary Computation. To date however, most studies of Evolutionary Algorithms have only been able to take place within tightly restricted experimental conditions. For instance, many analytical methods can only be applied to canonical algorithmic forms or can only evaluate evolution over simple test functions. Analysis of EA behavior under more complex conditions is needed to broaden our understanding of this population-based search process. This paper presents an approach to analyzing EA behavior that can be applied to a diverse range of algorithm designs and environmental conditions. The approach is based on evaluating an individual’s impact on population dynamics using metrics derived from genealogical graphs.
From experiments conducted over a broad range of conditions, some important conclusions are drawn in this study. First, it is determined that very few individuals in an EA population have a significant influence on future population dynamics with the impact size fitting a power law distribution. The power law distribution indicates there is a non-negligible probability that single individuals will dominate the entire population, irrespective of population size. Two EA design features are however found to cause strong changes to this aspect of EA behavior: i) the population topology and ii) the introduction of completely new individuals. If the EA population topology has a long path length or if new (i.e. historically uncoupled) individuals are continually inserted into the population, then power law deviations are observed for large impact sizes. It is concluded that such EA designs can not be dominated by a small number of individuals and hence should theoretically be capable of exhibiting higher degrees of parallel search behavior.
date: 2009-06
date_type: published
publication: Memetic Computing
volume: 1
number: 2
publisher: Springer
pagerange: 125-137
refereed: TRUE
referencetext: [1] D. E. Goldberg and K. Deb, "A Comparative Analysis of Selection Schemes Used in Genetic Algorithms," Urbana, vol. 51, pp. 61801-2996.
[2] T. Blickle, "Theory of Evolutionary Algorithms and Application to System Synthesis," Swiss Federal Institute of Technology, 1996.
[3] W. Wieczorek and Z. J. Czech, "Selection Schemes in Evolutionary Algorithms," Proceedings of the Symposium on Intelligent Information Systems (IIS'2002 ), pp. 185-194, 2002.
[4] E. Van Nimwegen and J. P. Crutchfield, "Optimizing Epochal Evolutionary Search: Population-Size Dependent Theory," Machine Learning, vol. 45, pp. 77-114, 2001.
[5] T. Smith, P. Husbands, and M. O'Shea, "Local evolvability of statistically neutral GasNet robot controllers," Biosystems, vol. 69, pp. 223-243, 2003.
[6] S. Nijssen and T. Back, "An analysis of the behavior of simplified evolutionary algorithms on trap functions," IEEE Transactions on Evolutionary Computation, vol. 7, pp. 11-22, 2003.
[7] L. Davis, Handbook of Genetic Algorithms: Van Nostrand Reinhold New York, 1991.
[8] B. A. Julstrom, "What Have You Done for Me Lately? Adapting Operator Probabilities in a Steady-State Genetic Algorithm," Proceedings of the 6th International Conference on Genetic Algorithms, pp. 81-87, 1995.
[9] B. A. Julstrom, "Adaptive operator probabilities in a genetic algorithm that applies three operators," in ACM Symposium on Applied Computing (SAC '97) 1997, pp. 233-238.
[10] J. M. Whitacre, T. Q. Pham, and R. A. Sarker, "Credit assignment in adaptive evolutionary algorithms," in Proceedings of the 8th Annual Genetic and Evolutionary Computation Conference 2006, pp. 1353-1360.
[11] J. M. Whitacre, "Adaptation and Self-Organization in Evolutionary Algorithms," Thesis: University of New South Wales, 2007, p. 283.
[12] S. W. Mahfoud, "A Comparison of Parallel and Sequential Niching Methods," Conference on Genetic Algorithms, vol. 136, p. 143, 1995.
[13] P. Pfaffelhuber, A. Lehnert, and W. Stephan, "Linkage Disequilibrium Under Genetic Hitchhiking in Finite Populations," Genetics, vol. 179, p. 527, 2008.
[14] P. W. Hedrick, "Genetic Hitchhiking: A New Factor in Evolution?," Bioscience, vol. 32, 2007.
[15] M. A. Félix and A. Wagner, "Robustness and evolution: concepts, insights and challenges from a developmental model system," Heredity, vol. 100, pp. 132-140, 2008.
[16] A. Wagner, "Neutralism and selectionism: a network-based reconciliation," Nature Reviews Genetics, 2008.
[17] G. Gibson and I. Dworkin, "Uncovering cryptic genetic variation," Nature Reviews Genetics, vol. 5, pp. 681-690, 2004.
[18] C. D. Schlichting, "Hidden Reaction Norms, Cryptic Genetic Variation, and Evolvability," Annals of the New York Academy of Sciences, vol. 1133, pp. 187-203, 2008.
[19] J. Hermisson and G. P. Wagner, "The Population Genetic Theory of Hidden Variation and Genetic Robustness," Genetics, vol. 168, pp. 2271-2284, 2004.
[20] A. Bergman and M. L. Siegal, "Evolutionary capacitance as a general feature of complex gene networks," Nature, vol. 424, pp. 549-552, 2003.
[21] J. L. Hartman, B. Garvik, and L. Hartwell, "Principles for the Buffering of Genetic Variation," Science, vol. 291, pp. 1001-1004, 2001.
citation:   Whitacre, Dr James M and Sarker, Dr Ruhul A and Pham, Dr Q. Tuan  (2009) Making and breaking power laws in evolutionary algorithm population dynamics.  [Journal (Paginated)]     
document_url: http://cogprints.org/6583/1/Genealogical_analysis_of_EA_population_dynamics.pdf