Abstract
In the last two decades, dynamic optimization problems (DOPs) have drawn a lot of research studies from the evolutionary computation (EC) community due to the importance in real-world applications. A variety of evolutionary computation approaches have been developed to address DOPs. In parallel with developing new approaches, many benchmark and real-world DOPs have been constructed and used to compare them under different performance measures. In this chapter, we describe the concept of DOPs and review existing dynamic test problems that are commonly used by researchers to investigate their EC approaches in the literature. Some discussions regarding the major features of existing dynamic test environments are presented. Typical dynamic benchmark problems and real-world DOPs are described in detail. We also review the performance measures that are widely used by researchers to evaluate and compare their developed EC approaches for DOPs. Suggestions are also given for potential improvement regarding dynamic test and evaluation environments for the EC community.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Knapsack Problem
- Dynamic Optimization
- Evaluation Environment
- Dynamic Optimization Problem
- System Control Parameter
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., Saucedo Badia, J., Luque, G.: A study of canonical gas for nsops. In: Doerner, et al. (eds.) Metaheuristics. Operations Research/Computer Science Interfaces Series, vol. 39, pp. 245–260. Springer (2007)
Alba, E., Sarasola, B.: Measuring fitness degradation in dynamic optimization problems. In: Di Chio, C., et al. (eds.) EvoApplicatons 2010, Part I. LNCS, vol. 6024, pp. 572–581. Springer, Heidelberg (2010)
Alba, E., Sarasola, B.: Abc, a new performance tool for algorithms solving dynamic optimization problems. In: Proc. 2010 IEEE World Congr. on Comput. Intell. (WCCI 2010), pp. 734–740 (2010)
Aragón, V.S., Esquivel, S.C.: An evolutionary algorithm to track changes of optimum value locations in dynamic environments. J. of Comp. Sci. and Tech. 4(3), 127–134 (2004)
Bäck, T.: On the behavior of evolutionary algorithms in dynamic environments. In: Proc. 1998 IEEE Int. Conf. Evol. Comput., pp. 446–451 (1998)
Bird, S., Li, X.: Informative performance metrics for dynamic optimisation problems. In: Proc. 9th Annual Conf. on Genetic and Evol. Comput., pp. 18–25 (2007)
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. SCI, vol. 51, pp. 129–152. Springer, Heidelberg (2007)
Bosman, P.A.N., Poutré, H.L.: Learning and anticipation in online dynamic optimization with evolutionary algorithms: the stochastic case. In: Proc. 9th Annual Conf. on Genetic and Evol. Comput., pp. 1165–1172 (2007)
Branke, J.: Memory enhanced evolutionary algorithms for changing optimization problems. In: Proc. 1999 IEEE Congr. Evol. Comput., pp. 1875–1882 (1999)
Branke, J.: Evolutionary approaches to dynamic environments - updated survey. In: Proc. 2001 GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, pp. 27–30 (2001)
Branke, J.: Evolutionary Optimization in Dynamic Environments. Kluwer Academic Publishers (2002)
Branke, J., Schmeck, H.: Designing evolutionary algorithms for dynamic optimization problems. In: Tsutsui, S., Ghosh, A. (eds.) Theory and Application of Evolutionary Computation: Recent Trends, pp. 239–262. Springer (2003)
Branke, J., Kaußler, T., Schmidth, C., Schmeck, H.: A multi-population approach to dynamic optimization problems. In: Proc. 4th Int. Conf. Adaptive Comput. Des. Manuf., pp. 299–308 (2000)
Branke, J., Orbayı, M., Uyar, Ş.: The role of representations in dynamic knapsack problems. In: Rothlauf, F., et al. (eds.) EvoWorkshops 2006. LNCS, vol. 3907, pp. 764–775. Springer, Heidelberg (2006)
Chazottes, J., Fernandez, B.: Dynamics of Coupled Map Lattices and of Related Spatially Extended Systems. Springer, Heidelberg (2005)
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. Engg. Appl. of Artif. Intell. 23(5), 806–819 (2010)
Cobb, H.G.: An investigation into the use of hypermutation as an adaptive operator in genetic algorithms having continuouis, time-dependent nonstationary environments. Technical Report AIC-90-001, Naval Research Laboratory, Washington, USA (1990)
Cobb, H.G., Grefenstette, J.J.: Genetic algorithms for tracking changing environments. In: Proc. 5th Int. Conf. Genetic Algorithms, pp. 523–530 (1993)
Cruz, C., Gonzalez, J.R., Pelta, D.A.: Optimization in dynamic environments: A survey on problems, methods and measures. Soft Comput. 15(7), 1427–1448 (2011)
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)
Eberhart, R.C., Kennedy, J.: A new optimizer using particle swarm theory. In: Proc. 6th Int. Symp. on Micro Machine and Human Science, pp. 39–43 (1995)
Farina, M., Deb, K., Amato, P.: Dynamic multiobjective optimization problems: test cases, approximations, and applications. IEEE Trans. Evol. Comput. 8(5), 425–442 (2004)
Feng, W., Brune, T., Chan, L., Chowdhury, M., Kuek, C., Li, Y.: Benchmarks for testing evolutionary algorithms. Technical Report, Center for System and Control, University of Glasgow (1997)
Gaspar, A., Collard, P.: From gas to artificial immune systems: Improving adaptation in time dependent optimization. In: Proc. 1999 IEEE Congr. Evol. Comput., vol. 3, pp. 1859–1866 (1999)
Goh, C.K., Tan, K.C.: A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization. IEEE Trans. Evol. Comput. 13(1), 103–127 (2009)
Grefenstette, J.J.: Genetic algorithms for changing environments. In: Proc. 2nd Int. Conf. Parallel Problem Solving from Nature, pp. 137–144 (1992)
Grefenstette, J.J.: Evolvability in dynamic fitness landscapes: a genetic algorithm approach. In: Proc. 1999 IEEE Congr. Evol. Comput., vol. 3, pp. 2031–2038 (1999)
Hatzakis, I., Wallace, D.: Dynamic multi-objective optimization with evolutionary algorithms: a forward-looking approach. In: Proc. 8th Annual Conf. on Genetic and Evol. Comput., pp. 1201–1208 (2006)
Jin, Y., Branke, J.: Evolutionary optimization in uncertain environments – a survey. IEEE Trans. Evol. Comput. 9(3), 303–317 (2005)
Jin, Y., Sendhoff, B.: Constructing dynamic optimization test problems using the multi-objective optimization concept. In: Raidl, G.R., et al. (eds.) EvoWorkshops 2004. LNCS, vol. 3005, pp. 525–536. Springer, Heidelberg (2004)
Kellerer, K., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer (2004)
Kennedy, J., Eberhart, R.C.: Particle swarm optimization. In: Proc. 1995 IEEE Int. Conf. on Neural Networks, pp. 1942–1948 (1995)
Lewis, J., Hart, E., Ritchie, G.: A comparison of dominance mechanisms and simple mutation on non-stationary problems. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) PPSN 1998. LNCS, vol. 1498, pp. 139–148. Springer, Heidelberg (1998)
Li, C., Yang, M., Kang, L.: A new approach to solving dynamic traveling salesman problems. In: Wang, T.-D., Li, X., Chen, S.-H., Wang, X., Abbass, H.A., Iba, H., Chen, G.-L., Yao, X. (eds.) SEAL 2006. LNCS, vol. 4247, pp. 236–243. Springer, Heidelberg (2006)
Li, C., Yang, S.: A generalized approach to construct benchmark problems for dynamic optimization. In: Li, X., et al. (eds.) SEAL 2008. LNCS, vol. 5361, pp. 391–400. Springer, Heidelberg (2008)
Li, C., Yang, S., Nguyen, T.T., Yu, E.L., Yao, X., Jin, Y., Beyer, H.-G., Suganthan, P.N.: Benchmark generator for CEC 2009 competition on dynamic optimization. Technical Report 2008, Department of Computer Science, University of Leicester, U.K. (2008)
Li, X., Branke, J., Kirley, M.: On performance metrics and particle swarm methods for dynamic multiobjective optimization problems. In: Proc. 2007 IEEE Congr. Evol. Comput., pp. 576–583 (2007)
Liang, J.J., Suganthan, P.N., Deb, K.: Novel composition test functions for numerical global optimization. In: Proc. 2005 IEEE Congr. Evol. Comput., pp. 68–75 (2005)
Mavrovouniotis, M., Yang, S.: A memetic ant colony optimization algorithm for the dynamic traveling salesman problem. Soft Comput. 15(7), 1405–1425 (2011)
Mavrovouniotis, M., Yang, S.: Memory-based immigrants for ant colony optimization in changing environments. In: Di Chio, C., et al. (eds.) EvoApplications 2011, Part I. LNCS, vol. 6624, pp. 324–333. Springer, Heidelberg (2011)
Mei, Y., Tang, K., Yao, X.: Capacitated arc routing problem in uncertain environments. In: Proc. 2010 IEEE Congr. Evol. Comput., pp. 1400–1407 (2010)
Mori, N., Imanishi, S., Kita, H., Nishikawa, Y.: Adaptation to changing environments by means of the memory based thermodynamical genetic algorithm. In: Proc. 1997 Int. Conf. on Genetic Algorithms, pp. 299–306 (1997)
Morrison, R.W., De Jong, K.A.: A test problem generator for non-stationary environments. In: Proc. 1999 IEEE Congr. Evol. Comput., pp. 2047–2053 (1999)
Morrison, R.W., De Jong, K.A.: Triggered hypermutation revisited. In: Proc. 2000 IEEE Congr. Evol. Comput., pp. 1025–1032 (2000)
Morrison, R.W., De Jong, K.A.: Measurement of population diversity. In: Collet, P., Fonlupt, C., Hao, J.-K., Lutton, E., Schoenauer, M. (eds.) EA 2001. LNCS, vol. 2310, pp. 31–41. Springer, Heidelberg (2002)
Morrison, R.W.: Performance measurement in dynamic environments. In: Proc. 2003 GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, pp. 5–8 (2003)
Morrison, R.W.: Designing Evolutionary Algorithms for Dynamic Environments. Springer, Berlin (2004)
Ng, K.P., Wong, K.C.: A new diploid scheme and dominance change mechanism for non-stationary function optimization. In: Proc. 6th Int. Conf. on Genetic Algorithms, pp. 159–166 (1995)
Nguyen, T.T.: A proposed real-valued dynamic constrained benchmark set. Technical report, School of Computer Science, Univesity of Birmingham (2008)
Nguyen, T.T.: Continuous Dynamic Optimisation Using Evolutionary Algorithms. PhD thesis, School of Computer Science, University of Birmingham (January 2011), http://etheses.bham.ac.uk/1296 and http://www.staff.ljmu.ac.uk/enrtngu1/theses/phd_thesis_nguyen.pdf
Nguyen, T.T., Yao, X.: Dynamic time-linkage problems revisited. In: Giacobini, M., et al. (eds.) EvoWorkshops 2009. LNCS, vol. 5484, pp. 735–744. Springer, Heidelberg (2009)
Nguyen, T.T., Yao, X.: Benchmarking and solving dynamic constrained problems. In: Proc. 2009 IEEE Congr. Evol. Comput., pp. 690–697 (2009)
Oppacher, F., Wineberg, M.: The shifting balance genetic algorithm: Improving the ga in a dynamic environment. In: Proc. 1999 Genetic and Evol. Comput. Conf., vol. 1, pp. 504–510 (1999)
Parrott, D., Li, X.: Locating and tracking multiple dynamic optima by a particle swarm model using speciation. IEEE Trans. Evol. Comput. 10(4), 440–458 (2006)
Rand, W., Riolo, R.: Measurements for understanding the behavior of the genetic algorithm in dynamic environments: A case study using the shaky ladder hyperplane-defined functions. In: Yang, S., Branke, J. (eds.) GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization (2005)
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.: 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.: 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)
Rohlfshagen, P., Yao, X.: Attributes of dynamic combinatorial optimisation. In: Li, X., et al. (eds.) SEAL 2008. LNCS, vol. 5361, pp. 442–451. Springer, Heidelberg (2008)
Rohlfshagen, P., Yao, X.: Dynamic combinatorial optimisation problems: an analysis of the subset sum problem. Soft Comput. 15(9), 1723–1734 (2011)
Salomon, R., Eggenberger, P.: Adaptation on the evolutionary time scale: A working hypothesis and basic experiments. In: Hao, J.-K., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds.) AE 1997. LNCS, vol. 1363, pp. 251–262. Springer, Heidelberg (1998)
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 2008. LNCS, vol. 5199, pp. 306–315. Springer, Heidelberg (2008)
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)
Tinos, R., Yang, S.: Continuous dynamic problem generators for evolutionary algorithms. In: Proc. 2007 IEEE Congr. Evol. Comput., pp. 236–243 (2007)
Trojanowski, K., Michalewicz, Z.: Searching for optima in non-stationary environments. In: Proc. 1999 IEEE Congr. Evol. Comput., vol. 3, pp. 1843–1850 (1999)
Uyar, Ş., Uyar, H.T.: A critical look at dynamic multi-dimensional knapsack problem generation. In: Giacobini, M., et al. (eds.) EvoWorkshops 2009. LNCS, vol. 5484, pp. 762–767. Springer, Heidelberg (2009)
Van Veldhuizen, D.A.: Multiobjective evolutionary algorithms: classifications, analyses, and new innovations. PhD thesis, Air Force Institute of Technolog, Wright Patterson AFB, OH, USA (1999)
Wang, H., Wang, D.-W., Yang, S.: Triggered memory-based swarm optimization in dynamic environments. In: Giacobini, M. (ed.) EvoWorkshops 2007. LNCS, vol. 4448, pp. 637–646. Springer, Heidelberg (2007)
Weicker, K.: An analysis of dynamic severity and population size. In: Deb, K., Rudolph, G., Lutton, E., Merelo, J.J., Schoenauer, M., Schwefel, H.-P., Yao, X. (eds.) PPSN 2000. LNCS, vol. 1917, pp. 159–168. Springer, Heidelberg (2000)
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 2002. LNCS, vol. 2439, pp. 64–73. Springer, Heidelberg (2002)
Weicker, K., Weicker, N.: Dynamic rotation and partial visibility. In: Proc. 2003 IEEE Congr. Evol. Comput., pp. 1125–1131 (2003)
Weicker, K., Weicker, N.: On evolution strategy optimization in dynamic environments. In: Proc. 1999 IEEE Congr. Evol. Comput., vol. 3, pp. 2039–2046 (1999)
Weise, T., Podlich, A., Reinhard, K., Gorldt, C., Geihs, K.: Evolutionary freight transportation planning. In: Giacobini, M., et al. (eds.) EvoWorkshops 2009. LNCS, vol. 5484, pp. 768–777. Springer, Heidelberg (2009)
Woldesenbet, Y.G., Yen, G.G.: Dynamic evolutionary algorithm with variable relocation. IEEE Trans. Evol. Comput. 13(3), 500–513 (2009)
Yang, S.: Non-stationary problem optimization using the primal-dual genetic algorithm. In: Proc. 2003 IEEE Congr. Evol. Comput., pp. 2246–2253 (2003)
Yang, S.: Constructing dynamic test environments for genetic algorithms based on problem difficulty. In: Proc. 2004 IEEE Congr. Evol. Comput., vol. 2, pp. 1262–1269 (2004)
Yang, S.: Memory-enhanced univariate marginal distribution algorithms for dynamic optimization problems. In: Proc. 2005 IEEE Congr. Evol. Comput., vol. 3, pp. 2560–2567 (2005)
Yang, S.: Genetic algorithms with memory and elitism based immigrants in dynamic environments. Evol. Comput. 16(3), 385–416 (2008)
Yang, S., Cheng, H., Wang, F.: Genetic algorithms with immigrants and memory schemes for dynamic shortest path routing problems in mobile ad hoc networks. IEEE Trans. Syst., Man, and Cybern. Part C: Appl. and Rev. 40(1), 52–63 (2010)
Yang, S., Li, C.: A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments. IEEE Trans. Evol. Comput. 14(6), 959–974 (2010)
Yang, S., Ong, Y.-S., Jin, Y. (eds.): Evolutionary Computation in Dynamic and Uncertain Environments. Springer (2007)
Yang, S., Richter, H.: Hyper-learning for population-based incremental learning in dynamic environments. In: Proc. 2009 IEEE Congr. Evol. Comput., pp. 682–689 (2009)
Yang, S., Tinos, R.: Hyper-selection in dynamic environments. In: Proc. 2008 IEEE Congr. Evol. Comput., pp. 3185–3192 (2008)
Yang, S., Yao, X.: Dual population-based incremental learning for problem optimization in dynamic environments. In: Proc. 7th Asia Pacific Symp. on Intell. and Evol. Syst., pp. 49–56 (2003)
Yang, S., Yao, X.: Experimental study on population-based incremental learning algorithms for dynamic optimization problems. Soft Comput. 9(11), 815–834 (2005)
Yang, S., Yao, X.: Population-based incremental learning with associative memory for dynamic environments. IEEE Trans. Evol. Comput. 12(5), 542–561 (2008)
Yao, X., Liu, Y.: Fast evolutionary programming. In: Proc. 5th Annual Conf. on Evolutionary Programming, pp. 451–460 (1996)
Yu, X., Jin, Y., Tang, K., Yao, X.: Robust optimization over time – a new perspective on dynamic optimization problems. In: Proc. 2010 IEEE World Congr. Comput. Intell., pp. 3998–4003 (2010)
Zeng, S., Chen, G., Zheng, L., Shi, H., de Garis, H., Ding, L., Kang, L.: A dynamic multi-objective evolutionary algorithm based on an orthogonal design. In: Proc. 2006 IEEE Congr. Evol. Comput., pp. 573–580 (2006)
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
Yang, S., Nguyen, T.T., Li, C. (2013). Evolutionary Dynamic Optimization: Test and Evaluation Environments. 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_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-38416-5_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38415-8
Online ISBN: 978-3-642-38416-5
eBook Packages: EngineeringEngineering (R0)