Adaptive iterated local search for cross-domain optimisation

Citation

Burke E, Gendreau M, Ochoa G & Walker J (2011) Adaptive iterated local search for cross-domain optimisation. In: Krasnogor N & Lanzi P (eds.) GECCO'11 Proceedings of the 13th annual conference on Genetic and Evolutionary Computation. 13th annual conference on Genetic and evolutionary computation, Dublin, Ireland, 12.07.2011-16.07.2011. New York, NY: ACM, pp. 1987-1994. http://dl.acm.org/citation.cfm?doid=2001576.2001843; https://doi.org/10.1145/2001576.2001843

Abstract
We propose two adaptive variants of a multiple neighborhood iterated local search algorithm. These variants employ online learning techniques, also called adaptive operation selection, in order to select which perturbation to apply at each iteration step from a set of available move operators. Using a common software interface (the HyFlex framework), the proposed algorithms are tested across four hard combinatorial optimisation problems: permutation flow shop, 1D bin packing, maximum satisfiability, and personnel scheduling (including instance data from real-world industrial applications). Using the HyFlex framework, exactly the same high level search strategy can be applied to all the domains and instances. Our results confirm that the adaptive variants outperform a baseline iterated local search with uniform random selection of the move operators. We argue that the adaptive algorithms proposed are general yet powerful, and contribute to the goal of increasing the generality and applicability of heuristic search.

Keywords
; Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Artificial Intelligence (incl. Robotics); Processor Architectures; Discrete Mathematics in Computer Science