More Web Proxy on the site http://driver.im/

article

Real royal road functions-where crossover provably is essential

Authors:

Ingo WegenerAuthors Info & Claims

Discrete Applied Mathematics, Volume 149, Issue 1-3

Pages 111 - 125

Published: 01 August 2005 Publication History

Abstract

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->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.

References

[1]

Forrest, S. and Mitchell, M., Relative building-block fitness and the building-block hypothesis. In: Whitley, D. (Ed.), Proceedings of the Second Workshop on the Foundations of Genetic Algorithms (FOGA '92), Morgan Kaufmann, San Mateo, CA. pp. 109-126.

[2]

Goldberg, D.E., Genetic Algorithms in Search, Optimization, and Machine Learning. 1989. Addison-Wesley, Reading, MA.

[3]

Holland, J.H., Adaption in Natural and Artificial Systems. 1992. MIT Press, Cambridge, MA.

[4]

Jansen, T. and Wegener, I., On the analysis of evolutionary algorithms-a proof that crossover really can help. In: Nešetřil, J. (Ed.), Proceedings of the Seventh Annual European Symposium on Algorithms (ESA '99), Lecture Notes in Computer Science, vol. 1643. Springer, Berlin. pp. 184-193.

[5]

Mitchell, M., An Introduction to Genetic Algorithms. 1996. MIT Press, Cambridge, MA.

[6]

Mitchell, M., Forrest, S. and Holland, J.H., The royal road function for genetic algorithms: fitness landscapes and GA performance. In: Varela, F.J., Bourgine, P. (Eds.), Toward a Practice of Autonomous Systems, Proceedings of the First European Conference on Artificial Life, MIT Press, Cambridge, MA. pp. 245-254.

[7]

Mitchell, M., Holland, J.H. and Forrest, S., When will a genetic algorithm outperform hill climbing?. In: Advances in Neural Information Processing Systems (NIPS 6), pp. 51-58.

[8]

Mood, A.M., Graybill, F.A. and Boes, D.C., Introduction to the Theory of Statistics. 1974. McGraw-Hill, Singapore.

[9]

Motwani, R. and Raghavan, P., Randomized Algorithms. 1995. Cambridge University Press, Cambridge.

[10]

Watson, R.A., Analysis of recombinative algorithms on a non-separable building-block problem. In: Martin, W.N., Spears, W.M. (Eds.), Proceedings of the Sixth Workshop on the Foundations of Genetic Algorithms (FOGA 2000), pp. 69-89.

[11]

Watson, R.A., Hornby, G.S. and Pollack, J.B., Modeling building-block interdependency. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (Eds.), Parallel Problem Solving From Nature (PPSN V), Lecture Notes in Computer Science, vol. 1998. Springer, Berlin, Germany. pp. 97-106.

[12]

Watson, R.A. and Pollack, J.B., Hierarchically-consistent test problems for genetic algorithms. In: Congress on Evolutionary Computation (CEC '99), pp. 1406-1413.

[13]

Watson, R.A. and Pollack, J.B., Recombination without respect: schema disruption in genetic algorithm crossover. . In: Whitley, D., Goldberg, D., Cantu-Paz, E., Spector, L., Parmee, I., Beyer, H.-G. (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2000), pp. 112-119.

[14]

Watson, R.A. and Pollack, J.B., Symbiotic combination as an alternative to sexual recombination in genetic algorithms. In: Schoenauer, M., Deb, K., Rudolph, G., Yao, X., Lutton, E., Merelo, J.J., Schwefel, H.-P. (Eds.), Parallel Problem Solving from Nature (PPSN VI), Lecture Notes in Computer Science, vol. 1917. Springer, Berlin, Germany. pp. 425-434.

[15]

Wright, A.H. and Zhao, Y., Markov chain models of genetic algorithms. In: Banzhaf, W., Daida, J., Eiben, A.E., Garzon, M., Honavar, V., Jakiela, M., Smith, R.E. (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '99), pp. 734-741.

Cited By

Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Doerr BSilva SPaquete L(2023)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595042(946-975)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595042
Doerr BWagner M(2022)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533628(890-921)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533628
Show More Cited By

Real royal road functions-where crossover provably is essential
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis

Recommendations

Real royal road functions: where crossover provably is essential
Special issue: Boolean and pseudo-boolean funtions

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}ⁿ → ...
A building-block royal road where crossover is provably essential
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

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 ...
Real royal road functions — where crossover provably is essential
GECCO'01: Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation

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}ⁿ → ℝ ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Applied Mathematics

Discrete Applied Mathematics Volume 149, Issue 1-3

Special issue: Boolean and pseudo-boolean funtions

1 August 2005

257 pages

ISSN:0166-218X

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2005.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 August 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doerr BLi XHandl J(2024)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648402(800-829)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648402
Doerr BSilva SPaquete L(2023)A Gentle Introduction to Theory (for Non-Theoreticians)Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595042(946-975)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595042
Doerr BWagner M(2022)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533628(890-921)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533628
Antipov DNaumov SFinck SHellwig MOliveto P(2021)The effect of non-symmetric fitnessProceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3450218.3477311(1-15)Online publication date: 6-Sep-2021
https://dl.acm.org/doi/10.1145/3450218.3477311
Doerr BKrawiec K(2021)A gentle introduction to theory (for non-theoreticians)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3461406(369-398)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3461406
Doerr BCoello Coello C(2020)A gentle introduction to theory (for non-theoreticians)Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389889(373-403)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389889
Sutton AWitt CAuger AStützle T(2019)Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3321707.3321848(1515-1522)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3321707.3321848
Karavaev VAntipov DDoerr BAuger AStützle T(2019)Theoretical and empirical study of the (1 + (λ, λ)) EA on the leadingones problemProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3326910(2036-2039)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3326910
Doerr BAuger AStützle T(2019)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323373(523-549)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323373
Doerr BTakadama K(2018)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207889(389-414)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207889
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents