A Primary Theoretical Study on Decomposition-Based Multiobjective Evolutionary Algorithms

Decomposition-based multiobjective evolutionary algorithms (MOEAs) have been studied a lot and have been widely and successfully used in practice. However, there are no related theoretical studies on this kind of MOEAs. In this paper, we theoretically analyze the MOEAs based on decomposition. First,...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on evolutionary computation 2016-08, Vol.20 (4), p.563-576
Main Authors: Li, Yuan-Long, Zhou, Yu-Ren, Zhan, Zhi-Hui, Zhang, Jun
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Complexity
Complexity theory
Constants
Decomposition
Decomposition-based multiobjective evolutionary algorithms (MOEAs)
Evolutionary algorithms
Evolutionary computation
Optimization
Pareto optimality
Polynomials
Run time (computers)
Runtime
runtime analysis
Sociology
Statistics
theoretical study
Citations: Items that this one cites
Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Decomposition-based multiobjective evolutionary algorithms (MOEAs) have been studied a lot and have been widely and successfully used in practice. However, there are no related theoretical studies on this kind of MOEAs. In this paper, we theoretically analyze the MOEAs based on decomposition. First, we analyze the runtime complexity with two basic simple instances. In both cases the Pareto front have oneto-one map to the decomposed subproblems or not. Second, we analyze the runtime complexity on two difficult instances with bad neighborhood relations in fitness space or decision space. Our studies show that: 1) in certain cases, polynomialsized evenly distributed weight parameters-based decomposition cannot map each point in a polynomial sized Pareto front to a subproblem; 2) an ideal serialized algorithm can be very efficient on some simple instances; 3) the standard MOEA based on decomposition can benefit a runtime cut of a constant fraction from its neighborhood coevolution scheme; and 4) the standard MOEA based on decomposition performs well on difficult instances because both the Pareto domination-based and the scalar subproblem-based search schemes are combined in a proper way.
ISSN:1089-778X
1941-0026
DOI:10.1109/TEVC.2015.2501315