Abstract
Landscapes whose fitness values change with time occur in several contexts. A first is that the evolutionary process takes place in a dynamic environment. Dynamics may be connected to optimization problems with changing objective functions, or generally that conditions apart from the genetic makeup of the population, but massively influencing the evolutionary outcome, are not constant. Mathematically, such dynamic fitness landscapes can be described either by static landscapes that are externally driven to change with time, or by spatially extended dynamical systems which internally and simultaneously define topology and dynamics of the landscape. Another setting for time-dependent fitness are coevolutionary processes where the fitness of a given individual depends on the fitness and the genotype of other individuals in a temporal or spatial fashion. This is known to create coupled, interactive, tunable or deformable landscapes. Such coevolutionary processes induce time-dependence that is population-based and produce landscapes that are codynamic. In this chapter we intend to give an unified overview about issues in and problems of time-dependent fitness landscapes and particularly highlight several types of mathematical descriptions and their properties, similarities and differences.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alba, E., Sarasola, B.: Measuring fitness degeneration in dynamic optimization problems. In: Di Chio, C., et al. (eds.) Applications of Evolutionary Computation - EvoApplications 2010, pp. 572–581. Springer, Berlin (2010)
Bäck, T.: Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, New York (1996)
Bascompte, J., Jordano, P.: Plant-animal mutualistic networks: the architecture of biodiversity. Annu. Rev. Ecol. Evol. Syst. 38, 567–593 (2007)
Bosman, P.A.N., La Poutré, H.: Computationally intelligent online dynamic vehicle routing by explicit load prediction in an evolutionary algorithm. In: Runarsson, T.P., Beyer, H.-G., Burke, E.K., Merelo-Guervós, J.J., Whitley, L.D., Yao, X. (eds.) PPSN 2006. LNCS, vol. 4193, pp. 312–321. Springer, Heidelberg (2006)
Bosman, P.A.N.: Learning and anticipation in online dynamic optimization. In: Yang, S., Ong, Y.S., Jin, Y. (eds.) Evolutionary Computation in Dynamic and Uncertain Environments, pp. 129–152. Springer, Heidelberg (2007)
Brabazon, A., Silva, A., de Sousa, T.F., O’Neill, M., Matthews, R., Costa, E.: A particle swarm model of organizational adaptation. In: Deb, K., Tari, Z. (eds.) GECCO 2004. LNCS, vol. 3102, pp. 12–23. Springer, Heidelberg (2004)
Branke, J.: Memory enhanced evolutionary algorithms for changing optimization problems. In: Angeline, P.J., Michalewicz, Z., Schoenauer, M., Yao, X., Zalzala, A. (eds.) Proc. Congress on Evolutionary Computation, IEEE CEC 1999, pp. 1875–1882. IEEE Press, Piscataway (1999)
Buckling, A., Rainey, P.B.: Antagonistic coevolution between a bacterium and a bacteriophage. Proc. R. Soc. Lond. B 269, 931–936 (2002)
Bull, L.: Coevolutionary species adaptation genetic algorithms: a continuing SAGA on coupled fitness landscapes. In: Capcarrère, M.S., Freitas, A.A., Bentley, P.J., Johnson, C.G., Timmis, J. (eds.) ECAL 2005. LNCS (LNAI), vol. 3630, pp. 322–331. Springer, Heidelberg (2005)
Chazottes, J.R., Fernandez, B.: Dynamics of Coupled Map Lattices and of Related Spatially Extended Systems. Springer, Heidelberg (2005)
Chellapilla, K., Fogel, D.B.: Evolving neural networks to play checkers without relying on expert knowledge. IEEE Trans. Neural Netw. 10, 1382–1391 (1999)
Cheng, H., Yang, S.: Multi-population genetic algorithms with immigrants scheme for dynamic shortest path routing problems in mobile ad hoc networks. In: Di Chio, C., et al. (eds.) EvoApplicatons 2010, Part I. LNCS, vol. 6024, pp. 562–571. Springer, Heidelberg (2010)
Cheng, H., Yang, S.: Genetic algorithms with immigrants schemes for dynamic multicast problems in mobile ad hoc networks. Engineering Applications of Artificial Intelligence 23, 806–819 (2010)
Crutchfield, J.P., Kaneko, K.: Phenomenology of spatiotemporal chaos. In: Hao, B. (ed.) Directions in Chaos, vol. 1, pp. 272–353. World Scientific, Singapore (1987)
Cruz, C., Gonzlez, J.R., Pelta, D.A.: Optimization in dynamic environments: a survey on problems, methods and measures. Soft Computing 15, 1427–1448 (2011)
de Jong, E.D., Polack, J.B.: Ideal evaluation from coevolution. Evolutionary Computation 12, 159–192 (2004)
Ebner, M., Watson, R.A., Alexander, J.: Co–evolutionary dynamics on a deformable landscape. In: Zalzala, A., Fonseca, C., Kim, J.H., Smith, A., Yao, X. (eds.) Proc. Congress on Evolutionary Computation, IEEE CEC 2000, pp. 1284–1291. IEEE Press, Piscataway (2000)
Ebner, M.: Coevolution and the red queen effect shape virtual plants. Genetic Programming and Evolvable Machines 7, 103–123 (2006)
Ebner, M., Watson, R.A., Alexander, J.: Coevolutionary dynamics of interacting species. In: Di Chio, C., et al. (eds.) EvoApplicatons 2010, Part I. LNCS, vol. 6024, pp. 1–10. Springer, Heidelberg (2010)
Goh, C.K., Tan, K.C.: A competitive–cooperative coevolutionary paradigm for dynamic multiobjective optimization. IEEE Trans. Evolut. Comp. 13, 103–127 (2009)
Hordijk, W., Kauffman, S.A.: Correlation analysis of coupled fitness landscapes. Complexity 10, 42–49 (2005)
Jansen, T., Wiegand, R.P.: The cooperative coevolutionary (1+1) EA. Evolutionary Computation 12, 405–434 (2004)
Jones, T.: Evolutionary algorithms, fitness landscape and search. PhD thesis, The University of New Mexico, Albuquerque (1995), http://www.santafe.edu/media/workingpapers/95-05-048.pdf (retrieved November 11, 2012)
Kallel, L., Naudts, B., Reeves, C.R.: Properties of fitness functions and search landscapes. In: Kallel, L., Naudts, B., Rogers, A. (eds.) Theoretical Aspects of Evolutionary Computing, pp. 177–208. Springer, Heidelberg (2001)
Kaneko, K.: The coupled map lattice. In: Kaneko, K. (ed.) Theory and Application of Coupled Map Lattices, pp. 1–49. John Wiley, Chichester (1993)
Kaneko, K., Tsuda, I.: Complex Systems: Chaos and Beyond. Springer, Heidelberg (2001)
Kardar, M., Parisi, G., Zhang, Y.C.: Dynamic scaling of growing interfaces. Phys. Rev. Lett. 56, 889–892 (1986)
Kashtan, N., Noor, E., Alon, U.: Varying environments can speed up evolution. Proc. Natl. Acad Sci USA (PNAS) 104, 13711–13716 (2007)
Katada, Y., Handa, Y.: Tracking the Red Queen effect by estimating features of competitive co–evolutionary fitness landscapes. In: Fogel, D.B. (ed.) Proc. Congress on Evolutionary Computation, IEEE CEC 2010, pp. 4417–4424. IEEE Press, Piscataway (2010)
Katzav, E., Cugliandolo, L.F.: From coupled map lattices to the stochastic Kardar–Parisi–Zhang equation. Physica A371, 96–99 (2006)
Kauffman, S.A., Levin, S.: Towards a general theory of adaptive walks on rugged landscapes. J. Theor. Biol 128, 11–45 (1987)
Kauffman, S.A.: The Origin of Order: Self–Organization and Selection in Evolution. Oxford University Press, New York (1993)
Kauffman, S.A., Weinberger, E.D.: The NK Model of rugged fitness landscapes and its application to the maturation of the immune response. J. Theor. Biol. 141, 211–245 (1989)
Kauffman, S.A., Johnsen, S.: Coevolution to the edge of chaos: Coupled fitness landscapes, poised states, and coevolutionary avalanches. J. Theor. Biol. 149, 467–505 (1991)
Lin, S.C., Goodman, E.D., Punch, W.F.: A genetic algorithm approach to dynamic job shop scheduling problems. In: Bäck, T. (ed.) Proc. Seventh International Conference on Genetic Algorithms, pp. 481–488. Morgan Kaufmann, San Francisco (1997)
Ma, K., Jianga, J., Yanga, C.B.: Scaling behavior of roughness in the two–dimensional Kardar–Parisi–Zhang growth. Physica 378, 194–200 (2007)
Mendes, R., Mohais, A.: DynDE: Differential Evolution for dynamic optimization problems. In: Corne, D. (ed.) Proc. Congress on Evolutionary Computation, IEEE CEC 2005, pp. 2808–2815. IEEE Press, Piscataway (2005)
Merz, P.: Advanced fitness landscape analysis and the performance of memetic algorithms. Evolutionary Computation 12, 303–325 (2004)
Meyers, L.A., Bull, J.J.: Fighting change with change: adaptive variation in an uncertain world. Trends in Ecology & Evolution 17, 551–557 (2002)
Miranda, V.G., Aarão Reis, F.D.A.: Numerical study of the Kardar–Parisi–Zhang equation. Phys. Rev. 77, 031134–1–6 (2008)
Morrison, R.W., De Jong, K.A.: A test problem generator for non–stationary environments. In: Angeline, P.J., Michalewicz, Z., Schoenauer, M., Yao, X., Zalzala, A. (eds.) Proc. Congress on Evolutionary Computation, IEEE CEC 1999, pp. 2047–2053. IEEE Press, Piscataway (1999)
Morrison, R.W., De Jong, K.A.: Triggered hypermutation revisited. In: Zalzala, A., et al. (eds.) Proc. Congress on Evolutionary Computation, IEEE CEC 2000, pp. 1025–1032. IEEE Press, Piscataway (2000)
Nguyen, T.T., Yao, X.: Benchmarking and solving dynamic constrained problems. In: Tyrrell, A. (ed.) Proc. Congress on Evolutionary Computation, IEEE CEC 2009, pp. 690–697. IEEE Press, Piscataway (2009)
Nguyen, T.T., Yang, S., Branke, J.: Evolutionary dynamic optimization: A survey of the state of the art. Swarm and Evolutionary Computation 6, 1–24 (2012)
Oliehoek, F.A., de Jong, E.D., Vlassis, N.A.: The parallel Nash memory for asymmetric games. In: Cattolico, M. (ed.) Proc. Genetic and Evolutionary Computation Conference, GECCO 2006, pp. 337–344. ACM Press, New York (2006)
Panait, L., Luke, S.: Time–dependent collaboration schemes for cooperative coevolutionary algorithms. In: Potter, M.A., Wiegand, R.P. (eds.) 2005 AAAI Fall Symposium on Coevolutionary and Coevolving Systems. AAAI Press, Palo Alto (2005)
Panait, L., Luke, S.: Selecting informative actions improves cooperative multiagent learning. In: Nakashima, H., Wellman, M.P., Weiss, G., Stone, P. (eds.) Proc. Fifth International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS 2006), pp. 760–766. ACM Press, New York (2006)
Panait, L., Luke, S., Harrison, J.: Archive–based cooperative coevolutionary algorithms. In: Cattolico, M. (ed.) Proc. Genetic and Evolutionary Computation Conference, GECCO 2006, pp. 345–352. ACM Press, New York (2006)
Popovici, E., Bucci, A., Wiegand, R.P., de Jong, E.D.: Coevolutionary principles. In: Rozenberg, G., Bäck, T., Kok, J.N. (eds.) Handbook of Natural Computing, pp. 987–1033. Springer, Heidelberg (2010)
Popovici, E., de Jong, K.A.: Understanding competitive co–evolutionary dynamics via fitness landscapes. In: Luke, S. (ed.) 2004 AAAI Fall Symposium on Artificial Multiagent Learning. AAAI Press, Palo Alto (2005)
Popovici, E., de Jong, K.A.: Understanding cooperative co–evolutionary dynamics via simple fitness landscapes. In: Beyer, H.G., O’Reilly, U.M. (eds.) Proc. Genetic and Evolutionary Computation Conference, GECCO 2005, pp. 507–514. Morgan Kaufmann, San Francisco (2005)
Popovici, E., de Jong, K.A.: The dynamics of the best individuals in co–evolution. Natural Computing 5, 229–255 (2006)
Potter, M.A., de Jong, K.A.: Cooperative coevolution: An architecture for evolving coadapted subcomponents. Evolutionary Computation 8, 1–29 (2000)
Prügel–Bennett, A., Tayarani–Najaran, M.H.: Maximum satisfiability: Anatomy of the fitness landscape for a hard combinatorial optimization problem. IEEE Trans. Evolut. Comp. 16, 319–338 (2012)
Richter, H.: Behavior of evolutionary algorithms in chaotically changing fitness landscapes. In: Yao, X., et al. (eds.) PPSN 2004. LNCS, vol. 3242, pp. 111–120. Springer, Heidelberg (2004)
Richter, H.: A study of dynamic severity in chaotic fitness landscapes. In: Corne, D. (ed.) Proc. Congress on Evolutionary Computation, IEEE CEC 2005, pp. 2824–2831. IEEE Press, Piscataway (2005)
Richter, H.: Evolutionary optimization in spatio–temporal fitness landscapes. In: Runarsson, T.P., Beyer, H.-G., Burke, E.K., Merelo-Guervós, J.J., Whitley, L.D., Yao, X. (eds.) PPSN 2006. LNCS, vol. 4193, pp. 1–10. Springer, Heidelberg (2006)
Richter, H.: Coupled map lattices as spatio–temporal fitness functions: Landscape measures and evolutionary optimization. Physica 237, 167–186 (2008)
Richter, H.: Evolutionary optimization and dynamic fitness landscapes: From reaction-diffusion systems to chaotic CML. In: Zelinka, I., Celikovsky, S., Richter, H., Chen, G. (eds.) Evolutionary Algorithms and Chaotic Systems. SCI, vol. 267, pp. 409–446. Springer, Heidelberg (2010)
Richter, H.: Memory design for constrained dynamic optimization problems. In: Di Chio, C., et al. (eds.) EvoApplicatons 2010, Part I. LNCS, vol. 6024, pp. 552–561. Springer, Heidelberg (2010)
Richter, H., Dietel, F.: Solving dynamic constrained optimization problems with asynchronous change pattern. In: Di Chio, C., et al. (eds.) EvoApplications 2011, Part I. LNCS, vol. 6624, pp. 334–343. Springer, Heidelberg (2011)
Richter, H., Yang, S.: Memory based on abstraction for dynamic fitness functions. In: Giacobini, M., et al. (eds.) EvoWorkshops 2008. LNCS, vol. 4974, pp. 596–605. Springer, Heidelberg (2008)
Richter, H., Yang, S.: Learning behavior in abstract memory schemes for dynamic optimization problems. Soft Computing 13, 1163–1173 (2009)
Rosin, C.D., Belew, R.K.: New methods for competitive coevolution. Evolutionary Computation 5, 1–29 (1997)
Simões, A., Costa, E.: Variable–size memory evolutionary algorithm to deal with dynamic environments. In: Giacobini, M., et al. (eds.) EvoWorkshops 2007. LNCS, vol. 4448, pp. 617–626. Springer, Heidelberg (2007)
Simões, A., Costa, E.: Evolutionary algorithms for dynamic environments: Prediction using linear regression and Markov chains. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN X 2008. LNCS, vol. 5199, pp. 306–315. Springer, Heidelberg (2008)
Smith, T., Husbands, P., Layzell, P., O’Shea, M.: Fitness landscapes and evolvability. Evolutionary Computation 10, 1–34 (2002)
Stadler, P.F., Stephens, C.R.: Landscapes and effective fitness. Comm. Theor. Biol. 8, 389–431 (2003)
Stadler, B.M.R., Stadler, P.F., Wagner, G.P., Fontana, W.: The topology of the possible: Formal spaces underlying patterns of evolutionary change. J. Theor. Biol. 213, 241–274 (2001)
Stanhope, S.A., Daida, J.M.: (1+1) Genetic algorithm fitness dynamics in a changing environment. In: Angeline, P.J., Michalewicz, Z., Schoenauer, M., Yao, X., Zalzala, A. (eds.) Proc. Congress on Evolutionary Computation, IEEE CEC 1999, pp. 1851–1858. IEEE Press, Piscataway (1999)
Tavares, J., Pereira, F.B., Costa, E.: Multidimensional knapsack problem: a fitness landscape analysis. IEEE Trans. Sys. Man Cyber. B 38, 604–616 (2008)
Tinós, R., Yang, S.: A self–organizing random immigrants genetic algorithm for dynamic optimization problems. Genetic Programming and Evolvable Machines 8, 255–286 (2007)
van Hemert, J., La Poutré, J.A.H.: Dynamic routing problems with fruitful regions: Models and evolutionary computation. In: Yao, X., et al. (eds.) PPSN VIII 2004. LNCS, vol. 3242, pp. 692–701. Springer, Heidelberg (2004)
Watson, R.A., Pollack, J.B.: Coevolutionary dynamics in a minimal substrate. In: Spector, L., Goodman, E.D., Wu, A., Langdon, W.B., Voigt, H.M., Gen, M., Sen, S., Dorigo, M., Pezeshk, S., Garzon, M.H., Burke, E. (eds.) Proc. Genetic and Evolutionary Computation Conference, GECCO 2001, pp. 702–709. Morgan Kaufmann, San Francisco (2001)
Weicker, K.: Performance measures for dynamic environments. In: Guervós, J.J.M., Adamidis, P.A., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) PPSN VII 2002. LNCS, vol. 2439, pp. 64–73. Springer, Heidelberg (2002)
Wilke, C.O., Martinetz, T.: Adaptive walks on time-dependent fitness landscapes. Phys. Rev. E60, 2154–2159 (1999)
Yang, S.: Non–stationary problem optimization using the primal-dual genetic algorithm. In: Sarker, R., Reynolds, R., Abbass, H., Tan, K.C., Essam, D., McKay, R., Gedeon, T. (eds.) Proc. Congress on Evolutionary Computation, IEEE CEC 2003, pp. 2246–2253. IEEE Press, Piscataway (2003)
Yang, S., Yao, X.: Experimental study on population-based incremental learning algorithms for dynamic optimization problems. Soft Computing 9, 815–834 (2005)
Yang, Z., Tang, K., Yao, X.: Large scale evolutionary optimization using cooperative coevolution. Information Science 178, 2985–2999 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Richter, H. (2014). Fitness Landscapes That Depend on Time. In: Richter, H., Engelbrecht, A. (eds) Recent Advances in the Theory and Application of Fitness Landscapes. Emergence, Complexity and Computation, vol 6. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41888-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-41888-4_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41887-7
Online ISBN: 978-3-642-41888-4
eBook Packages: EngineeringEngineering (R0)