Scaling up Dynamic Optimization Problems: A Divide-and-Conquer Approach

Danial YAZDANI, Mohammad Nabi OMIDVAR, Jurgen BRANKE, Trung Thanh NGUYEN, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

48 Citations (Scopus)

Abstract

Scalability is a crucial aspect of designing efficient algorithms. Despite their prevalence, large-scale dynamic optimization problems are not well studied in the literature. This paper is concerned with designing benchmarks and frameworks for the study of large-scale dynamic optimization problems. We start by a formal analysis of the moving peaks benchmark (MPB) and show its nonseparable nature irrespective of its number of peaks. We then propose a composite MPB suite with exploitable modularity covering a wide range of scalable partially separable functions suitable for the study of large-scale dynamic optimization problems. The benchmark exhibits modularity, heterogeneity, and imbalance features to resemble real-world problems. To deal with the intricacies of large-scale dynamic optimization problems, we propose a decomposition-based coevolutionary framework which breaks a large-scale dynamic optimization problem into a set of lower-dimensional components. A novel aspect of the framework is its efficient bi-level resource allocation mechanism which controls the budget assignment to components and the populations responsible for tracking multiple moving optima. Based on a comprehensive empirical study on a wide range of large-scale dynamic optimization problems with up to 200-D, we show the crucial role of problem decomposition and resource allocation in dealing with these problems. The experimental results clearly show the superiority of the proposed framework over three other approaches in solving large-scale dynamic optimization problems. © 1997-2012 IEEE.
Original languageEnglish
Article number8657680
Pages (from-to)1-15
Number of pages15
JournalIEEE Transactions on Evolutionary Computation
Volume24
Issue number1
Early online date5 Mar 2019
DOIs
Publication statusPublished - Feb 2020
Externally publishedYes

Keywords

  • Computational resource allocation
  • cooperative coevolutionary (CC)
  • decomposition
  • dynamic optimization problems
  • large-scale optimization problems
  • multipopulation

Fingerprint

Dive into the research topics of 'Scaling up Dynamic Optimization Problems: A Divide-and-Conquer Approach'. Together they form a unique fingerprint.

Cite this