Tiago Paixão
ABSTRACT
Prediction of the evolutionary process is a long standing problem both in the theory of evolutionary biology and evolutionary computation (EC). It has long been realized that heritable variation is crucial to both the response to selection and the success of genetic algorithms. However, not all variation contributes in the same way to the response. Quantitative genetics has developed a large body of work trying to estimate and understand how different components of the variance in fitness in the population contribute to the response to selection. We illustrate how to apply some concepts of quantitative genetics to the analysis of genetic algorithms. In particular, we derive estimates for the short term prediction of the response to selection and we use variance decomposition to gain insight on local aspects of the landscape. Finally, we propose a new population based genetic algorithm that uses these methods to improve its operation.
- D. S. Falconer and T. F. C. Mackay. Introduction to Quantitative Genetics. Benjamin Cummings, 4 edition, Feb. 1996.Google Scholar
- R. A. Fisher. The correlation between relatives on the supposition of mendelian inheritance. Transaction of the Royal Society of Edinburgh, 52:399--433, 1918.Google ScholarCross Ref
- R. A. Fisher. The Genetical Theory of Natural Selection. Clarendon Press, Oxford, 1930.Google ScholarCross Ref
- T. Friedrich, N. Hebbinghaus, and F. Neumann. Rigorous analyses of simple diversity mechanisms. In In Proc. of Genetic and Evolutionary Computation Conference (GECCO 2007), pages 1219--1225. ACM Press, 2007. Google ScholarDigital Library
- J. H. Holland. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press, 1975.Google ScholarDigital Library
- T. Jansen and I. Wegener. Real royal road functions where crossover provably is essential. Discrete Applied Mathematics, 149(1--3):111--125, 2005. Google ScholarDigital Library
- A. Livnat, C. Papadimitriou, N. Pippenger, and M. W. Feldman. Sex, mixability, and modularity. Proceedings of the National Academy of Sciences, 107(4):1452--1457, Jan. 2010.Google ScholarCross Ref
- M. Lynch and B. Walsh. Genetics and Analysis of Quantitative Traits. Sinauer, 1998.Google Scholar
- M. Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms: Fitness landscapes and GA performance. In Proceedings of the First European Conference on Artificial Life, pages 245--254. MIT Press, 1991.Google Scholar
- G. R. Price. Fisher's "fundamental theorem" made clear. Annals of Human Genetics, 36(2):129--140, 1972.Google ScholarCross Ref
- R. R. Sokal and F. J. Rohlf. Biometry: The Principles and Practices of Statistics in Biological Research. W. H. Freeman, 3rd edition, Sept. 1994.Google Scholar
- R. K. Ursem. Diversity-guided evolutionary algorithms. In Proceedings of the Congress on Evolutionary Computation, pages 1633--1640. IEEE Press, 2002.Google ScholarCross Ref
- S. Wright. The roles of mutation, inbreeding, crossbreeding and selection in evolution. Proceedings of the Sixth International Congress of Genetics, 1:356--366, 1932.Google Scholar
- S. Wright. The distribution of gene frequencies in populations. Proceedings of the National Academy of Sciences of the United States of America, 23(6):307--320, 1937.Google ScholarCross Ref
Index Terms
- A variance decomposition approach to the analysis of genetic algorithms
Recommendations
Can quantitative and population genetics help us understand evolutionary computation?
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computationEven though both population and quantitative genetics, and evolutionary computation, deal with the same questions, they have developed largely independently of each other. I review key results from each field, emphasising those that apply independently ...
Towards a Runtime Comparison of Natural and Artificial Evolution
Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative ...
Three interconnected parameters for genetic algorithms
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computationWhen an optimization problem is encoded using genetic algorithms, one must address issues of population size, crossover and mutation operators and probabilities, stopping criteria, selection operator and pressure, and fitness function to be used in ...
Comments