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

Information landscapes

Published: 25 June 2005 Publication History

Abstract

We give a new interpretation to the concept of "landscape". This allows us to develop a new theoretical model to study search algorithms. Particularly, we are able to quantify the amount and quality of "information" embedded in a landscape and to predict the performance of a search algorithm over it. We conclude presenting empirical results for a simple genetic algorithm which strongly support this idea.

References

[1]
C. Blum and A.Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv. 35(3): 268--308 2003.
[2]
D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Morgan Kaufmann, 1989
[3]
S.Forrest and M.Mitchell. Relative Building Block Fitness and the Building Block Hypothesis. Foundations of Genetic Algorithms 2. Morgan Kaufmann, San Mateo, CA, 1992.
[4]
Y.Davidor. Epistasis variance: A viewpoint on GA-hardness. Foundations of Genetic Algorithms, Morgan Kaufmann, 1991.
[5]
B.Naudts.Measuring GA-hardness. Ph.d thesis. UV. Of Antwerp. Belgium, 1998.
[6]
B.Naudts and L. Kallel, Comparison of summary statistics of fitness landscapes,IEEE Trans. Evol. Comp. V.4.1:1--15, 2000
[7]
J.J.Grefenstette. Deception considered harmful. Foundations of Genetic Algorithms 2,Morgan Kaufmann: 75--91 1993
[8]
T. Jansen. On Classifications of Fitness Functions. Reihe CI 76/99, SFB 531, Universitat Dortmund, 1999
[9]
H. Guo and W.H.Hsu. GA-hardness Revisited. GECCO 2003, Lecture Notes in Computer Science 2724, 1584--1585 Springer 2003.
[10]
Christian M. Reidys Peter F. Stadler. Combinatorial Landscapes. SIAM Review 44: 3--54 2002.
[11]
D. E. Goldberg. Making genetic algorithm fly: a lesson from the Wright brothers. Advanced Technology For Developers, 2 pp.1--8, February 1993.
[12]
S. Rana. Examining the Role of Local Optima and Schema Processing in Genetic Search. PhD thesis, Colorado State University, 1998.
[13]
L. Kallel, B. Naudts, and C. R. Reeves. Properties of fitness functions and search landscapes. In L. Kallel, B. Naudts, and A. Rogers, editors, Theoretical Aspects of Evolutionary Computing, 175--206. Springer, Berlin, 2001.
[14]
T.Jones and S.Forrest. Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In Larry Eshelman, editor, Proceedings of the Sixth International Conference on Genetic Algorithms, pages 184--192, San Francisco, CA, 1995.
[15]
L.Altenberg. Fitness Distance Correlation analysis: An instructive counter-example. ICGA, pp 57--64, 1997.
[16]
S.A. Kauffman. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, Oxford, 1993.
[17]
L.Altenberg. NK fitness landscapes. Handbook of Evolutionary Computation Section B2.7.2 . 1997.
[18]
C.R.Reeves. Landscapes, operators and heuristic search. Annals of Operational Research, 86 473--490, 1999.
[19]
P.F.Stadler and C.R.Stephens. Landscapes and Effective Fitness. Comments Theori. Biol. 8: 389--431, 2002.
[20]
Y.Borenstein and R.Poli. Information Landscapes and Problem Hardness. In Proceedings of the Genetic and Evolutionary Computation Conference, ACM, 2005.
[21]
Y.Borenstein and R.Poli. Fitness distribution and GA hardness. PPSN VIII, Lecture Notes in Computer Science 3242 Springer 2004
[22]
Y.Borenstein and R.Poli. Information Landscapes and the Analysis of Search Algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference, ACM, 2005.

Cited By

View all
  • (2024)On the representativeness metric of benchmark problems in numerical optimizationSwarm and Evolutionary Computation10.1016/j.swevo.2024.10171691(101716)Online publication date: Dec-2024
  • (2023)Keenness for characterizing continuous optimization problems and predicting differential evolution algorithm performanceComplex & Intelligent Systems10.1007/s40747-023-01005-79:5(5251-5266)Online publication date: 16-Mar-2023
  • (2023)A comprehensive survey of feature selection techniques based on whale optimization algorithmMultimedia Tools and Applications10.1007/s11042-023-17329-y83:16(47775-47846)Online publication date: 28-Oct-2023
  • Show More Cited By

Index Terms

  1. Information landscapes

    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)11
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)On the representativeness metric of benchmark problems in numerical optimizationSwarm and Evolutionary Computation10.1016/j.swevo.2024.10171691(101716)Online publication date: Dec-2024
    • (2023)Keenness for characterizing continuous optimization problems and predicting differential evolution algorithm performanceComplex & Intelligent Systems10.1007/s40747-023-01005-79:5(5251-5266)Online publication date: 16-Mar-2023
    • (2023)A comprehensive survey of feature selection techniques based on whale optimization algorithmMultimedia Tools and Applications10.1007/s11042-023-17329-y83:16(47775-47846)Online publication date: 28-Oct-2023
    • (2020)Forecasting Electricity Prices: A Machine Learning ApproachAlgorithms10.3390/a1305011913:5(119)Online publication date: 8-May-2020
    • (2020)Mutation Strategy Selection Based on Fitness Landscape Analysis: A Preliminary StudyBio-inspired Computing: Theories and Applications10.1007/978-981-15-3425-6_23(284-298)Online publication date: 2-Apr-2020
    • (2019)On the Robustness of Random Walks for Fitness Landscape Analysis2019 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI44817.2019.9002761(1898-1906)Online publication date: Dec-2019
    • (2019)Domination landscape in evolutionary algorithms and its applicationsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-018-3206-x23:11(3563-3570)Online publication date: 1-Jun-2019
    • (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
    • (2017)Interpolated continuous optimisation problems with tunable landscape featuresProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3076045(169-170)Online publication date: 15-Jul-2017
    • (2016)Two-phase differential evolution framework for solving optimization problems2016 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI.2016.7850258(1-8)Online publication date: Dec-2016
    • 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