MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition

TLDR

Decomposition is a fundamental strategy in traditional multiobjective optimization but has not yet been widely adopted in multiobjective evolutionary optimization. This study proposes the MOEA/D algorithm and examines its performance with small populations, scalability, and sensitivity. MOEA/D decomposes a multiobjective problem into scalar subproblems optimized simultaneously, using only neighboring subproblems, which lowers per‑generation computational complexity compared to MOGLS and NSGA‑II. Experiments demonstrate that MOEA/D with simple decomposition outperforms or matches MOGLS and NSGA‑II on 0‑1 knapsack and continuous problems, handles disparately‑scaled objectives via normalization, and produces evenly distributed solutions for 3‑objective test instances with advanced decomposition.

Abstract

Decomposition is a basic strategy in traditional multiobjective optimization. However, it has not yet been widely used in multiobjective evolutionary optimization. This paper proposes a multiobjective evolutionary algorithm based on decomposition (MOEA/D). It decomposes a multiobjective optimization problem into a number of scalar optimization subproblems and optimizes them simultaneously. Each subproblem is optimized by only using information from its several neighboring subproblems, which makes MOEA/D have lower computational complexity at each generation than MOGLS and nondominated sorting genetic algorithm II (NSGA-II). Experimental results have demonstrated that MOEA/D with simple decomposition methods outperforms or performs similarly to MOGLS and NSGA-II on multiobjective 0-1 knapsack problems and continuous multiobjective optimization problems. It has been shown that MOEA/D using objective normalization can deal with disparately-scaled objectives, and MOEA/D with an advanced decomposition method can generate a set of very evenly distributed solutions for 3-objective test instances. The ability of MOEA/D with small population, the scalability and sensitivity of MOEA/D have also been experimentally investigated in this paper.