Drils revisited
Lorenzo Canonne, Bilel Derbel · Proceedings of the Genetic and Evolutionary Computation Conference · 2022
Designed for graybox optimization problems, the state-of-the-art Drils algorithm (Deterministic Recombination and Iterated Local Search) follows the framework of a hybrid iterated local search by combining the efficient identification of improving moves and the fast recombination of local optima. The Drils algorithm uses a perturbation mechanism in order to feed the graybox crossover with promising local optima. The perturbation is a key element to avoid that the search gets trapped. In this paper, we revisit the Drils algorithm by focusing on two main questions: (i) how the perturbation is performed, and (ii) how strong it should be. We propose two alternative designs of the perturbation within the framework of Drils. The so-obtained algorithms are proved to provide substantial improvements. This is demonstrated based on extensive experiments using a diverse set of NKQ-landscapes, with different degrees of ruggedness, as well as, different dimensions ranging from relatively small to very large. Besides, we provide a comprehensive analysis on the impact of the proposed mechanisms allowing us to highlight the guiding principles for an accurate design and configuration of the perturbation as a function of landscape characteristics.