Skip to main content

Research Repository

Advanced Search

Inferring Future Landscapes: Sampling the Local Optima Level

Thomson, Sarah L.; Ochoa, Gabriela; Verel, Sébastien; Veerapen, Nadarajen

Authors

Gabriela Ochoa

Sébastien Verel

Nadarajen Veerapen



Abstract

Connection patterns among Local Optima Networks (LONs) can inform heuristic design for optimisation. LON research has predominantly required complete enumeration of a fitness landscape, thereby restricting analysis to problems diminutive in size compared to real-life situations. LON sampling algorithms are therefore important. In this article, we study LON construction algorithms for the Quadratic Assignment Problem (QAP). Using machine learning, we use estimated LON features to predict search performance for competitive heuristics used in the QAP domain. The results show that by using random forest regression, LON construction algorithms produce fitness landscape features which can explain almost all search variance. We find that LON samples better relate to search than enumerated LONs do. The importance of fitness levels of sampled LONs in search predictions is crystallised. Features from LONs produced by different algorithms are combined in predictions for the first time, with promising results for this “super-sampling”: a model to predict tabu search success explained 99% of variance. Arguments are made for the use-case of each LON algorithm and for combining the exploitative process of one with the exploratory optimisation of the other.

Citation

Thomson, S. L., Ochoa, G., Verel, S., & Veerapen, N. (2020). Inferring Future Landscapes: Sampling the Local Optima Level. Evolutionary Computation, 28(4), 621-641. https://doi.org/10.1162/evco_a_00271

Journal Article Type Article
Acceptance Date Feb 12, 2020
Online Publication Date Dec 1, 2020
Publication Date 2020
Deposit Date Aug 16, 2023
Print ISSN 1063-6560
Electronic ISSN 1530-9304
Publisher MIT Press
Peer Reviewed Peer Reviewed
Volume 28
Issue 4
Pages 621-641
DOI https://doi.org/10.1162/evco_a_00271
Keywords Combinatorial optimisation, fitness landscapes, local optima networks, funnel landscapes



You might also like



Downloadable Citations