Paper Info
Title
On Funnel Depths and Acceptance Criteria in Stochastic Local Search
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.
Year
DOI
Venue
2022
10.1145/3512290.3528831
PROCEEDINGS OF THE 2022 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'22)
Keywords
DocType
Citations 
Fitness Landscapes, Quadratic Assignment Problem (QAP), Local Optima Networks (LONs), Funnels, Iterated Local Search, Acceptance Criteria
Conference
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Sarah L. Thomson100.34
Gabriela Ochoa201.01