A Runtime Analysis of Typical Decomposition Approaches in MOEA/D Framework for Many-objective Optimization Problems

Huang, Zhengxin; Zhou, Yuren; Luo, Chuan; Lin, Qingwei

doi:10.24963/ijcai.2021/232

A Runtime Analysis of Typical Decomposition Approaches in MOEA/D Framework for Many-objective Optimization Problems

Zhengxin Huang, Yuren Zhou, Chuan Luo, Qingwei Lin

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 1682-1688.

https://doi.org/10.24963/ijcai.2021/232

Keywords

Heuristic Search and Game Playing: Combinatorial Search and Optimisation
Heuristic Search and Game Playing: Heuristic Search
Heuristic Search and Game Playing: Evaluation and Analysis

Abstract

Decomposition approach is an important component in multi-objective evolutionary algorithm based on decomposition (MOEA/D), which is a popular method for handing many-objective optimization problems (MaOPs). This paper presents a theoretical analysis on the convergence ability of using the typical weighted sum (WS), Tchebycheff (TCH) or penalty-based boundary intersection (PBI) approach in a basic MOEA/D for solving two benchmark MaOPs. The results show that using WS, the algorithm can always find an optimal solution for any subproblem in polynomial expected runtime. In contrast, the algorithm needs at least exponential expected runtime for some subproblems if using TCH or PBI. Moreover, our analyses discover an obvious shortcoming of using WS, that is, the optimal solutions of different subproblems are easily corresponding to the same solution. In addition, this analysis indicates that if using PBI, a small value of the penalty parameter is a good choice for faster converging to the Pareto front, but it may lose the diversity. This study reveals some optimization behaviors of using three typical decomposition approaches in the well-known MOEA/D framework for solving MaOPs.

Zhengxin Huang, Yuren Zhou, Chuan Luo, and Qingwei Lin. 2021. A Runtime Analysis of Typical Decomposition Approaches in MOEA/D Framework for Many-objective Optimization Problems. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 1682–1688. https://doi.org/10.24963/ijcai.2021/232

@inproceedings{ijcai2021p232,
  title     = {A Runtime Analysis of Typical Decomposition Approaches in MOEA/D Framework for Many-objective Optimization Problems},
  author    = {Huang, Zhengxin and Zhou, Yuren and Luo, Chuan and Lin, Qingwei},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {1682--1688},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/232},
  url       = {https://doi.org/10.24963/ijcai.2021/232},
}

TY  - CPAPER
TI  - A Runtime Analysis of Typical Decomposition Approaches in MOEA/D Framework for Many-objective Optimization Problems
AU  - Huang, Zhengxin
AU  - Zhou, Yuren
AU  - Luo, Chuan
AU  - Lin, Qingwei
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 1682
EP  - 1688
DO  - 10.24963/ijcai.2021/232
UR  - https://doi.org/10.24963/ijcai.2021/232
ER  -