On Funnel Depths and Acceptance Criteria in Stochastic Local Search

Citation

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. https://dl.acm.org/doi/abs/10.1145/3512290.3528831; https://doi.org/10.1145/3512290.3528831

Abstract
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.

People

Professor Gabriela Ochoa

Professor, Computing Science