Article

Learning building block structure from crossover failure

Authors:

Erik D. GoodmanAuthors Info & Claims

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Pages 1280 - 1287

https://doi.org/10.1145/1276958.1277202

Published: 07 July 2007 Publication History

Abstract

In the classical binary genetic algorithm, although crossover within a building block (BB) does not always cause a decrease in fitness, any decrease in fitness results from the destruction of some building blocks, in problems where such structures are well defined, such as those considered here. Those crossovers that cause both offspring to be worse, or one to be worse and one unchanged, are here designated as failed crossovers. Counting the failure frequency of single-point crossovers performed at each locus reveals something of the BB structure. Guided by the failure record, GA operators could choose appropriate points for crossover, in order to work moreefficiently and effectively. Experiments on test functions RoyalRoad R1 and R2, Holland's Royal Road Challenge function and H-IFF functions show that such a guided operator improves performance. While many methods exist to discover building blocks, this "quick-and-dirty" method can sketch the linkage nearly "for free", requiring very little extra computation.

References

[1]

C. Aporntewan and P. Chongstitvatana. A quantitative approach for validating the building-block hypothesis. In 2005 IEEE Congress on Evolutionary Computation, pages 1403--1409. IEEE CEC 2005, September 2005.

[2]

J. S. de Bonet, C. L. Isbell, Jr., and P. Viola. MIMIC: Finding optima by estimating probability densities. In M. C. Mozer, M. I. Jordan, and T. Petsche, editors, Advances in Neural Information Processing Systems, volume 9, pages 424--430. The MIT Press, 1997.

[3]

S. Forrest and M. Mitchell. Relative building-block fitness and the building-block hypothesis. In L. D. Whitley, editor, Foundations of Genetic Algorithms 2, pages 109--126. Morgan Kaufmann, San Mateo, CA, 1993.

[4]

D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989.

Digital Library

[5]

D. E. Goldberg, B. Korb, and K. Deb. Messy genetic algorithms: Motivation, analysis, and first results. Complex Systems, 3 (5):493--530, 1989.

[6]

G. Harik. Learning linkage to efficiently solve problems of bounded difficulty using genetic algorithms. PhD thesis, University of Michigan, 1997.

Digital Library

[7]

G. Harik. Linkage learning via probabilistic modeling in the ECGA. Technical Report IlliGAL Report No. 99010, IlliGAL, University of Illinois at Urbana-Champaign, 1999.

[8]

G. R. Harik, F. G. Lobo, andD. E. Goldberg. The compact genetic algorithm. IEEE-EC, 3 (4):287--297, November 1999.

Digital Library

[9]

J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, 1975.

Digital Library

[10]

B. Howard and J. Sheppard. The royal road not taken: A re-examination of the reasons for GA failure on R1. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), pages 1208--1219, June 2004.

[11]

M. P. Lobo and D. E. Goldberg. A hierarchy machine: learning to optimize from nature and humans. Complexity, 8 (5):36--45, 1999.

Digital Library

[12]

R. S. Michalski. LEARNABLE EVOLUTION MODEL: Evolutionary processes guided by machine learning. Machine Learning, 38 (1-2):9--40, 2000.

Digital Library

[13]

M. Mitchell, S. Forrest, and J. H. Holland. The royal road for genetic algorithms:Fitness landscapes and GA performance. In F. J. Varela and P. Bourgine, editors, Towards a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life, 1991, pages 245--254, Paris, 11--13 1992. A Bradford book, The MIT Press.

[14]

H. Mü and G. Paas. From recombination of genes to the estimation of distributions I. Binary parameters. In Lecture Notes in Computer Science 1411: Parallel Problem Solving from Nature (PPSN IV), pages 178--187, 1996.

Digital Library

[15]

M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. In L. Spector, E. D. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. H. Garzon, and E. Burke, editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 511--518, San Francisco, California, USA, July 2001. Morgan Kaufmann.

[16]

M. Pelikan, D. E. Goldberg, and E. Cantú-Paz. BOA: The Bayesian optimization algorithm. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, editors, Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99, volume I, pages 525--532, Orlando, FL, July 1999. Morgan Kaufmann Publishers, San Fransisco, CA.

[17]

J. D. Scha . er and A. Morishima. An adaptive crossover distribution mechanism for genetic algorithms. In Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, pages 36--40. Lawrence Erlbaum Associates, Inc., July 1987.

Digital Library

[18]

M. Sebag and M. Schoenauer. Controlling crossover through inductive learning. In Y. Davidor, H.-P. Schwefel, and R. Männer, editors, Parallel Problem Solving from Nature -PPSN III, pages 209--218, Berlin, 1994. Springer.

Digital Library

[19]

D. Thierens and D. E. Goldberg. Mixing in genetic algorithms. In Proceedings of the Fifth International Conference on Genetic Algorithms, pages 38--45. ICGA93 ', June 1993.

Digital Library

[20]

R. A. Watson, G. S. Hornby, and J. B. Pollack. Modeling building-block interdependency. In Proceedings of the Third Conference on Parallel Problem Solving from Nature (PPSN V), volume 1498, pages 97--106, 1998.

Digital Library

[21]

R. A. Watson and J. B. Pollack. Hierarchically consistent test problems for genetic algorithms: Summary and additional results. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-1999), pages 292--297. Morgan Kaufmann, July 1999.

Cited By

Schwaab JDeb KGoodman ELautenbach Svan Strien MGrêt-Regamey A(2017)Improving the performance of genetic algorithms for land-use allocation problemsInternational Journal of Geographical Information Science10.1080/13658816.2017.141924932:5(907-930)Online publication date: 26-Dec-2017
https://doi.org/10.1080/13658816.2017.1419249
Bao YZhao EGan XLuo DHan Z(2009)A Review on Cutting-Edge Techniques in Evolutionary AlgorithmsProceedings of the 2009 Fifth International Conference on Natural Computation - Volume 0510.1109/ICNC.2009.459(347-351)Online publication date: 14-Aug-2009
https://dl.acm.org/doi/10.1109/ICNC.2009.459
Iclanzan DDumitrescu DRyan C(2008)Going for the big fishesProceedings of the 10th annual conference on Genetic and evolutionary computation10.1145/1389095.1389173(423-430)Online publication date: 13-Jul-2008
https://dl.acm.org/doi/10.1145/1389095.1389173
Show More Cited By

Index Terms

Learning building block structure from crossover failure
1. Computing methodologies
  1. Artificial intelligence
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Off-line building block identification: detecting building blocks directly from fitness without genetic algorithms
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

This paper aims at detecting the existence of building blocks directly from the fitness function without performing genetic algorithms. To do so, this paper extends the convergence time model and the gambler's ruin model so they can be applied to a ...
How crossover speeds up building block assembly in genetic algorithms

We reinvestigate a fundamental question: How effective is crossover in genetic algorithms in combining building blocks of good solutions? Although this has been discussed controversially for decades, we are still lacking a rigorous and intuitive answer. ...
A practical search index and population size analysis based on the building block hypothesis
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Use of the Building Block Hypothesis to illuminate GA search behavior, as pursued by J. H. Holland and D. E. Goldberg, invites additional investigation. This paper re-examines the space actually searched by a GA, in light of the Building Block ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

July 2007

2313 pages

ISBN:9781595936974

DOI:10.1145/1276958

General Chair:
Hod Lipson
Cornell University, USA

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO07

Sponsor:

GECCO07: Genetic and Evolutionary Computation Conference

July 7 - 11, 2007

London, England

Acceptance Rates

GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
204
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schwaab JDeb KGoodman ELautenbach Svan Strien MGrêt-Regamey A(2017)Improving the performance of genetic algorithms for land-use allocation problemsInternational Journal of Geographical Information Science10.1080/13658816.2017.141924932:5(907-930)Online publication date: 26-Dec-2017
https://doi.org/10.1080/13658816.2017.1419249
Bao YZhao EGan XLuo DHan Z(2009)A Review on Cutting-Edge Techniques in Evolutionary AlgorithmsProceedings of the 2009 Fifth International Conference on Natural Computation - Volume 0510.1109/ICNC.2009.459(347-351)Online publication date: 14-Aug-2009
https://dl.acm.org/doi/10.1109/ICNC.2009.459
Iclanzan DDumitrescu DRyan C(2008)Going for the big fishesProceedings of the 10th annual conference on Genetic and evolutionary computation10.1145/1389095.1389173(423-430)Online publication date: 13-Jul-2008
https://dl.acm.org/doi/10.1145/1389095.1389173
Li ZGoodman E(2008)Exploring Building Blocks through CrossoverProceedings of the 3rd International Symposium on Advances in Computation and Intelligence10.1007/978-3-540-92137-0_77(707-714)Online publication date: 19-Dec-2008
https://dl.acm.org/doi/10.1007/978-3-540-92137-0_77

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten