Richard A. Watson
ABSTRACT
One of the most controversial yet enduring hypotheses about what genetic algorithms (GAs) are good for concerns the idea that GAs process building-blocks. More specifically, it has been suggested that crossover in GAs can assemble short low-order schemata of above average fitness (building blocks) to create higher-order higher-fitness schemata. However, there has been considerable difficulty in demonstrating this rigorously and intuitively. Here we provide a simple building-block function that a GA with two-point crossover can solve on average in polynomial time, whereas an asexual population or mutation hill-climber cannot.
- J. C. Culberson, "Mutation-Crossover Isomorphisms and the Construction of Discriminating Functions", Evolutionary Computation 2, 279 (1995). Google Scholar
Digital Library
- K. Deb, D. E. Goldberg. "Analyzing Deception in Trap Functions", in D. Whitley, Ed. Foundations of Genetic Algorithms 2, (Morgan Kaufmann, San Mateo, CA, 1992) pp. 93--108.Google Scholar
- K. Deb, D. E. Goldberg, "Sufficient Conditions for Deceptive and Easy Binary Functions", Annals of Mathematics and Artificial Intelligence 10, 385 (1992).Google ScholarCross Ref
- M. Dietzfelbinger, B. Naudts, C. van Hoyweghen, I. Wegener, "The analysis of a recombinative hill-climber on H IFF", IEEE-Trans. on Evolutionary Computation 7, 417 (2002). Google ScholarDigital Library
- S. Droste, T. Jansen, I. Wegener, "On the analysis of the (1+1) evolutionary algorithm", Theoretical Computer Science, 276, 51. (2002) Google ScholarDigital Library
- S. Forrest, M. Mitchell, "Relative Building-block fitness and the Building-block Hypothesis", in D. Whitley, Ed., Foundations of Genetic Algorithms 2, (Morgan Kaufmann, San Mateo, CA, 1993), pp. 109--126.Google Scholar
- S. Forrest, M. Mitchell, "What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation", Machine Learning 13(2), 285 (1993). Google ScholarDigital Library
- D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning (Addison-Wesley, Reading, MA, 1989). Google ScholarDigital Library
- G. Harik, D. E. Goldberg, "Learning Linkage", in R. K. Belew, M. D. Vose, Eds. Foundations of Genetic Algorithms 4 (Morgan Kaufmann, San Francisco, 1997), pp. 247--262.Google Scholar
- J. H. Holland, Adaptation in Natural and Artificial Systems (Ann Arbor, MI: Univ. Michigan Press, 1975). Google ScholarDigital Library
- J. H. Holland, "Building Blocks, Cohort Genetic Algorithms, and Hyperplane-Defined Functions", Evolutionary Computation 8, 373 (2000). Google ScholarDigital Library
- C. Igel, M. Toussaint, "A no-free-lunch theorem for non-uniform distributions of target functions", Journal of Mathematical Modeling and Algorithms, 3(4), 313 (2004).Google ScholarCross Ref
- T. Jansen, I. Wegener, "Real royal road functions -- where crossover provably is essential", Discrete Applied Mathematics 149, 111 (2005). Google ScholarDigital Library
- T. Jones, Evolutionary Algorithms, Fitness Landscapes and Search, PhD dissertation, 95-05-048, University of New Mexico, Albuquerque (1995).Google Scholar
- S. Kauffman, S. Levin, "Towards a general theory of adaptive walks on rugged landscapes", J. Theor. Biol. 128, 11 (1987).Google ScholarCross Ref
- V. Kvasnicka, "An Evolutionary Model of Symbiosis", Studies in Fuzziness and Soft Computing, 54, 293 (2000).Google Scholar
- M. Mitchell, S. Forrest, J. H. Holland, "The royal road for genetic algorithms: Fitness landscapes and GA performance", in F. J. Varela, P. Bourgine Eds., Procs. of first European Conference on Artificial Life, (MIT Press, Cambridge, MA, 1992) pp. 245--254.Google Scholar
- R. Motwani, P. Raghavan. Randomized Algorithms. (Cambridge Univ. Press, 1995). Google ScholarDigital Library
- M. Pelikan, Bayesian Optimization Algorithm: From Single Level to Hierarchy, Ph.D. Dissertation, Dept. of Computer Science at the University of Illinois at Urbana-Champaign (2002). Google ScholarDigital Library
- M. A. Potter, K. A. De Jong, "Cooperative Co-evolution: An Architecture for Evolving Coadapted Subcomponents", Evolutionary Computation, 8(1), 1 (2000). Google ScholarDigital Library
- A. Rogers, A. Prügel-Bennett, "A Solvable Model of a Hard Optimisation Problem", in L. Kallel, B.Naudts, A.Rogers, Eds. Procs. of Theoretical Aspects of Evolutionary Computing (Springer, Berlin, 2001), pp. 207--221. Google ScholarDigital Library
- J.L. Shapiro, A. Prügel-Bennett, "Genetic algorithm dynamics in two-well potentials with basins and barrier", in Foundations of Genetic Algorithms 4, R. K. Belew, M. D. Vose, Eds. (Morgan Kaufmann, San Francisco, 1997), pp. 101--116.Google Scholar
- W. M. Spears, "Crossover or Mutation?", in D. Whitley, Ed. Foundations of Genetic Algorithms 2, (Morgan Kaufmann, San Mateo, CA, 1992), pp. 221--237.Google Scholar
- M. D. Vose, G. E. Liepins,. "Schema disruption", in Procs. of the Fourth International Conference on Genetic Algorithms, (Morgan Kaufmann: San Mateo, 1991), pp. 237--243.Google Scholar
- M. D. Vose, A. H. Wright, "The Simple Genetic Algorithm and the Walsh Transform: part I, Theory", Evolutionary Computation, 6(3), 253 (1998). Google ScholarDigital Library
- R. A. Watson, "A Simple Two-Module Problem to Exemplify Building-Block Assembly Under Crossover", in X. Yao et al. Eds. Parallel Problem Solving from Nature -- PPSN VIII, (Springer, Berlin, 2004), pp. 161--171.Google ScholarCross Ref
- R. A. Watson, "Analysis of Recombinative Algorithms on a Non-Separable Building-Block Problem", in W.N. Martin, W.M. Spears, Eds. Foundation of Genetic Algorithms 6, (Morgan Kaufmann, San Francisco, 2001) pp. 69--89.Google Scholar
- R. A. Watson, "On the Unit of Selection in Sexual Populations", in Advances in Artificial Life, Eighth European Conference (ECAL 2005) (Springer, Berlin, 2005), pp. 895--905. Google ScholarDigital Library
- R. A. Watson, D. Weinreich, J. Wakeley, "Sex avoids intragenic local optima that trap asexuals", in prep.Google Scholar
- J. B. Wolf, E. D. Brodie III, M. J. Wade, Epistasis and the Evolutionary Process. (Oxford University Press: New York, 2000).Google Scholar
Index Terms
- A building-block royal road where crossover is provably essential
Recommendations
Crossover speeds up building-block assembly
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computationWe re-investigate a fundamental question: how effective is crossover in combining building blocks? Although this has been discussed controversially for decades, we are still lacking a rigorous and intuitive answer. We provide such answers for royal road ...
Real royal road functions-where crossover provably is essential
Special issue: Boolean and pseudo-boolean funtionsMutation and crossover are the main search operators of different variants of evolutionary algorithms. Despite the many discussions on the importance of crossover nobody has proved rigorously for some explicitly defined fitness functions f"n:{0,1}^n->R ...
A parameter-less genetic algorithm with customized crossover and mutation operators
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computationGenetic algorithm is one of the well-known population based meta-heuristics. The reasonable performance of the algorithm on a wide variety of problems as well as its simplicity made this algorithm a first choice in lots of cases. However, the algorithm ...
Comments