Fitness landscapes

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


Referenz

Stadler, P.F.: Fitness landscapes. In: Biological Evolution and Statistical Physics, pp. 183–204. Springer, Heidelberg (2002)

DOI

http://dx.doi.org/10.1007/3-540-45692-9_10

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.

Extended Abstract

Bibtex

@Inbook{Stadler2002,
author="Stadler, Peter F.",
editor="L{\"a}ssig, Michael and Valleriani, Angelo",
title="Fitness landscapes",
bookTitle="Biological Evolution and Statistical Physics",
year="2002",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="183--204",
isbn="978-3-540-45692-6",
doi="10.1007/3-540-45692-9_10",
url="http://dx.doi.org/10.1007/3-540-45692-9_10 http://de.evo-art.org/index.php?title=Fitness_landscapes"
}

Used References

1. 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

2. K. Binder, A.P. Young: Rev. Mod. Phys. 58, 801–976 (1986)CrossRef

3. M. Mézard, G. Parisi, M. Virasoro: Spin Glass Theory and Beyond (World Scientific, Singapore, 1987)

4. H.S. Chan, K.A. Dill: J. Chem. Phys. 95, 3775–3787 (1991)CrossRef

5. 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)CrossRef

6. J.N. Onuchic, H. Nymeyer, A.E. Garcia, J. Chahine, N.D. Socci: Adv. Protein Chem. 53, 87–152 (2000)PubMedCrossRef

7. C. Flamm, I.L. Hofacker, P.F. Stadler: Adv. Complex Syst. 2, 65–90 (1999)CrossRef

8. C. Flamm, W. Fontana, I. Hofacker, P. Schuster: RNA 6, 325–338 (2000)PubMedCrossRef

9. P.G. Mezey: Potential Energy Hypersurfaces (Elsevier, Amsterdam, 1987)

10. D. Heidrich, W. Kliesch, W. Quapp: Properties of Chemically Interesting Potential Energy Surfaces, Vol. 56 of Lecture Notes in Chemistry (Springer-Verlag, Berlin, 1991)

11. K. Kollman, J.H. Miller, S.E. Page: Amer. Pol. Sci. Rev. 86, 929–937 (1992)CrossRef

12. B.M. Stadler: Adv. Complex Syst. 2, 101–116 (1999)CrossRef

13. M. Garey, D. Johnson: Computers and Intractability. A Guide to the Theory of NP Completeness (Freeman, San Francisco, 1979)

14. I. Rechenberg: Evolutionstrategie (Frommann-Holzboog, Stuttgart, 1973)

15. J.R. Koza: Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press, Cambridge, MA, 1992)

16. J.H. Holland: Adaptation in Natural and Artificial Systems (MIT Press, Cambridge, MA, 1993)

17. S.A. Kauffman: The Origin of Order (Oxford University Press, New York, Oxford, 1993)

18. D.B. Fogel: Evolutionary Computation (IEEE Press, New York, 1995)

19. P. Schuster, W. Fontana, P.F. Stadler, I.L. Hofacker: Proc. Roy. Soc. Lond. B 255, 279–284 (1994)CrossRef

20. A.S. Perelson, S.A. Kauffman (Eds.): Molecular Evolution on Rugged Landscapes: Proteins, RNA, and the Immune System (Addison-Wesley, Reading, MA, 1991) (1991)

21. 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)

22. 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

23. J. Hofbauer, K. Sigmund: Dynamical Systems and the Theory of Evolution (Cambridge University Press, Cambridge U.K., 1988)

24. R. Bürger: The Mathematical Theory of Selection, Recombination, and Mutation (John Wiley & Sons, Chichester UK, 2000)

25. L. Altenberg, M.W. Feldman: Genetics 117, 559–572 (1987)PubMed

26. Y.I. Lyubich: Mathematical structures in population genetics (Springer-Verlag, Berlin, 1992)

27. J.W. Weibull: Evolutionary Game Dynamics (MIT Press, Cambridge MA, 1996)

28. A. Dress, D. Rumschitzki: Acta Appl. Math. 11, 103–111 (1988)CrossRef

29. P.F. Stadler: J. Math. Chem. 20, 1–45 (1996)CrossRef

30. 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

31. J. Felsenstein: J. Mol. Evol. 17, 368–376 (1981)PubMedCrossRef

32. L.R. Foulds, R.L. Graham: Adv. Appl. Math. 3, 43–49 (1982)CrossRef

33. W.H.E. Day, D.S. Johnson, D. Sanko.: Math. Biosci. 81, 33–42 (1986)CrossRef

34. D.F. Robinson: J. Combin. Theory B 11, 105–119 (1971)CrossRef

35. M. Li, J. Tromp, L. Zhang: J. Theor. Biol. 182, 463–467(1996)PubMedCrossRef

36. O. Bastert, D. Rockmore, P.F. Stadler, G. Tinhofer: (2000), “Landscapes on spaces of trees” submitted, SFI preprint 01-01-006

37. J. Kececioglu, D. Sanko.: Algorithmica 13, 180–210 (1995)CrossRef

38. D. Sanko., G. Sundaram, J. Kececioglu: Internatl. J. Foundations Computer Sci. 7, 1–9 (1996)CrossRef

39. J.C. Culberson: Evol. Comp. 2, 279–311 (1995)CrossRef

40. T. Jones: (1995), “One operator, one landscape” Tech. Rep. #95-02-025, Santa Fe Institute

41. P. Gitcho., G.P. Wagner: Complexity 2, 47–43 (1996)CrossRef

42. P.F. Stadler, G.P. Wagner: Evol. Comp. 5, 241–275 (1998)CrossRef

43. 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

44. P. Larrañaga, C.M.H. Kuijpers, R.H. Murga, I. Inza, S. Dizdarevic: Articial Intelligence Review 13, 129–170 (1999)CrossRef

45. A. Brouwer, A. Cohen, A. Neumaier: Distance-regular Graphs (Springer Verlag, Berlin, New York, 1989)

46. M. Shpak, G.P. Wagner: Artificial Life 6, 25–43 (2000)PubMedCrossRef

47. 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

48. E.D. Weinberger: Biol. Cybern. 63, 325–336 (1990)CrossRef

49. E.D. Weinberger: Biol. Cybern. 65, 321–330 (1991)CrossRef

50. W. Hordijk: Evolutionary Computation 4(4), 335–360 (1996)CrossRef

51. W. Hordijk: Physica D 107, 255–264 (1997)CrossRef

52. P.F. Stadler, R. Seitz, G.P. Wagner: Bull. Math. Biol. 62, 399–428 (2000)PubMedCrossRef

53. H.R. Fischer: Math. Annalen 137, 269–303 (1959)CrossRef

54. D.C. Kent: Fund. Math. 54, 125–133 (1964)

55. E. Čech: Topological Spaces (Wiley, London, 1966)

56. D.C. Kent: Fund. Math. 62, 95–100 (1968)

57. B.M.R. Stadler, P.F. Stadler, W. Fontana, G.P. Wagner: J. Theor. Biol. (2001). Submitted, SFI preprint 00-12-070

58. B.M.R. Stadler, P.F. Stadler, M. Shpak, G.P. Wagner: Artificial Life (2001). Submitted, SFI preprint 01-02-011

59. 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

60. P.F. Stadler, W. Schnabl: Phys. Lett. A 161, 337–344 (1992)CrossRef

61. P.F. Stadler, B. Krakhofer: Rev. Mex. Fis. 42, 355–363 (1996)

62. R. García-Pelayo, P.F. Stadler: Physica D 107, 240–254 (1997)CrossRef

63. D.J. Thouless, P.W. Anderson, R.G. Palmer: Phil. Mag. 35, 593–601 (1977)CrossRef

64. F. Tanaka, S.F. Edwards: J. Phys. F 10, 2769–2778 (1980)CrossRef

65. A.J. Bray, M.A. Moore: J. Phys. C 14, 1313–1327 (1981)CrossRef

66. D.J. Gross, M. Mézard: Nucl. Phys. B 240, 431–452 (1984)CrossRef

67. B. Derrida, E. Gardner: J. Physique 47, 959–965 (1986)CrossRef

68. H. Rieger: Phys. Rev. B 46, 14655–14661 (1992)

69. V.M. de Oliveira, J.F. Fontanari, P.F. Stadler: J. Phys. A: Math. Gen. 32, 8793–8802 (1999)CrossRef

70. F.F. Ferreira, J.F. Fontanari, P.F. Stadler: J. Phys. A: Math. Gen. 33, 8635–8647 (2000)CrossRef

71. J. Garnier, L. Kallel: SIAM J. Discr. Math. (2000). Submitted

72. E.D. Weinberger: Phys. Rev. A 44, 6399–6413 (1991)PubMedCrossRef

73. 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)CrossRef

74. J.H. Gillespie: Evolution 38, 1116–1129 (1984)CrossRef

75. S.A. Kauffman, S. Levin: J. Theor. Biol. 128, 11–45 (1987)PubMedCrossRef

76. H. Flyvbjerg, B. Lautrup: Phys. Rev. A 46, 6714–6723 (1992)PubMedCrossRef

77. C.A. Macken, A.S. Perelson: Proc. Natl. Acad. Sci. USA 86, 6191–6195 (1989)PubMedCrossRef

78. C.A. Macken, P.S. Hagan, A.S. Perelson: SIAM J. Appl. Math. 51, 799–827 (1991)CrossRef

79. A.S. Perelson, C.A. Macken: Proc. Natl. Acad. Sci. USA 92, 9657–9661 (1995)PubMedCrossRef

80. K.J. Niklas: Amer. J. Botany 84, 16–25 (1997)CrossRef

81. R. Rammal, G. Toulouse, M.A. Virasoro: Rev. Mod. Phys. 58, 765–788 (1986)CrossRef

82. A.M. Vertechi, M.A. Virasoro: J. Phys. France 50, 2325–2332 (1989)

83. S.R. Morgan, P.G. Higgs: J. Phys. A 31, 3153–3170 (1998)CrossRef

84. C. Flamm, I.L. Hofacker, S. Maurer-Stroh, P.F. Stadler, M. Zehl: RNA 7, 254–265 (2001)PubMedCrossRef

85. W. Kern: Discr. Appl. Math. 43, 115–129 (1993)CrossRef

86. R. Azencott: Simulated Annealing (John Wiley & Sons, New York, 1992)

87. O. Catoni: Ann. Probab. 20, 1109–1146 (1992)CrossRef

88. 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

89. B. Hajek: Math. Operations Res. 13, 311–329 (1988)CrossRef

90. J. Ryan: Discr. Appl. Math. 56, 75–82 (1995)CrossRef

91. G.B. Sorkin: (1988), “Combinatorial optimization, simulated annealing, and fractals” Tech. Rep. RC13674 (No.61253), IBM Research Report

92. M. Eigen, J. McCaskill, P. Schuster: Adv. Chem. Phys. 75, 149–263 (1989)CrossRef

93. P.F. Stadler: Discr. Math. 145, 229–238 (1995)CrossRef

94. P. Schuster, P.F. Stadler: Computers & Chem. 18, 295–314 (1994)CrossRef

95. P.F. Stadler, R. Happel: J. Math. Biol. 38, 435–478 (1999)CrossRef

96. P.F. Stadler, W. Schnabl: Phys. Letters A 161, 337–344 (1992)CrossRef

97. B. Krakhofer, P.F. Stadler: Europhys. Lett. 34, 85–90 (1996)CrossRef

98. 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

99. R. Merris: Lin. Alg. Appl. 39, 19–31 (1995)

100. F.R.K. Chung: Spectral Graph Theory, Vol. 92 of CBMS (American Mathematical Society, Providence RI, 1997)

101. 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

102. 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

103. D. Rockmore, P. Kostelec, W. Hordijk, P.F. Stadler: Appl. Comput. Harmonic Anal. (2000). In press Santa Fe Institute preprint 99-10-068

104. 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

105. D.E. Goldberg: Complex Systems 3, 129–152 (1989)

106. D.E. Goldberg: Complex Systems 3, 153–176 (1989)

107. S.E. Page, D.E. Richardson: Complex Systems 6, 125–136 (1992)

108. M.D. Vose, A.H. Wright: Evol. Comp. 6, 253–274 (1998)CrossRef

109. M.D. Vose, A.H. Wright: Evol. Comp. 6, 275–289 (1998)CrossRef

110. L.K. Grover: Oper. Res. Lett. 12, 235–243 (1992)CrossRef

111. B. Codenotti, L. Margara: (1992), “Local properties of some np-complete problems” Tech. Rep. TR 92-021, International Computer Science Institute, Berkeley, CA

112. E. Angel, V. Zissimopoulos: Discr. Appl. Math. 99, 261–277 (2000)CrossRef

113. I. Chavel: Eigenvalues in Riemannian Geometry (Academic Press, Orlando Fl., 1984)

114. Y.C. de Verdière: Rendiconti di Matematica 13, 433–460 (1993)

115. J. Friedman: Duke Math. J. 69(3), 487–525 (1993)CrossRef

116. H. van der Holst: (1996), “Topological and spectral graph characterizations” Ph.D. thesis, Universiteit van Amsterdam

117. A.M. Duval, V. Reiner: Lin. Alg. Appl. 294, 259–268 (1999)CrossRef

118. E.B. Davies, G.M.L. Gladwell, J. Leydold, P.F. Stadler: Lin. Alg. Appl. (2001). In press, see also: math.SP/0009120

119. R. Happel, P.F. Stadler: Complexity 2, 53–58 (1996)CrossRef

120. W. Hordijk, P.F. Stadler: J. Complex Systems 1, 39–66 (1998)CrossRef

121. Y. Davidor: Complex Systems 4, 369–383 (1990)

122. M. Whitlock, P.C. Phillips, F.B.G. Moore, S. Tonsor: Ann. Review Ecol. Systematics 26, 601–629 (1995)CrossRef

123. J.B. Wolf, E.D. Brodie III, M.J. Wade (Eds.): Epistasis and the Evolutionary Process (Oxford Univ. Press, Oxford, UK, 2000)

124. C.M. Reidys, P.F. Stadler: Appl. Math. & Comput. 117, 321–350 (2001)CrossRef

125. C.M. Reidys: Adv. Appl. Math. 19, 360–377 (1997)CrossRef

126. S. Gavrilets, J. Gravner: J. Theor. Biol. 184, 51–64 (1997)PubMedCrossRef

127. C.M. Reidys, P.F. Stadler, P. Schuster: Bull. Math. Biol. 59, 339–397(1997 )PubMedCrossRef

128. S. Gavrilets, H. Li, M.D. Vose: Proc. Roy. Soc. London B 265, 1483–1489 (1998)CrossRef

129. S. Kopp, C.M. Reidys: Adv. Complex Syst. 2, 283–301 (1999)CrossRef

130. P.F. Stadler: J. Mol. Struct. (THEOCHEM) 463, 7–19 (1999)CrossRef

131. W. Fontana, D.A.M. Konings, P.F. Stadler, P. Schuster: Biopolymers 33, 1389–1404 (1993)PubMedCrossRef

132. W. Fontana, P. Schuster: Science 280, 1451–1455 (1998)PubMedCrossRef

133. D.E. Goldberg, M. Rudnik: Complex Systems 5, 265–278 (1991)

134. G.E. Liepins, M.D. Vose: Complex Systems 5, 45–61 (1991)

135. P. Field: Complex Systems 9, 11–28 (1995)

136. 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

137. A.D. Bethke: (1991), “Genetic algorithms and function optimizers” Ph.D. thesis, University of Michigan

138. 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

139. 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

140. C.R. Stephens, H. Waelbroeck: Phys. Rev. E 57, 3251–3264 (1998)CrossRef

141. 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

142. 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

143. 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

144. B. Naudts, L. Kallel: IEEE Trans. Evol. Comp. (2000). To appear

145. M. Mitchell: An Introduction to Genetic Algorithms (MIT Press, Cambridge MA, 1996)

146. D.F. T. Baeck, Z. Michalewicz (Eds.): Handbook of Evolutionary Computation (Oxford University Press, New York, 1997)

147. E. Angel, V. Zissimopoulos: Theor. Computer Sci. 191, 229–243 (1998)CrossRef

Links

Full Text

https://www.bioinf.uni-leipzig.de/~studla/Publications/PREPRINTS/01-pfs-004.pdf

internal file


Sonstige Links

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.5364

Abgerufen von „http://de.evo-art.org/index.php?title=Fitness_landscapes&oldid=32625“