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.
Filter
Travelling Salesman:
Quadratic Assignment:
NK Landscapes:
Number Partitioning:
Genetic Improvement:
Protein Design:
LON Maps is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Travelling Salesman Problem
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.
Instance: att532. Node color: component. Node size: degree
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: att532. Node color: component. Node size: degree
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: d657. Node color: component. Node size: degree
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: gr666. Node color: component. Node size: degree
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: gr666. Node color: component. Node size: fitness.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: rat575. Node color: component. Node size: degree
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: rat575. Node colour: component. Node size: fitness.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: u574. Node colour: component. Node size: degree.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: u574. Node colour: component. Node size: fitness.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: att532. Node color: component. Layout: Kamada-Kawai
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: gr666. Node color: component. Layout: Kamada-Kawai.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: rat575. Node color: component. Layout: Kamada-Kawai.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: ali532, global optima in red.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: d493, global optima in red.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: ali532, global optima in red.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance: d493, global optima in red, good local optima in pink.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Instance:fl417, global optima in red.
Ochoa, Gabriela; Veerapen, Nadarajen. Deconstructing the Big Valley Search Space Hypothesis Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
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 fit tness 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.
Funnel floor network for Instance att532. Node color is fitness level. Node size is incoming degree.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
Funnel floor network for Instance u574. Node color is fitness level. Node size is incoming degree.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
Funnel floor network for Instance d657. Node colour is fitness level. Node size is incoming degree.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
2D LON for instance att532. Node colour is fitness level. Node size is incoming degree.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
2D LON for instance u574. Node color is fitness level. Node size is incoming degree.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
2D LON for instance gr666. Node colour is fitness level. Node size is incoming degree.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
3D LON for instance att532. Node color is fitness level. Node size is incoming degree. Z coordinate is fitness.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
3D LON for instance att532. Node color is fitness level. Node size is incoming degree. Z coordinate is fitness.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
3D LON for instance u574. Node color is fitness level. Node size is incoming degree. Z coordinate is fitness.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
3D LON for instance u574. Node color is fitness level. Node size is incoming degree. Z coordinate is fitness.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
3D LON for instance d657. Stronger perturbation (z =3). Node colour is fitness level. Node size is incoming degree. Z coordinate is fitness.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
3D LON for instance d657. Stronger perturbation (z =3). Node colour is fitness level. Node size is incoming degree. Z coordinate is fitness.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
3D LON for instance d657. Node colour is fitness level. Node size is incoming degree. Z coordinate is fitness.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
instance d657. Node colour is fitness level. Node size is incoming degree. Z coordinate is fitness.
Ochoa, Gabriela; Veerapen, Nadarajen. Additional Dimensions to the Study of Funnels in Combinatorial Landscapes Genetic and Evolutionary Computation Conference - GECCO 2016, pp. 373–380, ACM, 2016.
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.
2D LON for random clustered Instance C1243. Node colour represents fitness. Node size represents incoming weighted degree (strength).
Ochoa, Gabriela; Veerapen, Nadarajen. Mapping the global structure of TSP fitness landscapes Journal Article J. Heuristics, 24 (3), pp. 265–294, 2018.
2D LON for random uniform Instance E1243. Node colour represents fitness. Node size represents incoming weighted degree (strength).
Ochoa, Gabriela; Veerapen, Nadarajen. Mapping the global structure of TSP fitness landscapes Journal Article J. Heuristics, 24 (3), pp. 265–294, 2018.
2D LON for TSPLIB Instance pr1002. Node colour represents fitness. Node size represents incoming weighted degree (strength).
Ochoa, Gabriela; Veerapen, Nadarajen. Mapping the global structure of TSP fitness landscapes Journal Article J. Heuristics, 24 (3), pp. 265–294, 2018.
2D LON for TSPLIB Instance att532. Node colour represents fitness. Node size represents incoming weighted degree (strength).
Ochoa, Gabriela; Veerapen, Nadarajen. Mapping the global structure of TSP fitness landscapes Journal Article J. Heuristics, 24 (3), pp. 265–294, 2018.
3D LON for TSPLIB Instance u574.
Node colour represents fitness. Node size represents incoming weighted degree (strength). <\br>Ochoa, Gabriela; Veerapen, Nadarajen. href="http://hdl.handle.net/1893/25413">Mapping the global structure of TSP fitness landscapes Journal Article J. Heuristics, 24 (3), pp. 265–294, 2018.
3D LON for random clustered instance C1243. Node colour represents fitness. Node size represents incoming weighted degree (strength).
Ochoa, Gabriela; Veerapen, Nadarajen. Mapping the global structure of TSP fitness landscapes Journal Article J. Heuristics, 24 (3), pp. 265–294, 2018.
3D LON animation for random uniform Instance E1243. Node colour represents fitness. Node size represents incoming weighted degree (strength).
Ochoa, Gabriela; Veerapen, Nadarajen. Mapping the global structure of TSP fitness landscapes Journal Article J. Heuristics, 24 (3), pp. 265–294, 2018.
3D LON for TSPLIB Instance pr1002. Node colour represents fitness. Node size represents incoming weighted degree (strength).
3D LON TSPLIB Instance att532. Node colour represents fitness. Node size represents incoming weighted degree (strength).
Ochoa, Gabriela; Veerapen, Nadarajen. Mapping the global structure of TSP fitness landscapes Journal Article J. Heuristics, 24 (3), pp. 265–294, 2018.
Ochoa, Gabriela; Veerapen, Nadarajen. href="http://hdl.handle.net/1893/25413">Mapping the global structure of TSP fitness landscapes Journal Article J. Heuristics, 24 (3), pp. 265–294, 2018.
Tunnelling Crossover, PPSN 2016
LON for Chained-LK on asymmetric TSP instance rbg323. Node colours represent connected components.
Veerapen, Nadarajen; Ochoa, Gabriela; Tinós, Renato; Whitley, Darrell. Tunnelling Crossover Networks for the Asymmetric TSP Parallel Problem Solving from Nature - PPSN XIV, pp. 994–1003, Springer, 2016.
LON for Hybrid-GA on asymmetric TSP instance rbg323. Node colours represent connected components. With bright red indicating global opitma.
Veerapen, Nadarajen; Ochoa, Gabriela; Tinós, Renato; Whitley, Darrell. Tunnelling Crossover Networks for the Asymmetric TSP Parallel Problem Solving from Nature - PPSN XIV, pp. 994–1003, Springer, 2016.
3D LON for Chained-LK on asymmetric TSP instance rbg323.
Separate paths, none of them reaching a global optimum. <\br> Veerapen Nadarajen; Ochoa, Gabriela; Tinós, Renato; Whitley, Darrell.Tunnelling Crossover Networks for the Asymmetric TSP PPSN XIV, pp. 994–1003, Springer, 2016.
3D LON for Hybrid GA on asymmetric TSP instance rbg323. Red nodes are global opitma. A single generation is enough to tunnel through to global optima.
arajen; Ochoa, Gabriela; Tinós, Renato; Whitley, Darrell. Tunnelling Crossover Networks for the Asymmetric TSP Parallel Problem Solving from Nature - PPSN XIV, pp. 994–1003, Springer, 2016.
3D LON for Chained-LK on asymmetric TSP instance rbg323.
Red nodes are global optima.
arajen; Ochoa, Gabriela; Tinós, Renato; Whitley, Darrell. Tunnelling Crossover Networks for the Asymmetric TSP Parallel Problem Solving from Nature - PPSN XIV, pp. 994–1003, Springer, 2016.
Perturbation Strength and Funnels, EvoCOP 2018
LON for TSP random clustered instance C755. Perturbation strength: 1 double-bridge moves.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Larger nodes identify funnel bottoms (sinks). McMenemy, Paul; Veerapen, Nadarajen; Ochoa, Gabriela.How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes EvoCOP 2018, pp. 34–49, Springer, 2018.
LON for TSP random clustered instance C755. Perturbation strength: 5 double-bridge moves.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Larger nodes identify funnel bottoms (sinks). McMenemy, Paul; Veerapen, Nadarajen; Ochoa, Gabriela.How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes EvoCOP 2018, pp. 34–49, Springer, 2018.
LON for TSP random clustered instance C755. Perturbation strength: 7 double-bridge moves.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Larger nodes identify funnel bottoms (sinks). McMenemy, Paul; Veerapen, Nadarajen; Ochoa, Gabriela.How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes EvoCOP 2018, pp. 34–49, Springer, 2018.
LON for TSP random clustered instance C755. Perturbation strength: 8 double-bridge moves.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Larger nodes identify funnel bottoms (sinks). McMenemy, Paul; Veerapen, Nadarajen; Ochoa, Gabriela.How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes EvoCOP 2018, pp. 34–49, Springer, 2018.
LON for TSP random clustered instance C755. Perturbation strength: 10 double-bridge moves%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Larger nodes identify funnel bottoms (sinks). McMenemy, Paul; Veerapen, Nadarajen; Ochoa, Gabriela.How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes Evolutionary Computation in Combinatorial Optimization - EvoCOP 2018, pp. 34–49, Springer, 2018.
LON for TSP random uniform instance E755. Perturbation strength: 1 double-bridge moves.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Larger nodes identify funnel bottoms (sinks). McMenemy, Paul; Veerapen, Nadarajen; Ochoa, Gabriela.How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes EvoCOP 2018, pp. 34–49, Springer, 2018.
LON for TSP random uniform instance E755. Perturbation strength: 5 double-bridge moves.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Larger nodes identify funnel bottoms (sinks). McMenemy, Paul; Veerapen, Nadarajen; Ochoa, Gabriela.How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes EvoCOP 2018, pp. 34–49, Springer, 2018.
LON for TSP random uniform instance E755. Perturbation strength: 6 double-bridge moves.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Larger nodes identify funnel bottoms (sinks). McMenemy, Paul; Veerapen, Nadarajen; Ochoa, Gabriela.How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes EvoCOP 2018, pp. 34–49, Springer, 2018.
LON for TSP random uniform instance E755. Perturbation strength: 8 double-bridge moves.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Larger nodes identify funnel bottoms (sinks). McMenemy, Paul; Veerapen, Nadarajen; Ochoa, Gabriela.How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes EvoCOP 2018, pp. 34–49, Springer, 2018.
LON for TSP random uniform instance E755. Perturbation strength: 10 double-bridge moves.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Larger nodes identify funnel bottoms (sinks). McMenemy, Paul; Veerapen, Nadarajen; Ochoa, Gabriela.How Perturbation Strength Shapes the Global Structure of TSP Fitness Landscapes EvoCOP 2018, pp. 34–49, Springer, 2018.
Quadratic Assignment Problem
Perturbation Strength and Funnels, PPSN 2018
LON for QAP instance tho40. Perturbation strength: 12.5% .
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance kra30b. Perturbation strength: 25%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance kra30b. Perturbation strength: 50%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance kra30b. Perturbation strength: 75%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance kra30b. Perturbation: restart.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance nug30. Perturbation strength: 12.5% .
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance nug30. Perturbation strength: 25 %.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance nug30. Perturbation strength: 50%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance nug30. Perturbation strength: 75%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance nug30. Perturbation strength: restart.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance tho40. Perturbation strength: 12.5%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance tho40. Perturbation strength: 25%.
Ochoa, GabrielRed nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance tho40. Perturbation strength: 50%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance tho40. Perturbation strength: 75%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance tho40. Perturbation strength: restart.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance sko42. Perturbation strength: 12.5%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance sko42. Perturbation strength: 25%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance sko42. Perturbation strength: 50%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance sko42. Perturbation strength: 75%.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
LON for QAP instance sko42. Perturbation strength: restart.
Red nodes belong to global optimal funnels. Blue nodes to suboptimal funnels. Brighter colours identify Funnel bottoms (sinks). Ochoa, Gabriela; Herrmann, Sebastian. Perturbation Strength and the Global Structure of QAP PPSN XV, to appear, Springer, 2018.
NK Landscapes
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.
Ochoa, Gabriela; Chicano, Francisco; Tinós, Renato; Whitley, Darrell Tunnelling Crossover Networks Genetic and Evolutionary Computation Conference - GECCO 2015, pp. 449–456, ACM, 2015.
Ochoa, Gabriela; Chicano, Francisco; Tinós, Renato; Whitley, Darrell Tunnelling Crossover Networks Genetic and Evolutionary Computation Conference - GECCO 2015, pp. 449–456, ACM, 2015.
Ochoa, Gabriela; Chicano, Francisco; Tinós, Renato; Whitley, Darrell Tunnelling Crossover Networks Genetic and Evolutionary Computation Conference - GECCO 2015, pp. 449–456, ACM, 2015.
Optimizing one million variable NK landscapes, GECCO 2017
Chicano, Francisco; Whitley, Darrell; Ochoa, Gabriela; Tinós, Renato. Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search Genetic and Evolutionary Computation Conference - GECCO 2017, pp. 753–760, ACM, 2017.
Chicano, Francisco; Whitley, Darrell; Ochoa, Gabriela; Tinós, Renato. Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search Genetic and Evolutionary Computation Conference - GECCO 2017, pp. 753–760, ACM, 2017.
Chicano, Francisco; Whitley, Darrell; Ochoa, Gabriela; Tinós, Renato. Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search Genetic and Evolutionary Computation Conference - GECCO 2017, pp. 753–760, ACM, 2017.
Chicano, Francisco; Whitley, Darrell; Ochoa, Gabriela; Tinós, Renato. Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search Genetic and Evolutionary Computation Conference - GECCO 2017, pp. 753–760, ACM, 2017.
Chicano, Francisco; Whitley, Darrell; Ochoa, Gabriela; Tinós, Renato. Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search Genetic and Evolutionary Computation Conference - GECCO 2017, pp. 753–760, ACM, 2017.
Comparing communities of optima with funnels, GECCO 2017
Thomson, Sarah L; Daolio, Fabio; Ochoa, Gabriela Comparing communities of optima with funnels in combinatorial fitness landscapes Genetic and Evolutionary Computation Conference - GECCO 2017, pp. 377–384, ACM, 2017.
Thomson, Sarah L; Daolio, Fabio; Ochoa, Gabriela Comparing communities of optima with funnels in combinatorial fitness landscapes Genetic and Evolutionary Computation Conference - GECCO 2017, pp. 377–384, ACM, 2017.
Thomson, Sarah L; Daolio, Fabio; Ochoa, Gabriela Comparing communities of optima with funnels in combinatorial fitness landscapes Genetic and Evolutionary Computation Conference - GECCO 2017, pp. 377–384, ACM, 2017.
Number Partitioning Problem
Understanding Phase Transitions, EvoCOP 2017
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Ochoa G, Veerapen N, Daolio F & Tomassini M. Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.
Genetic Improvement
Protein Design
Local optima network with basin edges for 2ckx. The size is the log of the basin of attraction size. The color is the fitness: the better, the warmer. The thickness of the edges is proportional to the probability of passing from one basin to the other.
Simoncini, David; Barbe, Sophie; Schiex, Thomas; Verel, Sébastien. Fitness landscape analysis around the optimum in computational protein design Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 355–362, ACM, 2018.
Simoncini, David; Barbe, Sophie; Schiex, Thomas; Verel, Sébastien. Fitness landscape analysis around the optimum in computational protein design Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 355–362, ACM, 2018.