Which algorithm should I choose: An evolutionary algorithm portfolio approach

Shiu Yin YUEN *, Chi Kin CHOW, Xin ZHANG, Yang LOU

*Corresponding author for this work

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

21 Citations (Scopus)

Abstract

Many good evolutionary algorithms have been proposed in the past. However, frequently, the question arises that given a problem, one is at a loss of which algorithm to choose. In this paper, we propose a novel algorithm portfolio approach to address the above problem for single objective optimization. A portfolio of evolutionary algorithms is first formed. Covariance Matrix Adaptation Evolution Strategy (CMA-ES), History driven Evolutionary Algorithm (HdEA), Particle Swarm Optimization (PSO2011) and Self adaptive Differential Evolution (SaDE) are chosen as component algorithms. Each algorithm runs independently with no information exchange. At any point in time, the algorithm with the best predicted performance is run for one generation, after which the performance is predicted again. The best algorithm runs for the next generation, and the process goes on. In this way, algorithms switch automatically as a function of the computational budget. This novel algorithm is named Multiple Evolutionary Algorithm (MultiEA). The predictor we introduced has the nice property of being parameter-less, and algorithms switch automatically as a function of budget. The following contributions are made: (1) experimental results on 24 benchmark functions show that MultiEA outperforms (i) Multialgorithm Genetically Adaptive Method for Single Objective Optimization (AMALGAM-SO); (ii) Population-based Algorithm Portfolio (PAP); (iii) a multiple algorithm approach which chooses an algorithm randomly (RandEA); and (iv) a multiple algorithm approach which divides the computational budget evenly and execute all algorithms in parallel (ExhEA). This shows that it outperforms existing portfolio approaches and the predictor is functioning well. (2) Moreover, a neck to neck comparison of MultiEA with CMA-ES, HdEA, PSO2011, and SaDE is also made. Experimental results show that the performance of MultiEA is very competitive. In particular, MultiEA, being a portfolio algorithm, is sometimes even better than all its individual algorithms, and has more robust performance. (3) Furthermore, a positive synergic effect is discovered, namely, MultiEA can sometimes perform better than the sum of its individual EAs. This gives interesting insights into why an algorithm portfolio is a good approach. (4) It is found that MultiEA scales as well as the best algorithm in the portfolio. This suggests that MultiEA scales up nicely, which is a desirable algorithmic feature. (5) Finally, the performance of MultiEA is investigated on a real world problem. It is found that MultiEA can select the most suitable algorithm for the problem and is much better than choosing algorithms randomly.

Original languageEnglish
Pages (from-to)654-673
Number of pages20
JournalApplied Soft Computing Journal
Volume40
Early online date21 Dec 2015
DOIs
Publication statusPublished - Mar 2016
Externally publishedYes

Bibliographical note

Funding Information:
The question studied in this paper was raised by Ron S.Y. Hui, a researcher interested in applying evolutionary algorithms to energy and environmental applications, during a causal discussion with the first author. The work described in this paper was supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region , China [Project No. CityU 125313]. Yang Lou was also funded by a Research Studentship from City University of Hong Kong .

Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.

Keywords

  • Algorithm portfolio
  • Multi-method search
  • Performance prediction
  • Real world application
  • Scalability
  • Synergy

Fingerprint

Dive into the research topics of 'Which algorithm should I choose: An evolutionary algorithm portfolio approach'. Together they form a unique fingerprint.

Cite this