Skip to main content

Research Repository

Advanced Search

Outputs (33)

Temporal True and Surrogate Fitness Landscape Analysis for Expensive Bi-Objective Optimisation Expensive Bi-Objective (2024)
Presentation / Conference Contribution
Rodriguez, C. J., Thomson, S. L., Alderliesten, T., & Bosman, P. A. N. (2024, July). Temporal True and Surrogate Fitness Landscape Analysis for Expensive Bi-Objective Optimisation Expensive Bi-Objective. Presented at Genetic and Evolutionary Computation Conference (GECCO 2024), Melbourne, Australia

Many real-world problems have expensive-to-compute fitness functions and are multi-objective in nature. Surrogate-assisted evolutionary algorithms are often used to tackle such problems. Despite this, literature about analysing the fitness landscapes... Read More about Temporal True and Surrogate Fitness Landscape Analysis for Expensive Bi-Objective Optimisation Expensive Bi-Objective.

Understanding fitness landscapes in morpho-evolution via local optima networks (2024)
Presentation / Conference Contribution
Thomson, S. L., Le Goff, L., Hart, E., & Buchanan, E. (2024, July). Understanding fitness landscapes in morpho-evolution via local optima networks. Presented at Genetic and Evolutionary Computation Conference (GECCO 2024), Melbourne, Australia

Morpho-Evolution (ME) refers to the simultaneous optimisation of a robot's design and controller to maximise performance given a task and environment. Many genetic encodings have been proposed which are capable of representing design and control. Pre... Read More about Understanding fitness landscapes in morpho-evolution via local optima networks.

Factors Impacting Landscape Ruggedness in Control Problems: a Case Study (2024)
Presentation / Conference Contribution
Saliby, M. E., Medvet, E., Nadizar, G., Salvato, E., & Thomson, S. L. (2024, September). Factors Impacting Landscape Ruggedness in Control Problems: a Case Study. Presented at WIVACE 2024 (XVIII International Workshop on Artificial Life and Evolutionary Computation), Namur, Belgium

Understanding fitness landscapes in evolutionary robotics (ER) can provide valuable insights into the considered robotic problems as well as into the strategies found by evolutionary algorithms (EAs) to address them, ultimately guiding practitioners... Read More about Factors Impacting Landscape Ruggedness in Control Problems: a Case Study.

A Deep Dive into Effects of Structural Bias on CMA-ES Performance along Affine Trajectories (2024)
Presentation / Conference Contribution
van Stein, N., Thomson, S. L., & Kononova, A. V. (2024, September). A Deep Dive into Effects of Structural Bias on CMA-ES Performance along Affine Trajectories. Paper presented at Parallel Problem Solving from Nature (PPSN) 2024, Hagenberg, Austria

To guide the design of better iterative optimisation heuristics, it is imperative to understand how inherent structural biases within algorithm components affect the performance on a wide variety of search landscapes. This study explores the impact o... Read More about A Deep Dive into Effects of Structural Bias on CMA-ES Performance along Affine Trajectories.

Entropy, Search Trajectories, and Explainability for Frequency Fitness Assignment (2024)
Presentation / Conference Contribution
Thomson, S. L., Ochoa, G., van den Berg, D., Liang, T., & Weise, T. (2024, September). Entropy, Search Trajectories, and Explainability for Frequency Fitness Assignment. Presented at Parallel Problem Solving from Nature (PPSN 2024), Hagenberg, Austria

Local optima are a menace that can trap optimisation processes. Frequency fitness assignment (FFA) is an concept aiming to overcome this problem. It steers the search towards solutions with rare fitness instead of high-quality fitness. FFA-based algo... Read More about Entropy, Search Trajectories, and Explainability for Frequency Fitness Assignment.

Explaining evolutionary feature selection via local optima networks (2024)
Presentation / Conference Contribution
Adair, J., Thomson, S. L., & Brownlee, A. E. (2024, July). Explaining evolutionary feature selection via local optima networks. Presented at ACM Genetic and Evolutionary Computation Conference (GECCO) 2024, Melbourne, Australia

We analyse fitness landscapes of evolutionary feature selection to obtain information about feature importance in supervised machine learning. Local optima networks (LONs) are a compact representation of a landscape, and can potentially be adapted fo... Read More about Explaining evolutionary feature selection via local optima networks.

Exploring the use of fitness landscape analysis for understanding malware evolution (2024)
Presentation / Conference Contribution
Babaagba, K., Murali, R., & Thomson, S. L. (2024, July). Exploring the use of fitness landscape analysis for understanding malware evolution. Presented at ACM Genetic and Evolutionary Computation Conference (GECCO) 2024, Melbourne, Australia

We conduct a preliminary study exploring the potential of using fitness landscape analysis for understanding the evolution of malware. This type of optimisation is fairly new and has not previously been studied through the lens of landscape analysis.... Read More about Exploring the use of fitness landscape analysis for understanding malware evolution.

Where the Really Hard Quadratic Assignment Problems Are: the QAP-SAT instances (2024)
Presentation / Conference Contribution
Verel, S., Thomson, S. L., & Rifki, O. (2024, April). Where the Really Hard Quadratic Assignment Problems Are: the QAP-SAT instances. Presented at EvoCOP 2024, Aberystwyth, UK

The Quadratic Assignment Problem (QAP) is one of the major domains in the field of evolutionary computation, and more widely in combinatorial optimization. This paper studies the phase transition of the QAP, which can be described as a dramatic chang... Read More about Where the Really Hard Quadratic Assignment Problems Are: the QAP-SAT instances.

Frequency Fitness Assignment for Untangling Proteins in 2D (2024)
Presentation / Conference Contribution
Koutstaal, J., Kommandeur, J., Timmer, R., Horn, R., Thomson, S. L., & van den Berg, D. (2024, April). Frequency Fitness Assignment for Untangling Proteins in 2D. Presented at EvoStar 2024, Aberyswyth, UK

At the time of writing, there is no known deterministic-time algorithm to sample valid initial solutions with uniform random distribution for the HP protein folding model, because guaranteed uniform random sampling produces collisions (i.e. constrain... Read More about Frequency Fitness Assignment for Untangling Proteins in 2D.

Information flow and Laplacian dynamics on local optima networks (2024)
Presentation / Conference Contribution
Richter, H., & Thomson, S. L. (2024, June). Information flow and Laplacian dynamics on local optima networks. Presented at IEEE Congress on Evolutionary Computation (IEEE CEC), Yokohama, Japan

We propose a new way of looking at local optima networks (LONs). LONs represent fitness landscapes; the nodes are local optima, and the edges are search transitions between them. Many metrics computed on LONs have been proposed and shown to be linked... Read More about Information flow and Laplacian dynamics on local optima networks.

The Opaque Nature of Intelligence and the Pursuit of Explainable AI (2023)
Presentation / Conference Contribution
Thomson, S. L., van Stein, N., van den Berg, D., & van Leeuwen, C. (2023, November). The Opaque Nature of Intelligence and the Pursuit of Explainable AI. Presented at NCTA 2023: 15th International Conference on Neural Computation Theory and Applications, Rome, Italy

When artificial intelligence is used for making decisions, people are more likely to accept those decisions if they can be made intelligible to the public. This understanding has led to the emerging field of explainable artificial intelligence. We re... Read More about The Opaque Nature of Intelligence and the Pursuit of Explainable AI.

Can HP-protein folding be solved with genetic algorithms? Maybe not (2023)
Presentation / Conference Contribution
Jansen, R., Horn, R., van Eck, O., Version, K., Thomson, S. L., & van den Berg, D. (2023, November). Can HP-protein folding be solved with genetic algorithms? Maybe not. Presented at ECTA 2023 15th International Conference on Evolutionary Computation Theory and Applications, Rome, Italy

Genetic algorithms might not be able to solve the HP-protein folding problem because creating random individuals for an initial population is very hard, if not impossible. The reason for this, is that the expected number of constraint violations incr... Read More about Can HP-protein folding be solved with genetic algorithms? Maybe not.

Too Constrained for Genetic Algorithms. Too Hard for Evolutionary Computing. The Traveling Tournament Problem. (2023)
Presentation / Conference Contribution
Verduin, K., Thomson, S. L., & van den Berg, D. (2023, November). Too Constrained for Genetic Algorithms. Too Hard for Evolutionary Computing. The Traveling Tournament Problem. Presented at ECTA 2023 15th International Conference on Evolutionary Computation Theory and Applications, Rome, Italy

Unlike other NP-hard problems, the constraints on the traveling tournament problem are so pressing that it’s hardly possible to randomly generate a valid solution, for example, to use in a genetic algorithm’s initial population. In this study, we ran... Read More about Too Constrained for Genetic Algorithms. Too Hard for Evolutionary Computing. The Traveling Tournament Problem..

Unexplained Fluctuations in Particle Swarm Optimisation Performance with Increasing Problem Dimensionality (2023)
Presentation / Conference Contribution
Graham, K. C., Thomson, S. L., & Brownlee, A. E. I. (2023). Unexplained Fluctuations in Particle Swarm Optimisation Performance with Increasing Problem Dimensionality. . https://doi.org/10.1145/3583133.3596433

We study the behaviour of particle swarm optimisation (PSO) with increasing problem dimension for the Alpine 1 function as an exploratory and preliminary case study. Performance trends are analysed and the tuned population size for PSO across dimensi... Read More about Unexplained Fluctuations in Particle Swarm Optimisation Performance with Increasing Problem Dimensionality.

Randomness in Local Optima Network Sampling (2023)
Presentation / Conference Contribution
Thomson, S. L., Veerapen, N., Ochoa, G., & van den Berg, D. (2023, July). Randomness in Local Optima Network Sampling. Presented at GECCO '23, Lisbon, Portugal

We consider statistical randomness in the construction of local optima networks (LONs) and conduct a preliminary and exploratory study into this. LONs capture a fitness landscape into network format: the nodes are local optima, and edges are heuristi... Read More about Randomness in Local Optima Network Sampling.

From Fitness Landscapes to Explainable AI and Back (2023)
Presentation / Conference Contribution
Thomson, S. L., Adair, J., Brownlee, A. E. I., & van den Berg, D. (2023, July). From Fitness Landscapes to Explainable AI and Back. Presented at GECCO '23, Lisbon, Portugal

We consider and discuss the ways in which search landscapes might contribute to the future of explainable artificial intelligence (XAI), and vice versa. Landscapes are typically used to gain insight into algorithm search dynamics on optimisation prob... Read More about From Fitness Landscapes to Explainable AI and Back.

Channel Configuration for Neural Architecture: Insights from the Search Space (2023)
Presentation / Conference Contribution
Thomson, S. L., Ochoa, G., Veerapen, N., & Michalak, K. (2023, July). Channel Configuration for Neural Architecture: Insights from the Search Space. Presented at GECCO '23, Lisbon, Portugal

We consider search spaces associated with neural network channel configuration. Architectures and their accuracy are visualised using low-dimensional Euclidean embedding (LDEE). Optimisation dynamics are captured using local optima networks (LONs). L... Read More about Channel Configuration for Neural Architecture: Insights from the Search Space.

Frequency Fitness Assignment on JSSP: A Critical Review (2023)
Presentation / Conference Contribution
de Bruin, E., Thomson, S. L., & Berg, D. V. D. (2023, April). Frequency Fitness Assignment on JSSP: A Critical Review. Presented at EvoApplications 2023: Applications of Evolutionary Computation, Brno, Czech Republic

Metaheuristic navigation towards rare objective values instead of good objective values: is it a good idea? We will discuss the closed and open ends after presenting a successful replication study of Weise et al.’s ‘frequency fitness assignment’ for... Read More about Frequency Fitness Assignment on JSSP: A Critical Review.

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.