Abstract
The field of evolutionary dynamic optimization is concerned with the study and application of evolutionary algorithms to dynamic optimization problems: a significant number of new algorithms have been proposed in recent years that are designed specifically to overcome the limitations faced by traditional algorithms in the dynamic domain. Subsequently, a wealth of empirical studies have been published that evaluate the performance of these algorithms on a variety of benchmark problems. However, very few theoretical results have been obtained during this time. This relative lack of theoretical findings makes it difficult to fully assess the strengths and weaknesses of the individual algorithms. In this chapter we provide a review of theoretical advances in evolutionary dynamic optimization. In particular, we argue the importance of theoretical results, highlight the challenges faced by theoreticians and summarise the work that has been done to date. We subsequently identify relevant directions for future research.
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
Auger, A., Doerr, B. (eds.): Theory of randomized search heuristics. World Scientific Publishing (2011)
Back, T.: Optimal mutation rates in genetic search. In: Forrest, S. (ed.) Proc. 5th Int. Conf. Genetic Algorithms, pp. 2–8. Morgan Kaufmann (1993)
Branke, J.: Evolutionary algorithms for dynamic optimization problems - a survey. Tech. Rep. 387, Insitute AIFB, University of Karlsruhe (1999)
Branke, J.: Evolutionary approaches to dynamic environments - updated survey. In: GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, pp. 27–30 (2001)
Branke, J.: Evolutionary Optimization in Dynamic Environments. Kluwer (2002)
Chen, T., Chen, Y., Tang, K., Chen, G., Yao, X.: The impact of mutation rate on the computation time of evolutionary dynamic optimization. arXiv preprint arXiv:1106.0566 (2011)
Chen, T., Lehre, P.K., Tang, K., Yao, X.: When is an estimation of distribution algorithm better than an evolutionary algorithm? In: Proc. 2009 IEEE Congr. Evol. Comput., pp. 1470–1477. IEEE (2009)
Cruz, C., González, J.R., Pelta, D.A.: Optimization in dynamic environments: a survey on problems, methods and measures. Soft Comput. 15(7), 1427–1448 (2011)
Doerr, B., Klein, C., Storch, T.: Faster evolutionary algorithms by superior graph representation. In: Proc. 1st IEEE Symp. Foundations of Comput. Intell., pp. 245–250 (2007)
Droste, S.: Analysis of the (1+1) ea for a dynamically changing objective function. Tech. rep., Universität Dortmund (2001)
Droste, S.: Analysis of the (1+1) ea for a dynamically changing onemax-variant. In: Proc. 2002 IEEE Congr. Evol. Comput., pp. 55–60 (2002)
Droste, S.: Analysis of the (1+1) ea for a dynamically bitwise changing onemax. In: Cantú-Paz, E., et al. (eds.) GECCO 2003. LNCS, vol. 2723, pp. 909–921. Springer, Heidelberg (2003)
Droste, S., Jansen, T., Wegener, I.: On the optimization of unimodal functions with the (1 + 1) evolutionary algorithm. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 13–22. Springer, Heidelberg (1998)
Droste, S., Jansen, T., Wegener, I.: A rigorous complexity analysis of the (1+1) evolutionary algorithm for linear functions with boolean inputs. Evol. Comput. 6(2), 185–196 (1998)
Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) Evolutionary Algorithm. Theoretical Computer Science 276, 51–81 (2002)
Droste, S., Jansen, T., Wegener, I.: Optimization with randomized search heuristics the (a)nfl theorem, realistic scenarios, and difficult functions. Theoretical Computer Science 287 (2002)
Droste, S., Jansen, T., Wegener, I.: Upper and lower bounds for randomized search heuristics in black-box optimization. Electronic Colloquium on Computational Complexity (ECCC) 48, 2003 (2004)
Friedrich, T., Hebbinghaus, N., Neumann, F., He, J., Witt, C.: Approximating covering problems by randomized search heuristics using multi-objective models. In: Proc. 9th Annual Conf. Genetic and Evol. Comput., pp. 797–804 (2007)
Friedrich, T., Oliveto, P.S., Sudholt, D., Witt, C.: Analysis of diversity-preserving mechanisms for global exploration. Evol. Comput. 17(4), 455–476 (2009)
Giel, O.: Zur analyse von randomisierten suchheuristiken und online-heuristiken. Ph.D. thesis, Universität Dortmund (2005)
Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimisation. Evol. Comput. 18(3), 335–356 (2010)
Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 415–426. Springer, Heidelberg (2003)
Jägersküpper, J.: Probabilistic analysis of evolution strategies using isotropic mutations. Ph.D. thesis, Universität Dortmund (2006)
Jansen, T., Schellbach, U.: Theoretical analysis of a mutation-based evolutionary algorithm for a tracking problem in lattice. In: Beyer, H.G.G. (ed.) Proc. 2005 Genetic and Evol. Comput. Conf., pp. 841–848. ACM (2005)
Jansen, T., Wegener, I.: Real royal road functions–where crossover provably is essential. Discrete Applied Mathematics 149(1-3), 111–125 (2005)
Jin, Y., Branke, J.: Evolutionary optimization in uncertain environment - a survey. IEEE Trans. Evol. Comput. 9(3), 303–317 (2005)
Kashtan, N., Noor, E., Alon, U.: Varying environments can speed up evolution. PNAS 104(34), 13,711–13,716 (2007)
Kratsch, S., Lehre, P.K., Neumann, F., Oliveto, P.S.: Fixed parameter evolutionary algorithms and maximum leaf spanning trees: A matter of mutation. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN XI. LNCS, vol. 6238, pp. 204–213. Springer, Heidelberg (2010)
Kratsch, S., Neumann, F.: Fixed-parameter evolutionary algorithms and the vertex cover problem. In: Proc. 2009 Genetic and Evol. Comput. Conf., pp. 293–300 (2009)
Leguizamon, G., Blum, C., Alba, E.: Handbook of approximation algorithms and metaheuristics, pp. 24.1–24.X. CRC Press (2007)
Lehre, P.K.: Negative drift in populations. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN XI. LNCS, vol. 6238, pp. 244–253. Springer, Heidelberg (2010)
Lehre, P.K., Witt, C.: Black-box search by unbiased variation. In: Proc. 12th Annual Conf. Genetic and Evol. Comput., pp. 1441–1448. ACM, New York (2010)
Lehre, P.K., Yao, X.: Runtime analysis of search heuristics on software engineering problems. Frontiers of Computer Science in China 3(1), 64–72 (2009)
Lehre, P.K., Yao, X.: Runtime analysis of the (1+1) EA on computing unique input output sequences. Inform. Sci. (2011)
Morrison, R.W.: Designing Evolutionary Algorithms for Dynamic Environments. Springer, Berlin (2004) ISBN 3-540-21231-0
Muhlenbein, H.: How genetic algorithms really work i: Mutation and hillclimbing. In: Manner, R., Manderick, B. (eds.) Proc. 2nd Int. Conf. Parallel Problem Solving from Nature, pp. 15–25 (1992)
Neumann, F.: Combinatorial optimization and the analysis of randomized search heuristics. Ph.D. Thesis, Christian-Albrechts-Universität zu Kiel (2006)
Neumann, F., Sudholt, D., Witt, C.: A few ants are enough: Aco with iteration-best update. In: Proc. 12th Annual Conf. Genetic and Evol. Comput., pp. 63–70. ACM (2010)
Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science 378(1), 32–40 (2007)
Neumann, F., Witt, C.: Runtime analysis of a simple ant colony optimization algorithm. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, pp. 618–627. Springer, Heidelberg (2006)
Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization. Natural Computation Series. Springer (2010)
Oliveto, P.S., He, J., Yao, X.: Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results. Int. J. of Automation and Computing 4(1), 100–106 (2007)
Oliveto, P.S., He, J., Yao, X.: Analysis of population-based evolutionary algorithms for the vertex cover problem. In: Proc. 2008 IEEE World Congr. Comput. Intell., pp. 1563–1570 (2008)
Reichel, J., Skutella, M.: Evolutionary algorithms and matroid optimization problems. Algorithmica 57(1), 187–206 (2010)
Ridley, M.: The Red Queen: Sex and the Evolution of Human Nature. Penguin Books Ltd. (1993)
Rohlfshagen, P., Lehre, P.K., Yao, X.: Dynamic evolutionary optimisation: An analysis of frequency and magnitude of change. In: Proc. 2009 Genetic and Evol. Comput. Conf., pp. 1713–1720 (2009)
Scharnow, J., Tinnefeld, K., Wegener, I.: Fitness landscapes based on sorting and shortest paths problems. In: Guervós, J.J.M., Adamidis, P.A., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) PPSN 2002. LNCS, vol. 2439, pp. 54–63. Springer, Heidelberg (2002)
Smith, J.M.: The Evolution of Sex. Cambridge University Press, Cambridge (1978)
Stanhope, S.A., Daida, J.M.: Optimal mutation and crossover rates for a genetic algorithm operating in a dynamic environment. In: Porto, V.W., Waagen, D. (eds.) EP 1998. LNCS, vol. 1447, pp. 693–702. Springer, Heidelberg (1998)
Stanhope, S.A., Daida, J.M. (1+1) genetic algorithm fitness dynamics in a changing environments. In: Proc. 1999 IEEE Congr. Evol. Comput., vol. 3, pp. 1851–1858 (1999)
Storch, T., Wegener, I.: Real royal road functions for constant population size. Theoretical Computer Science 320(1), 123–134 (2004)
Sudholt, D., Witt, C.: Runtime analysis of binary pso. In: GECCO 2008: Proc. 10th Annual Conf. Genetic and Evol. Comput., pp. 135–142. ACM, New York (2008)
Tinos, R., Yang, S.: Continuous dynamic problem generators for evolutionary algorithms. In: Proc. 2007 IEEE Congr. Evol. Comput., pp. 236–243 (2007)
Tinós, R., Yang, S.: An analysis of the XOR dynamic problem generator based on the dynamical system. In: Schaefer, R., Cotta, C., Kołodziej, J., Rudolph, G. (eds.) PPSN XI. LNCS, vol. 6238, pp. 274–283. Springer, Heidelberg (2010)
Wegener, I., Witt, C.: On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions. Journal of Discrete Algorithms 3(1), 61–78 (2005)
Weicker, K.: Evolutionary algorithms and dynamic optimization problems. Der Andere Verlag (2003)
Weicker, K.: Analysis of local operators applied to discrete tracking problems. Soft Comput. 9(11), 778–792 (2005)
Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 44–56. Springer, Heidelberg (2005)
Witt, C.: Population size versus runtime of a simple evolutionary algorithm. Theoretical Computer Science 403(1), 104–120 (2008)
Witt, C.: Why standard particle swarm optimisers elude a theoretical runtime analysis. In: Proc. 10th Int. Workshop Foundations of Genetic Algorithms, pp. 13–20. ACM, New York (2009)
Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1(1) (1997)
Yang, S.: Non-stationary problem optimization using the primal-dual genetic algorithms. In: Sarker, R., Reynolds, R., Abbass, H., Tan, K.C., McKay, R., Essam, D., Gedeon, T. (eds.) Proc. 2003 IEEE Congr. Evol. Comput., vol. 3, pp. 2246–2253 (2003)
Yang, S.: Memory-based immigrants for genetic algorithms in dynamic environments. In: Proc. 2005 Genetic and Evol. Comput. Conf., pp. 1115–1122. ACM (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rohlfshagen, P., Lehre, P.K., Yao, X. (2013). Theoretical Advances in Evolutionary Dynamic Optimization. In: Yang, S., Yao, X. (eds) Evolutionary Computation for Dynamic Optimization Problems. Studies in Computational Intelligence, vol 490. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38416-5_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-38416-5_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38415-8
Online ISBN: 978-3-642-38416-5
eBook Packages: EngineeringEngineering (R0)