A Primary Theoretical Study on Decomposition-Based Multiobjective Evolutionary Algorithms

doi:10.1109/TEVC.2015.2501315

Return

A Primary Theoretical Study on Decomposition-Based Multiobjective Evolutionary Algorithms

2016-08-01

PRE

DOI：10.1109/TEVC.2015.2501315

Original

Original request for help

Save

Abstract

En 中文

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, 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.

Keywords:

Decomposition-based multiobjective evolutionary algorithms (MOEAs)

runtime analysis

theoretical study

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.