Abstract
Many real-world multiobjective optimization problems are dynamic, requiring an optimization algorithm that is able to continuously track the moving Pareto front over time. In this paper, we propose a directed search strategy (DSS) consisting of two mechanisms for improving the performance of multiobjective evolutionary algorithms in changing environments. The first mechanism reinitializes the population based on the predicted moving direction as well as the directions that are orthogonal to the moving direction of the Pareto set, when a change is detected. The second mechanism aims to accelerate the convergence by generating solutions in predicted regions of the Pareto set according to the moving direction of the non-dominated solutions between two consecutive generations. The two mechanisms, when combined together, are able to achieve a good balance between exploration and exploitation for evolutionary algorithms to solve dynamic multiobjective optimization problems. We compare DSS with two existing prediction strategies on a variety of test instances having different changing dynamics. Empirical results show that DSS is powerful for evolutionary algorithms to deal with dynamic multiobjective optimization problems.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Abello M, Bui L, Michalewicz Z (2011a) An adaptive approach for solving dynamic scheduling with time-varying number of tasks: part I. In: Proceedings of IEEE CEC. IEEE Press, New York, pp 1703–1710
Abello M, Bui LT, Michalewicz Z (2011b) An adaptive approach for solving dynamic scheduling with time-varying number of tasks: part II. In: Proceedings of IEEE CEC. IEEE, New York, pp 1711–1718
Aragon V, Esquivel S, Coello CC (2005) Evolutionary multiobjective optimization in non-stationary environments. J Comput Sci Technol 5(3):133–143
Azevedo C, Araujo A (2011) Generalized immigration schemes for dynamic evolutionary multiobjective optimization. In: Proceedings of IEEE CEC. IEEE, New York, pp 2033–2040
Camara M, Ortega J, de Toro F (2009) A single front genetic algorithm for parallel multiobjective optimization in dynamic environments. Neurocomputing 72(16–18):3570–3579
Camara M, Ortega J, de Toro F (2010) Generalized immigration schemes for dynamic evolutionary multiobjective optimization. In: Proceedings of advances multi-objective nature inspired computation. Springer, Berlin, pp 63–86
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197
Deb K, Rao U, Karthik S (2007) Dynamic multiobjective optimization and decision-making using modified NSGA-II: A case study on hydro-thermal power scheduling. In: Evolutionary multi-criterion optimization: 4th international conference, EMO. Springer, Berlin, pp 803–817
Farina M, Deb K, Amato P (2004) Dynamic multiobjective optimization problems: test cases, approximations, and applications. IEEE Trans Evol Comput 8(5):425–442
Goh CK, Tan K (2009) A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization. IEEE Trans Evol Comput 13(1):103–127
Greeff M, Engelbrecht A (2008) Solving dynamic multiobjective problems with vector evaluated particle swarm optimisation. In: Proceedings of IEEE CEC. IEEE Press, New York, pp 2922–2929
Hatzakis I, Wallace D (2006a) Dynamic multiobjective optimization with evolutionary algorithms: a forward-looking approach. In: Proceedings of GECCO. ACM Press, New York, pp 1201–1208
Hatzakis I, Wallace D (2006a) Topology of anticipatory populations for evolutionary dynamic multiobjective optimization. In: Proceedings of 11th AIAA/ISSMO multidisciplinary analysis and optimization conference, AIAA, pp 1944–1950
Helbig M, Engelbrecht A (2012) Analyses of guide update approaches for vector evaluated particle swarm optimisation on dynamic multiobjective optimisation problems. In: Proceedings of IEEE CEC. IEEE Press, New York, pp 2621–2628
Iorio A, Li X (2005) Solving rotated multi-objective optimization problems using differential evolution. In: Advances in artificial intelligence. LNAI 3339. Springer, Berlin, pp 861–872
Jin Y, Branke J (2005) Evolutionary optimization in uncertain environments: a survey. IEEE Trans Evol Comput 9(3):303–317
Jin Y, Tang K, Yu X, Sendhoff B, Yao X (2013) A framework for finding robust optimal solutions over time. Memet Comput 5(1):3–18
Jin Y, Sendhoff B (2004) Constructing dynamic test problems using the multi-objective optimization concept. In: Applications of evolutionary computing. LNCS 3005. Springer, Berlin, pp 525–536
Li H, Zhang Q (2009) Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II. IEEE Trans Evol Comput 13(2):284–302
Liu C, Wang Y (2009) Multiobjective evolutionary algorithm for dynamic nonlinear constrained optimization problems. J Syst Eng Electron 20(1):204–210
Liu C, Wang Y (2006) New evolutionary algorithm for dynamic multiobjective optimization problems. In: Advances in natural computation, LNCS 4221. Springer, Berlin, pp 889–892
Liu R, Zhang W, Jiao L, Liu F, Ma J (2011) A sphere-dominance based preference immune-inspired algorithm for dynamic multiobjective optimization. In: Proceedings of GECCO. ACM Press, New York, pp 423–430
Ma Y, Liu R, Shang R (2011) A hybrid dynamic multiobjective immune optimization algorithm using prediction strategy and improved differential evolution crossover operator. In: Neural information processing. LNCS 7063. Springer, Berlin, pp 435–444
Manriquez A, Pulido G, Torres J (2010) Handling dynamic multiobjective problems with particle swarm optimization. In: Proceedings of the international conference on agents and artificial intelligence, ICAART, pp 337–342
Martins F, Carrano E, Wanner E, Takahashi R, Mateus G (2009) A dynamic multiobjective hybrid approach for designing wireless sensor networks. In: Proceedings of IEEE CEC. IEEE Press, New York, pp 1145–1152
Nguyen T, Yang S, Branke J (2012) Evolutionary dynamic optimization: a survey of the state of the art. Swarm Evol Comput 6:1–24
Tang J, Alam S, Lokan C, Abbass H (2012) A multiobjective evolutionary method for dynamic airspace re-sectorization using sectors clipping and similarities. In: Proceedings of IEEE CEC. IEEE Press, New York, pp 3565–3572
Vinek E, Beran P, Schikuta E (2011) A dynamic multiobjective optimization framework for selecting distributed deployments in a heterogeneous environment. Procedia Comput Sci 4:166–175
Wang Y, Li B (2009) Investigation of memory-based multiobjective optimization evolutionary algorithm in dynamic environment. In: Proceedings of IEEE CEC. IEEE Press, New York, pp 630–637
Wei J, Wang Y (2012) Hyper rectangle search based particle swarm algorithm for dynamic constrained multiobjective optimization problems. In: Proceedings of IEEE CEC. IEEE Press, New York, pp 259–266
Wei J, Zhang M (2011) Simplex model based evolutionary algorithm for dynamic multiobjective optimization. In: Advances in artificial intelligence, LNCS 7106. Springer, Berlin, pp 372–381
Wu PY, Campbel D, Merz T (2011) Multiobjective four-dimensional vehicle motion planning in large dynamic environments. IEEE Trans Syst Man Cybern B Cybern 41(3):621–634
Yang M, Kang L, Guan J (2008) Multialgorithm co-evolution strategy for dynamic multiobjective TSP. In: Proceedings of IEEE CEC. IEEE Press, New York, pp 466–471
Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6):712–731
Zhang Q, Zhou A, Jin Y (2008) RM-MEDA: a regularity model based multiobjective estimation of distribution algorithm. IEEE Trans Evol Comput 12(1):41–63
Zhang Z (2008) Multiobjective optimization immune algorithm in dynamic environments and its application to greenhouse control. Appl Soft Comput 8(2):959–971
Zheng B (2007) A new dynamic multiobjective optimization evolutionary algorithm. In: Third international conference on natural computation (ICNC). IEEE Press, New York, pp 565–570
Zhou A, Jin Y, Zhang Q (2014) A population prediction strategy for evolutionary dynamic multiobjective optimization. IEEE Trans Cybern 44(1):40–53
Zhou A, Jin Y, Zhang Q, Sendhoff B, Tsang E (2007) Prediction based population re-initialization for evolutionary dynamic multiobjective optimization. In: Evolutionary multi-criterion optimization. LNCS 4403. Springer, Berlin, pp 832–846
Acknowledgments
This work was supported in part by the National Natural Science Foundation of China (No. 61105065 and No.11326188), the Fundamental Research Funds for the Central Universities (No. K5051270009), and the Joint Research Fund for Overseas Chinese, Hong Kong and Macao Scholars of the National Natural Science Foundation of China (Grant No. 61428302).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by V. Loia.
Rights and permissions
About this article
Cite this article
Wu, Y., Jin, Y. & Liu, X. A directed search strategy for evolutionary dynamic multiobjective optimization. Soft Comput 19, 3221–3235 (2015). https://doi.org/10.1007/s00500-014-1477-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-014-1477-4