Which algorithm should I choose: An evolutionary algorithm portfolio approach

Autor: Xin Zhang, Yang Lou, Shiu Yin Yuen, Chi Kin Chow
Rok vydání: 2016
Předmět:
0209 industrial biotechnology
Freivalds' algorithm
Mathematical optimization
Dinic's algorithm
Computer science
Population-based incremental learning
Population
Evolutionary algorithm
Parallel algorithm
02 engineering and technology
020901 industrial engineering & automation
Algorithmics
0202 electrical engineering
electronic engineering
information engineering
In-place algorithm
Probabilistic analysis of algorithms
CMA-ES
education
Difference-map algorithm
FSA-Red Algorithm
Push–relabel maximum flow algorithm
education.field_of_study
Weighted Majority Algorithm
Competitive analysis
Cultural algorithm
Particle swarm optimization
Hybrid algorithm
Nondeterministic algorithm
Differential evolution
020201 artificial intelligence & image processing
Output-sensitive algorithm
Suurballe's algorithm
Evolution strategy
Algorithm
Software
Zdroj: Applied Soft Computing. 40:654-673
ISSN: 1568-4946
Popis: A novel predictive measure that predicts which algorithm is best at any given point in time. Always select the predicted best algorithm to run for the next generation.The performance of our method is very competitive if viewed as another novel "individual" algorithm.A very interesting positive synergistic effect is found between algorithms in our method.A novel performance evaluation method that makes a lot of sense when one has an absolute maximum number of function evaluations allowed in your application.Application on a Heating Ventilation and Air Conditioning design problem demonstrates that the method can be used to solve real world problems with constraints and that it performs better than choosing an algorithm randomly. 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.
Databáze: OpenAIRE
Externí odkaz: