Abstract
Dynamic optimization and multi-objective optimization have separately gained increasing attention from the research community during the last decade. However, few studies have been reported on dynamic multi-objective optimization (dMO) and scarce effective dMO methods have been proposed. In this paper, we fulfill these gabs by developing new dMO test problems and new effective dMO algorithm. In the newly designed dMO problems, Pareto-optimal decision values (i.e., Pareto-optimal solutions: POS) or both POS and Pareto-optimal objective values (i.e., Pareto-optimal front: POF) change with time. A new multi-strategy ensemble multi-objective evolutionary algorithm (MS-MOEA) is proposed to tackle the challenges of dMO. In MS-MOEA, the convergence speed is accelerated by the new offspring creating mechanism powered by adaptive genetic and differential operators (GDM); a Gaussian mutation operator is employed to cope with premature convergence; a memory like strategy is proposed to achieve better starting population when a change takes place. In order to show the advantages of the proposed algorithm, we experimentally compare MS-MOEA with several algorithms equipped with traditional restart strategy. It is suggested that such a multi-strategy ensemble approach is promising for dealing with dMO problems.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abido MA (2006) Multi-objective evolutionary algorithms for electric power dispatch problem. IEEE Trans Evol Comput 10(3): 315–329
Amato P, Farina M (2005) An alife-inspired evolutionary algorithm for dynamic multiobjective optimization problems. Adv Soft Comput 1: 113–125
Annunziato M, Bertini I, Pannicelli A, Pizzuti S (2001) Evolutionary control and optimization: an industrial application for combustion processes. In: Proceedings of EUROGEN, Athens, Greece, September, pp 367–372
Bhattacharya M, Lu G (2003) A dynamic approximate fitness-based hybrid EA for optimization problems. In: Proceedings of congress evolutionary computation, pp 1879–1886
Bierwirth C, Kopfer H (1994) Dynamic task scheduling with genetic algorithms in manufacturing systems. Technical report, Department of Economics, University of Bremen, Bremen, Germany
Bingul Z (2007) Adaptive genetic algorithms applied to dynamic multiobjective problems. Appl Soft Comput 7(3): 791–799
Blackwell T (2007) Particle swarm optimization in dynamic environments. Evol Comput Dyn Uncertain Environ 51: 29–49
Blackwell T, Bentley PJ (2002) Dynamic search with charged swarms. In: Proceedings of genetic evolutionary computations conference. Morgan Kaufmann, London, pp 19–26
Blackwell T, Branke J (2004) Multi-swarm optimization in dynamic environments. Appl Evol Comput 3005: 489–500
Blackwell T, Branke J (2006) Multi-swarms, exclusion, and anti-convergence in dynamic environments. IEEE Trans Evol Comput 10(4): 459–472
Branke J (1999) Memory enhanced evolutionary algorithms for changing optimization problems. Proc Congr Evol Comput 3: 1875–1882
Branke J, Schmeck H (2002) Designing evolutionary algorithms for dynamic optimization problems. In: Proceedings of theory and applications of evolutionary computation, recent trends. Springer, Heidelberg, pp 239–262
Chan TM, Man KF, Kwong S, Tang KS (2008) A jumping gene paradigm for evolutionary multiobjective optimization. IEEE Trans Evol Comput 12(3): 143–159
Cobb HG (1990) An investigation into the use of hypermutation as an adaptive operator in genetic algorithms having continuous, time-dependent nonstationary environments. Tech Rep AIC-90-001, Naval Res Lab, Washington, DC
Coello C, Van Veldhuizen D, Lamont G (2002) Evolutionary algorithms for solving multi-objective problems. In: Ser. Genetic algorithms and evolutionary computation. Kluwer, Norwell
Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, New York
Deb K, Agrawal S (1999) A niched-penalty approach for constraint handling in genetic algorithms. In: Proceedings of international conference on artifical neural networks and genetic algorithms. Springer, Heidelberg, pp 235–243
Deb K. http://www.iitk.ac.in/kangal/code/newnsga/nsga2code.tar
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6: 182–197
Deb K, Mohan M, Mishra S (2005) Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solution. MIT Evol Comput 13(4): 501–502
Du WL, Li B (2008) Multi-strategy ensemble particle swarm optimization for dynamic optimization. Inf Sci 178(15): 3096–3109
Emmerich M, Beume N, Naujoks B (2005) An EMO algorithm using the hypervolume measure as selection criterion. In: Proceedings of third international conference on evolutionary multi-criterion optimization (EMO 2005), vol 3410. Springer, Berlin, pp 62–76
Farina M, Amato P, Deb K (2004) Dynamic multi-objective optimization problems: test cases approximations and applications. IEEE Trans Evol Comput 8(5): 425–442
Goh CK, Tan KC (2007) An investigation on noisy environments in evolutionary multiobjective optimization. IEEE Trans Evol Comput 11(3): 354–381
Handl J, Kell DB, Knowles J (2007) Multi-objective optimization in bioinformatics and computational biology. IEEE/ACM Trans Comput Biol Bioinform 4(2): 279–292
Hatzakis I, Wallace D (2006) Dynamic multi-objective optimization with evolutionary algorithms: a forward-looking approach. In: Proceedings of genetic and evolutionary computation conference (GECCO), pp 1201–1208
Huang VL, Suganthan PN, Baskar S (2005) Multiobjective differential evolution with external archive. Technical report, Nanyang Technological University, Singapore
Huang VL, Qin AK, Suganthan PN, Tasgetiren MF (2007) Multi-objective optimization based on self-adaptive differential evolution. In: Proceedings of IEEE conference on evolutionary computation, 25–28 September 2007, Singapore
Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evol Comput 7(2): 204–223
Jin Y, Branke J (2005) Evolutionary optimization in uncertain environments—a survey. IEEE Trans Evol Comput 9(3): 303–317
Jin YC, Sendhoff B et al (2004) Constructing dynamic optimization test problems using the multiobjective optimization concept. In: Raidl GR (eds) Proceedings of evolutionary workshops 2004, LNCS3005. Springer, Berlin, pp 525–536
Knowles J (2006) ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Trans Evol Comput 10(1): 50–66
Knowles J, Corne D (1999) The Pareto archived evolution strategy: a new baseline algorithm for multiobjective optimization. In: Proceedings of 1999 congress on evolutionary computation, Piscataway, NJ, pp 9–105
Knowles JD, Corne DW (2000) M-PAES: a memetic algorithm for multiobjective optimization. In: Proceedings of IEEE Congress on Evolutionary Computation, pp 325–332
Kukkonen S, Lampinen J (2007) Performance assessment of generalized differential evolution 3 (GDE3) with a given set of problems. In: Proceedings of IEEE conference on evolutionary computation, 25–28 September 2007, Singapore
Kumar A, Sharma D, Deb K (2007) A hybrid multi-objective optimization procedure using PCX based NSGA-II and sequential quadratic programming. In: Proceedings of IEEE conference on evolutionary computation, 25–28 September 2007, Singapore
Li C, Yang S, Nguyen TT, Yu EL, Yao X, Jin Y, Beyer H-G, Suganthan PN (2009) Benchmark generator for CEC 2009 competition on dynamic optimization. In: IEEE conference on evolutionary computation. Special session competition on evolutionary computation in dynamic and uncertain environments. http://www3.ntu.edu.sg/home/EPNSugan/index_files/
Mendoza F, Bernal-Agustin JL, Domnguez-Navarro JA (2006) NSGA and SPEA applied to multi-objective design of power distribution systems. IEEE Trans Power Syst 21(4)
Ramsey C, Grefensttete J (1993) Case-based initialization of genetic algorithms. In: Proceedings of the fifth international conference on genetic algorithms, pp 84–91
Schaffer JD (1985) Multiple objective optimization with vector evaluated genetic algorithms. In: Proceedings of 1st international conference on genetic algorithms, Pittsburgh, PA, pp 93–100
Sharma D, Kumar A, Deb K, Sindhya K (2007) Hybridization of SBX based NSGA-II and sequential quadratic programming for solving multi-objective optimization problems. In: Proceedings of IEEE conference on evolutionary computation, 25–28 September 2007, Singapore
Suganthan PN (2007) Performance assessment on multi-objective optimization algorithms. IEEE conference on evolutionary computation special session, competition on performance assessment of multi-objective optimization algorithms. http://www3.ntu.edu.sg/home/EPNSugan/index_files/
Wang Y, Li B (2008) FH-MOEA: multi-objective evolutionary algorithm based-on fast hyper-volume contribution approach. J Univ Sci Technol China 38(7):802–809 (special issue on information science for 50th Anniversary)
Wang Y, Li B (2009) Investigation of memory-based multi-objective optimization evolutionary algorithm in dynamic environment. In: Proceedings of IEEE congress on evolutionary computation (CEC 2009), pp 630–637 (accepted)
Wang Y, Li B (2009) ED-DE: cooperative estimation of distribution based differential evolution for economic dispatch optimization of power system. Inf Sci (accepted)
Wanner EF, Guimaraes FG, Takahashi RHC, Fleming PJ (2008) Local search with quadratic approximations into memetic algorithms for optimization with multiple criteria. MIT Evol Comput 16(2): 185–224
While L, Hingston P, Barone L, Huband S (2006) A faster algorithm for calculating hyper-volume. IEEE Trans Evol Comput 10(1): 29–38
Yang S (2005) Population-based incremental learning with memory scheme for changing environments. Proc Genet Evol Comput Conf 1: 711–718
Yang S (2007) Genetic algorithms with elitism-based immigrants for changing optimization problems. Applications of evolutionary computing. In: Lecture Notes in Computer Science, vol 4448. Springer, Berlin, pp 627–636
Yang S, Tinos R (2007) A hybrid immigrants scheme for genetic algorithms in dynamic environments. Int J Autom Comput 4(3): 243–254
Yang S, Yao X (2005) Experimental study on population-based incremental learning algorithms for dynamic optimization problems. Soft Comput 9(11): 815–834
Yang S, Yao X (2008) Population-based incremental learning with associative memory for dynamic environments. IEEE Trans Evol Comput 12(5): 542–561
Yao X, Liu Y, Lin G (1999) Evolutionary programming made faster. IEEE Trans Evol Comput 3(2): 82–102
Yu X, Tang K, Chen TS, Yao X (2009) Empirical analysis of evolutionary algorithms with immigrants schemes for dynamic optimization. Memet Comput 1(1): 3–24
Zhang QF, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6): 712–731
Zhang QF, Zhou AM, Jin YC (2008) RM-MEDA: a regularity model-based multiobjective estimation of distribution algorithm. IEEE Trans Evol Comput 12(1): 41–63
Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms—a comparative study. In: Proceedings of parallel problem solving from nature V. Springer, Amsterdam, pp 292–301
Zitzler E, Deb K, Thiele L (2000) Comparison of multiobjective evolutionary algorithms: empirical results. Evol Comput 8(2): 173–195
Zitzler E, Laumanns M, Thiele L (2001) SPEA2: improving the strength pareto evolutionary algorithm. Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, Tech Rep 103
Zitzler E, Thiele L, Laumanns M, Fonseca CM, Grunertda Fonseca V (2003) Performance assesment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7(2): 117–132
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, Y., Li, B. Multi-strategy ensemble evolutionary algorithm for dynamic multi-objective optimization. Memetic Comp. 2, 3–24 (2010). https://doi.org/10.1007/s12293-009-0012-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12293-009-0012-0