×

A set of new multi- and many-objective test problems for continuous optimization and a comprehensive experimental evaluation. (English) Zbl 1482.90208

Summary: Multi- and many-objective optimization problems have wide applications in the real world, and they have received growing attention from the evolutionary computation community. To promote the algorithm development in this area, numerous studies have been devoted to designing multi- and many-objective test problems. Most of these studies focus on handling complicated Pareto fronts (PFs), and the impact of the Pareto sets (PSs) has not been well-studied, although complicated PSs are prevalent in the real world. This paper presents a set of scalable test problems according to a new principle, which considers the geometrical properties of both PF and PS. A position function with a spherical form is proposed to introduce non-linear variable dependences to the PS, so as to simulate the variable dependencies in the real-world problems. According to the proposed principle, the first \(m\) (i.e., the number of objectives) decision variables are used to form the surface of a unit hypersphere, while the rest variables are designed to optimize a certain distance function. A set of test problems are generated by the proposed principle, which are then used to investigate six representative algorithms. The experimental results indicate that the proposed test problems pose considerable difficulties to existing algorithms, calling for the need for designing new algorithms capable of handling complicated PF and PS simultaneously.

MSC:

90C29 Multi-objective and goal programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Miettinen, K., Nonlinear Multiobjective Optimization, International Series in Operations Research & Management Science, vol. 12 (1998), Springer US: Springer US Boston, MA
[2] Li, B.; Li, J.; Tang, K.; Yao, X., Many-objective evolutionary algorithms: a survey, ACM Comput. Surv., 48, 1-35 (2015)
[3] Knowles, J.; Corne, D., Instance generators and test suites for the multiobjective quadratic assignment problem, (Evolutionary Multi-Criterion Optimization. Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science (2003), Springer Berlin Heidelberg), 295-310 · Zbl 1036.90542
[4] Corne, D. W.; Knowles, J. D., Techniques for highly multiobjective optimisation: some nondominated points are better than others, (Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation - GECCO ’07 (2007), ACM Press: ACM Press London, England), 773
[5] Zhang, Y.; Harman, M.; Mansouri, S. A., The multi-objective next release problem, (Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation - GECCO ’07 (2007), ACM Press: ACM Press London, England), 1129
[6] Ishibuchi, H.; Masuda, H.; Tanigaki, Y.; Nojima, Y., Review of Coevolutionary Developments of Evolutionary Multi-Objective and Many-Objective Algorithms and Test Problems, 178-184 (2014), IEEE
[7] Ishibuchi, H.; Akedo, N.; Nojima, Y., Behavior of multiobjective evolutionary algorithms on many-objective Knapsack problems, IEEE Trans. Evol. Comput., 19, 264-283 (2015)
[8] Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms, Wiley-Interscience Series in Systems and Optimization (2001), John Wiley & Sons: John Wiley & Sons Chichester, New York · Zbl 0970.90091
[9] Knowles, J. D.; Corne, D. W., Approximating the nondominated front using the Pareto archived evolution strategy, Evol. Comput., 8, 149-172 (2000), 02038
[10] Corne, D. W.; Jerram, N. R.; Knowles, J. D.; Oates PESA-II, M. J., Region-based selection in evolutionary multiobjective optimization, (Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, GECCO’01 (2001), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 283-290
[11] Zitzler, E.; Laumanns, M.; Thiele, L., SPEA2: Improving the Strength Pareto Evolutionary Algorithm (2001), ETH: ETH Zurich, Technical Report TIK-Report 103
[12] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 182-197 (2002), 17703
[13] Zhang, Qingfu; Li, Hui, MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 712-731 (2007)
[14] Li, Hui; Zhang, Qingfu, Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II, IEEE Trans. Evol. Comput., 13, 284-302 (2009)
[15] Qi, Y.; Ma, X.; Liu, F.; Jiao, L.; Sun, J.; Wu, J., MOEA/D with adaptive weight adjustment, Evol. Comput., 22, 231-264 (2014)
[16] Deb, K.; Jain, H., An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints, IEEE Trans. Evol. Comput., 18, 577-601 (2014)
[17] Cheng, R.; Jin, Y.; Olhofer, M.; Sendhoff, B., A reference vector guided evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 20, 773-791 (2016)
[18] Xiang, Y.; Zhou, Y.; Li, M.; Chen, Z., A vector angle-based evolutionary algorithm for unconstrained many-objective optimization, IEEE Trans. Evol. Comput., 21, 131-152 (2017)
[19] Chen, Z.; Zhou, Y.; Xiang, Y., A many-objective evolutionary algorithm based on a projection-assisted intra-family election, Appl. Soft Comput., 61, 394-411 (2017)
[20] Zitzler, E.; Künzli, S., Indicator-Based Selection in Multiobjective Search, Parallel Problem Solving From Nature - PPSN VIII, vol. 3242, 832-842 (2004), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg
[21] Beume, N.; Naujoks, B.; Emmerich SMS-EMOA, M., Multiobjective selection based on dominated hypervolume, Eur. J. Oper. Res., 181, 1653-1669 (2007) · Zbl 1123.90064
[22] Bader, J.; Zitzler, E., HypE: an algorithm for fast hypervolume-based many-objective optimization, Evol. Comput., 19, 45-76 (2011)
[23] Hernández Gómez, R.; Coello Coello, C. A., Improved metaheuristic based on the R2 indicator for many-objective optimization, (Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, GECCO ’15 (2015), ACM: ACM Madrid, Spain), 679-686
[24] Weise, T.; Chiong, R.; Tang, K., Evolutionary optimization: Pitfalls and Booby traps, J. Comput. Sci. Technol., 27, 907-936 (2012) · Zbl 1279.68281
[25] Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms: empirical results, Evol. Comput., 8, 173-195 (2000)
[27] Huband, S.; Hingston, P.; Barone, L.; While, L., A review of multiobjective test problems and a scalable test problem toolkit, IEEE Trans. Evol. Comput., 10, 477-506 (2006)
[28] Deb, K., Multi-objective genetic algorithms: problem difficulties and construction of test problems, Evol. Comput., 7, 205-230 (1999)
[29] Ishibuchi, H.; Setoguchi, Y.; Masuda, H.; Nojima, Y., Performance of decomposition-based many-objective algorithms strongly depends on Pareto front shapes, IEEE Trans. Evol. Comput., 21, 169-190 (2017)
[30] Liu, H. L.; Chen, L.; Zhang, Q.; Deb, K., Adaptively allocating search effort in challenging many-objective optimization problems, IEEE Trans. Evol. Comput., 22, 3, 433-448 (2018)
[31] Cheng, R.; Li, M.; Tian, Y.; Zhang, X.; Yang, S.; Jin, Y.; Yao, X., A benchmark test suite for evolutionary many-objective optimization, Complex Intell. Syst., 3, 67-81 (2017)
[32] Jain, H.; Deb, K., An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part II: handling constraints and extending to an adaptive approach, IEEE Trans. Evol. Comput., 18, 602-622 (2014)
[33] Wang, Z.; Ong, Y. S.; Ishibuchi, H., On scalable multiobjective test problems with hardly-dominated boundaries, IEEE Trans. Evol. Comput., 23, 2, 217-231 (2019)
[34] Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E., Scalable test problems for evolutionary multiobjective optimization, (Abraham, A.; Jain, L.; Goldberg, R., Evolutionary Multiobjective Optimization (2005), Springer-Verlag: Springer-Verlag London), 105-145 · Zbl 1078.90567
[35] Zapotecas-Martínez, S.; Coello, C. A.C.; Aguirre, H. E.; Tanaka, K., A review of features and limitations of existing scalable multi-objective test suites, IEEE Trans. Evol. Comput., 23, 1, 130-142 (2019)
[36] Zhang, Qingfu; Zhou, Aimin; RM-MEDA Yaochu Jin, A regularity model-based multiobjective estimation of distribution algorithm, IEEE Trans. Evol. Comput., 12, 41-63 (2008)
[37] Cheng, R.; Jin, Y.; Narukawa, K.; Sendhoff, B., A multiobjective evolutionary algorithm using Gaussian process-based inverse modeling, IEEE Trans. Evol. Comput., 19, 838-856 (2015)
[38] Cheng, R.; Jin, Y.; Olhofer, M.; sendhoff, B., Test problems for large-scale multiobjective and many-objective optimization, IEEE Trans. Cybern., 47, 4108-4121 (2017)
[39] Emmerich, M.; Beume, N.; Naujoks, B., An EMO Algorithm Using the Hypervolume Measure as Selection Criterion, Evolutionary Multi-Criterion Optimization, vol. 3410, 62-76 (2005), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg · Zbl 1109.68595
[40] Zitzler, E.; Laumanns, M.; Thiele, L., SPEA2: Improving the Strength Pareto Evolutionary Algorithm (2001), ETH: ETH Zurich, Switzerland, TIK-Report 103
[41] Yuan, Y.; Xu, H.; Wang, B.; Yao, X., A new dominance relation-based evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 20, 16-37 (2016)
[42] Zhou, Y.; Xiang, Y.; Chen, Z.; He, J.; Wang, J., A scalar projection and angle-based evolutionary algorithm for many-objective optimization problems, IEEE Trans. Cybern., 1-12 (2018)
[43] Sato, H., Inverted PBI in MOEA/D and Its Impact on the Search Performance on Multi and Many-Objective Optimization, 645-652 (2014), ACM Press
[44] Pan, L.; He, C.; Tian, Y.; Su, Y.; Zhang, X., A region division based diversity maintaining approach for many-objective optimization, Integr. Comput.-Aided Eng., 24, 279-296 (2017)
[45] Coello Coello, C. A.; Lamont, G. B.; Van Veldhuizen, D. A., Evolutionary Algorithms for Solving Multi-Objective Problems, Genetic and Evolutionary Computation Series (2007), Springer: Springer New York, NY, OCLC: 255368493 · Zbl 1142.90029
[46] Bosman, P.; Thierens, D., The balance between proximity and diversity in multiobjective evolutionary algorithms, IEEE Trans. Evol. Comput., 7, 174-188 (2003)
[47] Zhang, Q.; Zhou, A.; Zhao, S.; Suganthan, P. N.; Liu, W.; Tiwari, S., Multiobjective Optimization Test Instances for the CEC 2009 Special Session and Competition (2008), The School of Computer Science and Electronic Engieering University of Essex, Colchester, C04, 3SQ, UK; School of Electrical and Electronic Engineering Nanyang Technological University, 50 Nanyang Avenue, Singapore; Department of Mechanical Engineering Clemson University, Clemson, SC 29634, US
[48] Yang, S.; Li, M.; Liu, X.; Zheng, J., A grid-based evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 17, 721-736 (2013)
[49] Li, M.; Yang, S.; Liu, X., Shift-based density estimation for Pareto-based algorithms in many-objective optimization, IEEE Trans. Evol. Comput., 18, 348-365 (2014)
[50] Ishibuchi, H.; Masuda, H.; Tanigaki, Y.; Nojima, Y., Difficulties in specifying reference points to calculate the inverted generational distance for many-objective optimization problems, (2014 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making (MCDM) (2014)), 170-177
[51] Ishibuchi, H.; Masuda, H.; Nojima, Y., A study on performance evaluation ability of a modified inverted generational distance indicator, (Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, GECCO ’15 (2015), ACM: ACM New York, NY, USA), 695-702
[52] Das, I.; Dennis, J. E., Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems, SIAM J. Optim., 8, 631-657 (1998) · Zbl 0911.90287
[53] Ishibuchi, H.; Masuda, H.; Nojima, Y., Pareto fronts of many-objective degenerate test problems, IEEE Trans. Evol. Comput., 20, 807-813 (2016)
[54] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Trans. Evol. Comput., 3, 257-271 (1999)
[55] While, L.; Bradstreet, L.; Barone, L., A fast way of calculating exact hypervolumes, IEEE Trans. Evol. Comput., 16, 86-95 (2012)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.