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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ackley, D.H.: A connectionist machine for genetic hillclimbing. Kluwer, Dordrecht (1987)
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)
Altenberg, L.: The Evolution of Evolvability in Genetic Programming. In: Advances in Genetic Programming, pp. 47–74. MIT Press, Cambridge (1994)
Altenberg, L.: NK Fitness Landscapes. In: The Handbook of Evoluationary Computation, pp. B2.7.2:1–11. Oxford University Press, Oxford (1997)
Barnett, L.: Tangled Webs: Evolutionary Dynamics on Fitness Landscapes with Neutrality. MSc dissertation, School of Cognitive Sciences, University of East Sussex, Brighton (1997)
Barnett, L.: Ruggedness and neutrality—the NKp family of fitness landscapes. In: ALIFE, pp. 18–27. MIT Press, Cambridge (1998)
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)
Box, G.E.P., Jenkins, G.M., Reinsel, G.: Time Series Analysis: Forecasting & Control. Holden Day (1970)
Brandt, H., Dieckmann, U.: Correlation Analysis of Fitness Landscapes. Working papers, International Institute for Applied Systems Analysis (1999)
Chaitin, G.J.: Information, Randomness & Incompleteness. World Scientific, Singapore (1987)
Collard, P., Verel, S., Clergue, M.: Local search heuristics: Fitness Cloud versus Fitness Landscape. In: ECAI, pp. 973–974. IOS Press, Amsterdam (2004)
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)
Czech, Z.: Statistical measures of a fitness landscape for the vehicle routing problem. In: IPDPS, pp. 1–8 (2008)
Davidor, Y.: Epistasis variance: suitability of a representation to genetic algorithms. Complex Systems 4, 369–383 (1990)
Derrida, B.: Random energy model: Limit of a family of disordered models. Phys. Rev. Lett. 45, 79–82 (1980)
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)
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)
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)
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)
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)
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)
Gouvêa, F.Q.: p-adic Numbers: An Introduction. Springer, Heidelberg (1993)
Grefenstette, J.J.: Evolvability in Dynamic Fitness Landscapes: A Genetic Algorithm Approach. In: CEC, pp. 2031–2038 (1999)
Hastings, W.K.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57, 97–109 (1970)
Holland, J.H.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor (1975)
Holland, J.H.: Evolution, Learning and Cognition, pp. 111–127. World Scientific, Singapore (1988)
Hordijk, W.: A measure of landscapes. Evol. Comput. 4(4), 335–360 (1996)
Huynen, M.A.: Exploring phenotype space through neutral evolution. J. Mol. Evol. 43, 165–169 (1996)
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)
Jones, T.: Evolutionary Algorithms, Fitness Landscapes and Search. Ph.D. thesis, University of New Mexico, Albuquerque, New Mexico (1995)
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)
Kallel, L., Naudts, B., Schoenauer, M.: On functions with a given fitness-distance relation. In: CEC, vol. 3, pp. 1910–1916 (1999)
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)
Katada, Y., Ohkura, K., Ueda, K.: The Nei’s standard genetic distance in artificial evolution. In: CEC, pp. 1233–1239 (2004)
Kauffman, S.: Adaptation on rugged fitness landscapes. Lectures in the Sciences of Complexity, vol. 1, pp. 527–618. Addison-Wesley Longman, Amsterdam (1989)
Kauffman, S.A.: The Origins of Order. Oxford University Press, Oxford (1993)
Kimura, M.: Evolutionary Rate at the Molecular Level. Nature 217, 624–626 (1968)
Koopmans, T.C., Beckmann, M.: Assignment Problems and the Location of Economic Activities. Econometrica 25(1), 53–76 (1957)
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)
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)
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)
Lipsitch, M.: Adaptation on rugged landscapes generated by iterated local interactions of neighboring genes. In: ICGA, vol. 135, pp. 128–135 (1991)
Manderick, B., de Weger, M.K., Spiessens, P.: The Genetic Algorithm and the Structure of the Fitness Landscape. In: ICGA, pp. 143–150 (1991)
Marrow, P.: Evolvability: Evolution, Computation, Biology. In: GECCO, pp. 30–33 (1999)
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)
Mattfeld, D.C., Bierwirth, C.: A Search Space Analysis of the Job Shop Scheduling Problem. Ann. Oper. Res. 86, 441–453 (1996)
Merz, P.: Advanced fitness landscape analysis and the performance of memetic algorithms. Evol. Comput. 12(3), 303–325 (2004)
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)
Merz, P., Freisleben, B.: Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE T. Evolut. Comput. 4(4), 337–352 (2000)
Merz, P., Freisleben, B.: Memetic Algorithms for the Traveling Salesmen Problem. Complex Systems 13(4), 297–345 (2001)
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)
Moraglio, A., Poli, R.: Topological Crossover for the Permutation Representation. In: GECCO 2005, pp. 332–338 (2005)
Munkres, J.R.: Topology. Prentice-Hall, Englewood Cliffs (2000)
Naudts, B.: Measuring GA-hardness. Ph.D. thesis, University of Antwerp (June 1998)
Naudts, B., Kallel, L.: A Comparison of Predictive Measures of Problem Difficulty in Evolutionary Algorithms. IEEE T. Evolut. Comput. 4(1), 1–15 (2000)
Naudts, B., Verschoren, A.: Epistasis and Deceptivity. B Belg. Math. Soc-Sim 6(1), 147–154 (1999)
Nei, M.: Genetic distance between populations. Am. Nat. 106, 283–292 (1972)
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)
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)
Ohta, T.: The Nearly Neutral Theory of Molecular Evolution. Annu. Rev. Ecol. Syst. 23, 263–286 (1992)
Ohta, T.: The neutral theory is dead. The current significance and standing of neutral and nearly neutral theories. BioEssays 18(8), 673–677 (1996)
Ohta, T.: Evolution by nearly-neutral mutations. Genetica 102/103, 89–90 (1998)
Pitzer, E., Affenzeller, M., Beham, A.: A Closer Look Down the Basins of Attraction. In: UKCI, Colchester, UK, pp. 1–6 (2010)
Provine, W.B.: Sewall Wright and Evolutionary Biology. University of Chicago Press, Chicago (1989)
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)
Rechenberg, I.: Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog (1973)
Reeves, C.R., Rowe, J.E.: Genetic Algorithms—Principles and Perspectives. Kluwer, Dordrecht (2003)
Reeves, C.R., Wright, C.C.: Epistasis in Genetic Algorithms: An Experimental Design Perspective. In: ICGA, pp. 217–224. Morgan Kaufmann, San Francisco (1995)
Reidys, C.M., Stadler, P.F.: Neutrality in fitness landscapes. Appl. Math. Comput. 117(2-3), 321–350 (1998)
Reidys, C.M., Stadler, P.F.: Combinatorial Fitness Landscapes. SIAM Rev. 44, 3–54 (2002)
Rochet, S.: Epistasis in genetic algorithms revisited. Inform. Sciences 102(1-4), 133–155 (1997)
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)
Rockmore, D., Kostelec, P., Hordijk, W., Stadler, P.F.: Fast Fourier Transform for Fitness Landscapes. Appl. Comput. Harmon A 12(1), 57–76 (2002)
Saitou, N., Nei, M.: The Neighbor-joining Method: A New Method for Reconstructing Phylogenetic Trees. Mol. Biol. Evol. 4(4), 406–425 (1987)
Shannon, C.E.: A Mathematical Theory of Communication. AT&T Tech. J. 27, 379–423, 623–656 (1948)
Sherrington, D., Kirkpatrick, S.: Solvable model of a spin-glass. Phys. Rev. Lett. 35(26), 1792–1795 (1975)
Smith, T., Husbands, P., Layzell, P., O’Shea, M.: Fitness landscapes and evolvability. Evol. Comput. 10(1), 1–34 (2002)
Stadler, P., Wagner, G.: The Algebraic Theory of Recombination Spaces. Evol. Comput. 5, 241–275 (1998)
Stadler, P.F.: Linear Operators on Correlated Landscapes. J. Phys. I 4, 681–696 (1994)
Stadler, P.F.: Towards a Theory of Landscapes. Lecture Notes in Physics, vol. 461, pp. 78–163. Springer, Heidelberg (1995)
Stadler, P.F.: Landscapes and Their Correlation Functions. J. Math. Chem. 20, 1–45 (1996)
Stadler, P.F.: Fitness Landscapes. In: Biological Evolution and Statistical Physics, pp. 187–207. Springer, Heidelberg (2002)
Stadler, P.F., Happel, R.: Random field models for fitness landscapes. Working Papers 95-07-069, Santa Fe Institute, Santa Fe, NM (1995)
Stadler, P.F., Schnabl, W.: The Landscape of the Travelling Salesmand Problem. Phys. Lett. A 161, 337–344 (1992)
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)
Talbi, E.-G.: Metaheuristics: From Design to Implementation. Wiley, Chichester (2009)
Tavares, J., Pereira, F., Costa, E.: Multidimensional Knapsack Problem: A Fitness Landscape Analysis. IEEE T. Syst. Man Cy. B 38(3), 604–616 (2008)
Thompson, R.K., Wright, A.H.: Additively Decomposable Fitness Functions. Tech. rep., University of Montan, Computer Science Dept., Missoula, MT, USA (1996)
Turney, P.: Increasing evolvability considered as a large-scale trend in evolution. In: GECCO, pp. 43–46 (1999)
Uludağ, G., Uyar, A.Ş.: Fitness Landscape Analysis of Differential Evolution Algorithms. In: ICSCCW (2009)
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)
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)
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)
Vassilev, V.K., Fogarty, T.C., Miller, J.F.: Information Characteristics and the Structure of Landscapes. Evol. Comput. 8(1), 31–60 (2000)
Wagner, A.: Robustness, evolvability, and neutrality. FEBS Lett. 579, 1772–1778 (2005)
Wagner, A.: Robustness and evolvability: a paradox resolved. Proc. R Soc. B 275, 91–100 (2008)
Wagner, G., Stadler, P.: Complex Adaptations and the Structure of Recombination Spaces. In: Algebraic Engineering, pp. 96–115. World Scientific, Singapore (1998)
Wagner, G.P., Altenberg, L.: Complex Adaptations and the Evoluation of Evolvability. Evolution 50(3), 967–976 (1996)
Wang, S., Zhu, Q., Kang, L.: Landscape Properties and Hybrid Evolutionary Algorithm for Optimum Multiuser Detection Problem. In: ICCSA, pp. 340–347 (2006)
Weinberger, E.: Correlated and uncorrelated fitness landscapes and how to tell the difference. Biol. Cybern. 63(5), 325–336 (1990)
Weinberger, E.D.: Local properties of Kauffman’s N-k model, a tuneably rugged energy landscape. Phys. Rev. A 44(10), 6399–6413 (1991)
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)
Wright, S.: The Roles of Mutation, Inbreeding, Crossbreeding and Selection in Evolution. In: 6th International Congress of Genetics, vol. 1, pp. 356–366 (1932)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights 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)