This gallery portrays a collection of Local Optima Network visualisations. We have categorised the images by problem domain, and within each domain by the research paper most closely associated with the image. Not all the images in the gallery appeared in the named papers but were generated in a similar way as those in the paper. Most of the images were generated with the igraph package using the R software environment. The 3D plots and animations were generated with the OpenGL R package rgl. Different plots reflect different problem instances, graph layouts (mainly force-directed algorithms such as Fruchterman-Reingold and Kamada-Kawai), search operators and decorations of nodes and edges. For example, the colour of nodes reflects either the connected component/funnel membership or the fitness value (or range of values). The size of nodes represents either their incoming degree or their fitness value. More information and a large version of an image are given when clicking it.
These LONs are the result of sampling the landscape of TSP instances. They were generated by aggregating multiple runs of the Chained Lin-Kernighan heuristic, which is a form of iterated local search. Nodes are Lin-Kernighan optima and edges are escape transitions with the double-bridge move. We have studied benchmark instances from the TSPLIB with sizes in the range of 500-1500 cities, and synthetic instances (uniform and clustered points) in the same size range produced with the DIMACS instance generator code.
Deconstructing the Big-Valley, EvoCOP 2016
We analysed the LONs of representative instances from the TSPLIB, the idea was to explore their funnel structure. The colors of nodes identify connected components which we claimed are associated with the notion of funnels. TSP instances were found to have several funnels, deconstructing the idea of a single funnel or valley. The first two rows use Fruchterman-Reingold, while the last two rows use Kamada-Kawai graph layout, which spreads out the connected components (funnels). The last row features TSP instances with neutrality (sequences of local optima with the same fitness), which appear as intriguing worm-like structures.
Funnel Floors and 3D LON Visualisations, GECCO 2016
3D LON visualisations, where the z coordinate represents fitness (cost), are introduced for this first time. The 3D plots provide a concrete and intuitive depiction of the fittness landscape metaphor and the notion of funnels. We explored in detail the funnel floors and their connectivity. A funnel floor solution is a high quality local optimum that is conjectured to be at the bottom of a funnel. They are located by running Chained-LK for a large enough number of iterations and recognised by the lack of downward progress after a large number of double-bridge escape attempts. We found that a stronger perturbation can help in smoothing the funnel structure, that is, reducing the number of funnels and making the global optima more reachable.
Global Structure, Journal of Heuristics 2018
The colours of nodes identify funnels characterised with monotonic sequences (sequence of connected optima with no-deteriorating fitness). We used the heat colours palette, a sequential colour scheme skewed to the reds and yellows. Red identifies the global optima, and the yellow colour gradient reflects an increase in cost. The 2nd row represents a 3D view of the respective LON at the top.
Tunnelling Crossover, PPSN 2016
Perturbation Strength and Funnels, EvoCOP 2018
Quadratic Assignment Problem
Perturbation Strength and Funnels, PPSN 2018
These LONs are the result of fully enumerating NK landscape instances of sizes from 15 up to 30 bits.
Tunnelling Crossover Networks, GECCO 2015
Transitions based on recombination are introduced for the first time in a LON model. We define and analyze networks based on partition crossover for k-bounded pseudo-Boolean functions, using NKq landscapes as a case study. Partition crossover was initially proposed for the TSP, where it was found to “tunnel” between local optima, i.e., jump from local optimum to local optimum. Gray-box optimisation techniques are used to efficiently compute all the global optima for landscapes of up to 30 bits. Our network analysis shows that this also happens for NK landscapes: local optima are densely connected via partition crossover. We found marked differences between the adjacent and ran-dom interaction NK models. Surprisingly, with the random model, instances have a lower number of local optima on average, but their networks are more sparse and decompose into several clusters. So the number of local optima is not always a predictor of search difficulty, instead, the distribution of optima can be a key factor underlying difficulty.
Optimizing one million variable NK landscapes, GECCO 2017
Comparing communities of optima with funnels, GECCO 2017