Many situations in daily life represent complex combinatorial optimisation problems. These include issues such as efficient fuel consumption, nurse scheduling, or
distribution of humanitarian aid. There are many algorithms that attempt to solve
these problems but the ability to understand their likely performance on a given
problem is still lacking.
Fitness landscape analysis identifies some of the reasons why metaheuristic algorithms behave in a particular way. The Local Optima Network (LON) model,
proposed in 2008, encodes local optima connectivity in fitness landscapes. In this
approach, nodes are local optima and edges encode transitions between these optima. A LON provides a static image of the dynamics of algorithm-problem inter-
play. Analysing these structures provides insights into the reactions between optimisation problems and metaheuristic search algorithms.
This thesis proposes that analysis of the local optima space of combinatorial fitness landscapes encoded using a LON provides important information concerning
potential search algorithm performance. It considers the question as to whether or
not features of LONs can contribute to explaining or predicting the outcome of trying to optimise an associated combinatorial problem. Topological landscape features of LONs are proposed, analysed and compared. Benchmark and novel problem instances are studied; both types of problem are sampled and in some cases
exhaustively-enumerated such that LONs can be extracted for analysis. Investigations into the nature and biases of LON construction algorithms are conducted and
compared.
Contributions include aligning fractal geometry to the study of LONs; proposals for novel ways to compute fractal dimension from these structures; comparing
the power of different LON construction algorithms for explaining algorithm performances; and analysing the interplay between algorithmic operations and infeasible regions in the local optima space using LONs as a tool. Throughout the thesis,
large scale structural patterns in fitness landscapes are shown to be strongly linked
with metaheuristic algorithm performance. This includes arrangements of local optima funnel structures; spatial and geometric complexity in the LON (measured by
their fractal dimensionality) and fitness levels in the space of local optima. These
features are demonstrated to have explanatory or predictive ability with respect to
algorithm performance for the underlying combinatorial problems. The results presented here indicate that large topological patterns in fitness landscapes are important during metaheuristic search algorithm design. In many cases they are incontrovertibly linked to the success of the algorithm. These results indicate that use of the
suggested fitness landscape measures would be highly beneficial when considering
the design of search algorithms for a given problem domain.