skip to main content
10.1145/2460239.2460244acmconferencesArticle/Chapter ViewAbstractPublication PagesfogaConference Proceedingsconference-collections
research-article

Explaining optimization in genetic algorithms with uniform crossover

Published: 16 January 2013 Publication History

Abstract

Hyperclimbing is an intuitive, general-purpose, global optimization heuristic applicable to discrete product spaces with rugged or stochastic cost functions. The strength of this heuristic lies in its insusceptibility to local optima when the cost function is deterministic, and its tolerance for noise when the cost function is stochastic. Hyperclimbing works by decimating a search space, i.e., by iteratively fixing the values of small numbers of variables. The hyperclimbing hypothesis posits that genetic algorithms with uniform crossover (UGAs) perform optimization by implementing efficient hyperclimbing. Proof of concept for the hyperclimbing hypothesis comes from the use of an analytic technique that exploits algorithmic symmetry. By way of validation, we present experimental results showing that a simple tweak inspired by the hyperclimbing hypothesis dramatically improves the performance of a UGA on large, random instances of MAX-3SAT and the Sherrington Kirkpatrick Spin Glasses problem. An exciting corollary of the hyperclimbing hypothesis is that a form of implicit parallelism more powerful than the kind described by Holland underlies optimization in UGAs. The implications of the hyperclimbing hypothesis for Evolutionary Computation and Artificial Intelligence are discussed.

Supplementary Material

ZIP File (foga010.zip)
This online appendix contains a pdf file with two animations that serve as supplementary evidence for the Hyperclimbing Hypothesis described in the paper. For the animations to work, the pdf file must be viewed in Adobe Acrobat Reader version 7 or greater.

References

[1]
D.H. Ackley. A connectionist machine for genetic hillclimbing. Kluwer Academic Publishers, 1987.
[2]
James E. Baker. Adaptive selection methods for genetic algorithms. In John J. Grefenstette, editor, Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Lawrence Erlbaum Associates, Publishers, 1985.
[3]
Alfredo Braunstein, Marc MÈzard, and Riccardo Zecchina. Survey propagation: an algorithm for satisfiability. CoRR, cs.CC/0212002, 2002.
[4]
Keki Burjorjee. Sufficient conditions for coarse-graining evolutionary dynamics. In Foundations of Genetic Algorithms 9 (FOGA IX), 2007.
[5]
K.M. Burjorjee. Generative Fixation: A Unifed Explanation for the Adaptive Capacity of Simple Recombinative Genetic Algorithms. PhD thesis, Brandeis University, 2009.
[6]
T. H. Cormen, C. H. Leiserson, and R. L. Rivest. Introduction to Algorithms. McGraw-Hill, 1990.
[7]
Kenneth A De Jong and William M Spears. A formal analysis of the role of multi-point crossover in genetic algorithms. Annals of Mathematics and Artificial Intelligence, 5(1):1--26, 1992.
[8]
L.J. Eshelman, R.A. Caruana, and J.D. Schaffer. Biases in the crossover landscape. Proceedings of the third international conference on Genetic algorithms table of contents, pages 10--19, 1989.
[9]
D. B. Fogel. Evolutionary Computation: Towards a New Philosophy of Machine Intelligence. IEEE press, 2006.
[10]
David E. Goldberg. Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley, Reading, MA, 1989.
[11]
David E. Goldberg. The Design Of Innovation. Kluwer Academic Publishers, 2002.
[12]
John H. Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, 1975.
[13]
John H. Holland. Building blocks, cohort genetic algorithms, and hyperplane-defined functions. Evolutionary Computation, 8(4):373--391, 2000.
[14]
Holger H. Hoos and Thomas Stützle. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2004.
[15]
Li Huifang and Li Mo. A new method of image compression based on quantum neural network. In International Conference of Information Science and Management Engineering, pages p567--570, 2010.
[16]
E.T. Jaynes. Probability Theory: The Logic of Science. Cambridge University Press, 2007.
[17]
S.A. Kauffman. The Origins of Order: Self-Organization and Selection in Evolution. Biophysical Soc, 1993.
[18]
L. Kroc, A. Sabharwal, and B. Selman. Message-passing and local heuristics as decimation strategies for satisfiability. In Proceedings of the 2009 ACM symposium on Applied Computing, pages 1408--1414. ACM, 2009.
[19]
J. T. Langton, A. A. Prinz, and T. J. Hickey. Combining pixelization and dimensional stacking. In Advances in Visual Computing, pages II: 617--626, 2006.
[20]
M. Mézard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297(5582):812--815, 2002.
[21]
Melanie Mitchell. An Introduction to Genetic Algorithms. The MIT Press, Cambridge, MA, 1996.
[22]
A.E. Nix and M.D. Vose. Modeling genetic algorithms with Markov chains. Annals of Mathematics and Artificial Intelligence, 5(1):79--88, 1992.
[23]
Martin Pelikan. Finding ground states of sherrington-kirkpatrick spin glasses with hierarchical boa and genetic algorithms. In GECCO 2008: Proceedings of the 10th annual conference on Genetic and Evolutionary Computation Conference, 2008.
[24]
Karl Popper. The Logic Of Scientific Discovery. Routledge, 2007.
[25]
C.R. Reeves and J.E. Rowe. Genetic Algorithms: Principles and Perspectives: a Guide to GA Theory. Kluwer Academic Publishers, 2003.
[26]
Alexander Rosenbluth and Norbert Wiener. Purposeful and non-purposeful behavior. Philosophy of Science, 18, 1951.
[27]
B. Selman, H. Kautz, and B. Cohen. Local search strategies for satisfiability testing. Cliques, coloring, and satisfiability: Second DIMACS implementation challenge, 26:521--532, 1993.
[28]
William M. Spears and Kenneth De Jong. On the virtues of parameterized uniform crossover. In R. K. Belew and L. B. Booker, editors, Proc. of the Fourth Int. Conf. on Genetic Algorithms, pages 230--236, San Mateo, CA, 1991. Morgan Kaufmann.
[29]
G. Syswerda. Uniform crossover in genetic algorithms. In J. D. Schaffer, editor, Proceeding of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, 1989.
[30]
Sewall Wright. The roles of mutation, inbreeding, crossbreeding and selection in evolution. In Proceedings of the Sixth Annual Congress of Genetics, 1932.

Cited By

View all
  • (2024)Evolutionary Approach to Optimal Oil Skimmer Assignment for Oil Spill Response: A Case StudyBiomimetics10.3390/biomimetics90603309:6(330)Online publication date: 30-May-2024
  • (2020)DaTask: A Decomposition-Based Deadline-Aware Task Assignment and Workers’ Path-Planning in Mobile Crowd-SensingIEEE Access10.1109/ACCESS.2020.29801438(49920-49932)Online publication date: 2020
  • (2017)Impact of Reference Years on the Outcome of Multi-Objective Optimization for Building Energy RefurbishmentEnergies10.3390/en1011192510:11(1925)Online publication date: 21-Nov-2017
  • Show More Cited By

Index Terms

  1. Explaining optimization in genetic algorithms with uniform crossover

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII
    January 2013
    198 pages
    ISBN:9781450319904
    DOI:10.1145/2460239
    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: 16 January 2013

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. decimation
    2. genetic algorithms
    3. global optimization
    4. hyperclimbing
    5. maxsat
    6. spin glasses
    7. uniform crossover

    Qualifiers

    • Research-article

    Conference

    FOGA '13
    Sponsor:
    FOGA '13: Foundations of Genetic Algorithms XII
    January 16 - 20, 2013
    Adelaide, Australia

    Acceptance Rates

    Overall Acceptance Rate 72 of 131 submissions, 55%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)11
    • Downloads (Last 6 weeks)2
    Reflects downloads up to 03 Mar 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Evolutionary Approach to Optimal Oil Skimmer Assignment for Oil Spill Response: A Case StudyBiomimetics10.3390/biomimetics90603309:6(330)Online publication date: 30-May-2024
    • (2020)DaTask: A Decomposition-Based Deadline-Aware Task Assignment and Workers’ Path-Planning in Mobile Crowd-SensingIEEE Access10.1109/ACCESS.2020.29801438(49920-49932)Online publication date: 2020
    • (2017)Impact of Reference Years on the Outcome of Multi-Objective Optimization for Building Energy RefurbishmentEnergies10.3390/en1011192510:11(1925)Online publication date: 21-Nov-2017
    • (2016)Evolutionary Computation Techniques for Community Detection in Social Network AnalysisAdvanced Methods for Complex Network Analysis10.4018/978-1-4666-9964-9.ch011(266-284)Online publication date: 2016
    • (2015)Hypomixability Elimination In Evolutionary SystemsProceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII10.1145/2725494.2725511(163-175)Online publication date: 17-Jan-2015
    • (2015)Exploiting Concurrency for the Automated Synthesis of MPSoC InterconnectsACM Transactions on Embedded Computing Systems10.1145/270007514:3(1-24)Online publication date: 30-Apr-2015
    • (2014)A hybrid evolutionary approach to the registration area planning problemApplied Intelligence10.1007/s10489-014-0582-541:4(1127-1149)Online publication date: 1-Dec-2014

    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