Conference Proceeding

On Funnel Depths and Acceptance Criteria in Stochastic Local Search



Thomson S & Ochoa G (2022) On Funnel Depths and Acceptance Criteria in Stochastic Local Search. In: GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference. Genetic and Evolutionary Computation Conference (GECCO) 2022, Boston, USA, 09.07.2022-13.07.2022. New York: ACM, pp. 287-295.;

We propose looking at the phenomenon of fitness landscape funnels in terms of their depth. In particular, we examine how the depth of funnels in Local Optima Networks (LONs) of benchmark Quadratic Assignment Problem instances relate to metaheuristic performance. Three distinct iterated local search (ILS) acceptance strategies are considered: better-or-equal (standard), annealing-like, and restart. Funnel measurements are analysed for their connection to ILS performance on the underlying combinatorial problems. We communicate the findings through hierarchical clustering of LONs, network visualisations, subgroup analysis, correlation analysis, and Random Forest regression models. The results show that funnel depth is associated with search difficulty, and that there is an interplay between funnel structure and acceptance strategy. Standard and annealing acceptance work better than restart on both deep-funnel and shallow-funnel problems; standard acceptance is the best strategy when optimal funnel(s) are deep, while annealing acceptance is superior when they are shallow. Regression models including funnel depth measurements could explain up to 96% of ILS runtime variance (with annealing-like acceptance). The runtime of ILS with restarts was less explainable using funnel features.

Publication date31/12/2022
Publication date online08/07/2022
Publisher URL
Place of publicationNew York
ConferenceGenetic and Evolutionary Computation Conference (GECCO) 2022
Conference locationBoston, USA

People (2)


Professor Gabriela Ochoa
Professor Gabriela Ochoa

Professor, Computing Science

Dr Sarah Thomson
Dr Sarah Thomson

Lecturer in Computing Science, Computing Science and Mathematics - Division