[Submitted on 4 May 2020]

Download PDF

Abstract: Not all generate-and-test search algorithms are created equal. Bayesian
Optimization (BO) invests a lot of computation time to generate the candidate
solution that best balances the predicted value and the uncertainty given all
previous data, taking increasingly more time as the number of evaluations
performed grows. Evolutionary Algorithms (EA) on the other hand rely on search
heuristics that typically do not depend on all previous data and can be done in
constant time. Both the BO and EA community typically assess their performance
as a function of the number of evaluations. However, this is unfair once we
start to compare the efficiency of these classes of algorithms, as the overhead
times to generate candidate solutions are significantly different. We suggest
to measure the efficiency of generate-and-test search algorithms as the
expected gain in the objective value per unit of computation time spent. We
observe that the preference of an algorithm to be used can change after a
number of function evaluations. We therefore propose a new algorithm, a
combination of Bayesian optimization and an Evolutionary Algorithm, BEA for
short, that starts with BO, then transfers knowledge to an EA, and subsequently
runs the EA. We compare the BEA with BO and the EA. The results show that BEA
outperforms both BO and the EA in terms of time efficiency, and ultimately
leads to better performance on well-known benchmark objective functions with
many local optima. Moreover, we test the three algorithms on nine test cases of
robot learning problems and here again we find that BEA outperforms the other
algorithms.