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.
| Original language | English |
|---|---|
| Article number | 8657680 |
| Pages (from-to) | 1-15 |
| Number of pages | 15 |
| Journal | IEEE Transactions on Evolutionary Computation |
| Volume | 24 |
| Issue number | 1 |
| Early online date | 5 Mar 2019 |
| DOIs | |
| Publication status | Published - Feb 2020 |
| Externally published | Yes |
Bibliographical note
Publisher Copyright:© 1997-2012 IEEE.
Funding
This work was supported in part by the National Key Research and Development Program of China under Grant 2017YFC0804002 and Grant 2017YFC0804003, in part by Engineering and Physical Sciences Research Council under Grant EP/J017515/1 and Grant EP/P005578/1, in part by the Program for Guangdong Introducing Innovative and Entrepreneurial Teams under Grant 2017ZT07X386, in part by the Shenzhen Peacock Plan under Grant KQTD2016112514355531, in part by the Science and Technology Innovation Committee Foundation of Shenzhen under Grant ZDSYS201703031748284, in part by the Program for University Key Laboratory of Guangdong Province under Grant 2017KSYS008, in part by the Dean’s Scholarship by Faculty of Engineering and Technology, Liverpool John Moores University, a Newton Research Collaboration Programme under Grant NRCP1617-6-125 delivered by Royal Academy of Engineering, and in part by RSSB-Funded under Grant COF-INP-05. (Danial Yazdani and Mohammad Nabi Omidvar contributed equally to this work.)
Keywords
- Computational resource allocation
- cooperative coevolutionary (CC)
- decomposition
- dynamic optimization problems
- large-scale optimization problems
- multipopulation