Tutorial abstract
The notion of a fitness landscape was first introduced in 1932 to understand natural evolution, but the concept was later applied to evolutionary computation to understand algorithm behaviour on different problems. More recently, landscape analysis has been used in contexts beyond evolutionary computation in areas such as feature selection for data mining, hyperparameter optimisation and neural network training.
A further recent advance has been the analysis of landscapes through the trajectories of algorithms. The search paths of algorithms provide samples of the search space that can be seen as a view of the landscape from the perspective of the algorithm. What algorithms "see" as they move through the search space of different problems can help us understand how evolutionary and other search algorithms behave on problems with different characteristics.
This tutorial provides an overview of landscape analysis in different contexts, including techniques for understanding and characterising discrete and continuous optimisation problems, applications of landscape analysis in performance prediction and algorithm selection, and the analysis of search trajectories to understand the behaviour of search algorithms.
Topic overview
The goal of this tutorial is to provide an overview of landscape analysis for optimisation and learning. The subject matter will be relevant not only to delegates who are interested in applying landscape analysis for the first time, but also to those involved in landscape analysis research to obtain a broad view of recent developments in the field. The tutorial will cover foundational work in fitness landscape analysis as well as new techniques that have been developed in the last few years. Case studies will be presented of recent applications of landscape analysis in both discrete and continuous domains.
The tutorial also covers recent results on local optima networks (LONs), a network-based model of fitness landscapes where nodes are local optima and edges are possible search transitions among these optima. We also introduce search trajectory networks (STNs) as a tool to analyse and visualise the behaviour of metaheuristics. STNs model the search trajectories of algorithms. Unlike LONs, nodes are not restricted to local optima but instead represent given states of the search process. Edges represent search progression between consecutive states. This extends the power and applicability of network-based models. Both LONs and STNs allow us to visualise realistic search spaces in ways not previously possible and bring a whole new set of quantitative network metrics for characterising and understanding computational search.
The tutorial is aimed at delegates interested in developing a deeper understanding of the complexities of search spaces and how these impact on the performance of algorithms. The material will be accessible to delegates without experience in landscape analysis, but should also be of interest to those working in the field. Because the tutorial provides a broad overview of developments in the field (including both discrete and continuous domains) and will include practical case studies, it should be relevant to a wide audience. The tutorial will include visual demonstrations and animations from case studies.
Outline
Proposed outline of topics to be covered:- Part 1: Landscape analysis
- 1.1 Introduction to fitness landscapes
- 1.2 Recent advances in landscape analysis
- 1.3 Fitness landscape analysis techniques
- 1.4 Applications of landscape analysis
- Part 2: Complex networks for landscape analysis
- 2.1 Complex network modelling
- 2.2 Local optima networks
- 2.3 Search trajectory networks