Algorithm portfolio for individual-based surrogate-assisted evolutionary algorithms

Tong, Hao; Liu, Jialin; Yao, Xin

10.1145/3321707.3321715

2019

2019 Genetic and Evolutionary Computation Conference, GECCO 2019

943-950

Prague, Czech republic

1515 BROADWAY, NEW YORK, NY 10036-9998 USA

Association for Computing Machinery, Inc

Surrogate-assisted evolutionary algorithms (SAEAs) are powerful optimisation tools for computationally expensive problems (CEPs). However, a randomly selected algorithm may fail in solving unknown problems due to no free lunch theorems, and it will cause more computational resource if we re-run the algorithm or try other algorithms to get a much solution, which is more serious in CEPs. In this paper, we consider an algorithm portfolio for SAEAs to reduce the risk of choosing an inappropriate algorithm for CEPs. We propose two portfolio frameworks for very expensive problems in which the maximal number of fitness evaluations is only 5 times of the problem's dimension. One framework named Par-IBSAEA runs all algorithm candidates in parallel and a more sophisticated framework named UCB-IBSAEA employs the Upper Confidence Bound (UCB) policy from reinforcement learning to help select the most appropriate algorithm at each iteration. An effective reward definition is proposed for the UCB policy. We consider three state-of-the-art individual-based SAEAs on different problems and compare them to the portfolios built from their instances on several benchmark problems given limited computation budgets. Our experimental studies demonstrate that our proposed portfolio frameworks significantly outperform any single algorithm on the set of benchmark problems.
© 2019 Association for Computing Machinery.

Algorithm portfolio surrogate model evolutionary algorithm computationally expensive problem

第一 ; 通讯

英语

EI ; CPCI-S

National Basic Research Program of China (973 Program)[2017YFC0804003]

Computer Science ; Operations Research & Management Science

Computer Science, Artificial Intelligence ; Operations Research & Management Science

WOS:000523218400111

20193807458895

Benchmarking ; Budget control ; Computation theory ; Iterative methods ; Reinforcement learning

Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory:721.1 ; Artificial Intelligence:723.4 ; Numerical Methods:921.6

EV Compendex

Shenzhen Key Laboratory of Computational Intelligence, University Key Laboratory of Evolving Intelligent Systems of Guangdong Province, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, China

Tong, Hao,Liu, Jialin,Yao, Xin. Algorithm portfolio for individual-based surrogate-assisted evolutionary algorithms[C]. 1515 BROADWAY, NEW YORK, NY 10036-9998 USA:Association for Computing Machinery, Inc,2019:943-950.