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

research-article

A survey of genetic improvement search spaces

Authors:

Brad Alexander,

Alexander E. I. Brownlee,

David R. WhiteAuthors Info & Claims

GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Pages 1715 - 1721

https://doi.org/10.1145/3319619.3326870

Published: 13 July 2019 Publication History

Abstract

Genetic Improvement (GI) uses automated search to improve existing software. Most GI work has focused on empirical studies that successfully apply GI to improve software's running time, fix bugs, add new features, etc. There has been little research into why GI has been so successful. For example, genetic programming has been the most commonly applied search algorithm in GI. Is genetic programming the best choice for GI? Initial attempts to answer this question have explored GI's mutation search space. This paper summarises the work published on this question to date.

References

[1]

ACM. 2019. Digital Library. http://dl.acm.org/. (2019).

[2]

Andrea Arcuri. 2008. On the automation of fixing software bugs. In 30th International Conference on Software Engineering (ICSE 2008), Leipzig, Germany, May 10--18, 2008, Companion Volume, Wilhelm Schäfer, Matthew B. Dwyer, and Volker Gruhn (Eds.). ACM, 1003--1006.

Digital Library

[3]

Andrea Arcuri and Xin Yao. 2008. A novel co-evolutionary approach to automatic software bug fixing. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2008, June 1--6, 2008, Hong Kong, China. IEEE, 162--168.

[4]

Christian Bienia, Sanjeev Kumar, Jaswinder Pal Singh, and Kai Li. 2008. The PARSEC benchmark suite: characterization and architectural implications. In 17th International Conference on Parallel Architecture and Compilation Techniques, PACT 2008, Toronto, Ontario, Canada, October 25--29, 2008, Andreas Moshovos, David Tarditi, and Kunle Olukotun (Eds.). ACM, 72--81.

Digital Library

[5]

Bobby R. Bruce, Justyna Petke, Mark Harman, and Earl T. Barr. 2017. Approximate Oracles and Synergy in Software Energy Search Spaces. (2017). Accepted to TSE.

[6]

Stephanie Forrest, ThanhVu Nguyen, Westley Weimer, and Claire Le Goues. 2009. A genetic programming approach to automated software repair. In Genetic and Evolutionary Computation Conference, GECCO 2009, Proceedings, Montreal, Québec, Canada, July 8--12, 2009, Franz Rothlauf (Ed.). ACM, 947--954.

Digital Library

[7]

Saemundur O. Haraldsson. 2017. Genetic improvement of software: from program landscapes to the automatic improvement of a live system. Ph.D. Dissertation. University of Stirling, UK. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos. 725136

[8]

Saemundur O. Haraldsson, John R. Woodward, and Alexander E. I. Brownlee. 2017. The Use of Automatic Test Data Generation for Genetic Improvement in a Live System. In 10th IEEE/ACM International Workshop on Search-Based Software Testing, SBST@ICSE 2017, Buenos Aires, Argentina, May 22--23, 2017. IEEE, 28--31.

Digital Library

[9]

Saemundur O. Haraldsson, John R. Woodward, Alexander E. I. Brownlee, and David Cairns. 2017. Exploring Fitness and Edit Distance of Mutated Python Programs. In Genetic Programming, James McDermott, Mauro Castelli, Lukas Sekanina, Evert Haasdijk, and Pablo García-Sánchez (Eds.). Springer International Publishing, Cham, 19--34.

[10]

Saemundur O. Haraldsson, John R. Woodward, Alexander E. I. Brownlee, and Kristin Siggeirsdottir. 2017. Fixing bugs in your sleep: how genetic improvement became an overnight success. In Genetic and Evolutionary Computation Conference, Berlin, Germany, July 15--19, 2017, Companion Material Proceedings, Peter A. N. Bosman (Ed.). ACM, 1513--1520.

Digital Library

[11]

Saemundur O. Haraldsson, John R. Woodward, Alexander E. I. Brownlee, Albert V. Smith, and Vilmundur Gudnason. 2017. Genetic improvement of runtime and its fitness landscape in a bioinformatics application. In Genetic and Evolutionary Computation Conference, Berlin, Germany, July 15--19, 2017, Companion Material Proceedings, Peter A. N. Bosman (Ed.). ACM, 1521--1528.

Digital Library

[12]

IEEE Xplore. 2019. Digital Library. http://ieeexplore.ieee.org/Xplore/home.jsp. (2019).

[13]

Colin G. Johnson and John R. Woodward. 2015. Fitness as Task-relevant Information Accumulation. In Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Spain, July 11--15, 2015, Companion Material Proceedings, Sara Silva and Anna Isabel Esparcia-Alcázar (Eds.). ACM, 855--856.

Digital Library

[14]

Terry Jones and Stephanie Forrest. 1995. Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms. In Proceedings of the 6th International Conference on Genetic Algorithms, Pittsburgh, PA, USA, July 15--19, 1995, Larry J. Eshelman (Ed.). Morgan Kaufmann, 184--192.

Digital Library

[15]

William B. Langdon and Mark Harman. 2010. Evolving a CUDA kernel from an nVidia template. In Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2010, Barcelona, Spain, 18--23 July 2010. IEEE, 1--8.

[16]

William B. Langdon and Mark Harman. 2015. Optimizing Existing Software With Genetic Programming. IEEE Trans. Evolutionary Computation 19, 1 (2015), 118--135.

[17]

William B. Langdon, Mark Harman, and Yue Jia. 2010. Efficient multi-objective higher order mutation testing with genetic programming. Journal of Systems and Software 83, 12 (2010), 2416--2430.

Digital Library

[18]

William B. Langdon, Brian Yee Hong Lam, Marc Modat, Justyna Petke, and Mark Harman. 2017. Genetic improvement of GPU software. Genetic Programming and Evolvable Machines 18, 1 (2017), 5--44.

Digital Library

[19]

William B. Langdon, Brian Yee Hong Lam, Justyna Petke, and Mark Harman. 2015. Improving CUDA DNA Analysis Software with Genetic Programming. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Spain, July 11--15, 2015, Sara Silva and Anna Isabel Esparcia-Alcázar (Eds.). ACM, 1063--1070.

Digital Library

[20]

William B. Langdon and Gabriela Ochoa. 2016. Genetic improvement: A key challenge for evolutionary computation. In IEEE Congress on Evolutionary Computation, CEC 2016, Vancouver, BC, Canada, July 24--29, 2016. IEEE, 3068--3075.

[21]

William B. Langdon and Justyna Petke. 2017. Software is not fragile. In First Complex Systems Digital Campus World E-Conference 2015. Springer, 203--211.

[22]

William B. Langdon, Nadarajen Veerapen, and Gabriela Ochoa. 2017. Visualising the Search Landscape of the Triangle Program. In Genetic Programming - 20th European Conference, EuroGP 2017, Amsterdam, The Netherlands, April 19--21, 2017, Proceedings (Lecture Notes in Computer Science), James McDermott, Mauro Castelli, Lukás Sekanina, Evert Haasdijk, and Pablo García-Sánchez (Eds.), Vol. 10196. 96--113.

[23]

Xuan-Bach D. Le, Duc-Hiep Chu, David Lo, Claire Le Goues, and Willem Visser. 2017. S3: syntax- and semantic-guided repair synthesis via programming by examples. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2017, Paderborn, Germany, September 4--8, 2017, Eric Bodden, Wilhelm Schäfer, Arie van Deursen, and Andrea Zisman (Eds.). ACM, 593--604.

Digital Library

[24]

Claire Le Goues, ThanhVu Nguyen, Stephanie Forrest, and Westley Weimer. 2012. GenProg: A Generic Method for Automatic Software Repair. IEEE Trans. Software Eng. 38, 1 (2012), 54--72.

Digital Library

[25]

Fan Long and Martin C. Rinard. 2016. An analysis of the search spaces for generate and validate patch generation systems. In Proceedings of the 38th International Conference on Software Engineering, ICSE 2016, Austin, TX, USA, May 14--22, 2016, Laura K. Dillon, Willem Visser, and Laurie Williams (Eds.). ACM, 702--713.

Digital Library

[26]

Matias Martinez and Martin Monperrus. 2015. Mining software repair models for reasoning on the search space of automated program fixing. Empirical Software Engineering 20, 1 (2015), 176--205.

Digital Library

[27]

Gabriela Ochoa, Marco Tomassini, Sébastien Vérel, and Christian Darabos. 2008. A study of NK landscapes' basins and local optima networks. In Genetic and Evolutionary Computation Conference, GECCO 2008, Proceedings, Atlanta, GA, USA, July 12--16, 2008, Conor Ryan and Maarten Keijzer (Eds.). ACM, 555--562.

Digital Library

[28]

Justyna Petke. 2017. New operators for non-functional genetic improvement. In Genetic and Evolutionary Computation Conference, Berlin, Germany, July 15--19, 2017, Companion Material Proceedings, Peter A. N. Bosman (Ed.). ACM, 1541--1542.

Digital Library

[29]

Justyna Petke, Saemundur O. Haraldsson, Mark Harman, David R. White, Woodward, and John R. Woodward. 2017. Genetic Improvement of Software: a Comprehensive Survey. IEEE Transactions on Evolutionary Computation (2017).

[30]

Justyna Petke, Saemundur O. Haraldsson, Mark Harman, David R. White, Woodward, and John R. Woodward. 2017. Genetic Improvement of Software: a Comprehensive Survey: Supplemental Material: Core Papers on Genetic Improvement. IEEE Transactions on Evolutionary Computation (2017). https://ieeexplore.ieee.org/abstract/document/7911210/media

[31]

Program-repair.org. 2019. Online library on automated program repair. http://program-repair.org/bibliography.html. (2019).

[32]

Christian M. Reidys and Peter F. Stadler. 2002. Combinatorial Landscapes. SIAM Rev. 44, 1 (2002), 3--54.

Digital Library

[33]

Joseph Renzullo, Stephanie Forrest, Westley Weimer, and Melanie Moses. 2018. Neutrality and Epistasis in Program Space. In Genetic Improvement Workshop, co-located with ICSE 2018.

Digital Library

[34]

Conor Ryan and Paul Walsh. 1997. Paragen II: Evolving Parallel Transformation Rules. In Computational Intelligence, Theory and Applications, International Conference, 5th Fuzzy Days, Dortmund, Germany, April 28--30, 1997, Proceedings (Lecture Notes in Computer Science), Bernd Reusch (Ed.), Vol. 1226. Springer, 573.

Digital Library

[35]

Eric M. Schulte, Zachary P. Fry, Ethan Fast, Westley Weimer, and Stephanie Forrest. 2014. Software mutational robustness. Genetic Programming and Evolvable Machines 15, 3 (2014), 281--312.

Digital Library

[36]

Stelios Sidiroglou-Douskos, Sasa Misailovic, Henry Hoffmann, and Martin C. Rinard. 2011. Managing performance vs. accuracy trade-offs with loop perforation. In SIGSOFT/FSE'11 19th ACM SIGSOFT Symposium on the Foundations of Software Engineering (FSE-19) and ESEC'11: 13th European Software Engineering Conference (ESEC-13), Szeged, Hungary, September 5--9, 2011, Tibor Gyimóthy and Andreas Zeller (Eds.). ACM, 124--134.

Digital Library

[37]

SpringerLink. 2019. Online search platform. http://link.springer.com/. (2019).

[38]

Nadarajen Veerapen, Fabio Daolio, and Gabriela Ochoa. 2017. Modelling genetic improvement landscapes with local optima networks. In Genetic and Evolutionary Computation Conference, Berlin, Germany, July 15--19, 2017, Companion Material Proceedings, Peter A. N. Bosman (Ed.). ACM, 1543--1548.

Digital Library

[39]

Nadarajen Veerapen and Gabriela Ochoa. 2018. Visualising the global structure of search landscapes: genetic improvement as a case study. Genetic Programming and Evolvable Machines 19, 3 (2018), 317--349.

Digital Library

[40]

Paul Walsh and Conor Ryan. 1995. Automatic conversion of programs from serial to parallel using Genetic Programming - The Paragen System. In In Proceedings of ParCo'95. NorthHolland, 2--2.

[41]

Westley Weimer, ThanhVu Nguyen, Claire Le Goues, and Stephanie Forrest. 2009. Automatically finding patches using genetic programming. In 31st International Conference on Software Engineering, ICSE 2009, May 16--24, 2009, Vancouver, Canada, Proceedings. IEEE, 364--374.

Digital Library

[42]

David R. White. 2009. Genetic Programming for Low-Resource Systems. Ph.D. Dissertation. University of York.

[43]

David R. White. 2016. Guiding Unconstrained Genetic Improvement. In Genetic and Evolutionary Computation Conference, GECCO 2016, Denver, CO, USA, July 20--24, 2016, Companion Material Proceedings, Tobias Friedrich, Frank Neumann, and Andrew M. Sutton (Eds.). ACM, 1133--1134.

Digital Library

[44]

David Robert White and Jeremy Singer. 2015. Rethinking Genetic Improvement Programming. In Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Spain, July 11--15, 2015, Companion Material Proceedings, Sara Silva and Anna Isabel Esparcia-Alcázar (Eds.). ACM, 845--846.

Digital Library

[45]

Yue Jia, Ke Mao, Mark Harman. {n. d.}. Finding and fixing software bugs automatically with SapFix and Sapienz. https://code.fb.com/developer-tools/finding-and-fixing-software-bugs-automatically-with-sapfix-and-sapienz/. ({n. d.}).

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
Brownlee ACallan JEven-Mendoza KGeiger AHanna CPetke JSarro FSobania D(2025)Large language model based mutations in genetic improvementAutomated Software Engineering10.1007/s10515-024-00473-632:1Online publication date: 21-Jan-2025
https://doi.org/10.1007/s10515-024-00473-6
Brownlee AHaraldsson SWoodward JWagner MLi XHandl J(2024)Genetic Improvement: Taking real-world source code and improving it using computational search methodsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648418(1197-1230)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648418
Show More Cited By

Index Terms

A survey of genetic improvement search spaces
1. Software and its engineering
  1. Software creation and management
    1. Search-based software engineering

Recommendations

Reducing Energy Consumption Using Genetic Improvement
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Genetic Improvement (GI) is an area of Search Based Software Engineering which seeks to improve software's non-functional properties by treating program code as if it were genetic material which is then evolved to produce more optimal solutions. ...
Gin: genetic improvement research made easy
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference

Genetic improvement (GI) is a young field of research on the cusp of transforming software development. GI uses search to improve existing software. Researchers have already shown that GI can improve human-written code, ranging from program repair to ...
GI4GI: Improving Genetic Improvement Fitness Functions
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Genetic improvement (GI) has been successfully used to optimise non-functional properties of software, such as execution time, by automatically manipulating program's source code. Measurement of non-functional properties, however, is a non-trivial task; ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

July 2019

2161 pages

ISBN:9781450367486

DOI:10.1145/3319619

Editor:
Manuel López-Ibáñez
University of Manchester, UK
,
General Chairs:
Anne Auger
Inria and Ecole Polytechnique, France
,
Thomas Stützle
IRIDIA, Université libre de Bruxelles Belgium

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

GECCO '19

Sponsor:

SIGEVO

GECCO '19: Genetic and Evolutionary Computation Conference

July 13 - 17, 2019

Prague, Czech Republic

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
143
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)8

Reflects downloads up to 09 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
Brownlee ACallan JEven-Mendoza KGeiger AHanna CPetke JSarro FSobania D(2025)Large language model based mutations in genetic improvementAutomated Software Engineering10.1007/s10515-024-00473-632:1Online publication date: 21-Jan-2025
https://doi.org/10.1007/s10515-024-00473-6
Brownlee AHaraldsson SWoodward JWagner MLi XHandl J(2024)Genetic Improvement: Taking real-world source code and improving it using computational search methodsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648418(1197-1230)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648418
Renzullo JWeimer WForrest S(2023)Evolving Software: Combining Online Learning with Mutation-Based Stochastic SearchACM Transactions on Evolutionary Learning and Optimization10.1145/35976173:4(1-32)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3597617
Browniee AHaraldsson SWoodward JSilva SPaquete L(2023)Genetic Improvement: Taking real-world source code and improving it using computational search methodsProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3595044(1213-1247)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3595044
Reid BTreude CWagner M(2023)Using the TypeScript compiler to fix erroneous Node.js snippets2023 IEEE 23rd International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM59687.2023.00031(220-230)Online publication date: 2-Oct-2023
https://doi.org/10.1109/SCAM59687.2023.00031
Langdon WAlexander B(2023)Genetic Improvement of OLC and H3 with Magpie2023 IEEE/ACM International Workshop on Genetic Improvement (GI)10.1109/GI59320.2023.00011(9-16)Online publication date: May-2023
https://doi.org/10.1109/GI59320.2023.00011
Langdon W(2023)Response to comments on “Jaws 30”Genetic Programming and Evolvable Machines10.1007/s10710-023-09474-y24:2Online publication date: 22-Nov-2023
https://dl.acm.org/doi/10.1007/s10710-023-09474-y
Petke JAlexander BBarr EBrownlee AWagner MWhite D(2023)Program transformation landscapes for automated program modification using GinEmpirical Software Engineering10.1007/s10664-023-10344-528:4Online publication date: 14-Jul-2023
https://dl.acm.org/doi/10.1007/s10664-023-10344-5
Langdon WAl-Subaihin ABlot AClark D(2023)Genetic Improvement of LLVM Intermediate RepresentationGenetic Programming10.1007/978-3-031-29573-7_16(244-259)Online publication date: 12-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-29573-7_16
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten