Top

Progress in Artificial Intelligence

Published in:

04-03-2019 | Review

A comparative study of the evolutionary many-objective algorithms

Authors: Haitong Zhao, Changsheng Zhang, Jiaxu Ning, Bin Zhang, Peng Sun, Yunfei Feng

Published in: Progress in Artificial Intelligence | Issue 1/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article A snapshot on nonstandard supervised learning problems: taxonomy, relationships, problem transformations and algorithm adaptations

next article A review of different cost-based distributed query optimizers

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

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)CrossRef

Srinivas, S.N., Deb, K.: Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolut. Comput. 2(3), 221–248 (1994)CrossRef

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)CrossRef

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)CrossRef

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)CrossRef

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)CrossRef

He, Z., Yen, G.G.: Visualization and performance metric in many-objective optimization. IEEE Trans. Evol. Comput. 20(3), 386–402 (2016)CrossRef

10.

Ibrahim, A., Rahnamayan, S., Martin, M.V., et al.: 3D-RadVis: visualization of Pareto front in many-objective optimization. In: Evolutionary Computation. IEEE, 2016

11.

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)

12.

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)

13.

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)

14.

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)

15.

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)

16.

He, Z., Yen, G.G.: An improved visualization approach in many-objective optimization. In: IEEE Congress on Evolutionary Computation, pp. 1618–1625. IEEE, (2016)

17.

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)CrossRef

18.

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)CrossRefMathSciNet

19.

Cheng, R., Jin, Y., Olhofer, M., et al.: A reference vector guided evolutionary algorithm for many-objective optimization. In: IEEE Transactions on Evolutionary Computation, (2016)

20.

Asafuddoula, M., Ray, T., Sarker, R.: A decomposition-based evolutionary algorithm for many objective optimization. IEEE Trans. Evol. Comput. 19(3), 445–460 (2014)MATHCrossRef

21.

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)CrossRef

22.

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)

23.

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)CrossRef

24.

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)CrossRef

25.

Zhang, X., Tian, Y., Jin, Y.: A knee point-driven evolutionary algorithm for many-objective optimization. IEEE Trans. Evolut. Comput. 19(6), 761–776 (2014)CrossRef

26.

Zou, J., Fu, L., Zheng, J., et al.: A many-objective evolutionary algorithm based on rotated grid. Appl. Soft Comput. 67, 596–609 (2018)CrossRef

27.

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)CrossRef

28.

Qi, Y., Ma, X., Liu, F., et al.: Moea/d with adaptive weight adjustment. Evolut. Comput. 22(2), 231–264 (2014)CrossRef

29.

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)

30.

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)CrossRef

31.

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)

32.

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)

33.

Chugh, T., Jin, 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)CrossRef

34.

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)MathSciNetCrossRef

35.

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)CrossRef

36.

He, Z., Yen, G.G.: Many-objective evolutionary algorithms based on coordinated selection strategy. IEEE Trans. Evolut. Comput. 21(2), 220–233 (2017)CrossRef

37.

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)CrossRef

38.

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)

39.

Laumanns, M., Thiele, L., Deb, K., et al.: Combining convergence and diversity in evolutionary multiobjective optimization. Evolut. Comput. 10(3), 263–282 (2002)CrossRef

40.

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)CrossRef

41.

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)

42.

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)CrossRef

43.

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)CrossRef

44.

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)CrossRef

45.

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)

46.

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)CrossRef

47.

Kukkonen, S., Lampinen, J.: Ranking-dominance and many-objective optimization. In: IEEE Congress on Evolutionary Computation, CEC 2007, pp. 3983–3990. IEEE, (2007)

48.

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)CrossRef

49.

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)

50.

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)CrossRef

51.

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)

52.

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)MathSciNetMATHCrossRef

53.

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)

54.

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)CrossRef

55.

Zhao, H., Xiao, 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)

56.

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)CrossRef

57.

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)CrossRef

58.

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)CrossRef

59.

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)

60.

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)CrossRef

61.

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)

62.

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)

63.

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)CrossRef

64.

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)

65.

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)

66.

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)

67.

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)CrossRef

68.

He, Z., Yen, G.G.: Many-objective evolutionary algorithm: objective space reduction and diversity improvement. IEEE Trans. Evolut. Comput. 20(1), 145–160 (2016)CrossRef

69.

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)CrossRef

70.

Bader, J., Zitzler, E.: HypE: an algorithm for fast hypervolume-based many-objective optimization. Evolut. Comput. 19(1), 45–76 (2011)CrossRef

71.

Beume, N., Naujoks, B., Emmerich, M.: SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur. J. Oper. Res. 181(3), 1653–1669 (2007)MATHCrossRef

72.

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)

73.

Xiao, 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)

74.

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)CrossRef

75.

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)

76.

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)

77.

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)

78.

Deb, K., Thiele, L., Laumanns, M., et al.: Scalable test problems for evolutionary multiobjective optimization. In: Evolutionary Multiobjective Optimization, pp. 105–145, (2006)

79.

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)CrossRef

80.

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)

81.

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)

82.

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)

83.

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)

84.

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)

85.

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)CrossRef

86.

Richtárik, P., Takáč, M.: Parallel coordinate descent methods for big data optimization. Math. Program. 156(1–2), 433–484 (2016)MathSciNetMATHCrossRef

87.

Jones, J.J.: Earnings management during import relief investigations. J. Account. Res. 29(2), 193–228 (1991)MathSciNetCrossRef

88.

Demšar, J.: Statistical comparisons of classifiers over multiple data sets. J. Mach. Learn. Res. 7, 1–30 (2006)MathSciNetMATH

89.

Knowles, J., Thiele, L., Zitzler, E.: A tutorial on the performance assessment of stochastic multiobjective optimizers. Tik Rep. 214, 327–332 (2006)

90.

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)MATHCrossRef

Title: A comparative study of the evolutionary many-objective algorithms
Authors: Haitong Zhao
Changsheng Zhang
Jiaxu Ning
Bin Zhang
Peng Sun
Yunfei Feng
Publication date: 04-03-2019
Publisher: Springer Berlin Heidelberg
Published in: Progress in Artificial Intelligence / Issue 1/2019
Print ISSN: 2192-6352
Electronic ISSN: 2192-6360
DOI: https://doi.org/10.1007/s13748-019-00174-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 1/2019

Gene selection and disease prediction from gene expression data using a two-stage hetero-associative memory

Path planning of a mobile robot in a free-space environment using Q-learning

A snapshot on nonstandard supervised learning problems: taxonomy, relationships, problem transformations and algorithm adaptations

Integrating fitness predator optimizer with multi-objective PSO for dynamic partitional clustering

Fuzzy clustering-based semi-supervised approach for outlier detection in big text data

A review of different cost-based distributed query optimizers

Premium Partner