Abstract
Fitness landscapes are a valuable concept in evolutionary biology, combinatorial optimization, and the physics of disordered systems. A fitness landscape is a mapping from a configuration space that is equipped with some notion of adjacency, nearness, distance or accessibility, into the real numbers. Landscape theory has emerged as an attempt to devise suitable mathematical structures for describing the “static” properties of landscapes as well as their influence on the dynamics of adaptation. This chapter gives a brief overview on recent developments in this area, focusing on “geometrical” properties of landscapes.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
S. Wright: “The roles of mutation, inbreeding, crossbreeeding and selection in evolution” in International Proceedings of the Sixth International Congress on Genetics, ed. by D.F. Jones, Vol. 1 (1932), pp. 356–366
K. Binder, A.P. Young: Rev. Mod. Phys. 58, 801–976 (1986)
M. Mézard, G. Parisi, M. Virasoro: Spin Glass Theory and Beyond (World Scientific, Singapore, 1987)
H.S. Chan, K.A. Dill: J. Chem. Phys. 95, 3775–3787 (1991)
K.A. Dill, S. Bromberg, K. Yue, K.M. Fiebig, D.P. Yeo, P.D. Thomas, H.S. Chan: Prot. Sci. 4, 561–602 (1995)
J.N. Onuchic, H. Nymeyer, A.E. Garcia, J. Chahine, N.D. Socci: Adv. Protein Chem. 53, 87–152 (2000)
C. Flamm, I.L. Hofacker, P.F. Stadler: Adv. Complex Syst. 2, 65–90 (1999)
C. Flamm, W. Fontana, I. Hofacker, P. Schuster: RNA 6, 325–338 (2000)
P.G. Mezey: Potential Energy Hypersurfaces (Elsevier, Amsterdam, 1987)
D. Heidrich, W. Kliesch, W. Quapp: Properties of Chemically Interesting Potential Energy Surfaces, Vol. 56 of Lecture Notes in Chemistry (Springer-Verlag, Berlin, 1991)
K. Kollman, J.H. Miller, S.E. Page: Amer. Pol. Sci. Rev. 86, 929–937 (1992)
B.M. Stadler: Adv. Complex Syst. 2, 101–116 (1999)
M. Garey, D. Johnson: Computers and Intractability. AGuide to the Theory of NP Completeness (Freeman, San Francisco, 1979)
I. Rechenberg: Evolutionstrategie (Frommann-Holzboog, Stuttgart, 1973)
J.R. Koza: Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press, Cambridge, MA, 1992)
J.H. Holland: Adaptation in Natural and Artificial Systems (MIT Press, Cambridge, MA, 1993)
S.A. Kauffman: The Origin of Order (Oxford University Press, New York, Oxford, 1993)
D.B. Fogel: Evolutionary Computation (IEEE Press, New York, 1995)
P. Schuster, W. Fontana, P.F. Stadler, I.L. Hofacker: Proc. Roy. Soc. Lond. B 255, 279–284 (1994)
A.S. Perelson, S.A. Kauffman (Eds.): Molecular Evolution on Rugged Landscapes: Proteins, RNA, and the Immune System (Addison-Wesley, Reading, MA, 1991) (1991)
H. Frauenfelder, A.R. Bishop, A. Garcia, A. Perelson, P. Schuster, D. Sherrington, P.J. Swart (Eds.): Landscape Paradigms in Physics and Biology: Concepts, Structures, and Dynamics (Elsevier, Amsterdam, 1997), special Issue of Phyica D vol. 107(2–4)
J.P. Crutchfield, P. Schuster (Eds.): Evolutionary Dynamics-Exploring the Interplay of Selection, Neutrality, Accident, and Function (Oxford Univ. Press, Oxford UK, 2000), to appear
J. Hofbauer, K. Sigmund: Dynamical Systems and the Theory of Evolution (Cambridge University Press, Cambridge U.K., 1988)
R. Bürger: The Mathematical Theory of Selection, Recombination, and Mutation (John Wiley & Sons, Chichester UK, 2000)
L. Altenberg, M.W. Feldman: Genetics 117, 559–572 (1987)
Y.I. Lyubich: Mathematical structures in population genetics (Springer-Verlag, Berlin, 1992)
J.W. Weibull: Evolutionary Game Dynamics (MIT Press, Cambridge MA, 1996)
A. Dress, D. Rumschitzki: Acta Appl. Math. 11, 103–111 (1988)
P.F. Stadler: J. Math. Chem. 20, 1–45 (1996)
J.S. Farris: “The logical basis of phylogenetic analysis” in Advances in Cladistics, ed. by N.I. Platnick, V.A. Funk (Columbia University Press, New York, 1983), pp. 1–36
J. Felsenstein: J. Mol. Evol. 17, 368–376 (1981)
L.R. Foulds, R.L. Graham: Adv. Appl. Math. 3, 43–49 (1982)
W.H.E. Day, D.S. Johnson, D. Sanko.: Math. Biosci. 81, 33–42 (1986)
D.F. Robinson: J. Combin. Theory B 11, 105–119 (1971)
M. Li, J. Tromp, L. Zhang: J. Theor. Biol. 182, 463–467(1996)
O. Bastert, D. Rockmore, P.F. Stadler, G. Tinhofer: (2000), “Landscapes on spaces of trees” submitted, SFI preprint 01-01-006
J. Kececioglu, D. Sanko.: Algorithmica 13, 180–210 (1995)
D. Sanko., G. Sundaram, J. Kececioglu: Internatl. J. Foundations Computer Sci. 7, 1–9 (1996)
J.C. Culberson: Evol. Comp. 2, 279–311 (1995)
T. Jones: (1995), “One operator, one landscape” Tech. Rep. #95-02-025, Santa Fe Institute
P. Gitcho., G.P. Wagner: Complexity 2, 47–43 (1996)
P.F. Stadler, G.P. Wagner: Evol. Comp. 5, 241–275 (1998)
G.P. Wagner, P.F. Stadler: “Complex adaptations and the structure of recombination spaces” in Algebraic Engineering, ed. by C. Nehaniv, M. Ito (World Scientific, Singapore, 1999), pp. 96–115, proceedings of the Conference on Semi-Groups and Algebraic Engineering, University of Aizu, Japan
P. Larrañaga, C.M.H. Kuijpers, R.H. Murga, I. Inza, S. Dizdarevic: Articial Intelligence Review 13, 129–170 (1999)
A. Brouwer, A. Cohen, A. Neumaier: Distance-regular Graphs (Springer Verlag, Berlin, New York, 1989)
M. Shpak, G.P. Wagner: Artificial Life 6, 25–43 (2000)
L. Lovasz: “Random walks on graphs: A survey” in Combinatorics, Paul Erdős is Eighty Vol.2 Budapest (1996), pp. 353–398, keszthely (Hungary) 1993
E.D. Weinberger: Biol. Cybern. 63, 325–336 (1990)
E.D. Weinberger: Biol. Cybern. 65, 321–330 (1991)
W. Hordijk: Evolutionary Computation 4(4), 335–360 (1996)
W. Hordijk: Physica D 107, 255–264 (1997)
P.F. Stadler, R. Seitz, G.P. Wagner: Bull. Math. Biol. 62, 399–428 (2000)
H.R. Fischer: Math. Annalen 137, 269–303 (1959)
D.C. Kent: Fund. Math. 54, 125–133 (1964)
E. Čech: Topological Spaces (Wiley, London, 1966)
D.C. Kent: Fund. Math. 62, 95–100 (1968)
B.M.R. Stadler, P.F. Stadler, W. Fontana, G.P. Wagner: J. Theor. Biol. (2001). Submitted, SFI preprint 00-12-070
B.M.R. Stadler, P.F. Stadler, M. Shpak, G.P. Wagner: Artificial Life (2001). Submitted, SFI preprint 01-02-011
R. Palmer: “Optimization on rugged landscapes” in Molecular Evolution on Rugged Landscapes: Proteins, RNA, and the Immune System, ed. by A.S. Perelson, S.A. Kauffman (Addison Wesley, Redwood City, CA, 1991), pp. 3–25
P.F. Stadler, W. Schnabl: Phys. Lett. A 161, 337–344 (1992)
P.F. Stadler, B. Krakhofer: Rev. Mex. Fis. 42, 355–363 (1996)
R. García-Pelayo, P.F. Stadler: Physica D 107, 240–254 (1997)
D.J. Thouless, P.W. Anderson, R.G. Palmer: Phil. Mag. 35, 593–601 (1977)
F. Tanaka, S.F. Edwards: J. Phys. F 10, 2769–2778 (1980)
A.J. Bray, M.A. Moore: J. Phys. C 14, 1313–1327 (1981)
D.J. Gross, M. Mézard: Nucl. Phys. B 240, 431–452 (1984)
B. Derrida, E. Gardner: J. Physique 47, 959–965 (1986)
H. Rieger: Phys. Rev. B 46, 14655–14661 (1992)
V.M. de Oliveira, J.F. Fontanari, P.F. Stadler: J. Phys. A: Math. Gen. 32, 8793–8802 (1999)
F.F. Ferreira, J.F. Fontanari, P.F. Stadler: J. Phys. A: Math. Gen. 33, 8635–8647 (2000)
J. Garnier, L. Kallel: SIAM J. Discr. Math. (2000). Submitted
E.D. Weinberger: Phys. Rev. A 44, 6399–6413 (1991)
W. Fontana, P.F. Stadler, E.G. Bornberg-Bauer, T. Griesmacher, I.L. Hofacker, M. Tacker, P. Tarazona, E.D. Weinberger, P. Schuster: Phys. Rev. E 47, 2083–2099 (1993)
J.H. Gillespie: Evolution 38, 1116–1129 (1984)
S.A. Kauffman, S. Levin: J. Theor. Biol. 128, 11–45 (1987)
H. Flyvbjerg, B. Lautrup: Phys. Rev. A 46, 6714–6723 (1992)
C.A. Macken, A.S. Perelson: Proc. Natl. Acad. Sci. USA 86, 6191–6195 (1989)
C.A. Macken, P.S. Hagan, A.S. Perelson: SIAM J. Appl. Math. 51, 799–827 (1991)
A.S. Perelson, C.A. Macken: Proc. Natl. Acad. Sci. USA 92, 9657–9661 (1995)
K.J. Niklas: Amer. J. Botany 84, 16–25 (1997)
R. Rammal, G. Toulouse, M.A. Virasoro: Rev. Mod. Phys. 58, 765–788 (1986)
A.M. Vertechi, M.A. Virasoro: J. Phys. France 50, 2325–2332 (1989)
S.R. Morgan, P.G. Higgs: J. Phys. A 31, 3153–3170 (1998)
C. Flamm, I.L. Hofacker, S. Maurer-Stroh, P.F. Stadler, M. Zehl: RNA 7, 254–265 (2001)
W. Kern: Discr. Appl. Math. 43, 115–129 (1993)
R. Azencott: Simulated Annealing (John Wiley & Sons, New York, 1992)
O. Catoni: Ann. Probab. 20, 1109–1146 (1992)
O. Catoni: “Simulated annealing algorithms and Markov chains with rate transitions” in Seminaire de Probabilites XXXIII, ed. by J. Azema, M. Emery, M. Ledoux, M. Yor (Springer, Berlin/Heidelberg, 1999), Vol. 709 of Lecture Notes in Mathematics, pp. 69–119
B. Hajek: Math. Operations Res. 13, 311–329 (1988)
J. Ryan: Discr. Appl. Math. 56, 75–82 (1995)
G.B. Sorkin: (1988), “Combinatorial optimization, simulated annealing, and fractals” Tech. Rep. RC13674 (No.61253), IBM Research Report
M. Eigen, J. McCaskill, P. Schuster: Adv. Chem. Phys. 75, 149–263 (1989)
P.F. Stadler: Discr. Math. 145, 229–238 (1995)
P. Schuster, P.F. Stadler: Computers & Chem. 18, 295–314 (1994)
P.F. Stadler, R. Happel: J. Math. Biol. 38, 435–478 (1999)
P.F. Stadler, W. Schnabl: Phys. Letters A 161, 337–344 (1992)
B. Krakhofer, P.F. Stadler: Europhys. Lett. 34, 85–90 (1996)
B. Mohar: “The Laplacian spectrum of graphs” in Graph Theory, Combinatorics, and Applications, ed. by Y. Alavi, G. Chartrand, O. Ollermann, A. Schwenk (John Wiley and Sons, Inc., New York, 1991), pp. 871–898
R. Merris: Lin. Alg. Appl. 39, 19–31 (1995)
F.R.K. Chung: Spectral Graph Theory, Vol. 92 of CBMS (American Mathematical Society, Providence RI, 1997)
B. Mohar: “Some applications of Laplace eigenvalues of graphs” in Graph Symmetry: Algebraic Methods and Applications, ed. by G. Hahn, G. Sabidussi (Kluwer, Dordrecht, 1997), Vol. 497 of NATO ASI Series C, pp. 227–275
D. Rockmore: “Some applications of generalized FFTs” in Groups and Computation II, ed. by L. Finkelstein, W. Kantor (American Mathmatical Society, Providence, RI, 1995), Vol. 28 of DIMACS, pp. 329–370
D. Rockmore, P. Kostelec, W. Hordijk, P.F. Stadler: Appl. Comput. Harmonic Anal. (2000). In press Santa Fe Institute preprint 99-10-068
T.J. Schaefer: “The complexity of satisfiability problems” in Proceedings of the 10th Annual ACM Symposium on Theory of Computing, ed. by N.N. (Association for Computing Machinery, New York, 1978), pp. 216–226
D.E. Goldberg: Complex Systems 3, 129–152 (1989)
D.E. Goldberg: Complex Systems 3, 153–176 (1989)
S.E. Page, D.E. Richardson: Complex Systems 6, 125–136 (1992)
M.D. Vose, A.H. Wright: Evol. Comp. 6, 253–274 (1998)
M.D. Vose, A.H. Wright: Evol. Comp. 6, 275–289 (1998)
L.K. Grover: Oper. Res. Lett. 12, 235–243 (1992)
B. Codenotti, L. Margara: (1992), “Local properties of some np-complete problems” Tech. Rep. TR 92-021, International Computer Science Institute, Berkeley, CA
E. Angel, V. Zissimopoulos: Discr. Appl. Math. 99, 261–277 (2000)
I. Chavel: Eigenvalues in Riemannian Geometry (Academic Press, Orlando Fl., 1984)
Y.C. de Verdière: Rendiconti di Matematica 13, 433–460 (1993)
J. Friedman: Duke Math. J. 69(3), 487–525 (1993)
H. van der Holst: (1996), “Topological and spectral graph characterizations” Ph.D. thesis, Universiteit van Amsterdam
A.M. Duval, V. Reiner: Lin. Alg. Appl. 294, 259–268 (1999)
E.B. Davies, G.M.L. Gladwell, J. Leydold, P.F. Stadler: Lin. Alg. Appl. (2001). In press, see also: math.SP/0009120
R. Happel, P.F. Stadler: Complexity 2, 53–58 (1996)
W. Hordijk, P.F. Stadler: J. Complex Systems 1, 39–66 (1998)
Y. Davidor: Complex Systems 4, 369–383 (1990)
M. Whitlock, P.C. Phillips, F.B.G. Moore, S. Tonsor: Ann. Review Ecol. Systematics 26, 601–629 (1995)
J.B. Wolf, E.D. Brodie III, M.J. Wade (Eds.): Epistasis and the Evolutionary Process (Oxford Univ. Press, Oxford, UK, 2000)
C.M. Reidys, P.F. Stadler: Appl. Math. & Comput. 117, 321–350 (2001)
C.M. Reidys: Adv. Appl. Math. 19, 360–377 (1997)
S. Gavrilets, J. Gravner: J. Theor. Biol. 184, 51–64 (1997)
C.M. Reidys, P.F. Stadler, P. Schuster: Bull. Math. Biol. 59, 339–397(1997 )
S. Gavrilets, H. Li, M.D. Vose: Proc. Roy. Soc. London B 265, 1483–1489 (1998)
S. Kopp, C.M. Reidys: Adv. Complex Syst. 2, 283–301 (1999)
P.F. Stadler: J. Mol. Struct. (THEOCHEM) 463, 7–19 (1999)
W. Fontana, D.A.M. Konings, P.F. Stadler, P. Schuster: Biopolymers 33, 1389–1404 (1993)
W. Fontana, P. Schuster: Science 280, 1451–1455 (1998)
D.E. Goldberg, M. Rudnik: Complex Systems 5, 265–278 (1991)
G.E. Liepins, M.D. Vose: Complex Systems 5, 45–61 (1991)
P. Field: Complex Systems 9, 11–28 (1995)
L. Altenberg: “The schema theorem and the Price’s theorem” in Foundations of Genetic Algorithms 3, ed. by L.D. Whitley, M.D. Vose (Morgan Kauffman, San Francisco CA, 1995), pp. 23–49
A.D. Bethke: (1991), “Genetic algorithms and function optimizers” Ph.D. thesis, University of Michigan
J.H. Holland: “Genetic algorithms and classifier systems: foundations and future directions” in Proceedings of the 2nd International Conference on Genetic Algorithms (1987), pp. 82–89
S. Forrest, M. Mitchell: “Relative building block fitness and the building block hypothesis” in Foundations of Genetic Algorithms 2, ed. by L.D. Whitley (Morgan Kaufmann, San Mateo, CA, 1993), pp. 109–126
C.R. Stephens, H. Waelbroeck: Phys. Rev. E 57, 3251–3264 (1998)
L.D. Whitley: “Fundamental principles of deception in genetic search” in Foundations of Genetic Algorithms, ed. by G. Rawlins (Morgan Kaufmann, San Mateo, CA, 1991), pp. 221–241
K. Deb, D.E. Goldberg: “Analyzing deception in trap functions” in Foundations of Genetic Algorithms 2, ed. by L.D. Whitley (Morgan Kaufmann, San Mateo, CA, 1993), pp. 93–108
P.F. Stadler: “Spectral landscape theory” in Evolutionary Dynamics-Exploring the Interplay of Selection, Neutrality, Accident, and Function, ed. by J.P. Crutchfield, P. Schuster (Oxford University Press, New York, 2001), in press
B. Naudts, L. Kallel: IEEE Trans. Evol. Comp. (2000). To appear
M. Mitchell: An Introduction to Genetic Algorithms (MIT Press, Cambridge MA, 1996)
D.F. T. Baeck, Z. Michalewicz (Eds.): Handbook of Evolutionary Computation (Oxford University Press, New York, 1997)
E. Angel, V. Zissimopoulos: Theor. Computer Sci. 191, 229–243 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Stadler, P.F. (2002). Fitness landscapes. In: Lässig, M., Valleriani, A. (eds) Biological Evolution and Statistical Physics. Lecture Notes in Physics, vol 585. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45692-9_10
Download citation
DOI: https://doi.org/10.1007/3-540-45692-9_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43188-6
Online ISBN: 978-3-540-45692-6
eBook Packages: Springer Book Archive