Conference Proceeding

Local search pivoting rules and the landscape global structure



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.

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.

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

Publication date30/06/2021
Publication date online26/06/2021
PublisherAssociation for Computing Machinery, Inc
Place of publicationNew York
Conference2021 Genetic and Evolutionary Computation Conference, GECCO 2021
Conference locationLille, France

People (1)


Professor Gabriela Ochoa

Professor Gabriela Ochoa

Professor, Computing Science

Research centres/groups