Optimizing Epochal Evolutionary Search: Population-Size Dependent Theory
Tóm tắt
Epochal dynamics, in which long periods of stasis in an evolving population are punctuated by a sudden burst of change, is a common behavior in both natural and artificial evolutionary processes. We analyze the population dynamics for a class of fitness functions that exhibit epochal behavior using a mathematical framework developed recently, which incorporates techniques from the fields of mathematical population genetics, molecular evolution theory, and statistical mechanics. Our analysis predicts the total number of fitness function evaluations to reach the global optimum as a function of mutation rate, population size, and the parameters specifying the fitness function. This allows us to determine the optimal evolutionary parameter settings for this class of fitness functions. We identify a generalized error threshold that smoothly bounds the two-dimensional regime of mutation rates and population sizes for which epochal evolutionary search operates most efficiently. Specifically, we analyze the dynamics of epoch destabilization under finite-population sampling fluctuations and show how the evolutionary parameters effectively introduce a coarse graining of the fitness function. More generally, we find that the optimal parameter settings for epochal evolutionary search correspond to behavioral regimes in which the consecutive epochs are marginally stable against the sampling fluctuations. Our results suggest that in order to achieve optimal search, one should set evolutionary parameters such that the coarse graining of the fitness function induced by the sampling fluctuations is just large enough to hide local optima.
Tài liệu tham khảo
Adami, C. (1995). Self-organized criticality in living systems. Phys. Lett. A 203, 29–32.
Alves, D. & J. F. Fontanari. (1998). Error thresholds in finite populations. Phys. Rev. E 57, 7008–7013.
Bäck, T. (1996). Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. New York, NY: Oxford University Press.
Barnett, L. (1997). Tangled webs: Evolutionary dynamics on fitness landscapes with neutrality. Master's thesis, School of Cognitive Sciences, University of East Sussex, Brighton. http://www.cogs.susx.ac.uk/ lab/adapt/nnbib.html.
Belew, R. K. & Booker, L. B. (Eds.) (1991). In Proceedings of the Fourth International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann.
Chambers, L. (Ed.) (1995). Practical Handbook of Genetic Algorithms. Boca Raton: CRC Press.
Crutchfield, J. P. & Mitchell, M. (1995). The evolution of emergent computation. Proc. Natl. Acad. Sci. U.S.A. 92, 10742–10746.
Crutchfield, J. P. & van Nimwegen, E. (1999). The evolutionary unfolding of complexity. In L. F. Landweber, E. Winfree, R. Lipton, & S. Freeland (Eds.), Evolution as Computation. SFI Working Paper 99-02-015; http://xxx.lanl.gov/abs/adap-org/9903001.
Davis, L. D. (Ed.). (1991). The Handbook of Genetic Algorithms. Van Nostrand Reinhold.
Eigen, M. (1971). Self-organization of matter and the evolution of biological macromolecules. Naturwissen., 58, 465–523.
Eigen, M., McCaskill, J., & Schuster, P. (1989). The molecular quasispecies. Adv. Chem. Phys., 75, 149–263.
Eigen, M. & Schuster, P. (1977). The hypercycle. a principle of natural self-organization. Part A: Emergence of the hypercycle Naturwissen., 64, 541–565.
Elena, S. F., Cooper, V. S., & Lenski, R. E. (1996). Punctuated evolution caused by selection of rare beneficial mutations. Science, 272, 1802–1804.
Eshelman, L. (Ed.) (1995). In Proceedings of the Sixth International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann.
Ewens, W. J. (1979). Mathematical Population Genetics (Vol. 9 of Biomathematics). Springer-Verlag, Berlin.
Fontana, W. & Schuster, P. (1998). Continuity in evolution: On the nature of transitions. Science, 280, 1451–1455.
Forrest, S. (Ed.) (1993). In Proceedings of the Fifth International Conference on Genetic Algorithms. San Mateo, CA: Morgan Kaufmann.
Gantmacher, F. R. (1959). Applications of the Theory of Matrices. New York: Interscience Publishers.
Gardiner, C. W. (1985). Handbook of Stochastic Methods. Springer-Verlag, Berlin.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley.
Gould, S. J. & Eldredge, N. (1977). Punctuated equilibria: The tempo and mode of evolution reconsidered. Paleobiology, 3, 115–251.
Hartl, D. L. & Clark, A. G. (1989). Principles of Population Genetics. (2nd edn.) Sunderland, MA: Sinauer Associates.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor, MI: The University of Michigan Press.
Huynen, M., Stadler, P. F., & Fontana, W. (1996). Smoothness within ruggedness: The role of neutrality in adaptation. Proc. Natl. Acad. Sci., 93, 397–401.
Huynen, M. A. (1995). Exploring phenotype space through neutral evolution. J. Mol. Evol., 43, 165–169.
Kauffman, S. (1993). The Origins of Order. Oxford University Press.
Kauffman, S. A. & Levin, S. (1987). Towards a general theory of adaptive walks in rugged fitness landscapes. J. Theo. Bio., 128, 11–45.
Kimura, M. (1964). Diffusion models in population genetics. J. Appl. Prob., 1, 177–232.
Kimura, M. (1983). The Neutral Theory of Molecular Evolution. Cambridge University Press.
Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA: MIT Press.
Leuthäusser, I. (1987). Statistical mechanics of Eigen's evolution model. J. Stat. Phys., 48, 343–360.
Macken, C. A. & Perelson, A. S. (1989). Protein evolution in rugged fitness landscapes. Proc. Nat. Acad. Sci., 86, 6191–6195.
Mitchell, M. (1996). An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press.
Mitchell, M., Crutchfield, J. P., & Hraber, P. T. (1994a). Evolving cellular automata to perform computations: Mechanisms and impediments. Physica D, 75, 361–391.
Mitchell, M., Holland, J. H., & Forrest, S. (1994b). When will a genetic algorithm outperform hill climbing? In J. D. Cowan, G. Tesauro, & J. Alspector (Eds.), Advances in Neural Information Processing Systems 6 (Vol. 6). San Mateo, CA: Morgan Kaufmann.
Newman, M. & Engelhardt, R. (1998). Effects of selective neutrality on the evolution of molecular species. Proc. R. Soc. London B., 265, 1333–1338.
Nowak, M. & Schuster, P. (1989). Error thresholds of replication in finite populations, mutation frequencies and the onset of Muller's ratchet. J. Theo. Bio., 137, 375–395.
Ohta, T. (1973). Slightly deleterious mutant substitutions in evolution. Nature, 247, 96–98.
Ohta, T. & Gillespie, J. H. (1996). Development of neutral and nearly neutral theories. Theo. Pop. Bio., 49, 128–142.
Pr¨ugel-Bennett, A. & Shapiro, J. L. (1994). Analysis of genetic algorithms using statistical mechanics. Phys. Rev. Lett., 72(9), 1305–1309.
Pr¨ugel-Bennett, A. & Shapiro, J. L. (1997). The dynamics of a genetic algorithm in simple random Ising systems. Physica D, 104(1), 75–114.
Rattray, M. & Shapiro, J. L. (1996). The dynamics of a genetic algorithm for a simple learning problem. J. Phys. A, 29(23), 7451–7473.
Reidys, C. M., Forst, C. V., & Schuster, P. K. (2001). Replication and mutation on neutral networks. Bull. Math. Bio., 63(1), 57–94.
Swetina, J. & Schuster, P. (1982). Self replicating with error, a model for polynucleotide replication. Biophys. Chem., 16, 329–340.
van Nimwegen, E. & Crutchfield, J. P. (2000). Optimizing epochal evolutionary search: Population-size independent theory. In D. Goldberg & K. Deb (Eds.), Computer Methods in Applied Mechanics and Engineering, special issue on Evolutionary and Genetic Algorithms in Computational Mechanics and Engineering, (Vol. 186), pp. 171–194.
van Nimwegen, E., Crutchfield, J. P., & Mitchell, M. (1997). Finite populations induce metastability in evolutionary search. Phys. Lett., A 229, 144–150.
van Nimwegen, E., Crutchfield, J. P., & Mitchell, M. (1999). Statistical dynamics of the Royal Road genetic algorithm. A. Eiben & G. Rudolph, (Eds.), Theoretical Computer Science, special issue on Evolutionary Computation, (Vol. 229), (pp. 41–102). SFI working paper 97-04-35.
Weber, J. (1996). Dynamics of neutral evolution. A case study on RNA secondary structures. Ph.D. Thesis, Biologisch-Pharmazeutischen Fakultät der Friedrich Schiller-Universität Jena.
Wolpert, D. H. & Macready,W. G. (1997). No free lunch theorems for optimization. IEEE Trans. Evol. Comp., 1, 67–82.
Wright, S. (1982). Character change, speciation, and the higher taxa. Evolution, 36, 427–43.