More Web Proxy on the site http://driver.im/

article

Visualising the global structure of search landscapes: genetic improvement as a case study

Authors:

Nadarajen Veerapen,

Gabriela OchoaAuthors Info & Claims

Genetic Programming and Evolvable Machines, Volume 19, Issue 3

Pages 317 - 349

https://doi.org/10.1007/s10710-018-9328-1

Published: 01 September 2018 Publication History

Abstract

The search landscape is a common metaphor to describe the structure of computational search spaces. Different landscape metrics can be computed and used to predict search difficulty. Yet, the metaphor falls short in visualisation terms because it is hard to represent complex landscapes, both in terms of size and dimensionality. This paper combines local optima networks, as a compact representation of the global structure of a search space, and dimensionality reduction, using the t-distributed stochastic neighbour embedding algorithm, in order to both bring the metaphor to life and convey new insight into the search process. As a case study, two benchmark programs, under a genetic improvement bug-fixing scenario, are analysed and visualised using the proposed method. Local optima networks for both iterated local search and a hybrid genetic algorithm, across different neighbourhoods, are compared, highlighting the differences in how the landscape is explored.

References

[1]

R. Amar, J. Stasko, A knowledge task-based framework for design and evaluation of information visualizations, in IEEE Symposium on Information Visualization, pp. 143---150 (2004).

Digital Library

[2]

M. Bastian, S. Heymann, M. Jacomy, Gephi : an open source software for exploring and manipulating networks, in International AAAI Conference on Web and Social Media. Association for the Advancement of Artificial (2009). https://www.aaai.org/ocs/index.php/ICWSM/09/paper/view/154

[3]

G. Csardi, T. Nepusz, The igraph software package for complex network research. InterJ. Complex Syst. 1695 (2006). http://igraph.org

[4]

R.A. DeMillo, R.J. Lipton, F.G. Sayward, Hints on test data selection: help for the practicing programmer. Computer 11(4), 34---41 (1978).

Digital Library

[5]

H. Do, S. Elbaum, G. Rothermel, Supporting controlled experimentation with testing techniques: an infrastructure and its potential impact. Empir. Softw. Eng. 10(4), 405---435 (2005).

Digital Library

[6]

Q. Duan, C. Shao, X. Li, Y. Shi, Visualizing the search dynamics in a high-dimensional space for a particle swarm optimizer. In: Simulated Evolution and Learning, Lecture Notes in Computer Science, pp. 994---1002. Springer, Cham (2017).

[7]

R. Dybowski, T.D. Collins, P.R. Weller, Visualization of Binary String Convergence by Sammon Mapping (Loughborough University, Loughborough, 1996)

[8]

C. Flamm, I.L. Hofacker, P.F. Stadler, M.T. Wolfinger, Barrier trees of degenerate landscapes. Phys. Chem. 216, 155---173 (2002)

[9]

J. Hallam, A. Prugel-Bennett, Large barrier trees for studying search. IEEE Trans. Evolut. Comput. 9(4), 385---397 (2005)

Digital Library

[10]

E. Hart, P. Ross, GAVEL--a new tool for genetic algorithm visualization. IEEE Trans. Evolut. Comput. 5(4), 335---348 (2001).

Digital Library

[11]

D. Holten, J.J. Van Wijk, Force-directed edge bundling for graph visualization. Comput. Graph. Forum 28(3), 983---990 (2009).

Digital Library

[12]

D.A. Keim, F. Mansmann, J. Schneidewind, H. Ziegler, Challenges in visual data analysis, in Tenth International Conference on Information Visualisation (IV'06), pp. 9---16 (2006).

Digital Library

[13]

Y.H. Kim, B.R. Moon, New usage of Sammon's mapping for genetic visualization, in Genetic and Evolutionary Computation--GECCO 2003, Lecture Notes in Computer Science, pp. 1136---1147. Springer, Berlin, Heidelberg (2003).

Digital Library

[14]

S.G. Kobourov, Force-directed drawing algorithms, in Handbook of Graph Drawing and Visualization, 1st edn., ed. by R. Tamassia (CRC Press, Boca Raton, 2013), pp. 349---381

[15]

O. Kramer, D. Luckehe, Visualization of evolutionary runs with isometric mapping, in 2015 IEEE Congress on Evolutionary Computation (CEC), pp. 1359---1363 (2015).

[16]

W.B. Langdon, M. Harman, Y. Jia, Efficient multi-objective higher order mutation testing with genetic programming. J. Syst. Softw. 83(12), 2416---2430 (2010).

Digital Library

[17]

W.B. Langdon, G. Ochoa, Genetic improvement: a key challenge for evolutionary computation, in 2016 IEEE Congress on Evolutionary Computation (CEC), pp. 3068---3075 (2016).

Digital Library

[18]

W.B. Langdon, J. Petke, Software is not fragile, in First Complex Systems Digital Campus World E-Conference 2015, pp. 203---211. Springer, Cham (2017).

[19]

W.B. Langdon, N. Veerapen, G. Ochoa, Visualising the search landscape of the triangle program, in Genetic Programming, vol. 10196, Lecture Notes in Computer Science, ed. by J. McDermott, M. Castelli, L. Sekanina, E. Haasdijk, P. Garcia-Sànchez (Springer, Cham, 2017), pp. 96---113.

[20]

J.A. Lee, M. Verleysen, Nonlinear Dimensionality Reduction, 1st edn. (Springer, Berlin, 2007)

Digital Library

[21]

E. Lutton, J. Foucquier, N. Perrot, J. Louchet, J.D. Fekete, Visual Analysis of Population Scatterplots, in Artificial Evolution, no. 7401 in Lecture Notes in Computer Science, ed. by J.K. Hao, P. Legrand, P. Collet, N. Monmarché, E. Lutton, M. Schoenauer (Springer, Berlin, 2011), pp. 61---72

Digital Library

[22]

K.M. Malan, A.P. Engelbrecht, A survey of techniques for characterising fitness landscapes and some possible ways forward. Inf. Sci. 241, 148---163 (2013)

Digital Library

[23]

S. Martin, W.M. Brown, B.N. Wylie, Dr.L: Distributed Recursive (Graph) Layout. Tech. Rep. dRl; 002182MLTPL00, Sandia National Laboratories (2007). https://www.osti.gov/scitech/biblio/1231060

[24]

M.E.J. Newman, R. Engelhardt, Effect of neutral selection on the evolution of molecular species. Proc. R. Soc. Lond. B 265, 1333---1338 (1998)

[25]

G. Ochoa, M. Tomassini, S. Vérel, C. Darabos, A study of NK landscapes' basins and local optima networks, in Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, GECCO '08, pp. 555---562. ACM, New York, NY, USA (2008).

Digital Library

[26]

G. Ochoa, N. Veerapen, Mapping the global structure of TSP fitness landscapes. J. Heuristics 24(3), 265---294 (2018).

Digital Library

[27]

G. Ochoa, N. Veerapen, F. Daolio, M. Tomassini, Understanding phase transitions with local optima networks: number partitioning as a case study, in Evolutionary Computation in Combinatorial Optimization, vol. 10197, Lecture Notes in Computer Science, ed. by B. Hu, M. López-Ibáñez (Springer, Cham, 2017), pp. 233---248.

[28]

G. Ochoa, N. Veerapen, D. Whitley, E.K. Burke, The multi-funnel structure of TSP fitness landscapes: a visual exploration, in Artificial Evolution, vol. 9554, Lecture Notes in Computer Science, ed. by S. Bonnevay, P. Legrand, N. Monmarché, E. Lutton, M. Schoenauer (Springer, Berlin, 2015), pp. 1---13.

Digital Library

[29]

J. Petke, S.O. Haraldsson, M. Harman, W.B. Langdon, D.R. White, J.R. Woodward, Genetic improvement of software: a comprehensive survey. IEEE Trans. Evolut. Comput. 22(3), 415---432 (2018).

[30]

E. Schulte, Z.P. Fry, E. Fast, W. Weimer, S. Forrest, Software mutational robustness. Genet. Program. Evolvable Mach. 15(3), 281---312 (2014).

Digital Library

[31]

P. Shannon, A. Markiel, O. Ozier, N.S. Baliga, J.T. Wang, D. Ramage, N. Amin, B. Schwikowski, T. Ideker, Cytoscape: a software environment for integrated models of biomolecular interaction networks. Genome Res. 13(11), 2498---2504 (2003).

[32]

P.F. Stadler, Appl. Math. Comput. 117, 187---207 (2002)

[33]

S.L. Thomson, F. Daolio, G. Ochoa, Comparing communities of optima with funnels in combinatorial fitness landscapes, in Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '17, pp. 377---384. ACM, New York, NY, USA (2017).

Digital Library

[34]

R.H. Untch, A.J. Offutt, M.J. Harrold, Mutation analysis using mutant schemata, in Proceedings of the 1993 ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA '93, pp. 139---148. ACM, New York, NY, USA (1993).

Digital Library

[35]

L. Van Der Maaten, Accelerating t-SNE using tree-based algorithms. J. Mach. Learn. Res. 15(1), 3221---3245 (2014)

Digital Library

[36]

L. Van Der Maaten, G. Hinton, Visualizing data using t-SNE. J. Mach. Learn. Res. 9(Nov), 2579---2605 (2008)

[37]

L. Van Der Maaten, E. Postma, J. Van den Herik, Dimensionality reduction: a comparative review. Technical Report 2009-005, Tilburg University, Tilburg, The Netherlands (2009)

[38]

N. Veerapen, F. Daolio, G. Ochoa, Modelling genetic improvement landscapes with local optima networks, in Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO '17, pp. 1543---1548. ACM, New York, NY, USA (2017).

Digital Library

[39]

N. Veerapen, G. Ochoa, R. Tinós, D. Whitley, Tunnelling crossover networks for the asymmetric TSP, in Parallel Problem Solving from Nature--PPSN XIV, vol. 9921, Lecture Notes in Computer Science, ed. by J. Handl, E. Hart, P.R. Lewis, M. López-Ibáñez, G. Ochoa, B. Paechter (Springer, Berlin, 2016), pp. 994---1003.

Digital Library

[40]

S. Verel, F. Daolio, G. Ochoa, M. Tomassini, Local optima networks with escape edges, in Artificial Evolution, EA 2011, vol. 7401, Lecture Notes in Computer Science, ed. by J.K. Hao, P. Legrand, P. Collet, N. Monmarché, E. Lutton, M. Schoenauer (Springer, Berlin, 2012), pp. 49---60.

Digital Library

[41]

S. Vérel, G. Ochoa, M. Tomassini, Local optima networks of NK landscapes with neutrality. IEEE Trans. Evolut. Comput. 15(6), 783---797 (2011).

[42]

S. Volke, D. Zeckzer, M. Middendorf, G. Scheuermann, Visualizing topological properties of the search landscape of combinatorial optimization problems. In: Topological Methods in Data Analysis and Visualization IV, Mathematics and Visualization, pp. 69---85. Springer, Cham (2015).

[43]

S. Volke, D. Zeckzer, G. Scheuermann, M. Middendorf, A Visual method for analysis and comparison of search landscapes, in Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, GECCO '15, pp. 497---504. ACM, New York, NY, USA (2015).

Digital Library

[44]

D.J. Wales, Ma. Miller, Walsh T.R, Archetypal energy landscapes. Nature 394(August), 758---760 (1998)

[45]

W. Weimer, S. Forrest, Automatic program repair with evolutionary computation. Commun. ACM 53, 109---116 (2010)

Digital Library

[46]

X. Yao, M. Harman, Y. Jia, A study of equivalent and stubborn mutation operators using human analysis of equivalence, in Proceedings of the 36th International Conference on Software Engineering, ICSE 2014, pp. 919---930. ACM, New York, NY, USA (2014).

Digital Library

Cited By

Langdon WClark D(2025)Deep imperative mutations have less impactAutomated Software Engineering10.1007/s10515-024-00475-432:1Online publication date: 1-Jun-2025
https://dl.acm.org/doi/10.1007/s10515-024-00475-4
Tanaka SOchoa GLiefooghe ATakadama KSato HLi XHandl J(2024)Approximating Pareto Local Optimal Solution NetworksProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3653999(603-611)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3653999
Huang MLi KElkind E(2023)Exploring structural similarity in fitness landscapes via graph data miningProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/621(5595-5603)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/621
Show More Cited By

Recommendations

Modelling genetic improvement landscapes with local optima networks
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Local optima networks are a compact representation of the global structure of a search space. They can be used for analysis and visualisation. This paper provides one of the first analyses of program search spaces using local optima networks. These are ...
Fitness landscapes and graphs: multimodularity, ruggedness and neutrality
GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computation

One of the most commonly-used metaphors to describe the process of heuristic search methods in solving combinatorial optimization problems is that of a fitness landscape. The landscape metaphor appears most commonly in work related to evolutionary ...
Fitness landscapes and graphs: multimodularity, ruggedness and neutrality
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

One of the most commonly-used metaphors to describe the process of heuristic search methods in solving combinatorial optimization problems is that of a fitness landscape. The landscape metaphor appears most commonly in work related to evolutionary ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Genetic Programming and Evolvable Machines

Genetic Programming and Evolvable Machines Volume 19, Issue 3

September 2018

155 pages

ISSN:1389-2576

Issue’s Table of Contents

Copyright © Copyright © 2018 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 September 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Langdon WClark D(2025)Deep imperative mutations have less impactAutomated Software Engineering10.1007/s10515-024-00475-432:1Online publication date: 1-Jun-2025
https://dl.acm.org/doi/10.1007/s10515-024-00475-4
Tanaka SOchoa GLiefooghe ATakadama KSato HLi XHandl J(2024)Approximating Pareto Local Optimal Solution NetworksProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3653999(603-611)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3653999
Huang MLi KElkind E(2023)Exploring structural similarity in fitness landscapes via graph data miningProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/621(5595-5603)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/621
Sadler SRahat AWalker DArchambault DSilva SPaquete L(2023)Extrema Graphs: Fitness Landscape Analysis to the Extreme!Proceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596343(2081-2089)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596343
Langdon W(2022)Deep Genetic Programming Trees Are RobustACM Transactions on Evolutionary Learning and Optimization10.1145/35397382:2(1-34)Online publication date: 16-Aug-2022
https://dl.acm.org/doi/10.1145/3539738
Ahmad HCashin PForrest SWeimer W(2022)Digging into Semantics: Where Do Search-Based Software Repair Methods Search?Parallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_1(3-18)Online publication date: 10-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-14721-0_1
Feutrier TKessaci MVeerapen NKrawiec K(2021)Investigating the landscape of a hybrid local search approach for a timetabling problemProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3463175(1665-1673)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3463175
Langdon WPetke JClark DKrawiec K(2021)Dissipative polynomialsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3463147(1683-1691)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3463147
Tanabe RKrawiec K(2021)Towards exploratory landscape analysis for large-scale optimizationProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459300(546-555)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459300
Hénaux VGoëffon ASaubion FCoello Coello C(2020)Evolving search trajectoriesProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3390025(101-102)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3390025
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents