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

Information landscapes and problem hardness

Published: 25 June 2005 Publication History

Abstract

In [20] we introduced a new concept of a landscape: the information landscape. We showed that for problems of very small size (e.g. a 3-bit problem), it can be used to generally and accurately predict the performance of a GA. Based on this framework, in this paper we develop a method to predict GA hardness on realistic landscapes. We give empirical results which support our approach.

References

[1]
D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Morgan Kaufmann, 1989.
[2]
S.Forrest and M.Mitchell. Relative Building Block Fitness and the Building Block Hypothesis. In FOGA 2. Morgan Kaufmann, 1992.
[3]
D. E. Goldberg. Making genetic algorithm fly: a lesson from the Wright brothers. Advanced Technology For Developers, 2 pp.1--8, February 1993.
[4]
S. Rana. Examining the Role of Local Optima and Schema Processing in Genetic Search. PhD thesis, Colorado State University, 1998.
[5]
J.J.Grefenstette. Deception considered harmful. In Foundations of Genetic Algorithms 2, D. Whitley (Ed.), San Mateo, CA: Morgan Kaufmann, 1993.
[6]
T. Jansen. On Classifications of Fitness Functions. Reihe CI 76/99, SFB 531, Universitat Dortmund, 1999.
[7]
Y.Davidor. Epistasis variance: A viewpoint on GA-hardness. In G.J.E Rawlines, editor FOGA-1,pp. 23--55. Morgan Kaufman 1991.
[8]
B. Naudts. Measuring GA-hardness. Ph.d thesis. UV. Of Antwerp. Belgium, 1998.
[9]
S.A. Kauffman. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, Oxford, 1993.
[10]
L.Altenberg. NK fitness landscapes. Handbook of Evolutionary Computation 1997b.
[11]
B.Naudts and L.Kallel, Comparison of summery statistics of fitness landscapes, IEEE Trans.Evol.Comp. 2000.
[12]
H. Guo and W.H.Hsu. GA-hardness Revisited. GECCO 2003 Poster paper.
[13]
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 CEC, 1995.
[14]
L.Altenberg. Fitness Distance Correlation analysis: An instructive counter-example. ICGA, pp 57--64, 1997.
[15]
F.Rothlauf. Representations for Genetic and Evolutionary Algorithms. Studies in Fuzziness and Soft Computing, Volume 104. Heidelberg: Springer, 1st edition 2002.
[16]
L.Altenberg. Evolving better representations through selective genome growth. Proceedings of the 1st IEEE Conference on Evolutionary Computation. Part 1, 1994.
[17]
A.Moraglio and R.Poli. Topological interpretation of crossover. In Proceedings of GECCO, Springer, 2004.
[18]
N.J.Radcliffe. Equivalence class analysis of genetic algorithms. In Foundations of Genetic Algorithms 3. Morgan Kaufmann, 1994.
[19]
H. Huttel. On Rice's Theorem. Aalborg University. 2001.
[20]
Y.Borenstein and R.Poli. Information Landscapes. In Proceedings of the Genetic and Evolutionary Computation Conference, ACM, 2005.
[21]
Y.Borenstein and R.Poli. Information Landscapes and the Analysis of Search Algorithms. In Proceedings of GECCO, ACM, 2005.
[22]
M.Clergue, P.Collard. GA-hard functions built by combination of trap functions. In Proceedings CEC2002, IEEE Press. 2002.
[23]
C.R.Reeves. Landscapes, operators and heuristic search. Annals of Operational Research, 86 473--490, 199

Cited By

View all
  • (2024)Algorithm for Local Extrema Seeking of Black-Box Functions Based on Information Landscape Measure2024 China Automation Congress (CAC)10.1109/CAC63892.2024.10865284(4121-4126)Online publication date: 1-Nov-2024
  • (2023)A deep hybrid transfer learning-based evolutionary algorithm and its application in the optimization of high-order problemsSoft Computing10.1007/s00500-023-08192-y27:14(9661-9672)Online publication date: 2-May-2023
  • (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
  • Show More Cited By

Index Terms

  1. Information landscapes and problem hardness

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

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Algorithm for Local Extrema Seeking of Black-Box Functions Based on Information Landscape Measure2024 China Automation Congress (CAC)10.1109/CAC63892.2024.10865284(4121-4126)Online publication date: 1-Nov-2024
    • (2023)A deep hybrid transfer learning-based evolutionary algorithm and its application in the optimization of high-order problemsSoft Computing10.1007/s00500-023-08192-y27:14(9661-9672)Online publication date: 2-May-2023
    • (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
    • (2020)Covariance Local Search for Memetic Frameworks: A Fitness Landscape Analysis Approach2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185548(1-8)Online publication date: Jul-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)Complexity of an Identification Problem of Sharp Local Density Loss in Fractional BodyAdvances in Non-Integer Order Calculus and Its Applications10.1007/978-3-030-17344-9_21(282-293)Online publication date: 17-Apr-2019
    • (2018)Predictive Models of Problem Difficulties for Differential Evolutionary Algorithm Based on Fitness Landscape Analysis2018 37th Chinese Control Conference (CCC)10.23919/ChiCC.2018.8483931(3221-3226)Online publication date: Jul-2018
    • (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
    • (2014)Particle swarm optimisation failure prediction based on fitness landscape characteristics2014 IEEE Symposium on Swarm Intelligence10.1109/SIS.2014.7011789(1-9)Online publication date: Dec-2014
    • (2014)Exploration-exploitation tradeoffs in metaheuristics: Survey and analysisProceedings of the 33rd Chinese Control Conference10.1109/ChiCC.2014.6896450(8633-8638)Online publication date: Jul-2014
    • 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