Genetic improvement (computer science): Difference between revisions
Content deleted Content added
| (3 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
In [[Software|computer software]] development, '''genetic Improvement''' is the use of [[Mathematical optimization|optimisation]] and [[machine learning]] techniques, particularly [[search-based software engineering]] techniques such as [[genetic programming]] to improve existing [[software]].<ref>{{cite book | doi = 10.1007/978-3-319-20883-1_8 |author=Langdon, William B. | |
In [[Software|computer software]] development, '''genetic Improvement''' is the use of [[Mathematical optimization|optimisation]] and [[machine learning]] techniques, particularly [[search-based software engineering]] techniques such as [[genetic programming]] to improve existing [[software]].<ref>{{cite book | doi = 10.1007/978-3-319-20883-1_8 |author=Langdon, William B. |title=Handbook of Genetic Programming Applications | chapter=Genetically Improved Software | pages=181–220|year=2015 |isbn=978-3-319-20882-4 }}</ref> |
||
<ref>{{cite journal | doi = 10.1109/TEVC.2017.2693219 |author=Justyna Petke and Saemundur O. Haraldsson and Mark Harman and William B. Langdon and David R. White and John R. Woodward | title=Genetic Improvement of Software: a Comprehensive Survey | journal=IEEE Transactions on Evolutionary Computation|volume=22 |issue=3 |pages=415–432 |year=2018 |url=http://discovery.ucl.ac.uk/10038273/1/07911210.pdf |hdl=1893/25358 |hdl-access=free }}</ref> |
<ref>{{cite journal | doi = 10.1109/TEVC.2017.2693219 |author=Justyna Petke and Saemundur O. Haraldsson and Mark Harman and William B. Langdon and David R. White and John R. Woodward | title=Genetic Improvement of Software: a Comprehensive Survey | journal=IEEE Transactions on Evolutionary Computation|volume=22 |issue=3 |pages=415–432 |year=2018 |url=http://discovery.ucl.ac.uk/10038273/1/07911210.pdf |hdl=1893/25358 |s2cid=30314751 |hdl-access=free }}</ref> |
||
The improved [[Computer program|program]] need not behave identically to the original. For example, [[automatic bug fixing]] improves [[program code]] by reducing or eliminating [[Software bug|buggy]] behaviour.<ref>{{cite journal | doi = 10.1145/1735223.1735249 |author=Weimer, Westley|display-authors=etal | volume=53 |issue=5| title=Automatic program repair with evolutionary computation | journal=Communications of the ACM | pages= |
The improved [[Computer program|program]] need not behave identically to the original. For example, [[automatic bug fixing]] improves [[program code]] by reducing or eliminating [[Software bug|buggy]] behaviour.<ref>{{cite journal | doi = 10.1145/1735223.1735249 |author=Weimer, Westley|display-authors=etal | volume=53 |issue=5| title=Automatic program repair with evolutionary computation | journal=Communications of the ACM | pages=109–116|year=2010|citeseerx=10.1.1.170.188|s2cid=7408151 }}</ref> |
||
In other cases the improved software should behave identically to the old version but is better because, |
In other cases the improved software should behave identically to the old version but is better because, |
||
for example: |
for example: |
||
it runs faster,<ref>{{cite journal | doi = 10.1109/TEVC.2013.2281544 | volume=19 | title=Optimizing Existing Software With Genetic Programming | journal=IEEE Transactions on Evolutionary Computation | pages=118–135| year=2015 | last1=Langdon | first1=William B. | last2=Harman | first2=Mark }}</ref> |
it runs faster,<ref>{{cite journal | doi = 10.1109/TEVC.2013.2281544 | volume=19 | title=Optimizing Existing Software With Genetic Programming | journal=IEEE Transactions on Evolutionary Computation | pages=118–135| year=2015 | last1=Langdon | first1=William B. | last2=Harman | first2=Mark | s2cid=9891830 }}</ref> |
||
it uses less [[Computer memory|memory]],<ref>{{cite book | doi = 10.1145/2739480.2754648 |
it uses less [[Computer memory|memory]],<ref>{{cite book | doi = 10.1145/2739480.2754648 | pages=1375–1382 | year=2015 | last1=Wu | first1=Fan | last2=Weimer | first2=Westley | last3=Harman | first3=Mark | last4=Jia | first4=Yue | last5=Krinke | first5=Jens | title=Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation | chapter=Deep Parameter Optimisation | isbn=9781450334723 | s2cid=17820784 }}</ref> |
||
it uses less [[Electrical energy|energy]]<ref>{{cite book | doi = 10.1145/2739480.2754752 |
it uses less [[Electrical energy|energy]]<ref>{{cite book | doi = 10.1145/2739480.2754752 | pages=1327–1334 | year=2015 | last1=Bruce | first1=Bobby R. | last2=Petke | first2=Justyna | last3=Harman | first3=Mark | title=Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation | chapter=Reducing Energy Consumption Using Genetic Improvement | isbn=9781450334723 | s2cid=207224618 }}</ref> |
||
or |
or |
||
it runs on a different type of computer.<ref>{{cite book | doi = 10.1007/978-3-662-44303-3_8 |
it runs on a different type of computer.<ref>{{cite book | doi = 10.1007/978-3-662-44303-3_8 | journal=EuroGP 2014 | volume=8599 | pages=87–99| series=Lecture Notes in Computer Science | year=2014 | last1=Langdon | first1=William B. | last2=Harman | first2=Mark | title=Genetic Programming | chapter=Genetically Improved CUDA C++ Software | isbn=978-3-662-44302-6 | url=https://discovery.ucl.ac.uk/id/eprint/1419637/ }}</ref> |
||
GI differs from, for example, [[Formal methods|formal program translation]], in that it primarily verifies the behaviour of the new mutant version by running both the new and the old software on [[Software testing|test inputs]] and comparing their output and performance in order to see if the new software can still do what is wanted of the original program and is now better. |
GI differs from, for example, [[Formal methods|formal program translation]], in that it primarily verifies the behaviour of the new mutant version by running both the new and the old software on [[Software testing|test inputs]] and comparing their output and performance in order to see if the new software can still do what is wanted of the original program and is now better. |
||
| Line 15: | Line 15: | ||
Genetic improvement can be used with [[multi-objective optimization]] to consider improving software along multiple dimensions or to consider [[trade-off]]s between several objectives, such as asking GI to evolve programs which trade speed against the quality of answers they give. Of course it may be possible to find programs which are both faster and give better answers. |
Genetic improvement can be used with [[multi-objective optimization]] to consider improving software along multiple dimensions or to consider [[trade-off]]s between several objectives, such as asking GI to evolve programs which trade speed against the quality of answers they give. Of course it may be possible to find programs which are both faster and give better answers. |
||
Mostly Genetic Improvement makes typically small changes or edits (also known as [[Mutation testing|mutations]]) to the program's [[source code]] but sometimes the mutations are made to [[assembly code]], [[Bytecode|byte code]]<ref>{{cite journal | doi = 10.1109/TEVC.2010.2052622 | volume=15 | issue=2 | title=Flight of the FINCH Through the Java Wilderness | journal=IEEE Transactions on Evolutionary Computation | pages=166–182| year=2011 | last1=Orlov | first1=Michael | last2=Sipper | first2=Moshe | citeseerx=10.1.1.298.6272 }}</ref> |
Mostly Genetic Improvement makes typically small changes or edits (also known as [[Mutation testing|mutations]]) to the program's [[source code]] but sometimes the mutations are made to [[assembly code]], [[Bytecode|byte code]]<ref>{{cite journal | doi = 10.1109/TEVC.2010.2052622 | volume=15 | issue=2 | title=Flight of the FINCH Through the Java Wilderness | journal=IEEE Transactions on Evolutionary Computation | pages=166–182| year=2011 | last1=Orlov | first1=Michael | last2=Sipper | first2=Moshe | citeseerx=10.1.1.298.6272 | s2cid=14616802 }}</ref> |
||
or binary [[machine code]].<ref>{{cite book | doi = 10.1145/2739482.2768427 | |
or binary [[machine code]].<ref>{{cite book | doi = 10.1145/2739482.2768427 | pages=847–854 | year=2015 | last1=Schulte | first1=Eric M. | last2=Weimer | first2=Westley | last3=Forrest | first3=Stephanie | title=Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation | chapter=Repairing COTS Router Firmware without Access to Source Code or Test Suites | isbn=9781450334884 | s2cid=14772346 }}</ref> |
||
==References== |
==References== |
||
| Line 24: | Line 24: | ||
*Open PhD tutorial http://phdopen.mimuw.edu.pl/index.php?page=z15w1 (also covers SBSE and CIT but last of three topics is Genetic Improvement of software). |
*Open PhD tutorial http://phdopen.mimuw.edu.pl/index.php?page=z15w1 (also covers SBSE and CIT but last of three topics is Genetic Improvement of software). |
||
*International Workshops on Genetic Improvement: http://www.geneticimprovementofsoftware.com web pages include GI community pages http://geneticimprovementofsoftware.com/learn/about |
*International Workshops on Genetic Improvement: http://www.geneticimprovementofsoftware.com web pages include GI community pages http://geneticimprovementofsoftware.com/learn/about |
||
| ⚫ | |||
==Tools== |
==Tools== |
||
| Line 31: | Line 29: | ||
*Magpie https://github.com/bloa/magpie |
*Magpie https://github.com/bloa/magpie |
||
*PyGGI https://github.com/coinse/pyggi |
*PyGGI https://github.com/coinse/pyggi |
||
{{Evolutionary computation}} |
|||
| ⚫ | |||
Latest revision as of 19:30, 6 October 2023
In computer software development, genetic Improvement is the use of optimisation and machine learning techniques, particularly search-based software engineering techniques such as genetic programming to improve existing software.[1] [2] The improved program need not behave identically to the original. For example, automatic bug fixing improves program code by reducing or eliminating buggy behaviour.[3] In other cases the improved software should behave identically to the old version but is better because, for example: it runs faster,[4] it uses less memory,[5] it uses less energy[6] or it runs on a different type of computer.[7] GI differs from, for example, formal program translation, in that it primarily verifies the behaviour of the new mutant version by running both the new and the old software on test inputs and comparing their output and performance in order to see if the new software can still do what is wanted of the original program and is now better.
Genetic improvement can be used to create multiple versions of programs, each tailored to be better for a particular use or for a particular computer.
Genetic improvement can be used with multi-objective optimization to consider improving software along multiple dimensions or to consider trade-offs between several objectives, such as asking GI to evolve programs which trade speed against the quality of answers they give. Of course it may be possible to find programs which are both faster and give better answers.
Mostly Genetic Improvement makes typically small changes or edits (also known as mutations) to the program's source code but sometimes the mutations are made to assembly code, byte code[8] or binary machine code.[9]
References
[edit]- ^ Langdon, William B. (2015). "Genetically Improved Software". Handbook of Genetic Programming Applications. pp. 181–220. doi:10.1007/978-3-319-20883-1_8. ISBN 978-3-319-20882-4.
- ^ Justyna Petke and Saemundur O. Haraldsson and Mark Harman and William B. Langdon and David R. White and John R. Woodward (2018). "Genetic Improvement of Software: a Comprehensive Survey" (PDF). IEEE Transactions on Evolutionary Computation. 22 (3): 415–432. doi:10.1109/TEVC.2017.2693219. hdl:1893/25358. S2CID 30314751.
- ^ Weimer, Westley; et al. (2010). "Automatic program repair with evolutionary computation". Communications of the ACM. 53 (5): 109–116. CiteSeerX 10.1.1.170.188. doi:10.1145/1735223.1735249. S2CID 7408151.
- ^ Langdon, William B.; Harman, Mark (2015). "Optimizing Existing Software With Genetic Programming". IEEE Transactions on Evolutionary Computation. 19: 118–135. doi:10.1109/TEVC.2013.2281544. S2CID 9891830.
- ^ Wu, Fan; Weimer, Westley; Harman, Mark; Jia, Yue; Krinke, Jens (2015). "Deep Parameter Optimisation". Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. pp. 1375–1382. doi:10.1145/2739480.2754648. ISBN 9781450334723. S2CID 17820784.
- ^ Bruce, Bobby R.; Petke, Justyna; Harman, Mark (2015). "Reducing Energy Consumption Using Genetic Improvement". Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. pp. 1327–1334. doi:10.1145/2739480.2754752. ISBN 9781450334723. S2CID 207224618.
- ^ Langdon, William B.; Harman, Mark (2014). "Genetically Improved CUDA C++ Software". Genetic Programming. Lecture Notes in Computer Science. Vol. 8599. pp. 87–99. doi:10.1007/978-3-662-44303-3_8. ISBN 978-3-662-44302-6.
{{cite book}}:|journal=ignored (help) - ^ Orlov, Michael; Sipper, Moshe (2011). "Flight of the FINCH Through the Java Wilderness". IEEE Transactions on Evolutionary Computation. 15 (2): 166–182. CiteSeerX 10.1.1.298.6272. doi:10.1109/TEVC.2010.2052622. S2CID 14616802.
- ^ Schulte, Eric M.; Weimer, Westley; Forrest, Stephanie (2015). "Repairing COTS Router Firmware without Access to Source Code or Test Suites". Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. pp. 847–854. doi:10.1145/2739482.2768427. ISBN 9781450334884. S2CID 14772346.
External links
[edit]- Open PhD tutorial http://phdopen.mimuw.edu.pl/index.php?page=z15w1 (also covers SBSE and CIT but last of three topics is Genetic Improvement of software).
- International Workshops on Genetic Improvement: http://www.geneticimprovementofsoftware.com web pages include GI community pages http://geneticimprovementofsoftware.com/learn/about