Back to Search Start Over

A Primary Theoretical Study on Decomposition-Based Multiobjective Evolutionary Algorithms.

Authors :
Li, Yuan-Long
Zhou, Yu-Ren
Zhan, Zhi-Hui
Zhang, Jun
Source :
IEEE Transactions on Evolutionary Computation; Aug2016, Vol. 20 Issue 4, p563-576, 14p
Publication Year :
2016

Abstract

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 one-to-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, polynomial-sized 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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
1089778X
Volume :
20
Issue :
4
Database :
Complementary Index
Journal :
IEEE Transactions on Evolutionary Computation
Publication Type :
Academic Journal
Accession number :
117145767
Full Text :
https://doi.org/10.1109/TEVC.2015.2501315