Local search pivoting rules and the landscape global structure

Citation

Tari S & Ochoa G (2021) Local search pivoting rules and the landscape global structure. In: Chicano F (ed.) GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference. 2021 Genetic and Evolutionary Computation Conference, GECCO 2021, Lille, France, 10.07.2021-14.07.2021. New York: Association for Computing Machinery, Inc, pp. 278-286. https://doi.org/10.1145/3449639.3459295

Abstract
In local search algorithms, the pivoting rule determines which neighboring solution to select and thus strongly influences the behavior of the algorithm and its capacity to sample good-quality local optima. The classical pivoting rules are first and best improvement, with alternative rules such as worst improvement and maximum expansion recently studied on hill-climbing algorithms. This article conducts a thorough empirical comparison of five pivoting rules (best, first, worst, approximated worst and maximum expansion) on two benchmark combinatorial problems, NK landscapes and the unconstrained binary quadratic problem (UBQP), with varied sizes and ruggedness. We present both a performance analysis of the alternative pivoting rules within an iterated local search (ILS) framework and a fitness landscape analysis and visualization using local optima networks. Our results reveal that the performance of the pivoting rules within an ILS framework may differ from their performance as single climbers and that worst improvement and maximum expansion can outperform classical pivoting rules.

Keywords
Local Search; Iterated Local Search; Pivoting Rules; Local Optima Networks

People

Professor Gabriela Ochoa

Professor, Computing Science