×

zbMATH — the first resource for mathematics

Real royal road functions – where crossover provably is essential. (English) Zbl 1101.68079
Summary: Mutation 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 \to \mathbb R\) that a genetic algorithm with crossover can optimize \(f_n\) in expected polynomial time while all evolution strategies based only on mutation (and selection) need expected exponential time. Here such functions and proofs are presented for a genetic algorithm without any idealization. For some functions one-point crossover is appropriate while for others uniform crossover is the right choice.

MSC:
68T05 Learning and adaptive systems in artificial intelligence
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Forrest, S.; Mitchell, M., Relative building-block fitness and the building-block hypothesis, (), 109-126
[2] Goldberg, D.E., Genetic algorithms in search, optimization, and machine learning, (1989), Addison-Wesley Reading, MA · Zbl 0721.68056
[3] Holland, J.H., Adaption in natural and artificial systems, (1992), MIT Press Cambridge, MA
[4] Jansen, T.; Wegener, I., On the analysis of evolutionary algorithms—a proof that crossover really can help, (), 184-193 · Zbl 0943.68139
[5] Mitchell, M., An introduction to genetic algorithms, (1996), MIT Press Cambridge, MA, (Chapter 4.2)
[6] Mitchell, M.; Forrest, S.; Holland, J.H., The royal road function for genetic algorithms: fitness landscapes and GA performance, (), 245-254
[7] Mitchell, M.; Holland, J.H.; Forrest, S., When will a genetic algorithm outperform Hill climbing?, (), 51-58
[8] Mood, A.M.; Graybill, F.A.; Boes, D.C., Introduction to the theory of statistics, (1974), McGraw-Hill Singapore · Zbl 0277.62002
[9] Motwani, R.; Raghavan, P., Randomized algorithms, (1995), Cambridge University Press Cambridge · Zbl 0849.68039
[10] Watson, R.A., Analysis of recombinative algorithms on a non-separable building-block problem, (), 69-89 · Zbl 1001.68116
[11] Watson, R.A.; Hornby, G.S.; Pollack, J.B., Modeling building-block interdependency, (), 97-106
[12] Watson, R.A.; Pollack, J.B., Hierarchically-consistent test problems for genetic algorithms, (), 1406-1413
[13] Watson, R.A.; Pollack, J.B., Recombination without respectschema disruption in genetic algorithm crossover, (), 112-119
[14] Watson, R.A.; Pollack, J.B., Symbiotic combination as an alternative to sexual recombination in genetic algorithms, (), 425-434
[15] Wright, A.H.; Zhao, Y., Markov chain models of genetic algorithms, (), 734-741
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.