Article

Empirical analysis of ideal recombination on random decomposable problems

Authors:

Martin Pelikan,

David E. GoldbergAuthors Info & Claims

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

Pages 1388 - 1395

https://doi.org/10.1145/1276958.1277216

Published: 07 July 2007 Publication History

Abstract

This paper analyzes the behavior of a selectorecombinative genetic algorithm (GA) with an ideal crossover on a class of random additively decomposable problems (rADPs). Specifically, additively decomposable problems of order k whose subsolution fitnesses are sampled from the standard uniform distribution U[0,1] are analyzed. The scalability of the selectorecombinative GA is investigated for 10,000 rADP instances. The validity of facetwise models in bounding the population size, run duration, and the number of function evaluations required to successfully solve the problems is also verified. Finally, rADP instances that are easiest and most difficult are also investigated.

References

[1]

D. H. Ackley. A connectionist machine for genetic hill climbing. Kluwer Academic Publishers, 1987.

Digital Library

[2]

H. Asoh and H. Mühlenbein. On the mean convergence time of evolutionary algorithms without selection and mutation. Parallel Problem Solving from Nature, 3:98--107, 1994.

[3]

T. Bäck. Generalized convergence models for tournament -- and (μ, λ) -- selection. Proceedings of the Sixth International Conference on Genetic Algorithms, pages 2--8, 1995.

Digital Library

[4]

N. Balakrishnan and W. W. S. Chen. Handbook of tables for order statistics from lognormal distributions with applications. Kluwer Academic Publishers, Amsterdam, Netherlands, 1999.

[5]

N. Balakrishnan and A. C. Cohen. Order statistics and inference. Academic Press, New York, NY, 1991.

[6]

N. Balakrishnan and C. R. Rao, editors. Order statistics: Applications . Elsevier, Amsterdam, Netherlands, 1999.

[7]

N. Balakrishnan and C. R. Rao, editors. Order statistics: Theory and methods . Elsevier, Amsterdam, Netherlands, 1999.

[8]

A. D. Bethke. Genetic algorithms as function Re-optimizers . PhD thesis, University of Michigan, Ann Arbor, MI, 1981. (University Microfilms No. 8106101).

Digital Library

[9]

M. G. Bulmer. The Mathematical Theory of Quantitative Genetics. Oxford University Press, Oxford, 1985.

[10]

K. Deb and D. E. Goldberg. Analyzing deception in trap functions. Foundations of Genetic Algorithms, 2:93--108, 1992. (Also IlliGAL Report No. 91009).

[11]

W. Feller. An Introduction to Probability Theory and its Applications. Wiley, New York, NY, 1970.

[12]

D. E. Goldberg. Simple genetic algorithms and the minimal deceptive problem. In L. Davis, editor, Genetic algorithms and simulated annealing, chapter 6, pages 74--88. Morgan Kaufmann, Los Altos, CA, 1987.

[13]

D. E. Goldberg. Design of innovation:Lessons from and for competent genetic algorithms. Kluwer Academic Publishers, Boston, MA, 2002.

Digital Library

[14]

D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6:333--362, 1992. (Also IlliGAL Report No. 91010).

[15]

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

[16]

D. E. Goldberg and P. Segrest. Finite Markov chain analysis of genetic algorithms. Proceedings of the Second International Conference on Genetic Algorithms, pages 1--8, 1987.

Digital Library

[17]

G. Harik, E. Cantú-Paz, D. E. Goldberg, and B. L. Miller. The gambler's ruin problem, genetic algorithms, and the sizing of populations. Evolutionary Computation, 7(3):231--253, 1999. (Also IlliGAL Report No. 96004).

Digital Library

[18]

R. V. Hogg and A. T. Craig. Introduction to Mathematical Statistics . Macmillan, New York, NY, 5th edition, 1995.

[19]

M. Kimura. Diffusion models in population genetics. Journal of Applied Probability, 1:177--232, 1964.

[20]

G. E. Liepins and M. D. Vose. Representational issues in genetic optimization. Journal of Experimental and Theoretical Artificial Intelligence, 2:101--115, 1990.

[21]

B. L. Miller and D. E. Goldberg. Genetic algorithms, tournament selection, and the effects of noise. Complex Systems, 9(3):193--212, 1995. (Also IlliGAL Report No. 95006).

[22]

H. Mühlenbein and D. Schlierkamp-Voosen. Predictive models for the breeder genetic algorithm: I. continous parameter optimization. Evolutionary Computation, 1(1):25--49, 1993.

Digital Library

[23]

M. Pelikan, K. Sastry, M. V. Butz, and D. E. Goldberg. Hierarchical BOA on random decomposable problems. IlliGAL Report No. 2006002, University of Illinois at Urbana Champaign, Urbana, IL, January 2006.

[24]

K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at Urbana-Champaign, Urbana, IL, 2001. (Also IlliGAL Report No. 2002004).

[25]

K. Sastry and D. E. Goldberg. Modeling tournament selection with replacement using apparent added noise. Intelligent Engineering Systems Through ArtificialNeuralNetworks, 11:129--134, 2001. (Also IlliGAL Report No. 2001014).

[26]

K. Sastry and D. E. Goldberg. Let's get ready to rumble: Crossover versus mutation head to head. Proceedings of the 2004 Genetic and Evolutionary Computation Conference, 2:126--137, 2004. Also IlliGAL Report No. 2004005.

[27]

K. Sastry, M. Pelikan, and D. E. Goldberg. Analysis of ideal recombination on random decomposable problems. IlliGAL Report No. 2006016, University of Illinois at Urbana-Champaign, Urbana, IL, April 2006.

[28]

D. Thierens and D. E. Goldberg. Convergence models of genetic algorithm selection schemes. Parallel Problem Solving from Nature, 3:116--121, 1994.

[29]

L. D. Whitley. Fundamental principles of deception in genetic search. Foundations of Genetic Algorithms, pages 221--241, 1991.

Cited By

Garousi V(2010)A Genetic Algorithm-Based Stress Test Requirements Generator Tool and Its Empirical EvaluationIEEE Transactions on Software Engineering10.1109/TSE.2010.536:6(778-797)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1109/TSE.2010.5
Pelikan MSastry KGoldberg DButz MHauschild MRothlauf F(2009)Performance of evolutionary algorithms on NK landscapes with nearest neighbor interactions and tunable overlapProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1570018(851-858)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1570018
Hauschild MPelikan MSastry KLima C(2009)Analyzing probabilistic models in hierarchical BOAIEEE Transactions on Evolutionary Computation10.1109/TEVC.2008.200442313:6(1199-1217)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1109/TEVC.2008.2004423
Show More Cited By

Index Terms

Empirical analysis of ideal recombination on random decomposable problems

Recommendations

Let's get ready to rumble redux: crossover versus mutation head to head on exponentially scaled problems
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

This paper analyzes the relative advantages between crossover and mutation on a class of deterministic and stochastic additively separable problems with substructures of non-uniform salience. This study assumes that the recombination and mutation ...
Sub-structural niching in estimation of distribution algorithms
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

We propose a sub-structural niching method that fully exploits the problem decomposition capability of linkage-learning methods such as the estimation distribution algorithms and concentrate on maintaining diversity at the sub-structural level. The ...
An analysis of multi-chromosome GAs in deceptive problems
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

This paper discusses a new approach to using GAs to solve deceptive fitness landscapes by incorporating mechanisms to control the convergence direction instead of simply increasing the population diversity. In order to overcome some of the difficulties ...

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

6
Total Citations
View Citations
153
Total Downloads

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

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Garousi V(2010)A Genetic Algorithm-Based Stress Test Requirements Generator Tool and Its Empirical EvaluationIEEE Transactions on Software Engineering10.1109/TSE.2010.536:6(778-797)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1109/TSE.2010.5
Pelikan MSastry KGoldberg DButz MHauschild MRothlauf F(2009)Performance of evolutionary algorithms on NK landscapes with nearest neighbor interactions and tunable overlapProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1570018(851-858)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1570018
Hauschild MPelikan MSastry KLima C(2009)Analyzing probabilistic models in hierarchical BOAIEEE Transactions on Evolutionary Computation10.1109/TEVC.2008.200442313:6(1199-1217)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1109/TEVC.2008.2004423
Hauschild MPelikan M(2008)Enhancing Efficiency of Hierarchical BOA Via Distance-Based Model RestrictionsProceedings of the 10th International Conference on Parallel Problem Solving from Nature --- PPSN X - Volume 519910.5555/2951659.2951704(417-427)Online publication date: 13-Sep-2008
https://dl.acm.org/doi/10.5555/2951659.2951704
Garousi VRyan C(2008)Empirical analysis of a genetic algorithm-based stress test techniqueProceedings of the 10th annual conference on Genetic and evolutionary computation10.1145/1389095.1389433(1743-1750)Online publication date: 13-Jul-2008
https://dl.acm.org/doi/10.1145/1389095.1389433
Hauschild MPelikan M(2008)Enhancing Efficiency of Hierarchical BOA Via Distance-Based Model RestrictionsParallel Problem Solving from Nature – PPSN X10.1007/978-3-540-87700-4_42(417-427)Online publication date: 2008
https://doi.org/10.1007/978-3-540-87700-4_42

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.

Media

Figures

Other

Tables

View Table of Contents