Abstract
A commonly used strategy for improving optimization algorithms is to restart the algorithm when it is believed to be trapped in an inferior part of the search space. Building on the recent success of BET-AND-RUN approaches for restarted local search solvers, we introduce a more generic version that makes use of performance prediction. It is our goal to obtain the best possible results within a given time budget t using a given black-box optimization algorithm. If no prior knowledge about problem features and algorithm behavior is available, the question about how to use the time budget most efficiently arises. We first start k = 1 independent runs of the algorithm during an initialization budget t1 < t, pause these runs, then apply a decision maker D to choose 1 = m < k runs from them (consuming t2 = 0 time units in doing so), and then continue these runs for the remaining t3 = t-t1-t2 time units. In previous BET-AND-RUN strategies, the decision maker D = currentBest would simply select the run with the best-so-far results at negligible time. We propose using more advanced methods to discriminate between “good” and “bad” sample runs with the goal of increasing the correlation of the chosen run with the a-posteriori best one. In over 157 million experiments, we test different approaches to predict which run may yield the best results if granted the remaining budget. We show (1) that the currentBest method is indeed a very reliable and robust baseline approach, and (2) that our approach can yield better results than the previous methods.
Original language | English |
---|---|
Title of host publication | Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence |
Editors | Pascal Van Hentenryck, Zhi-Hua Zhou |
Place of Publication | Palo Alto CA USA |
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Pages | 2395-2402 |
Number of pages | 8 |
ISBN (Electronic) | 9781577358091 |
DOIs | |
Publication status | Published - 2019 |
Externally published | Yes |
Event | AAAI Conference on Artificial Intelligence 2019 - Honolulu, United States of America Duration: 27 Jan 2019 → 1 Feb 2019 Conference number: 33rd https://aaai.org/Conferences/AAAI-19/ |
Conference
Conference | AAAI Conference on Artificial Intelligence 2019 |
---|---|
Abbreviated title | AAAI 2019 |
Country/Territory | United States of America |
City | Honolulu |
Period | 27/01/19 → 1/02/19 |
Internet address |