×

zbMATH — the first resource for mathematics

Balancing exploration and exploitation in multiobjective evolutionary optimization. (English) Zbl 1451.90175
Summary: The tradeoff between exploration and exploitation is critical to the performance of an evolutionary algorithm. Different levels of exploration-exploitation tradeoff are required at different evolutionary stages for achieving a satisfactory performance of an evolutionary algorithm. In this paper, we propose a novel survival analysis method to intelligently guide the maintenance of the exploration-exploitation tradeoff in multiobjective evolutionary algorithms. The survival analysis stems from a deep understanding of the evolutionary search procedure. Through survival analysis, an indicator is derived, which is used to guide the adoption of appropriate recombination operators, based on the assumption that the roles of these operators in terms of their capabilities on exploration-exploitation can be asserted. In the developed algorithm, a differential evolution recombination operator and a new sampling strategy are hybridized. Empirical comparison with five well-known multiobjective evolutionary algorithms on a number of test instances with complex Pareto sets and Pareto fronts indicates the effectiveness and superiority of the developed algorithm in terms of commonly-used performance metrics on these test instances.
MSC:
90C59 Approximation methods and heuristics in mathematical programming
68W50 Evolutionary algorithms, genetic algorithms (computational aspects)
90C29 Multi-objective and goal programming
Software:
HypE; SMS-EMOA; SPEA2
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bader, J.; Zitzler, E., Hype: an algorithm for fast hypervolume-based many-objective optimization, Evol. Comput., 19, 1, 45-76 (2011)
[2] Beume, N.; Naujoks, B.; Emmerich, M., SMS-EMOA: Multiobjective selection based on dominated hypervolume, Eur. J. Oper. Res., 181, 3, 1653-1669 (2007) · Zbl 1123.90064
[3] Beyer, H.-G.; Deb, K., On self-adaptive features in real-parameter evolutionary algorithms, IEEE Trans. Evol. Comput., 5, 3, 250-270 (2001)
[4] Brockhoff, D.; Zitzler, E., Improving Hypervolume-based Multiobjective Evolutionary Algorithms by Using Objective Reduction Methods, IEEE Congress on Evolutionary Computation (CEC 2007), 2086-2093 (2007)
[5] Caraffini, F.; Neri, F.; Epitropakis, M., Hyperspam: a study on hyperheuristic coordination strategies in the continuous domain, Inf. Sci., 477, 186-202 (2019)
[6] Das, S.; Suganthan, P. N., Differential evolution: a survey of the state-of-the-art, IEEE Trans. Evol. Comput., 15, 1, 4-31 (2011)
[7] Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms (2001), John Wiley & Sons LTD, Chichester · Zbl 0970.90091
[8] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 2, 182-197 (2002)
[9] Hernández-Díaz, A. G.; Santana-Quintero, L. V.; Coello, C. A.C.; Molina, J., Pareto-adaptive ϵ-dominance, Evol. Comput., 15, 4, 493-517 (2007)
[10] Herrera, F.; Lozano, M., Adaptation of Genetic Algorithm Parameters Based on Fuzzy Logic Controllers, Genetic Algorithms and Soft Computing, 95-125 (1996), Physica-Verlag
[11] Huband, S.; Barone, L.; While, L.; Hingston, P., A scalable multi-objective test problem toolkit, Proceedings of the 3rd International Conference on Evolutionary Multi-Criterion Optimization (EMO), 280-295 (2005) · Zbl 1109.68603
[12] Ishibuchi, H.; Yoshida, T.; Murata, T., Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling, IEEE Trans. Evol. Comput., 7, 2, 204-223 (2003)
[13] Ji, J.-Y.; Yu, W.-J.; Gong, Y.-J.; Zhang, J., Multiobjective optimization with ϵ-constrained method for solving real-parameter constrained optimization problems, Inf. Sci., 467, 15-34 (2018)
[14] Jiang, S.; Zhang, J.; Ong, Y.-S.; Zhang, A. N.; Tan, P. S., A simple and fast hypervolume indicator-based multiobjective evolutionary algorithm, IEEE Trans. Cybern., 45, 10, 2202-2213 (2015)
[15] Karshenas, H.; Santana, R.; Bielza, C.; Larranaga, P., Multiobjective estimation of distribution algorithm based on joint modeling of objectives and variables, IEEE Trans. Evol. Comput., 18, 4, 519-542 (2014)
[16] Li, H.; Zhang, Q., Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II, IEEE Trans. Evol. Comput., 13, 2, 284-302 (2009)
[17] Liu, H.-L.; Gu, F.; Cheung, Y., T-MOEA/D: MOEA/D with Objective Transform in Multi-objective Problems, Information Science and Management Engineering, 282-285 (2010)
[18] Liu, H.-L.; Gu, F.; Zhang, Q., Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems, IEEE Trans. Evol. Comput., 18, 3, 450-455 (2014)
[19] Liua, S.-H.; Mernik, M.; Bryant, B. R., To explore or to exploit: an entropy-driven approach for evolutionary algorithms, Int. J. Knowl. Intell. Eng. Syst., 13, 3, 185-206 (2009)
[20] Marti, L.; Grimme, C.; Kerschke, P.; Trautmann, H.; Rudolph, G., Averaged Hausdorff approximations of Pareto fronts based on multiobjective estimation of distribution algorithms, Proceedings of the 17th Annual Genetic and Evolutionary Computation Conference, 1427-1428 (2015), ACM: ACM New York, USA
[21] Neri, F., Disturbed exploitation compact differential evolution for limited memory optimization problems, Inf. Sci., 181, 12, 2469-2487 (2011)
[22] Pan, A.; Wang, L.; Guo, W.; Wu, Q., A diversity enhanced multiobjective particle swarm optimization, Inf. Sci., 436-437, 441-465 (2018)
[23] Rostami, S.; Neri, F., Covariance matrix adaptation Pareto archived evolution strategy with hyper volume-sorted adaptive grid algorithm, Integr. Comput. Aided Eng., 23, 4, 319-329 (2016)
[24] Rostami, S.; Neri, F., A fast hypervolume driven selection mechanism for many-objective optimisation problems, Swarm Evol. Comput., 34, 50-67 (2017)
[25] Rostami, S.; Neri, F.; Epitropakis, M., Progressive preference articulation for decision making in multi-objective optimisation problems, Integr. Comput. Aided Eng., 24, 4, 315-335 (2017)
[26] Storn, R.; Price, K., Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces, J. Global Optim., 11, 4, 341-359 (1997) · Zbl 0888.90135
[27] Sun, J.; Zhang, Q.; Tsang, E., DE/EDA: a new evolutionary algorithm for globla optimization, Inf. Sci., 169, 3, 249-262 (2005)
[28] Sun, J.; Zhang, Q.; Tsang, E., An evolutionary algorithm with guided mutation for the maximum clique problem, IEEE Trans. Evol. Comput., 9, 2, 192-200 (2005)
[29] Trivedi, A.; Srinivasan, D.; Sanyal, K.; Ghosh, A., A survey of multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 21, 3, 440-462 (2017)
[30] Vrugt, J. A.; Robinson, B. A., Improved evolutionary optimization from genetically adaptive multimethod search, PNAS, 104, 3, 708-711 (2007)
[31] Yan, B.; Zhao, Q.; Wang, Z.; Zhang, J. A., Adaptive decomposition-based evolutionary approach for multiobjective sparse reconstruction, Inf. Sci., 462, 141-159 (2018)
[32] Zhang, G.; Rong, H.; Neri, F.; Pérez-Jiménez, M. J., An optimization spiking neural p system for approximately solving combinatorial optimization problems, Int. J. Neural Syst., 24, 5, 1440006 (2014)
[33] Zhang, H.; Zhou, A.; Song, S.; Zhang, Q.; Gao, X.-Z.; Zhang, J., A self-organizing multiobjective evolutionary algorithm, IEEE Trans. Evol. Comput., 20, 5, 792-806 (2016)
[34] Zhang, Q.; Zhou, A.; Jin, Y., RM-MEDA: a regularity model based multiobjective estimation of distribution algorithm, IEEE Trans. Evol. Comput., 12, 1, 41-63 (2008)
[35] Zhou, A.; Zhang, Q.; Jin, Y., Approximating the set of Pareto-optimal solutions in both the decision and objective spaces by an estimation of distribution algorithm, IEEE Trans. Evol. Comput., 13, 5, 1167-1189 (2009)
[36] Zhou, A.; Qu, B.-Y.; Li, H.; Zhao, S.-Z.; Suganthan, P. N.; Zhang, Q., Multiobjective evolutionary algorithms: a survey of the state of the art, Swarm Evol. Comput., 1, 1, 32-49 (2011)
[37] Zhu, Q.; Lin, Q.; Du, Z.; Liang, Z.; Wang, W.; Zhu, Z.; Chen, J.; Huang, P.; Ming, Z., A novel adaptive hybrid crossover operator for multiobjective evolutionary algorithm, Inf. Sci., 345, 177-198 (2016)
[38] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Trans. Evol. Comput., 3, 4, 257-271 (1999)
[39] Zitzler, E.; Laumanns, M.; Thiele, L., SPEA2: improving the strength Pareto evolutionary algorithm, Proceedings of Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems Conference, 95-100 (2002)
[40] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; Fonseca, V. G.D., Performance assessment of multiobjective optimizers: an analysis and review, IEEE Trans. Evol. Comput., 7, 2, 117-132 (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.