skip to main content
10.1145/1143997.1144024acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
Article

Comparing genetic robustness in generational vs. steady state evolutionary algorithms

Published: 08 July 2006 Publication History

Abstract

Previous research has shown that evolutionary systems not only try to develop solutions that satisfy a fitness requirement, but indirectly attempt to develop genetically robust solutions as well -solutions where average loss of fitness due to crossover and other genetic variation operators is minimized. It has been shown that in a simple "two peaks" problem, where the fitness landscape consists of a broad, low peak, and a narrow, high peak, individuals initially converge on the lower (less fit), but broader peak, and that increasing an individual's genetic robustness through growth is a necessary prerequisite for convergence on the higher, narrower peak 18. If growth is restricted, the population remains converged on the less fit solution. We tested whether this result holds true only for generational algorithms, or whether it applies to steady state algorithms as well. We conclude that although growth occurs with both algorithms, the steady state algorithm is able to converge on the higher peak without this growth. This result shows that the role of genetic robustness in the evolutionary process is significantly different in generational versus steady state algorithms.

References

[1]
Blickle, T., and Thiele, L. Genetic Programming and Redundancy. In Genetic Algorithms within the Framework of Evolutionary Computation. Max-Planck-Institut fur Informatik, Saarbrucken, Germany, 1994, 33--38.
[2]
DeVisser, A. G. M., Hermission, J., Wager, G., Meyers, L. A., Bagheri-ChaiChain, H., Blanchard, J. L., Chao, L., Cheverud, J. M., Elena, S. F., Fontana, W., Gibson, G., Hansen, T. F., Krakauer, D., Lewontin, R. C., Ofria, C., Rice, S. H., von Dassow, G., and Wagner, A. Perspective: Evolution and Detection of Genetic Robustness. Evolution, 57, 2003, 1959--1972.
[3]
Edlund, J., and Adami, C. Evolution of Robustness in Digital Organisms. Aritficial Life, 10, 2004, 167--179.
[4]
Hogeweg, P., and Hesper, B. Evolutionary Dynamics and the Coding Structure of Sequences: Multiple Coding as a Consequence of Crossover and High Mutation Rates. Computers and Chemistry, 16, 1992, 171--182.
[5]
Koza, J. R. Genetic Programming: On the Programming of Computers by Means of Natural Selection. The MIT Press, Cambridge, MA, 1992.
[6]
Krackauer, D. C., Plotkin, J. B. Redundnacy, antiredundancy, and the robustness of genomes. PNAS, 99 (2002), 1405--1409.
[7]
Langdon, W. Fitness Causes Bloat: Simulated Annealing, Hill Climbing and Populations. Technical Report CSRP-97-22, University of Birmingham, Birmingham, UK, 1997.
[8]
Langdon, W., and Poli, R. Fitness Causes Bloat. In Second On-line World Conference on Soft Computing in Engineering Design and Manufacturing, Springer-Verlag, London, 1997, 13--22.
[9]
Langdon, W., and Poli, R. Fitness Causes Bloat: Mutation. In Proceedings of the First European Workshop on Genetic Programming, Springer-Verlag, Paris, 1998, 37--48.
[10]
Langdon, W., Soule, T., Poli, R., and Foster, J. The Evolution of Size and Shape. In Advances in Genetic Programming III. The MIT Press, Cambridge, MA, 1999, 163--190.
[11]
McPhee, N. F., and Miller, J. D. Accurate Replication in Genetic Programming. In Proceedings of the Sixth International Conference on Genetic Algorithms. Morgan Kaufmann, San Francisco, CA, 1995, 310--317
[12]
Nordin, P., and Banzhaf, W. Complexity Compression and Evolution. In Proceedings of the Sixth International Conference on Genetic Algorithms. Morgan Kaufmann, San Francisco, CA, 1995, 310--317.
[13]
Nordin, P., Banzhaf, W., and Francone, F. Introns in Nature and in Simulated Structure Evolution. In Proceedings Bio-Computing and Emergent Computation. Springer, 1997, 22--35.
[14]
Smith, P., and Harries, K. Code Growth, Explicitly Defined Introns, and Alternative Selection Schemes. Evolutionary Computation, 6, 4 (1998), 339--360
[15]
Soule, T. Exons and Code Growth in Genetic Programming. In Genetic Programming, 5th European Conference, EuroGP 2002, 2002, 142--151.
[16]
Soule, T. Operator Choice and the Evolution of Robust Solutions. In Genetic Programming Theory and Practice, Riolo R., and Worzel, B., 2003, 257--270.
[17]
Soule, T. Resilient Individuals Improve Evolutionary Search. Artificial Life, 12, 1 (Winter 2005), 17--34.
[18]
Soule, T., Foster, J., and Dickinson, J. Code Growth in Genetic Programming. In Genetic Programming 1996: Proceedings of the First Annual Conference. MIT Press, Cambridge, MA, 1996, 215--223.
[19]
Soule, T., Heckendorn, R., and Shen, J. Solution Stability in Evolutonary Computation. In Proceedings of the 17th International Symposium on Computer and Information Systems, 2002, 237--241.
[20]
Wilke, C. Selection for Fitness versus Selection for Robustness in RNA Secondary Structure Folding. Evolution, 55 (2001), 2412--2420.
[21]
Wilke, C., Wang, J. L., Ofria, C, Lenski, R. E., and Adami, C. Evolution of digital organisms at high mutation rates leads to survival of the flattest. Nature, 412 (2001), 331--33.

Cited By

View all
  • (2023)Performance Comparison of Steady State GAs and Generational GAs for Capacitated Vehicle Routing ProblemsProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3590614(475-478)Online publication date: 15-Jul-2023
  • (2020)On the Performance of Generational and Steady-State MOEA/D in the Multi-Objective 0/1 Knapsack Problem2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185715(1-8)Online publication date: 19-Jul-2020
  • (2020)Selection Schemes Analysis in Genetic Algorithms for the Maximum Influence ProblemAdvances in Soft Computing10.1007/978-3-030-60884-2_16(211-222)Online publication date: 12-Oct-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation
July 2006
2004 pages
ISBN:1595931864
DOI:10.1145/1143997
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: 08 July 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. generational
  2. genetic robustness
  3. growth
  4. resiliency
  5. steady-state

Qualifiers

  • Article

Conference

GECCO06
Sponsor:
GECCO06: Genetic and Evolutionary Computation Conference
July 8 - 12, 2006
Washington, Seattle, USA

Acceptance Rates

GECCO '06 Paper Acceptance Rate 205 of 446 submissions, 46%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)8
  • Downloads (Last 6 weeks)0
Reflects downloads up to 08 Mar 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Performance Comparison of Steady State GAs and Generational GAs for Capacitated Vehicle Routing ProblemsProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3590614(475-478)Online publication date: 15-Jul-2023
  • (2020)On the Performance of Generational and Steady-State MOEA/D in the Multi-Objective 0/1 Knapsack Problem2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185715(1-8)Online publication date: 19-Jul-2020
  • (2020)Selection Schemes Analysis in Genetic Algorithms for the Maximum Influence ProblemAdvances in Soft Computing10.1007/978-3-030-60884-2_16(211-222)Online publication date: 12-Oct-2020
  • (2019)Inference of meteoroid characteristics using a genetic algorithmIcarus10.1016/j.icarus.2019.04.002329(270-281)Online publication date: Sep-2019
  • (2018)Adapting GA to solve a novel model for operating room scheduling problem with endogenous uncertaintyOperations Research for Health Care10.1016/j.orhc.2018.02.00219(26-43)Online publication date: Dec-2018
  • (2017)Multithreaded computing in evolutionary design and in artificial life simulationsThe Journal of Supercomputing10.1007/s11227-016-1923-473:5(2214-2228)Online publication date: 1-May-2017
  • (2017)New Adaptations for Evolutionary Algorithm Applied to Dynamic Difficulty Adjustment System for Serious GameMan-Machine Interactions 510.1007/978-3-319-67792-7_48(492-501)Online publication date: 20-Sep-2017
  • (2017)Dynamic Difficulty Adjustment for Serious Game Using Modified Evolutionary AlgorithmArtificial Intelligence and Soft Computing10.1007/978-3-319-59063-9_33(370-379)Online publication date: 27-May-2017
  • (2013)Critical Mutation Rate Has an Exponential Dependence on Population Size in Haploid and Diploid PopulationsPLoS ONE10.1371/journal.pone.00834388:12(e83438)Online publication date: 27-Dec-2013
  • (2012)Significant enhancements in feature selection to improve detecting network intrusionsInternational Conference on Education and e-Learning Innovations10.1109/ICEELI.2012.6360644(1-6)Online publication date: Jul-2012
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media