Skip header navigation

University of Stirling

×

Conference Proceeding

Clarifying the Difference in Local Optima Network Sampling Algorithms

Citation
Thomson SL, Ochoa G & Verel S (2019) Clarifying the Difference in Local Optima Network Sampling Algorithms. In: Liefooghe A & Paquete L (eds.) Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, 11452. The 19th European Conference on Evolutionary Computation in Combinatorial Optimisation, Leipzig, Germany, 24.04.2019-26.04.2019. Cham, Switzerland: Springer International Publishing, pp. 163-178. https://doi.org/10.1007/978-3-030-16711-0_11

Abstract
We conduct the first ever statistical comparison between two Local Optima Network (LON) sampling algorithms. These methodologies attempt to capture the connectivity in the local optima space of a fitness landscape. One sampling algorithm is based on a random-walk snowballing procedure, while the other is centred around multiple traced runs of an Iterated Local Search. Both of these are proposed for the Quadratic Assignment Problem (QAP), making this the focus of our study. It is important to note the sampling algorithm frameworks could easily be modified for other domains. In our study descriptive statistics for the obtained search space samples are contrasted and commented on. The LON features are also used in linear mixed models and random forest regression for predicting heuristic optimisation performance of two prominent heuristics for the QAP on the underlying combinatorial problems. The model results are then used to make deductions about the sampling algorithms’ utility. We also propose a specific set of LON metrics for use in future predictive models alongside previously-proposed network metrics, demonstrating the payoff in doing so.

Keywords
Combinatorial fitness landscapes; Local optima networks; Quadratic Assignment Problem

StatusPublished
Author(s)Thomson, Sarah L; Ochoa, Gabriela; Verel, Sébastien
FundersEPSRC Engineering and Physical Sciences Research Council
Title of seriesLecture Notes in Computer Science
Number in series11452
Publication date31/12/2019
Publication date online28/03/2019
URLhttp://hdl.handle.net/1893/29137
Related URLshttp://hdl.handle.net/11667/128
PublisherSpringer International Publishing
Place of publicationCham, Switzerland
ISSN of series0302-9743
ISBN9783030148119
eISBN9783030148126
ConferenceThe 19th European Conference on Evolutionary Computation in Combinatorial Optimisation
Conference locationLeipzig, Germany
Dates
Scroll back to the top