Comparison of MOEA/D Variants on Benchmark Problems

Abstract

Given that the definition of the multi-objective optimization problem is raised when number of objectives is increased in number at the optimization problem, where not only the number of objectives but also the computational resources which are needed to solve the problem, is also more desired. Therefore, novel approaches had required to solve multi-objective optimization problem in a reasonable time. One of this novel approach is utilization of the decomposition method with the evolutionary algorithm/operator. This algorithm was called multi-objective evolutionary algorithm based on decomposition (MOEA/D). Later on, variants have been proposed to improve the performance of the MOEA/D algorithm. However, a general comparison between these variants has needed for demonstrate the performance of these algorithm. For this reason, in this research the variants of MOEA/D algorithms have implemented on benchmark problems (DTLZ and MaF) and the performances has compared with each other. Two metrics had selected to evaluate/compare the performances of the variants. The metrics are IGD and Spread metrics. The results at the end of the implementations suggest that adaptive weighting idea is the most promising idea to increase the performance of the MOEA/D algorithm.

Keywords

• multi-objective optimization
• evolutionary algorithm
• decomposition
• evolutionary algorithms

References

1. [1] Q. Zhang and H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition,” IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712-731, 2007.
2. [2] Y. Qi, X. Ma, F. Liu, L. Jiao, J. Sun, and J. Wu, “MOEA/D with adaptive weight adjustment,” Evolutionary Computation, vol. 22, no. 2, pp. 231-264, 2014.
3. [3] H. Li, Q. Zhang, and J. Deng, “Biased multiobjective optimization and decomposition algorithm,” IEEE Transactions on Cybernetics, vol. 47, no. 1, pp. 52-66, 2017.
4. [4] K. Li, K. Deb, Q. Zhang, and S. Kwong, “An evolutionary many-objective optimization algorithm based on dominance and decomposition,” IEEE Transactions Evolutionary Computation, vol. 19, no. 5, pp. 694-716, 2015.
5. [5] Q. Zhu, Q. Zhang, and Q. Lin, “A constrained multi-objective evolutionary algorithm with detect-and-escape strategy,” IEEE Transactions on Evolutionary Computation, vol. 24, no. 5, pp. 938-947, 2020.
6. [6] H. Li and Q. Zhang, “Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 13, no. 2, pp. 284-302, 2009.
7. [7] Q. Zhang, W. Liu, and H. Li, “The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances,” Proceedings of the IEEE Congress on Evolutionary Computation, pp. 203-208, 2009.
8. [8] Y. Yuan, H. Xu, B. Wang, B. Zhang, and X. Yao, “Balancing convergence and diversity in decomposition-based many-objective optimizers,” IEEE Transactions on Evolutionary Computation, vol. 20, no. 2, pp. 180-198, 2016.

9. [9] K. Li, A. Fialho, S. Kwong, and Q. Zhang, “Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition,” IEEE Transactions on Evolutionary Computation, vol. 18, no. 1, pp. 114-130, 2014.
10. [10] Q. Zhang, W. Liu, E. Tsang, and B. Virginas, “Expensive multiobjective optimization by MOEA/D with Gaussian process model,” IEEE Transactions on Evolutionary Computation, vol. 14, no. 3, pp. 456-474, 2010.
11. [11] K. Li, A. Fialho, S. Kwong, and Q. Zhang, “Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition,” IEEE Transactions on Evolutionary Computation, vol. 18, no. 1, pp. 114-130, 2010.
12. [12] H. Liu, F. Gu, and Q. Zhang, “Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems,” IEEE Transactions on Evolutionary Computation, vol. 18, no. 3, pp. 450-455, 2014.
13. [13] S. B. Gee, K. C. Tan, V. A. Shim, and N. R. Pal, “Online diversity assessment in evolutionary multiobjective optimization: A geometrical perspective,” IEEE Transactions on Evolutionary Computation, vol. 19, no. 4, pp. 542-559, 2015.
14. [14] R. Wang, Q. Zhang, and T. Zhang, “Decomposition-based algorithms using Pareto adaptive scalarizing methods,” IEEE Transactions on Evolutionary Computation, vol. 20, no. 6, pp. 821-837, 2016.
15. [15] K. Li, Q. Zhang, S. Kwong, M. Li, and R. Wang, “Stable matching-based selection in evolutionary multiobjective optimization,” IEEE Transactions on Evolutionary Computation, vol. 18, no. 6, pp. 909-923, 2014.
16. [16] L. R. de Farias, A. F. Araujo, “A decomposition-based many-objective evolutionary algorithm updating weights when required,” Swarm and Evolutionary Computation, 2021.
17. [17] L. R. C. Farias and A. F. R. Araujo, “Many-objective evolutionary algorithm based on decomposition with random and adaptive weights,” In Proceedings of the IEEE International Conference on Systems, Mans and Cybernetics, 2019.
18. [18] K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, “Scalable test problems for evolutionary multiobjective optimization,” Evolutionary Multiobjective Optimization Theoretical Advances and Applications, pp. 105-145, 2005.
19. [19] R. Cheng, M. Li, Y. Tian, X. Zhang, S. Yang, Y. Jin, and X. Yao, “A Benchmark Test Suit for Evolutionary Many-objective Optimization,” Complex Intell. Syst. Vol. 3, pp. 67–81, 2017.
20. [20] H. Ishibuchi H. Masuda Y. Tanigaki and Y. Nojima “Modified distance calculation in generational distance and inverted generational distance,” in International Conference on Evolutionary Multi-Criterion Optimization. Springer, 2015, pp. 110–125.
21. [21] M. Ehrgott, “Approximation algorithms for combinatorial multicriteria optimization problems,” International Transactions in Operational Research, vol. 7, no. 531, 2000