Nothing Special   »   [go: up one dir, main page]

Skip to main content

A Comprehensive Survey on Fitness Landscape Analysis

  • Chapter
Recent Advances in Intelligent Engineering Systems

Part of the book series: Studies in Computational Intelligence ((SCI,volume 378))

Abstract

In the past, the notion of fitness landscapes has found widespread adoption. Many different methods have been developed that provide a general and abstract framework applicable to any optimization problem. We formally define fitness landscapes, provide an in-depth look at basic properties and give detailed explanations and examples of existing fitness landscape analysis techniques. Moreover, several common test problems or model fitness landscapes that are frequently used to benchmark algorithms or analysis methods are examined and explained and previous results are consolidated and summarized. Finally, we point out current limitations and open problems pertaining to the subject of fitness landscape analysis.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 169.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ackley, D.H.: A connectionist machine for genetic hillclimbing. Kluwer, Dordrecht (1987)

    Book  Google Scholar 

  2. Aita, T., Hayashi, Y., Toyota, H., Husimi, Y., Urabe, I., Yomo, T.: Extracting characteristic properties of fitness landscape from in vitro molecular evolution: A case study on infectivity of fd phage to E.coli. J. Theor. Biol. 246, 538–550 (2007)

    Article  MathSciNet  Google Scholar 

  3. Altenberg, L.: The Evolution of Evolvability in Genetic Programming. In: Advances in Genetic Programming, pp. 47–74. MIT Press, Cambridge (1994)

    Google Scholar 

  4. Altenberg, L.: NK Fitness Landscapes. In: The Handbook of Evoluationary Computation, pp. B2.7.2:1–11. Oxford University Press, Oxford (1997)

    Google Scholar 

  5. Barnett, L.: Tangled Webs: Evolutionary Dynamics on Fitness Landscapes with Neutrality. MSc dissertation, School of Cognitive Sciences, University of East Sussex, Brighton (1997)

    Google Scholar 

  6. Barnett, L.: Ruggedness and neutrality—the NKp family of fitness landscapes. In: ALIFE, pp. 18–27. MIT Press, Cambridge (1998)

    Google Scholar 

  7. Borenstein, Y., Poli, R.: Decomposition of fitness functions in random heuristic search. In: Stephens, C.R., Toussaint, M., Whitley, L.D., Stadler, P.F. (eds.) FOGA 2007. LNCS, vol. 4436, pp. 123–137. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  8. Box, G.E.P., Jenkins, G.M., Reinsel, G.: Time Series Analysis: Forecasting & Control. Holden Day (1970)

    Google Scholar 

  9. Brandt, H., Dieckmann, U.: Correlation Analysis of Fitness Landscapes. Working papers, International Institute for Applied Systems Analysis (1999)

    Google Scholar 

  10. Chaitin, G.J.: Information, Randomness & Incompleteness. World Scientific, Singapore (1987)

    MATH  Google Scholar 

  11. Collard, P., Verel, S., Clergue, M.: Local search heuristics: Fitness Cloud versus Fitness Landscape. In: ECAI, pp. 973–974. IOS Press, Amsterdam (2004)

    Google Scholar 

  12. Cordell, H.J.: Epistasis: what it means, what it doesn’t mean, and statistical methods to detect it in humans. Hum. Mol. Genet 11, 2463–2468 (2002)

    Article  Google Scholar 

  13. Czech, Z.: Statistical measures of a fitness landscape for the vehicle routing problem. In: IPDPS, pp. 1–8 (2008)

    Google Scholar 

  14. Davidor, Y.: Epistasis variance: suitability of a representation to genetic algorithms. Complex Systems 4, 369–383 (1990)

    Google Scholar 

  15. Derrida, B.: Random energy model: Limit of a family of disordered models. Phys. Rev. Lett. 45, 79–82 (1980)

    Article  MathSciNet  Google Scholar 

  16. Droste, S., Jansen, T., Wegener, I.: Perhaps Not a Free Lunch But At Least a Free Appetizer. In: GECCO, July 13-17, vol. 1, pp. 833–839. Morgan Kaufmann, San Francisco (1999)

    Google Scholar 

  17. Fonlupt, C., Robilliard, D., Preux, P.: Fitness Landscape and the Behavior of Heuristics. In: Monmarché, N., Talbi, E.-G., Collet, P., Schoenauer, M., Lutton, E. (eds.) EA 2007. LNCS, vol. 4926, pp. 321–329. Springer, Heidelberg (2008)

    Google Scholar 

  18. Fontana, W., Stadler, P.F., Bornberg Bauer, E.G., Griesmacher, T., Hofacker, I.L., Tacker, M., Tarazona, P., Weinberger, E.D., Schuster, P.: RNA folding and combinatory landscapes. Phys. Rev. E 47(3), 2083–2099 (1993)

    Article  Google Scholar 

  19. Gavrilets, S.: Evolution and Specitation in a Hyperspace: The Roles of Neutrality, Selection, Mutation and Random Drift. In: Evolutionary Dymaics: Exploring the Interplay of Selection, Accident, Neutrality and Function, pp. 135–162. Oxford University Press, Oxford (1999)

    Google Scholar 

  20. Geared, N., Wiles, J., Hallinan, J., Tonkes, B., Skellet, B.: A Comparison of Neutral Landscapes – NK, NKp and NKq. In: CEC, pp. 205–210. IEEE Press, Los Alamitos (2002)

    Google Scholar 

  21. Goldberg, D.E., Deb, K., Kargupta, H., Harik, G.: Rapid, Accurate Optimization of Difficult Problems Using Fast Messy Genetic Algorithms. In: ICGA, pp. 56–64. Morgan Kaufmann, San Francisco (1993)

    Google Scholar 

  22. Gouvêa, F.Q.: p-adic Numbers: An Introduction. Springer, Heidelberg (1993)

    MATH  Google Scholar 

  23. Grefenstette, J.J.: Evolvability in Dynamic Fitness Landscapes: A Genetic Algorithm Approach. In: CEC, pp. 2031–2038 (1999)

    Google Scholar 

  24. Hastings, W.K.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57, 97–109 (1970)

    Article  MATH  Google Scholar 

  25. Holland, J.H.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975)

    Google Scholar 

  26. Holland, J.H.: Evolution, Learning and Cognition, pp. 111–127. World Scientific, Singapore (1988)

    Google Scholar 

  27. Hordijk, W.: A measure of landscapes. Evol. Comput. 4(4), 335–360 (1996)

    Article  Google Scholar 

  28. Huynen, M.A.: Exploring phenotype space through neutral evolution. J. Mol. Evol. 43, 165–169 (1996)

    Article  Google Scholar 

  29. Huynen, M.A., Stadler, P.F., Fontana, W.: Smoothness within ruggedness: The role of neutrality in adaptation. P. Natl. Acad. Sci. USA 93, 397–401 (1996)

    Article  Google Scholar 

  30. Jones, T.: Evolutionary Algorithms, Fitness Landscapes and Search. Ph.D. thesis, University of New Mexico, Albuquerque, New Mexico (1995)

    Google Scholar 

  31. Jones, T., Forrest, S.: Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms. In: ICGA, pp. 184–192. Morgan Kaufmann, San Francisco (1995)

    Google Scholar 

  32. Kallel, L., Naudts, B., Schoenauer, M.: On functions with a given fitness-distance relation. In: CEC, vol. 3, pp. 1910–1916 (1999)

    Google Scholar 

  33. Katada, Y.: Estimating the Degree of Neutrality in Fitness Landscapes by the Nei’s Standard Genetic Distance – An Application to Evolutionary Robotics. In: CEC, pp. 483–490 (2006)

    Google Scholar 

  34. Katada, Y., Ohkura, K., Ueda, K.: The Nei’s standard genetic distance in artificial evolution. In: CEC, pp. 1233–1239 (2004)

    Google Scholar 

  35. Kauffman, S.: Adaptation on rugged fitness landscapes. Lectures in the Sciences of Complexity, vol. 1, pp. 527–618. Addison-Wesley Longman, Amsterdam (1989)

    Google Scholar 

  36. Kauffman, S.A.: The Origins of Order. Oxford University Press, Oxford (1993)

    Google Scholar 

  37. Kimura, M.: Evolutionary Rate at the Molecular Level. Nature 217, 624–626 (1968)

    Article  Google Scholar 

  38. Koopmans, T.C., Beckmann, M.: Assignment Problems and the Location of Economic Activities. Econometrica 25(1), 53–76 (1957)

    Article  MathSciNet  MATH  Google Scholar 

  39. Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R., Shmoys, D.B. (eds.): The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985)

    MATH  Google Scholar 

  40. Le, M.N., Ong, Y.-S., Jin, Y., Sendhoff, B.: Lamarckian memetic algorithms: local optimum and connectivity structure analysis. Memetic Comp. 1, 175–190 (2009)

    Article  Google Scholar 

  41. Lehn, R., Kuntz, P.: A contribution to the study of the fitness landscape for a graph drawing problem. In: Boers, E.J.W., Gottlieb, J., Lanzi, P.L., Smith, R.E., Cagnoni, S., Hart, E., Raidl, G.R., Tijink, H. (eds.) EvoWorkshops 2001. LNCS, vol. 2037, p. 172. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  42. Lipsitch, M.: Adaptation on rugged landscapes generated by iterated local interactions of neighboring genes. In: ICGA, vol. 135, pp. 128–135 (1991)

    Google Scholar 

  43. Manderick, B., de Weger, M.K., Spiessens, P.: The Genetic Algorithm and the Structure of the Fitness Landscape. In: ICGA, pp. 143–150 (1991)

    Google Scholar 

  44. Marrow, P.: Evolvability: Evolution, Computation, Biology. In: GECCO, pp. 30–33 (1999)

    Google Scholar 

  45. Mathias, K., Whitley, L.D.: Genetic operators, the fitness landscape and the traveling salesman problem. In: Parallel Problem Solving From Nature, vol. 2, pp. 219–228 (1992)

    Google Scholar 

  46. Mattfeld, D.C., Bierwirth, C.: A Search Space Analysis of the Job Shop Scheduling Problem. Ann. Oper. Res. 86, 441–453 (1996)

    Article  MathSciNet  Google Scholar 

  47. Merz, P.: Advanced fitness landscape analysis and the performance of memetic algorithms. Evol. Comput. 12(3), 303–325 (2004)

    Article  MathSciNet  Google Scholar 

  48. Merz, P., Freisleben, B.: Memetic Algorithms and the Fitness Landscape of the Graph Bi-Partitioning Problem. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 765–774. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  49. Merz, P., Freisleben, B.: Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE T. Evolut. Comput. 4(4), 337–352 (2000)

    Article  Google Scholar 

  50. Merz, P., Freisleben, B.: Memetic Algorithms for the Traveling Salesmen Problem. Complex Systems 13(4), 297–345 (2001)

    MathSciNet  MATH  Google Scholar 

  51. Moraglio, A., Poli, R.: Topological interpretation of crossover. In: Deb, K., et al. (eds.) GECCO 2004. LNCS, vol. 3102, pp. 1377–1388. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  52. Moraglio, A., Poli, R.: Topological Crossover for the Permutation Representation. In: GECCO 2005, pp. 332–338 (2005)

    Google Scholar 

  53. Munkres, J.R.: Topology. Prentice-Hall, Englewood Cliffs (2000)

    MATH  Google Scholar 

  54. Naudts, B.: Measuring GA-hardness. Ph.D. thesis, University of Antwerp (June 1998)

    Google Scholar 

  55. Naudts, B., Kallel, L.: A Comparison of Predictive Measures of Problem Difficulty in Evolutionary Algorithms. IEEE T. Evolut. Comput. 4(1), 1–15 (2000)

    Article  Google Scholar 

  56. Naudts, B., Verschoren, A.: Epistasis and Deceptivity. B Belg. Math. Soc-Sim 6(1), 147–154 (1999)

    MathSciNet  MATH  Google Scholar 

  57. Nei, M.: Genetic distance between populations. Am. Nat. 106, 283–292 (1972)

    Article  Google Scholar 

  58. Newman, M.E.J., Engelhardt, R.: Effects of selective neutrality on the evolution of molecular species. Proc. R Soc. Lond B 265, 1333–1338 (1998)

    Article  Google Scholar 

  59. Ochoa, G., Qu, R., Burke, E.K.: Analyzing the landscape of a graph based hyper-heuristic for timetabling problems. In: GECCO 2009, pp. 341–348. ACM, New York (2009)

    Chapter  Google Scholar 

  60. Ohta, T.: The Nearly Neutral Theory of Molecular Evolution. Annu. Rev. Ecol. Syst. 23, 263–286 (1992)

    Article  Google Scholar 

  61. Ohta, T.: The neutral theory is dead. The current significance and standing of neutral and nearly neutral theories. BioEssays 18(8), 673–677 (1996)

    Article  Google Scholar 

  62. Ohta, T.: Evolution by nearly-neutral mutations. Genetica 102/103, 89–90 (1998)

    Article  Google Scholar 

  63. Pitzer, E., Affenzeller, M., Beham, A.: A Closer Look Down the Basins of Attraction. In: UKCI, Colchester, UK, pp. 1–6 (2010)

    Google Scholar 

  64. Provine, W.B.: Sewall Wright and Evolutionary Biology. University of Chicago Press, Chicago (1989)

    Google Scholar 

  65. Quick, R.J., Rayward-Smith, V.J., Smith, G.D.: Fitness Distance Correlation and Ridge Functions. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 77–86. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  66. Rechenberg, I.: Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog (1973)

    Google Scholar 

  67. Reeves, C.R., Rowe, J.E.: Genetic Algorithms—Principles and Perspectives. Kluwer, Dordrecht (2003)

    Google Scholar 

  68. Reeves, C.R., Wright, C.C.: Epistasis in Genetic Algorithms: An Experimental Design Perspective. In: ICGA, pp. 217–224. Morgan Kaufmann, San Francisco (1995)

    Google Scholar 

  69. Reidys, C.M., Stadler, P.F.: Neutrality in fitness landscapes. Appl. Math. Comput. 117(2-3), 321–350 (1998)

    Article  MathSciNet  Google Scholar 

  70. Reidys, C.M., Stadler, P.F.: Combinatorial Fitness Landscapes. SIAM Rev. 44, 3–54 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  71. Rochet, S.: Epistasis in genetic algorithms revisited. Inform. Sciences 102(1-4), 133–155 (1997)

    Article  MathSciNet  Google Scholar 

  72. Rochet, S., Venturini, G., Slimane, M., El Kharoubi, E.M.: A Critical and Empirical Study of Epistasis Measures for Predicting GA Performances: A Summary. In: Hao, J.-K., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds.) AE 1997. LNCS, vol. 1363, pp. 275–286. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  73. Rockmore, D., Kostelec, P., Hordijk, W., Stadler, P.F.: Fast Fourier Transform for Fitness Landscapes. Appl. Comput. Harmon A 12(1), 57–76 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  74. Saitou, N., Nei, M.: The Neighbor-joining Method: A New Method for Reconstructing Phylogenetic Trees. Mol. Biol. Evol. 4(4), 406–425 (1987)

    Google Scholar 

  75. Shannon, C.E.: A Mathematical Theory of Communication. AT&T Tech. J. 27, 379–423, 623–656 (1948)

    MathSciNet  Google Scholar 

  76. Sherrington, D., Kirkpatrick, S.: Solvable model of a spin-glass. Phys. Rev. Lett. 35(26), 1792–1795 (1975)

    Article  Google Scholar 

  77. Smith, T., Husbands, P., Layzell, P., O’Shea, M.: Fitness landscapes and evolvability. Evol. Comput. 10(1), 1–34 (2002)

    Article  Google Scholar 

  78. Stadler, P., Wagner, G.: The Algebraic Theory of Recombination Spaces. Evol. Comput. 5, 241–275 (1998)

    Article  Google Scholar 

  79. Stadler, P.F.: Linear Operators on Correlated Landscapes. J. Phys. I 4, 681–696 (1994)

    Article  Google Scholar 

  80. Stadler, P.F.: Towards a Theory of Landscapes. Lecture Notes in Physics, vol. 461, pp. 78–163. Springer, Heidelberg (1995)

    Google Scholar 

  81. Stadler, P.F.: Landscapes and Their Correlation Functions. J. Math. Chem. 20, 1–45 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  82. Stadler, P.F.: Fitness Landscapes. In: Biological Evolution and Statistical Physics, pp. 187–207. Springer, Heidelberg (2002)

    Google Scholar 

  83. Stadler, P.F., Happel, R.: Random field models for fitness landscapes. Working Papers 95-07-069, Santa Fe Institute, Santa Fe, NM (1995)

    Google Scholar 

  84. Stadler, P.F., Schnabl, W.: The Landscape of the Travelling Salesmand Problem. Phys. Lett. A 161, 337–344 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  85. Stadler, P.F., Seitz, R., Wagner, G.P.: Evolvability of Complex Characters: Population Dependent Fourier Decomposition of Fitness Landscapes over Recombination Spaces. B Math. Biol. 62, 399–428 (2000)

    Article  Google Scholar 

  86. Talbi, E.-G.: Metaheuristics: From Design to Implementation. Wiley, Chichester (2009)

    MATH  Google Scholar 

  87. Tavares, J., Pereira, F., Costa, E.: Multidimensional Knapsack Problem: A Fitness Landscape Analysis. IEEE T. Syst. Man Cy. B 38(3), 604–616 (2008)

    Article  Google Scholar 

  88. Thompson, R.K., Wright, A.H.: Additively Decomposable Fitness Functions. Tech. rep., University of Montan, Computer Science Dept., Missoula, MT, USA (1996)

    Google Scholar 

  89. Turney, P.: Increasing evolvability considered as a large-scale trend in evolution. In: GECCO, pp. 43–46 (1999)

    Google Scholar 

  90. Uludağ, G., Uyar, A.Ş.: Fitness Landscape Analysis of Differential Evolution Algorithms. In: ICSCCW (2009)

    Google Scholar 

  91. Vanneschi, L., Clergue, M., Collard, P., Tomassini, M., Vérel, S.: Fitness Clouds and Problem Hardness in Genetic Programming. In: Deb, K., et al. (eds.) GECCO 2004. LNCS, vol. 3103, pp. 690–701. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  92. Vanneschi, L., Tomassini, M., Collard, P., Vérel, S.: Negative slope coefficient: A measure to characterize genetic programming fitness landscapes. In: Collet, P., Tomassini, M., Ebner, M., Gustafson, S., Ekárt, A. (eds.) EuroGP 2006. LNCS, vol. 3905, pp. 178–189. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  93. Vanneschi, L., Verel, S., Tomassini, M., Collard, P.: NK Landscapes Difficulty and Negative Slope Coefficient: How Sampling Influences the Results. In: Giacobini, M., Brabazon, A., Cagnoni, S., Di Caro, G.A., Ekárt, A., Esparcia-Alcázar, A.I., Farooq, M., Fink, A., Machado, P. (eds.) EvoWorkshops 2009. LNCS, vol. 5484, pp. 645–654. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  94. Vassilev, V.K., Fogarty, T.C., Miller, J.F.: Information Characteristics and the Structure of Landscapes. Evol. Comput. 8(1), 31–60 (2000)

    Article  Google Scholar 

  95. Wagner, A.: Robustness, evolvability, and neutrality. FEBS Lett. 579, 1772–1778 (2005)

    Article  Google Scholar 

  96. Wagner, A.: Robustness and evolvability: a paradox resolved. Proc. R Soc. B 275, 91–100 (2008)

    Article  Google Scholar 

  97. Wagner, G., Stadler, P.: Complex Adaptations and the Structure of Recombination Spaces. In: Algebraic Engineering, pp. 96–115. World Scientific, Singapore (1998)

    Google Scholar 

  98. Wagner, G.P., Altenberg, L.: Complex Adaptations and the Evoluation of Evolvability. Evolution 50(3), 967–976 (1996)

    Article  Google Scholar 

  99. Wang, S., Zhu, Q., Kang, L.: Landscape Properties and Hybrid Evolutionary Algorithm for Optimum Multiuser Detection Problem. In: ICCSA, pp. 340–347 (2006)

    Google Scholar 

  100. Weinberger, E.: Correlated and uncorrelated fitness landscapes and how to tell the difference. Biol. Cybern. 63(5), 325–336 (1990)

    Article  MATH  Google Scholar 

  101. Weinberger, E.D.: Local properties of Kauffman’s N-k model, a tuneably rugged energy landscape. Phys. Rev. A 44(10), 6399–6413 (1991)

    Article  Google Scholar 

  102. Weinberger, E.D.: NP Completeness of Kauffman’s N-k Model, A Tuneable Rugged Fitness Landscape. Working Papers 96-02-003, Santa Fe Institute (1996)

    Google Scholar 

  103. Wright, S.: The Roles of Mutation, Inbreeding, Crossbreeding and Selection in Evolution. In: 6th International Congress of Genetics, vol. 1, pp. 356–366 (1932)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Pitzer, E., Affenzeller, M. (2012). A Comprehensive Survey on Fitness Landscape Analysis. In: Fodor, J., Klempous, R., Suárez Araujo, C.P. (eds) Recent Advances in Intelligent Engineering Systems. Studies in Computational Intelligence, vol 378. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23229-9_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-23229-9_8

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-23228-2

  • Online ISBN: 978-3-642-23229-9

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics