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

Information landscapes and the analysis of search algorithms

Published: 25 June 2005 Publication History

Abstract

In [15] we introduced the information landscape as a new concept of a landscape. We showed that for a landscape of a small size, information landscape theory can be used to predict the performance of a GA without running the algorithm. Based on this framework, here we develop a new theoretical model to study search algorithms in general. Particularly, we are able to infer important properties of a search algorithm without having knowledge about its specific operators. We give an example of this technique for a simple GA.

References

[1]
C. Blum and A.Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv. 35 (3): 268--308, 2003.]]
[2]
S.Forrest and M.Mitchell. Relative Building Block Fitness and the Building Block Hypothesis. In D. Whitley (ed.) Foundations of Genetic Algorithms 2. Morgan Kaufmann, San Mateo, CA, 1992.]]
[3]
Stefan Droste: Analysis of the (1+1) EA for a Noisy OneMax. GECCO (1) 1088--1099, 2004.]]
[4]
A.H.Right, J.E.Row, J.R.Neil. Analysis of the Simple genetic Algorithm on the Single-peak and Double-peak Landscapes. In Proceedings of the 2002 Congress on Evolutionary Computation CEC 2002. Hawaii, USA, pages 214--219, 2002.]]
[5]
D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Morgan Kaufmann, 1989.]]
[6]
Stefan Droste, Thomas Jansen, Ingo Wegener: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276 (1-2): 51--81, 2002.]]
[7]
Thomas Jansen, Ingo Wegener: On the Choice of the Mutation Probability for the (1+1) EA. PPSN 2000: 89--98, 2002.]]
[8]
C.Höhn and C.R.Reeves (1996) The crossover landscape for the onemax problem. In J.Alander (Ed.) Proceedings of the 2nd Nordic Workshop on Genetic Algorithms and their Applications, University of Vaasa Press, Vaasa, Finland, pages 27--43, 1996.]]
[9]
H. Asoh and H. Muehlenbein. On the mean convergence time of evolutionary algorithms without selection and mutation. In PPSN III, volume 866 of Lecture Notes in Computer Science, pages 88--97. Springer-Verlag, 1994.]]
[10]
Vose, M.D. The Simple Genetic Algorithm. MIT Press, Cambridge, 1999]]
[11]
Riccardo Poli, Christopher R. Stephens, Alden H. Wright, and Jonathan E. Rowe, "On the Search Biases of Homologous Crossover in Linear Genetic Programming and Variable-length Genetic Algorithms", GECCO, Morgan Kaufmann, 2002.]]
[12]
C.-Y. Lee, E. K. Antonsson: Variable Length Genomes for Evolutionary Algorithms. GECCO 2000: 806, 2000.]]
[13]
Anabela Simões, Ernesto Costa: Parametric Study To Enhance The Genetic Algorithm's Performance When Using Transformation. GECCO 2002: 697, 2002.]]
[14]
Franz Rothlauf. Representations for Genetic and Evolutionary Algorithms. Springer 2002.]]
[15]
Y.Borenstein and R.Poli. Information landscapes. In Proceedings of GECCO, ACM, 2005.]]
[16]
J.H. Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to biology, control and artificial intelligence. MIT Press, 1998.]]
[17]
Y.Borenstein and R.Poli. Fitness distribution and GA hardness. In Proceedings of PPSN, Springer, 2004.]]

Cited By

View all
  • (2022)Adaptive local landscape feature vector for problem classification and algorithm selectionApplied Soft Computing10.1016/j.asoc.2022.109751131(109751)Online publication date: Dec-2022
  • (2022)Fitness Landscape Analysis: From Problem Understanding to Design of Evolutionary AlgorithmsBio-Inspired Computing: Theories and Applications10.1007/978-981-19-1256-6_21(281-293)Online publication date: 24-Mar-2022
  • (2018)Network-Based Problem Difficulty Prediction MeasuresEvolutionary Computation and Complex Networks10.1007/978-3-319-60000-0_4(53-74)Online publication date: 23-Sep-2018
  • Show More Cited By

Index Terms

  1. Information landscapes and the analysis of search algorithms

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation
    June 2005
    2272 pages
    ISBN:1595930108
    DOI:10.1145/1068009
    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: 25 June 2005

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. fitness landscape
    2. genetic algorithm
    3. theory

    Qualifiers

    • Article

    Conference

    GECCO05
    Sponsor:

    Acceptance Rates

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

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2022)Adaptive local landscape feature vector for problem classification and algorithm selectionApplied Soft Computing10.1016/j.asoc.2022.109751131(109751)Online publication date: Dec-2022
    • (2022)Fitness Landscape Analysis: From Problem Understanding to Design of Evolutionary AlgorithmsBio-Inspired Computing: Theories and Applications10.1007/978-981-19-1256-6_21(281-293)Online publication date: 24-Mar-2022
    • (2018)Network-Based Problem Difficulty Prediction MeasuresEvolutionary Computation and Complex Networks10.1007/978-3-319-60000-0_4(53-74)Online publication date: 23-Sep-2018
    • (2016)An adaptive model selection strategy for surrogate-assisted particle swarm optimization algorithm2016 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI.2016.7850208(1-8)Online publication date: Dec-2016
    • (2010)On aggregation of fitness landscapes2010 Second World Congress on Nature and Biologically Inspired Computing (NaBIC)10.1109/NABIC.2010.5716379(684-690)Online publication date: Dec-2010
    • (2007)Decomposition of fitness functions in random heuristic searchProceedings of the 9th international conference on Foundations of genetic algorithms10.5555/1757524.1757532(123-137)Online publication date: 8-Jan-2007
    • (2005)Information landscapesProceedings of the 7th annual conference on Genetic and evolutionary computation10.1145/1068009.1068248(1515-1522)Online publication date: 25-Jun-2005
    • (2005)Information landscapes and problem hardnessProceedings of the 7th annual conference on Genetic and evolutionary computation10.1145/1068009.1068236(1425-1431)Online publication date: 25-Jun-2005

    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