Outputs (35)

The Easiest Hard Problem: Now Even Easier (2024)
Presentation / Conference Contribution
Horn, R., Thomson, S. L., van den Berg, D., & Adriaans, P. (2024, July). The Easiest Hard Problem: Now Even Easier. Presented at ACM Genetic and Evolutionary Computation Conference (GECCO) 2024, Melbourne, Australia

We present an exponential decay function that characterizes the number of solutions to instances of the Number Partitioning Problem (NPP) with uniform distribution of bits across the integers. This function is fitted on the number of optimal solution... Read More about The Easiest Hard Problem: Now Even Easier.

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.

Addressing the traveling salesperson problem with frequency fitness assignment and hybrid algorithms (2024)
Journal Article
Liang, T., Wu, Z., Lässig, J., van den Berg, D., Thomson, S. L., & Weise, T. (2024). Addressing the traveling salesperson problem with frequency fitness assignment and hybrid algorithms. Soft Computing, 28, 9495–9508. https://doi.org/10.1007/s00500-024-09718-8

The traveling salesperson problem (TSP) is one of the most iconic hard optimization tasks. With frequency fitness assignment (FFA), a new approach to optimization has recently been proposed: instead of directing the search towards better solutions, t... Read More about Addressing the traveling salesperson problem with frequency fitness assignment and hybrid algorithms.

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.

Shape of the Waterfall: Solvability Transitions in the QAP (2024)
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.

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.

Information flow and Laplacian dynamics on local optima networks
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.

Understanding fitness landscapes in morpho-evolution via local optima networks
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.

Temporal True and Surrogate Fitness Landscape Analysis for Expensive Bi-Objective Optimisation Expensive Bi-Objective
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.