Time efficiency in optimization with a bayesian-Evolutionary algorithm

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 BO and EA community typically assess their performance as a function of the number of evaluations, i.e., data efficiency. 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, i.e., time efficiency. To the time-efficient search algorithm, we therefore propose a new algorithm, a combination of BO and an EA, BEA for short, that starts with BO, then transfers knowledge to an EA, and subsequently runs the EA. We compare the BEA with BO, the EA, Differential Evolution (DE), and Particle Swarm Optimization (PSO). The results show that BEA outperforms BO, the EA, DE and PSO in terms of time efficiency, and ultimately leads to better performance on well-known benchmark objective functions with many local optima. Moreover, we test BEA, BO, and the EA on nine test cases of robot learning problems and here again we find that BEA outperforms the other algorithms.