Dr Sarah L. Thomson S.Thomson4@napier.ac.uk
Lecturer
Clarifying the Difference in Local Optima Network Sampling Algorithms
Thomson, Sarah L.; Ochoa, Gabriela; Verel, Sébastien
Authors
Gabriela Ochoa
Sébastien Verel
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.
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 19th European Conference, EvoCOP 2019 |
Start Date | Apr 24, 2019 |
End Date | Aug 26, 2019 |
Online Publication Date | Mar 28, 2019 |
Publication Date | 2019 |
Deposit Date | Aug 16, 2023 |
Publisher | Springer |
Pages | 163-178 |
Series Title | Lecture Notes in Computer Science |
Series Number | 11452 |
Book Title | Evolutionary Computation in Combinatorial Optimization. EvoCOP 2019 |
ISBN | 978-3-030-16710-3 |
DOI | https://doi.org/10.1007/978-3-030-16711-0_11 |
Additional Information | The paper “Clarifying the Difference in Local Optima Network Sampling Algorithms” contained an error. The correct text was added at the end of the correction chapter. The correction to this chapter is available at https://doi.org/10.1007/978-3-030-16711-0_14 |
You might also like
Comparing communities of optima with funnels in combinatorial fitness landscapes
(2017)
Presentation / Conference Contribution
Multifractality and dimensional determinism in local optima networks
(2018)
Presentation / Conference Contribution
On the Fractal Nature of Local Optima Networks
(2018)
Presentation / Conference Contribution
The effect of landscape funnels in QAPLIB instances
(2017)
Presentation / Conference Contribution
Unexplained Fluctuations in Particle Swarm Optimisation Performance with Increasing Problem Dimensionality
(2023)
Presentation / Conference Contribution
Downloadable Citations
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search