A Survey on Search Strategy of Evolutionary Multi-Objective Optimization Algorithms
Source abstract
Abstract
The multi-objective optimization problem is difficult to solve with conventional optimization methods and algorithms because there are conflicts among several optimization objectives and functions. Through the efforts of researchers and experts from different fields for the last 30 years, the research and application of multi-objective evolutionary algorithms (MOEA) have made excellent progress in solving such problems. MOEA has become one of the primary used methods and technologies in the realm of multi-objective optimization. It is also a hotspot in the evolutionary computation research community. This survey provides a comprehensive investigation of MOEA algorithms that have emerged in recent decades and summarizes and classifies the classical MOEAs by evolutionary mechanism from the viewpoint of the search strategy. This paper divides them into three categories considering the search strategy of MOEA, i.e., decomposition-based MOEA algorithms, dominant relation-based MOEA algorithms, and evaluation index-based MOEA algorithms. This paper selects the relevant representative algorithms for a detailed summary and analysis. As a prospective research direction, we propose to combine the chaotic evolution algorithm with these representative search strategies for improving the search capability of multi-objective optimization algorithms. The capability of the new multi-objective evolutionary algorithm has been discussed, which further proposes the future research direction of MOEA. It also lays a foundation for the application and development of MOEA with these prospective works in the future.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Advanced Multi-Objective Optimization Algorithms · Metaheuristic Optimization Algorithms Research · Building Energy and Comfort Optimization
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Graduate School of Computer Science and Engineering, University of Aizu, Aizuwakamatsu 965-8580, Japan
Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China
References (100+)
Show source-provided references
1. Evolutionary multi-objective optimization: A historical view of the field10.1109/MCI.2006.1597059 ↗
2. Deb, K. (2011). Multi-Objective Evolutionary Optimisation for Product Design and Manufacturing, Springer.
3. Multi-Objective Neural Evolutionary Algorithm for Combinatorial Optimization Problems10.1109/TNNLS.2021.3105937 ↗
4. Schaffer, J.D. (1985). Some Experiments in Machine Learning Using Vector Evaluated Genetic Algorithms, Vanderbilt University. Technical Report.
5. Multiobjective optimization using nondominated sorting in genetic algorithms10.1162/evco.1994.2.3.221 ↗
6. Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization
7. Horn, J., Nafpliotis, N., and Goldberg, D.E. (1994, January 27–29). A niched Pareto genetic algorithm for multiobjective optimization. Proceedings of the First IEEE Conference on Evolutionary Computation, Orlando, FL, USA.
8. A two-archive algorithm with decomposition and fitness allocation for multi-modal multi-objective optimization10.1016/j.ins.2021.05.075 ↗
9. Zitzler, E., and Thiele, L. (1998). An evolutionary algorithm for multiobjective optimization: The strength Pareto approach. TIK Rep., 43.
10. Zitzler, E., Laumanns, M., and Thiele, L. (2001). SPEA2: Improving the strength Pareto evolutionary algorithm. TIK Rep., 103.
11. Approximating the nondominated front using the Pareto archived evolution strategy10.1162/106365600568167 ↗
12. Corne, D.W., Knowles, J.D., and Oates, M.J. (2000, January 18–20). The Pareto envelope-based selection algorithm for multiobjective optimization. Proceedings of the International Conference on Parallel Problem Solving from Nature, Paris, France.10.1007/3-540-45356-3_82 ↗
13. Corne, D.W., Jerram, N.R., Knowles, J.D., and Oates, M.J. (2001, January 7–11). PESA-II: Region-based selection in evolutionary multiobjective optimization. Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, San Francisco, CA, USA.
14. Erickson, M., Mayer, A., and Horn, J. (2001, January 7–9). The niched Pareto genetic algorithm 2 applied to the design of groundwater remediation systems. Proceedings of the International Conference on Evolutionary Multi-Criterion Optimization, Zurich, Switzerland.10.1007/3-540-44719-9_48 ↗
15. Coello, C.A., and Pulido, G.T. (2001, January 7–11). Multiobjective optimization using a micro-genetic algorithm. Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, San Francisco, CA, USA.
16. A fast and elitist multiobjective genetic algorithm: NSGA-II10.1109/4235.996017 ↗
17. A survey of multi-objective optimization in wireless sensor networks: Metrics, algorithms, and open problems10.1109/COMST.2016.2610578 ↗
18. Coello, C.C., and Lechuga, M.S. (2002, January 12–17). MOPSO: A proposal for multiple objective particle swarm optimization. Proceedings of the 2002 Congress on Evolutionary Computation, CEC’02, Honolulu, HI, USA.
19. Multiobjective immune algorithm with nondominated neighbor-based selection10.1162/evco.2008.16.2.225 ↗
20. MOEA/D: A multiobjective evolutionary algorithm based on decomposition10.1109/TEVC.2007.892759 ↗
21. Survey of multi-objective optimization methods for engineering10.1007/s00158-003-0368-6 ↗
22. Evolutionary multi-objective optimization: Some current research trends and topics that remain to be explored10.1007/s11704-009-0005-7 ↗
23. Multiobjective optimal control for wastewater treatment process using adaptive MOEA/D10.1007/s10489-018-1319-7 ↗
24. Oliveira, S.R.D.M. (2005). Data Transformation for Privacy-Preserving Data Mining, University of Alberta.
25. de la Iglesia, B., and Reynolds, A. (2005, January 27–28). The use of meta-heuristic algorithms for data mining. Proceedings of the 2005 International Conference on Information and Communication Technologies, Karachi, Pakistan.
26. Chiba, A., Fukao, T., Ichikawa, O., Oshima, M., Takemoto, M., and Dorrell, D.G. (2005). Magnetic Bearings and Bearingless Drives, Elsevier.10.1016/B978-075065727-3/50006-7 ↗
27. Konstantinidis, A., Charalambous, C., Zhou, A., and Zhang, Q. (2010, January 18–23). Multi-objective mobile agent-based sensor network routing using MOEA/D. Proceedings of the IEEE Congress on Evolutionary Computation, Barcelona, Spain.10.1109/CEC.2010.5586431 ↗
28. Zhang, Q., Li, H., Maringer, D., and Tsang, E. (2010, January 18–23). MOEA/D with NBI-style Tchebycheff approach for portfolio management. Proceedings of the IEEE Congress on Evolutionary Computation, Barcelona, Spain.10.1109/CEC.2010.5586185 ↗
29. Shan, J., and Nagashima, F. (2001, January 18–20). Biologically Inspired Spinal locomotion Controller for Humanoid Robot. Proceedings of the 19th Annual Conference of Robotics Society of Japan, Tokyo, Japan.
30. Arias-Montano, A., Coello Coello, C.A., and Mezura-Montes, E. (2011). Computational Optimization, Methods and Algorithms, Springer.
31. A multi-object genetic algorithm of QoS routing
32. Jourdan, L., Corne, D., Savic, D., and Walters, G. (2005, January 9–11). Preliminary investigation of the ‘learnable evolution model’ for faster/better multiobjective water systems design. Proceedings of the Evolutionary Multi-Criterion Optimization: Third International Conference, EMO 2005, Guanajuato, Mexico.10.1007/978-3-540-31880-4_58 ↗
33. Diseño de sistemas hidráulicos bajo criterios de optimización de puntos de pliegue y múltiples criterios
34. Multi-objective evolutionary design and knowledge discovery of logic circuits based on an adaptive genetic algorithm10.1007/s10710-006-9005-7 ↗
35. FGAs-based data association algorithm for multi-sensor multi-target tracking10.1016/S1000-9361(11)60180-5 ↗
36. A multi-objective approach for the motion planning of redundant manipulators10.1016/j.asoc.2011.11.006 ↗
37. Esquivel, G., and Messmacher, M. (2002). Sources of Regional (Non) Convergence in Mexico, El Colegio de México y Banco de Mexico.
38. Many-objective optimization and visual analytics reveal key trade-offs for London’s water supply10.1016/j.jhydrol.2015.11.003 ↗
39. A multi-objective evolutionary algorithm based QoS routing in wireless mesh networks10.1016/j.asoc.2015.12.007 ↗
40. Multi-objective energy-efficient dense deployment in wireless sensor networks using a hybrid problem-specific MOEA/D10.1016/j.asoc.2011.02.031 ↗
41. A Comprehensive Review on Multi-objective Optimization Techniques: Past, Present and Future10.1007/s11831-022-09778-9 ↗
42. Mezura-Montes, E., Reyes-Sierra, M., and Coello, C.A.C. (2008). Multi-objective optimization using differential evolution: A survey of the state-of-the-art. Adv. Differ. Evol., 173–196.10.1007/978-3-540-68830-3_7 ↗
43. Multimodal multi-objective optimization: Comparative study of the state-of-the-art10.1016/j.swevo.2023.101253 ↗
44. Many-objective evolutionary algorithms: A survey10.1145/2792984 ↗
45. Methods that optimize multi-objective problems: A survey and experimental evaluation10.1109/ACCESS.2020.2989219 ↗
46. Methods for multi-objective optimization: An analysis10.1016/j.ins.2014.08.071 ↗
47. Evolutionary large-scale multi-objective optimization: A survey
48. Multi-objective metaheuristics for discrete optimization problems: A review of the state-of-the-art10.1016/j.asoc.2020.106382 ↗
49. A survey of evolutionary algorithms for multi-objective optimization problems with irregular pareto fronts10.1109/JAS.2021.1003817 ↗
50. Coello, C.A.C., Brambila, S.G., Gamboa, J.F., and Tapia, M.G.C. (2021). Black Box Optimization, Machine Learning, and No-Free Lunch Theorems, Springer.
51. Nature-inspired optimization algorithms: Challenges and open problems10.1016/j.jocs.2020.101104 ↗
52. Constrained multimodal multi-objective optimization: Test problem construction and algorithm design10.1016/j.swevo.2022.101209 ↗
53. Investment portfolio optimization by applying a genetic algorithm-based approach10.15388/Ekon.2017.2.10998 ↗
54. Multi-objective meta-heuristics: An overview of the current state-of-the-art10.1016/S0377-2217(01)00123-0 ↗
55. Coupling economic multi-objective optimization and multiple design options: A business-oriented approach to size an off-grid hybrid microgrid10.1016/j.ijepes.2020.106686 ↗
56. An enhanced fast non-dominated solution sorting genetic algorithm for multi-objective problems10.1016/j.ins.2021.11.052 ↗
57. Stochastic multi-objective optimization: A survey on non-scalarizing methods10.1007/s10479-013-1369-5 ↗
58. Genetic diversity as an objective in multi-objective evolutionary algorithms10.1162/106365603766646816 ↗
59. Plane Separation: A method to solve dynamic multi-objective optimization problems with incorporated preferences10.1016/j.future.2019.10.039 ↗
60. Yu, J., Wang, Z., and Pei, Y. (July, January 28). Cooperative Chaotic Evolution. Proceedings of the 2021 IEEE Congress on Evolutionary Computation (CEC), Krakow, Poland.10.1109/CEC45853.2021.9504825 ↗
61. May, R.M. (2004). The Theory of Chaotic Attractors, Springer.
62. A two-dimensional mapping with a strange attractor10.1007/BF01608556 ↗
63. Analytic study of chaos of the tent map: Band structures, power spectra, and critical behaviors10.1007/BF01011583 ↗
64. Hilborn, R.C. (2000). Chaos and Nonlinear Dynamics: An Introduction for Scientists and Engineers, Oxford University Press on Demand.10.1093/acprof:oso/9780198507239.001.0001 ↗
65. Pei, Y. (2020, January 11–14). Chaotic evolution algorithm with elite strategy in single-objective and multi-objective optimization. Proceedings of the 2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Toronto, ON, Canada.10.1109/SMC42975.2020.9283144 ↗
66. Pei, Y., and Hao, J. (August, January 27). Non-dominated sorting and crowding distance based multi-objective chaotic evolution. Proceedings of the International Conference on Swarm Intelligence, Fukuoka, Japan.
67. Multiobjective evolutionary algorithm based on multimethod with dynamic resources allocation10.1016/j.asoc.2015.08.059 ↗
68. A multi-objective perspective on performance assessment and automated selection of single-objective optimization algorithms10.1016/j.asoc.2019.105901 ↗
69. The weighted sum method for multi-objective optimization: New insights10.1007/s00158-009-0460-7 ↗
70. Omran, S.M., El-Behaidy, W.H., and Youssif, A.A. (2020, January 16–17). Decomposition based multi-objectives evolutionary algorithms challenges and circumvention. Proceedings of the Intelligent Computing: Proceedings of the 2020 Computing Conference, London, UK.10.1007/978-3-030-52246-9_6 ↗
71. Du, K.L., and Swamy, M.N.S. (2016). Techniques and Algorithms Inspired by Nature, Springer.
72. MOEA/D with adaptive weight adjustment10.1162/EVCO_a_00109 ↗
73. Zhang, Q., Liu, W., and Li, H. (2009, January 18–21). The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances. Proceedings of the 2009 IEEE Congress on Evolutionary Computation, Trondheim, Norway.10.1109/CEC.2009.4982949 ↗
74. Nebro, A.J., and Durillo, J.J. (2010, January 18–22). A study of the parallelization of the multi-objective metaheuristic MOEA/D. Proceedings of the International Conference on Learning and Intelligent Optimization, Venice, Italy.10.1007/978-3-642-13800-3_32 ↗
75. Performance evaluation of evolutionary multiobjective optimization algorithms for multiobjective fuzzy genetics-based machine learning10.1007/s00500-010-0669-9 ↗
76. MOEA/D-ACO: A multiobjective evolutionary algorithm using decomposition and antcolony10.1109/TSMCB.2012.2231860 ↗
77. An overview of population-based algorithms for multi-objective optimisation10.1080/00207721.2013.823526 ↗
78. A comparative review between Genetic Algorithm use in composite optimisation and the state-of-the-art in evolutionary computation10.1016/j.compstruct.2019.111739 ↗
79. Hull geometry optimisation of wave energy converters: On the choice of the objective functions and the optimisation formulation10.1016/j.apenergy.2021.117153 ↗
80. Multiobjective optimization with an adaptive weight determination scheme using the concept of hyperplane10.1002/nme.6013 ↗
81. Bio-inspired computation: Where we stand and what’s next10.1016/j.swevo.2019.04.008 ↗
82. Hard turning behavior improvement using NSGA-II and PSO-NN hybrid model10.1007/s00170-016-8479-6 ↗
83. A comprehensive review on NSGA-II for multi-objective combinatorial optimization problems10.1109/ACCESS.2021.3070634 ↗
84. Xue, Y., Li, M., and Liu, X. (2020, January 27–29). Angle-based crowding degree estimation for many-objective optimization. Proceedings of the International Symposium on Intelligent Data Analysis, Konstanz, Germany.10.1007/978-3-030-44584-3_45 ↗
85. Optimal maintenance planning and resource allocation for wind farms based on non-dominated sorting genetic algorithm-II10.1016/j.renene.2020.10.125 ↗
86. Coello Coello, C.A. (2017, January 18–20). Recent results and open problems in evolutionary multiobjective optimization. Proceedings of the Theory and Practice of Natural Computing: 6th International Conference, TPNC 2017, Prague, Czech Republic.
87. Schott, J.R. (1995). Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. [Ph.D. Thesis, Massachusetts Institute of Technology].
88. Menchaca-Mendez, A., and Coello Coello, C.A. (April, January 29). GD-MOEA: A new multi-objective evolutionary algorithm based on the generational distance indicator. Proceedings of the International Conference on Evolutionary Multi-Criterion Optimization, Guimaraes, Portugal.
89. Ishibuchi, H., Masuda, H., Tanigaki, Y., and Nojima, Y. (April, January 29). Modified distance calculation in generational distance and inverted generational distance. Proceedings of the International Conference on Evolutionary Multi-Criterion Optimization, Guimaraes, Portugal.
90. SMS-EMOA: Multiobjective selection based on dominated hypervolume10.1016/j.ejor.2006.08.008 ↗
91. Zitzler, E., and Künzli, S. (2004, January 18–22). Indicator-based selection in multiobjective search. Proceedings of the International Conference on Parallel Problem Solving From Nature, Birmingham, UK.10.1007/978-3-540-30217-9_84 ↗
92. Region of Interest-Based Parameter Optimization for Approximate Image Processing on FPGAs
93. Evolutionary multiobjective optimization: Open research areas and some challenges lying ahead10.1007/s40747-019-0113-4 ↗
94. A review of uncertainty analysis in building energy assessment10.1016/j.rser.2018.05.029 ↗
95. Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions10.1162/106365605774666895 ↗
96. Sato, H., Aguirre, H.E., and Tanaka, K. (2010, January 1–4). Self-controlling dominance area of solutions in evolutionary many-objective optimization. Proceedings of the Simulated Evolution and Learning: 8th International Conference, SEAL 2010, Kanpur, India.10.1007/978-3-642-17298-4_49 ↗
97. Mkaouer, M.W., Kessentini, M., Bechikh, S., Deb, K., and Ó Cinnéide, M. (2014, January 12–16). High dimensional search-based software engineering: Finding tradeoffs among 15 objectives for automating software refactoring using NSGA-III. Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, Vancouver, BC, Canada.10.1145/2576768.2598366 ↗
98. Hughes, E.J. (2007, January 25–28). MSOPS-II: A general-purpose many-objective optimiser. Proceedings of the 2007 IEEE Congress on Evolutionary Computation, Singapore.10.1109/CEC.2007.4424985 ↗
99. HypE: An algorithm for fast hypervolume-based many-objective optimization10.1162/EVCO_a_00009 ↗
100. Shift-based density estimation for Pareto-based algorithms in many-objective optimization10.1109/TEVC.2013.2262178 ↗