Running Time Analysis of MOEA/D with Crossover on Discrete Optimization Problem

Authors

  • Zhengxin Huang Sun Yat-sen University
  • Yuren Zhou Sun Yat-sen University
  • Zefeng Chen Sun Yat-sen University
  • Xiaoyu He Sun Yat-sen University

DOI:

https://doi.org/10.1609/aaai.v33i01.33012296

Abstract

Decomposition-based multiobjective evolutionary algorithms (MOEAs) are a class of popular methods for solving 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 a running time analysis of a simple MOEA with crossover based on the MOEA/D framework (MOEA/D-C) on four discrete optimization problems. Our rigorous theoretical analysis shows that the MOEA/D-C can obtain a set of Pareto optimal solutions to cover the Pareto front of these problems in expected running time apparently lower than the one without crossover. Moreover, the MOEA/D-C only needs to decompose an MOP into a few scalar optimization subproblems according to several simple weight vectors. This result suggests that the use of crossover in decomposition-based MOEA can simplify the setting of weight vector for different problems and make the algorithm more efficient. This study theoretically explains why some decomposition-based MOEAs work well in computational experiments and provides insights in design of MOEAs for MOPs in future research.

Downloads

Published

2019-07-17

How to Cite

Huang, Z., Zhou, Y., Chen, Z., & He, X. (2019). Running Time Analysis of MOEA/D with Crossover on Discrete Optimization Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2296-2303. https://doi.org/10.1609/aaai.v33i01.33012296

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization