EUVIMEDEUVIMED entdecken
Crossref

Runtime Analysis of Typical Decomposition Approaches in MOEA/D for Many-Objective Optimization Problems

Zhengxin Huang iD, Yuren Zhou, Zefeng Chen, Qianlong Dang

Evolutionary Computation · 2026

DOI: 10.1162/evco_a_00364 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Evolutionary Computation, 2026. Verfasst von Zhengxin Huang und 3 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, Youjiang Medical University for Nationalities, Baise 533000, China. Hauptthemen laut MEDLINE: Algorithms. Die Arbeit nennt 52 Literaturangaben.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Decomposition-based multiobjective evolutionary algorithms (MOEAs) are popular methods utilized to address many-objective optimization problems (MaOPs). These algorithms decompose the original MaOP into several scalar optimization subproblems, and solve them to obtain a set of solutions to approximate the Pareto front (PF). The decomposition approach is an important component in them. This paper presents a runtime analysis of a MOEA based on the classic decomposition framework using the typical weighted sum (WS), Tchebycheff (TCH), and penalty-based boundary intersection (PBI) approaches to obtain an optimal solution for any subproblem of two pseudo-Boolean benchmark MaOPs, namely mLOTZ and mCOCZ. Due to the complexity and limitation of the theoretical analysis techniques, the analyzed algorithm employs 1-bit mutation to generate offspring individuals. The results indicate that when using WS, the analyzed algorithm can consistently find an optimal solution for every subproblem, which is located in the PF, in polynomial expected runtime. In contrast, the algorithm requires at least exponential expected runtime (with respect to the number of objectives m) for certain subproblems when using TCH or PBI, even though the landscapes of all objective functions in the two benchmarks are strictly monotone. Moreover, this analysis reveals a drawback of using WS: the optimal solutions obtained by solving subproblems are more easily mapped to the same point in the PF, compared to the case of using TCH. When using PBI, a smaller value of the penalty parameter is a good choice for faster convergence to the PF but may compromise diversity. To further understand the impact of these approaches in practical algorithms, numerical experiments on using bit-wise mutation to generate offspring individuals are conducted. The findings of this study may be helpful for designing more efficient decomposition approaches for MOEAs in future research.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsGenetic AlgorithmsComputer SimulationSoft Computing

Stichwörter der Autor:innen

MOEA/DRuntime analysisdecomposition methodmany-objective optimization problemmultiobjective evolutionary algorithm.

Autor:innen und Institutionen

  • Department of Computer Science, Youjiang Medical University for Nationalities, Baise 533000, China.
  • Key Laboratory of Molecular Pathology in Tumors of Guangxi Higher Education Institutions, Baise 533000, China huangzhx26@mail2.sysu.edu.cn.
  • School of Software Engineering, Sun Yat-sen University, Zhuhai 519082, China yurenzhou@mail.sysu.edu.cn.
  • School of Artificial Intelligence, Sun Yat-sen University, Zhuhai 519082, China chenzef5@mail.sysu.edu.cn.
  • College of Science, Northwest A&F University, Yangling 712100, China xidianqldang@163.com.

ORCID-Profile: Zhengxin Huang

Zitieren

APA

Huang, Z., Zhou, Y., Chen, Z., & Dang, Q. (2026). Runtime Analysis of Typical Decomposition Approaches in MOEA/D for Many-Objective Optimization Problems. Evolutionary Computation. https://doi.org/10.1162/evco_a_00364

Vancouver

Huang Z, Zhou Y, Chen Z, Dang Q. Runtime Analysis of Typical Decomposition Approaches in MOEA/D for Many-Objective Optimization Problems. Evolutionary Computation. 2026. doi:10.1162/evco_a_00364

BibTeX
@article{Huang2026,
  author = {Huang, Zhengxin and Zhou, Yuren and Chen, Zefeng and Dang, Qianlong},
  title = {Runtime Analysis of Typical Decomposition Approaches in MOEA/D for Many-Objective Optimization Problems},
  journal = {Evolutionary Computation},
  year = {2026},
  doi = {10.1162/evco_a_00364}
}
Kostenlos starten →