On funnel depths and acceptance criteria in stochastic local search

Thomson, Sarah L.; Ochoa, Gabriela

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.

Citation

Thomson, S. L., & Ochoa, G. (2022, July). On funnel depths and acceptance criteria in stochastic local search. Presented at GECCO '22: Genetic and Evolutionary Computation Conference, Boston Massachusetts

• Presentation Conference Type: Conference Paper (published)
• Conference Name: GECCO '22: Genetic and Evolutionary Computation Conference
• Start Date: Jul 9, 2022
• End Date: Jul 13, 2022
• Acceptance Date: Apr 1, 2022
• Online Publication Date: Jul 8, 2022
• Publication Date: 2022
• Deposit Date: Aug 16, 2023
• Publisher: Association for Computing Machinery (ACM)
• Pages: 287-295
• Book Title: GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference
• ISBN: 9781450392372
• DOI: https://doi.org/10.1145/3512290.3528831
• Keywords: Fitness Landscapes, Quadratic Assignment Problem (QAP), Local Optima Networks (LONs), Funnels, Iterated Local Search, Acceptance Criteria
• Public URL: http://researchrepository.napier.ac.uk/Output/3169637