A Bayesian Restarting Approach to Algorithm Selection

摘要

A Bayesian algorithm selection framework for black box optimization problems is proposed. A set of benchmark problems is used for training. The performance of a set of algorithms on the problems is recorded. In the beginning, an algorithm is randomly selected to run on the given unknown problem. A Bayesian approach is used to measure the similarity between problems. The most similar problem to the given problem is selected. Then the best algorithm for solving it is suggested for the second run. The process repeats until n algorithms have been run. The best solution out of n runs is recorded. We have experimentally evaluated the property and performance of the framework. Conclusions are (1) it can identify the most similar problem efficiently; (2) it benefits from a restart mechanism. It performs better when more knowledge is learned. Thus it is a good algorithm selection framework.