期刊
IEEE TRANSACTIONS ON CYBERNETICS
卷 51, 期 10, 页码 5130-5141出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TCYB.2019.2930979
关键词
Optimization; Upper bound; Computer science; Indexes; Cybernetics; Evolutionary computation; Crossover; MOEA/D; multiobjective optimization problem (MOP); running time analysis
类别
资金
- National Natural Science Foundation of China [61773410, 61673403, 61703183, 61562071]
- Public Welfare Technology Application Research Plan Project of Zhejiang Province [LGG19F030010]
Decomposition-based multiobjective evolutionary algorithms have been widely studied and successfully applied in practice. This paper presents a running time analysis of a simple MOEA with mutation and crossover, showing that the use of crossover can significantly improve the efficiency of the algorithm.
Decomposition-based multiobjective evolutionary algorithms (MOEAs) are a class of popular methods for solving the multiobjective optimization problems (MOPs), and have been widely studied in numerical experiments and successfully applied in practice. However, we know little about these algorithms from the theoretical aspect. In this paper, we present running time analysis of a simple MOEA with mutation and crossover based on the MOEA/D framework (MOEA/D-C) on five pseudo-Boolean functions. Our rigorous theoretical analysis shows that by properly setting the number of subproblems, the upper bounds of expected running time of MOEA/D-C obtaining a set of solutions to cover the Pareto fronts (PFs) of these problems are apparently lower than those of the one with mutation-only (MOEA/D-M). Moreover, to effectively obtain a set of solutions to cover the PFs of these problem, MOEA/D-C only needs to decompose these MOPs into several subproblems with a set of simple weight vectors while MOEA/D-M needs to find Omega(n) optimally decomposed weight vectors. This result suggests that the use of crossover in decomposition-based MOEA can simplify the setting of weight vectors for different problems and make the algorithm more efficient. This paper provides some insights into the working principles of MOEA/D and explains why some existing decomposition-based MOEAs work well in computational experiments.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据