Population-based algorithm portfolios for numerical optimization

Fei PENG, Ke TANG, Guoliang CHEN, Xin YAO

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

157 Citations (Scopus)

Abstract

In this paper, we consider the scenario that a population-based algorithm is applied to a numerical optimization problem and a solution needs to be presented within a given time budget. Although a wide range of population-based algorithms, such as evolutionary algorithms, particle swarm optimizers, and differential evolution, have been developed and studied under this scenario, the performance of an algorithm may vary significantly from problem to problem. This implies that there is an inherent risk associated with the selection of algorithms. We propose that, instead of choosing an existing algorithm and investing the entire time budget in it, it would be less risky to distribute the time among multiple different algorithms. A new approach named population-based algorithm portfolio (PAP), which takes multiple algorithms as its constituent algorithms, is proposed based upon this idea. PAP runs each constituent algorithm with a part of the given time budget and encourages interaction among the constituent algorithms with a migration scheme. As a general framework rather than a specific algorithm, PAP is easy to implement and can accommodate any existing population-based search algorithms. In addition, a metric is also proposed to compare the risks of any two algorithms on a problem set. We have comprehensively evaluated PAP via investigating 11 instantiations of it on 27 benchmark functions. Empirical results have shown that PAP outperforms its constituent algorithms in terms of solution quality, risk, and probability of finding the global optimum. Further analyses have revealed that the advantages of PAP are mostly credited to the synergy between constituent algorithms, which should complement each other either over a set of problems, or during different stages of an optimization process. © 2010 IEEE.
Original languageEnglish
Article number5439827
Pages (from-to)782-800
Number of pages19
JournalIEEE Transactions on Evolutionary Computation
Volume14
Issue number5
Early online date30 Mar 2010
DOIs
Publication statusPublished - Oct 2010
Externally publishedYes

Bibliographical note

This paper was partially supported by the National Natural Science Foundation of China under Grants 60533020, 60802036 and U0835002, the Fund for Foreign Scholars in University Research and Teaching Programs in China under Grant B07033, and the Engineering and Physical Science Research Council in U.K. under Grant EP/D052785/1 on “SEBASE: Software Engineering By Automated Search.”

Keywords

  • Algorithm portfolios
  • global optimization
  • metaheuristic algorithms
  • numerical optimization
  • population-based algorithms

Fingerprint

Dive into the research topics of 'Population-based algorithm portfolios for numerical optimization'. Together they form a unique fingerprint.

Cite this