All Outputs (33)

Universally Hard Hamiltonian Cycle Problem Instances (2022)
Presentation / Conference Contribution
Sleegers, J., Thomson, S. L., & van den Berg, D. (2022, November). Universally Hard Hamiltonian Cycle Problem Instances. Presented at ECTA 2022 : 14th International Conference on Evolutionary Computation Theory and Applications, Valletta, Malta

In 2021, evolutionary algorithms found the hardest-known yes and no instances for the Hamiltonian cycle problem. These instances, which show regularity patterns, require a very high number of recursions for the best exact backtracking algorithm (Vand... Read More about Universally Hard Hamiltonian Cycle Problem Instances.

Fractal Dimension and Perturbation Strength: A Local Optima Networks View (2022)
Presentation / Conference Contribution
Thomson, S. L., Ochoa, G., & Verel, S. (2022, September). Fractal Dimension and Perturbation Strength: A Local Optima Networks View

We study the effect of varying perturbation strength on the fractal dimensions of Quadratic Assignment Problem (QAP) fitness landscapes induced by iterated local search (ILS). Fitness landscapes are represented as Local Optima Networks (LONs), which... Read More about Fractal Dimension and Perturbation Strength: A Local Optima Networks View.

On funnel depths and acceptance criteria in stochastic local search (2022)
Presentation / Conference Contribution
Thomson, S. L., & Ochoa, G. (2022). On funnel depths and acceptance criteria in stochastic local search. In GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference (287-295). https://doi.org/10.1145/3512290.3528831

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... Read More about On funnel depths and acceptance criteria in stochastic local search.

The fractal geometry of fitness landscapes at the local optima level (2020)
Journal Article
Thomson, S. L., Ochoa, G., & Verel, S. (2022). The fractal geometry of fitness landscapes at the local optima level. Natural Computing, 21(2), 317-333. https://doi.org/10.1007/s11047-020-09834-y

A local optima network (LON) encodes local optima connectivity in the fitness landscape of a combinatorial optimisation problem. Recently, LONs have been studied for their fractal dimension. Fractal dimension is a complexity index where a non-integer... Read More about The fractal geometry of fitness landscapes at the local optima level.

Inferring Future Landscapes: Sampling the Local Optima Level (2020)
Journal Article
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

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 comp... Read More about Inferring Future Landscapes: Sampling the Local Optima Level.

The Local Optima Level in Chemotherapy Schedule Optimisation (2020)
Presentation / Conference Contribution
Thomson, S. L., & Ochoa, G. (2020, April). The Local Optima Level in Chemotherapy Schedule Optimisation. Presented at EvoCOP 2020: Evolutionary Computation in Combinatorial Optimization, Seville, Spain

In this paper a multi-drug Chemotherapy Schedule Optimisation Problem (CSOP) is subject to Local Optima Network (LON) analysis. LONs capture global patterns in fitness landscapes. CSOPs have not previously been subject to fitness landscape analysis.... Read More about The Local Optima Level in Chemotherapy Schedule Optimisation.

Clarifying the Difference in Local Optima Network Sampling Algorithms (2019)
Presentation / Conference Contribution
Thomson, S. L., Ochoa, G., & Verel, S. (2019). Clarifying the Difference in Local Optima Network Sampling Algorithms. In Evolutionary Computation in Combinatorial Optimization. EvoCOP 2019 (163-178). https://doi.org/10.1007/978-3-030-16711-0_11

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... Read More about Clarifying the Difference in Local Optima Network Sampling Algorithms.

Multifractality and dimensional determinism in local optima networks (2018)
Presentation / Conference Contribution
Thomson, S. L., Verel, S., Ochoa, G., Veerapen, N., & Cairns, D. (2018, July). Multifractality and dimensional determinism in local optima networks. Presented at GECCO '18: Genetic and Evolutionary Computation Conference, Kyoto, Japan

We conduct a study of local optima networks (LONs) in a search space using fractal dimensions. The fractal dimension (FD) of these networks is a complexity index which assigns a non-integer dimension to an object. We propose a fine-grained approach t... Read More about Multifractality and dimensional determinism in local optima networks.

On the Fractal Nature of Local Optima Networks (2018)
Presentation / Conference Contribution
Thomson, S. L., Verel, S., Ochoa, G., Veerapen, N., & McMenemy, P. (2018). On the Fractal Nature of Local Optima Networks. In Evolutionary Computation in Combinatorial Optimization. EvoCOP 2018 (18-33). https://doi.org/10.1007/978-3-319-77449-7_2

A Local Optima Network represents fitness landscape connectivity within the space of local optima as a mathematical graph. In certain other complex networks or graphs there have been recent observations made about inherent self-similarity. An object... Read More about On the Fractal Nature of Local Optima Networks.

The effect of landscape funnels in QAPLIB instances (2017)
Presentation / Conference Contribution
Thomson, S. L., Ochoa, G., Daolio, F., & Veerapen, N. (2017, July). The effect of landscape funnels in QAPLIB instances. Presented at GECCO '17: Genetic and Evolutionary Computation Conference, Berlin, Germany

The effectiveness of common metaheuristics on combinatorial optimisation problems can be limited by certain characteristics of the fitness landscape. We use the local optima network model to compress the 'inherent structure' of a problem space into a... Read More about The effect of landscape funnels in QAPLIB instances.

Comparing communities of optima with funnels in combinatorial fitness landscapes (2017)
Presentation / Conference Contribution
Thomson, S. L., Daolio, F., & Ochoa, G. (2017, July). Comparing communities of optima with funnels in combinatorial fitness landscapes. Presented at GECCO '17: Genetic and Evolutionary Computation Conference, Berlin, Germany

The existence of sub-optimal funnels in combinatorial fitness landscapes has been linked to search difficulty. The exact nature of these structures --- and how commonly they appear --- is not yet fully understood. Improving our understanding of funne... Read More about Comparing communities of optima with funnels in combinatorial fitness landscapes.

A Bi-Level Approach to Vehicle Fleet Reduction: Successful Case Study in Community Healthcare
Presentation / Conference Contribution
Brownlee, A. E., Thomson, S. L., & Oladapo, R. (2024, July). A Bi-Level Approach to Vehicle Fleet Reduction: Successful Case Study in Community Healthcare. Paper presented at The Genetic and Evolutionary Computation Conference (GECCO), Melbourne, Australia

We report on a case study application of metaheuristics with Argyll and Bute Health and Social Care Partnership in the West of Scotland. The Partnership maintains a fleet of pool vehicles that are available to service visits of staff to locations acr... Read More about A Bi-Level Approach to Vehicle Fleet Reduction: Successful Case Study in Community Healthcare.

Shape of the Waterfall: Solvability Transitions in the QAP
Presentation / Conference Contribution
Akova, S., Thomson, S. L., Verel, S., Rifki, O., & van den Berg, D. (2024, April). Shape of the Waterfall: Solvability Transitions in the QAP. Presented at EvoStar 2024, Aberyswyth, Wales

We consider a special formulation of the quadratic assignment problem (QAP): QAP-SAT, where the QAP is composed of smaller sub-problems or clauses which can be satisfied. A recent study showed a steep drop in solvability in relation to the number of... Read More about Shape of the Waterfall: Solvability Transitions in the QAP.