Abstract
The many-objective optimization problem (MaOP) is widespread in real life. It contains multiple conflicting objectives to be optimized. Many evolutionary many-objective (EMaO) algorithms are proposed and developed to solve it. The EMaO algorithms have received extensive attentions and in-depth studies. At the beginning of this paper, the challenges of designing EMaO algorithms are first summarized. Based on the optimization strategies, the existing EMaO algorithms are classified. Characteristics of each class of algorithms are interpreted and compared in detail. Their applicability for different types of MaOPs is discussed. Next, the numerical experiment was implemented to test the performance of typical EMaO algorithms. Their performance is analyzed from the perspectives of solution quality, convergence speed and the approximation of the Pareto front. Performance of different algorithms on different kind of test cases is analyzed, respectively. At last, the researching statuses of existing algorithms are summarized. The future researching directions of the EMaO algorithm are prospected.
Similar content being viewed by others
References
Ishibuchi, H., Setoguchi, Y., Masuda, H., et al.: Performance of decomposition-based many-objective algorithms strongly depends on Pareto front shapes. IEEE Trans. Evol. Comput. 21(2), 169–190 (2017)
Srinivas, S.N., Deb, K.: Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolut. Comput. 2(3), 221–248 (1994)
Horn, J., Nafpliotis, N., Goldberg, D.E.: A niched Pareto genetic algorithm for multiobjective optimization. In: IEEE World Congress on Computational Intelligence, Proceedings of the First IEEE Conference on Evolutionary Computation, 1994. IEEE Xplore, vol. 1, pp. 82–87
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)
Deb, K., Pratap, A., Agarwal, S., et al.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)
Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: improving the strength Pareto evolutionary algorithm. In: TIK-Report 103, Computer Engineering and Networks Laboratory (TIK), Department of Electrical Engineering, ETH, Zurich (2001)
Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6), 712–731 (2008)
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. Evolut. Comput. 18(4), 577–601 (2014)
He, Z., Yen, G.G.: Visualization and performance metric in many-objective optimization. IEEE Trans. Evol. Comput. 20(3), 386–402 (2016)
Ibrahim, A., Rahnamayan, S., Martin, M.V., et al.: 3D-RadVis: visualization of Pareto front in many-objective optimization. In: Evolutionary Computation. IEEE, 2016
Freitas, A.R.R., Silva, R.C.P.: On the visualization of trade-offs and reducibility in many-objective optimization. In: Companion Publication of the Conference on Genetic and Evolutionary Computation. ACM, (2014)
Tanigaki, Y., Narukawa, K., Nojima, Y., et al.: Preference-based NSGA-II for many-objective knapsack problems. In: International Symposium on Soft Computing and Intelligent Systems, pp. 637–642. IEEE, (2004)
Mohammadi, A., Omidvar, M.N., Li, X., et al.: Integrating user preferences and decomposition methods for many-objective optimization. In: Evolutionary Computation, pp. 421–428. IEEE, (2014)
Walker, D.J., Everson, R.M., Fieldsend, J.E.: Visualisation and ordering of many-objective populations. In: IEEE congress on evolutionary computation (CEC), pp. 1–8. IEEE, (2010)
Ibrahim, A., Rahnamayan, S., Martin, M.V., et al.: 3D-RadVis: visualization of Pareto front in many-objective optimization. In: IEEE Congress on Evolutionary Computation, pp. 736–745. IEEE, (2016)
He, Z., Yen, G.G.: An improved visualization approach in many-objective optimization. In: IEEE Congress on Evolutionary Computation, pp. 1618–1625. IEEE, (2016)
Silva, R., Salimi, A., Li, M., et al.: Visualization and analysis of tradeoffs in many-objective optimization: a case study on the interior permanent magnet motor design. IEEE Trans. Magn. 52(3), 1–4 (2016)
Jiang, S., Yang, S.: A strength pareto evolutionary algorithm based on reference direction for multiobjective and many-objective optimization. IEEE Trans. Evolut. Comput. 21(3), 329–346 (2017)
Cheng, R., **, Y., Olhofer, M., et al.: A reference vector guided evolutionary algorithm for many-objective optimization. In: IEEE Transactions on Evolutionary Computation, (2016)
Asafuddoula, M., Ray, T., Sarker, R.: A decomposition-based evolutionary algorithm for many objective optimization. IEEE Trans. Evol. Comput. 19(3), 445–460 (2014)
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)
Britto, A., Mostaghim, S., Pozo, A.: Archive based multi-swarm algorithm for many-objective problems. In: 2014 Brazilian Conference on Intelligent Systems (BRACIS), pp. 79–84. IEEE, (2014)
Cai, X., Li, Y., Fan, Z., et al.: An external archive guided multiobjective evolutionary algorithm based on decomposition for combinatorial optimization. IEEE Trans. Evol. Comput. 19(4), 508–523 (2015)
Yuan, Y., Xu, H., Wang, B., et al.: Balancing convergence and diversity in decomposition-based many-objective optimizers. IEEE Trans. Evolut. Comput. 20(2), 180–198 (2016)
Zhang, X., Tian, Y., **, Y.: A knee point-driven evolutionary algorithm for many-objective optimization. IEEE Trans. Evolut. Comput. 19(6), 761–776 (2014)
Zou, J., Fu, L., Zheng, J., et al.: A many-objective evolutionary algorithm based on rotated grid. Appl. Soft Comput. 67, 596–609 (2018)
Yang, S., Li, M., Liu, X., et al.: A grid-based evolutionary algorithm for many-objective optimization. IEEE Trans. Evolut. Comput. 17(5), 721–736 (2013)
Qi, Y., Ma, X., Liu, F., et al.: Moea/d with adaptive weight adjustment. Evolut. Comput. 22(2), 231–264 (2014)
Liu, H.L., Chen, L., Zhang, Q., et al.: An evolutionary many-objective optimisation algorithm with adaptive region decomposition. In: 2016 IEEE Congress on Evolutionary Computation (CEC), pp. 4763–4769. IEEE, (2016)
Cai, X., Yang, Z., Fan, Z., et al.: Decomposition-based-sorting and angle-based-selection for evolutionary multiobjective and many-objective optimization. IEEE Trans. Cybern. 47(9), 2824–2837 (2017)
He, Z., Yen, G.G.: Diversity improvement in decomposition-based multi-objective evolutionary algorithm for many-objective optimization problems. In: 2014 IEEE International Conference on Systems, Man and Cybernetics (SMC), pp. 2409–2414. IEEE, (2014)
Zhu, C., Cai, X., Fan, Z., et al.: A two-phase many-objective evolutionary algorithm with penalty based adjustment for reference lines. In: IEEE Congress on Evolutionary Computation, pp. 2161–2168. IEEE, (2016)
Chugh, T., **, Y., Miettinen, K., et al.: A surrogate-assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization. IEEE Trans. Evolut. Comput. 22(1), 129–142 (2018)
Zhou, C., Dai, G., Zhang, C., et al.: Entropy based evolutionary algorithm with adaptive reference points for many-objective optimization problems. Inf. Sci. 465, 232–247 (2018)
Wu, M., Li, K., Kwong, S., et al.: Matching-based selection with incomplete lists for decomposition multi-objective optimization. IEEE Trans. Evolut. Comput. 21, 554–568 (2017)
He, Z., Yen, G.G.: Many-objective evolutionary algorithms based on coordinated selection strategy. IEEE Trans. Evolut. Comput. 21(2), 220–233 (2017)
Li, K., Deb, K., Zhang, Q., et al.: An evolutionary many-objective optimization algorithm based on dominance and decomposition. IEEE Trans. Evolut. Comput. 19(5), 694–716 (2015)
Ray, T., Asafuddoula, M., Isaacs, A.A.: Steady state decomposition based quantum genetic algorithm for many objective optimization. In: Evolutionary Computation, pp. 2817–2824. IEEE, (2013)
Laumanns, M., Thiele, L., Deb, K., et al.: Combining convergence and diversity in evolutionary multiobjective optimization. Evolut. Comput. 10(3), 263–282 (2002)
Sato, H., Aguirre, H.E., Tanaka, K.: Self-controlling dominance area of solutions in evolutionary many-objective optimization. Lect. Notes Comput. Sci. 6457(2), 455–465 (2010)
Li, M., Zheng, J., Shen, R., et al.: A grid-based fitness strategy for evolutionary many-objective optimization. In: Proceedings of Genetic and Evolutionary Computation Conference, GECCO 2010, Portland, Oregon, USA, pp. 463–470. (2010)
Pierro, F.D., Khu, S.T., Savic, D.A.: An investigation on preference order ranking scheme for multiobjective evolutionary optimization. IEEE Trans. Evolut. Comput. 11(1), 17–45 (2007)
Farina, M., Amato, P.: A fuzzy definition of optimality for many-criteria optimization problems. IEEE Trans. Syst. Man Cybern. Part A Syst. Hum 34(3), 315–326 (2004)
He, Z., Yen, G.G., Zhang, J.: Fuzzy-based pareto optimality for many-objective evolutionary algorithms. IEEE Trans. Evolut. Comput. 18(2), 269–285 (2014)
Li, M., Zheng, J., Li, K., et al.: Enhancing diversity for average ranking method in evolutionary many-objective optimization. In: Parallel Problem Solving from Nature, PPSN XI, pp. 647–656. Springer, Berlin (2010)
Zou, X., Chen, Y., Liu, M., et al.: A new evolutionary algorithm for solving many-objective optimization problems. IEEE Trans. Syst. Man Cybern. Part B Cybern. Publ. IEEE Syst. Man Cybern. Soc. 38(5), 1402–1412 (2008)
Kukkonen, S., Lampinen, J.: Ranking-dominance and many-objective optimization. In: IEEE Congress on Evolutionary Computation, CEC 2007, pp. 3983–3990. IEEE, (2007)
Yuan, Y., Xu, H., Wang, B., et al.: A new dominance relation-based evolutionary algorithm for many-objective optimization. IEEE Trans. Evolut. Comput. 20(1), 16–37 (2016)
Gong, D.W., Sun, J., Miao, Z.: A set-based genetic algorithm for interval many-objective optimization problems. IEEE Trans. Evolut. Comput. 99, 1 (2016)
Deb, K., Pratap, A., Agarwal, S., et al.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evolut. Comput. 6(2), 182–197 (2002)
Deb, K., Jain, H.: Handling many-objective problems using an improved NSGA-II procedure. In: 2012 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE, (2012)
Das, I., Dennis, J.E.: Normal-boundary intersection: a new method for generating the pareto surface in nonlinear multicriteria optimization problems. SIAM J. Opt. 8(3), 631–657 (2000)
Seada, H., Deb, K.: U-NSGA-III: a unified evolutionary optimization procedure for single, multiple, and many objectives: proof-of-principle results. In: International Conference on Evolutionary Multi-Criterion Optimization, pp. 34–49. Springer, Cham, (2015)
Li, B., Li, J., Tang, K., et al.: An improved two archive algorithm for many-objective optimization. IEEE Trans. Evolut. Comput. 19(4), 524–541 (2015)
Zhao, H., **ao, J.: A new many-objective evolutionary algorithm based on self-adaptive differential evolution. In: Ninth International Conference on Natural Computation, pp. 601–605. IEEE, (2013)
Cheng, J., Yen, G.G., Zhang, G.: A many-objective evolutionary algorithm with enhanced mating and environmental selections. IEEE Trans. Evolut. Comput. 19(4), 592–605 (2015)
Li, M., Yang, S., Liu, X.: Shift-based density estimation for pareto-based algorithms in many-objective optimization. IEEE Trans. Evolut. Comput. 18(3), 348–365 (2014)
Elarbi, M., Bechikh, S., Gupta, A., et al.: A new decomposition-based NSGA-II for many-objective optimization. IEEE Trans. Syst. Man. Cybern. Syst. 48(7), 1191–1210 (2018)
Tanigaki, Y., Narukawa, K., Nojima, Y., et al.: Preference-based NSGA-II for many-objective knapsack problems. In: 15th International Symposium on Soft Computing and Intelligent Systems (SCIS), 2014 Joint 7th International Conference on and Advanced Intelligent Systems (ISIS), pp. 637–642. IEEE, (2014)
Bandyopadhyay, S., Mukherjee, A.: An Algorithm for many-objective optimization with reduced objective computations: a study in differential evolution. IEEE Trans. Evolut. Comput. 19(3), 400–413 (2015)
Murata, T., Taki, A.: Examination of the performance of objective reduction using correlation-based weighted-sum for many objective knapsack problems. In: International Conference on Hybrid Intelligent Systems, pp. 175–180. IEEE, (2010)
Guo, X., Wang, X., Wang, M., et al.: A new objective reduction algorithm for many-objective problems: employing mutual information and clustering algorithm. In: Eighth International Conference on Computational Intelligence and Security, pp. 11–16. IEEE, (2012)
Saxena, D.K., Duro, J.A., Tiwari, A., et al.: Objective reduction in many-objective optimization: linear and nonlinear algorithms. IEEE Trans. Evolut. Comput. 17(1), 77–99 (2013)
Freitas, A.R.R., Fleming, P.J., Guimaraes, F.G.: A non-parametric harmony-based objective reduction method for many-objective optimization. In: 2013 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 651–656, IEEE, (2013)
Pal, M., Saha, S., Bandyopadhyay, S.: Clustering based online automatic objective reduction to aid many-objective optimization. In: IEEE Congress on Evolutionary Computation, pp. 1131–1138. IEEE, (2016)
Li, Y., Liu, H.L., Gu, F. An objective reduction algorithm based on hyperplane approximation for many-objective optimization problems. In: 2016 IEEE Congress on Evolutionary Computation (CEC), pp. 2470–2476. IEEE, (2016)
Yuan, Y., Ong, Y.S., Gupta, A., et al.: Objective reduction in many-objective optimization: evolutionary multiobjective approaches and comprehensive analysis. IEEE Trans. Evolut. Comput. 22(2), 189–210 (2018)
He, Z., Yen, G.G.: Many-objective evolutionary algorithm: objective space reduction and diversity improvement. IEEE Trans. Evolut. Comput. 20(1), 145–160 (2016)
Dai, G., Zhou, C., Wang, M., et al.: Indicator and reference points co-guided evolutionary algorithm for many-objective optimization problems. Knowl.-Based Syst. 140, 50–63 (2018)
Bader, J., Zitzler, E.: HypE: an algorithm for fast hypervolume-based many-objective optimization. Evolut. Comput. 19(1), 45–76 (2011)
Beume, N., Naujoks, B., Emmerich, M.: SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur. J. Oper. Res. 181(3), 1653–1669 (2007)
Yuan, Y., Xu, H., Wang, B.: Evolutionary many-objective optimization using ensemble fitness ranking. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 669–676. ACM, (2014)
**ao, J., Wang, K.: Ranking-based elitist differential evolution for many-objective optimization. In: 2013 5th International Conference on Intelligent Human–Machine Systems and Cybernetics (IHMSC), vol. 1, pp. 310–313. IEEE, (2013)
Li, B., Tang, K., Li, J., et al.: Stochastic ranking algorithm for many-objective optimization based on multiple indicators. IEEE Trans. Evolut. Comput. 20(6), 924–938 (2016)
Li, F., Liu, J., Tan, S., et al.: R2-mopso: a multi-objective particle swarm optimizer based on r2-indicator and decomposition. In: 2015 IEEE Congress on Evolutionary Computation (CEC), pp. 3148–3155. IEEE, (2015)
Gómez, R.H., Coello, C.A.C.: MOMBI: a new metaheuristic for many-objective optimization based on the R2 indicator. In: 2013 IEEE Congress on Evolutionary Computation (CEC), pp. 2488–2495. IEEE, (2013)
Díaz-Manríquez, A., Toscano-Pulido, G., Coello, C.A.C., et al.: A ranking method based on the R2 indicator for many-objective optimization. In: 2013 IEEE Congress on Evolutionary Computation (CEC), pp. 1523–1530. IEEE, (2013)
Deb, K., Thiele, L., Laumanns, M., et al.: Scalable test problems for evolutionary multiobjective optimization. In: Evolutionary Multiobjective Optimization, pp. 105–145, (2006)
Huband, S., Hingston, P., Barone, L., et al.: A review of multiobjective test problems and a scalable test problem toolkit. Evolut. Comput. IEEE Trans. 10(5), 477–506 (2006)
Zitzler, E., Künzli, S.: Indicator-based selection in multiobjective search. In: International Conference on Parallel Problem Solving from Nature, pp. 832–842. Springer, Berlin, (2004)
Deb, K., Mohan, M., Mishra, S.: A fast multi-objective evolutionary algorithm for finding well-spread pareto-optimal solutions. KanGAL Rep. 2003002, 1–18 (2003)
Ishibuchi, H., Masuda, H., Tanigaki, Y., et al.: Difficulties in specifying reference points to calculate the inverted generational distance for many-objective optimization problems. In: IEEE, pp. 170–177 (2015)
Knowles, J., Corne, D.: On metrics for comparing nondominated sets. In: Proceedings of the 2002 Congress on Evolutionary Computation, CEC ‘02, pp. 711–716. IEEE, (2002)
Ishibuchi, H., Masuda, H., Nojima, Y.: A study on performance evaluation ability of a modified inverted generational distance indicator. In: Conference on Genetic and Evolutionary Computation, pp. 695–702. IEEE, (2015)
Williamson, D.F., Parker, R.A., Kendrick, J.S.: The box plot: a simple visual method to interpret data. Ann. Intern. Med. 110(11), 916–921 (1989)
Richtárik, P., Takáč, M.: Parallel coordinate descent methods for big data optimization. Math. Program. 156(1–2), 433–484 (2016)
Jones, J.J.: Earnings management during import relief investigations. J. Account. Res. 29(2), 193–228 (1991)
Demšar, J.: Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res. 7, 1–30 (2006)
Knowles, J., Thiele, L., Zitzler, E.: A tutorial on the performance assessment of stochastic multiobjective optimizers. Tik Rep. 214, 327–332 (2006)
García, S., Molina, D., Lozano, M., et al.: A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 special session on real parameter optimization. J. Heuristics 15(6), 617 (2009)
Acknowledgements
This work was supported by the National Natural Science Foundation Program of China (61572116, 61572117, 61502089) and the Special Fund for Fundamental Research of Central Universities of Northeastern University (N150408001, N161606003).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to juris- 967 dictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Zhao, H., Zhang, C., Ning, J. et al. A comparative study of the evolutionary many-objective algorithms. Prog Artif Intell 8, 15–43 (2019). https://doi.org/10.1007/s13748-019-00174-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13748-019-00174-2