Content deleted Content added
m Reverted edits by 69.217.74.80 (talk) to last version by 207.46.92.17 |
Citation bot (talk | contribs) Altered doi-broken-date. | Use this bot. Report bugs. | #UCB_CommandLine |
||
| (311 intermediate revisions by 97 users not shown) | |||
Line 1:
{{Short description|Application of metaheuristic search techniques to software engineering}}
{{Use dmy dates|date=December 2020}}
'''Search-based software engineering''' ('''SBSE''') applies [[metaheuristic]] search techniques such as [[genetic algorithms]], [[simulated annealing]] and [[tabu search]] to [[software engineering]] problems. Many activities in [[software engineering]] can be stated as [[Optimization (mathematics)|optimization]] problems. [[Optimization (mathematics)|Optimization]] techniques of [[operations research]] such as [[linear programming]] or [[dynamic programming]] are often impractical for large scale [[software engineering]] problems because of their [[Computational complexity theory|computational complexity]] or their assumptions on the problem structure. Researchers and practitioners use [[metaheuristic]] search techniques, which impose little assumptions on the problem structure, to find near-optimal or "good-enough" solutions.<ref>{{Cite journal |last1=Mohan |first1=M. |last2=Greer |first2=D. |date=2019-08-01 |title=Using a many-objective approach to investigate automated refactoring |url=https://www.sciencedirect.com/science/article/pii/S0950584919300916 |journal=Information and Software Technology |volume=112 |pages=83–101 |doi=10.1016/j.infsof.2019.04.009 |issn=0950-5849}}</ref>
SBSE problems can be divided into two types:
* black-box optimization problems, for example, assigning people to tasks (a typical [[combinatorial optimization]] problem).
* white-box problems where operations on source code need to be considered.<ref>
{{Cite conference
| doi = 10.1109/SCAM.2010.28
| conference = 10th IEEE Working Conference on Source Code Analysis and Manipulation (SCAM 2010)
| pages = 7–19
| last = Harman
| first = Mark
| title = Why Source Code Analysis and Manipulation Will Always be Important
| book-title = 10th IEEE Working Conference on Source Code Analysis and Manipulation (SCAM 2010)
| year = 2010
}}</ref>
==Definition==
SBSE converts a software engineering problem into a computational search problem that can be tackled with a [[metaheuristic]]. This involves defining a search space, or the set of possible solutions. This space is typically too large to be explored exhaustively, suggesting a [[metaheuristic]] approach. A metric<ref>
{{Cite conference
| doi = 10.1109/METRIC.2004.1357891
| conference = 10th International Symposium on Software Metrics, 2004
| pages = 58–69
| last = Harman
| first = Mark
|author2=John A. Clark
| title = Metrics are fitness functions too
| book-title = Proceedings of the 10th International Symposium on Software Metrics, 2004
| year = 2004
}}</ref> (also called a fitness function, cost function, objective function or quality measure) is then used to measure the quality of potential solutions. Many software engineering problems can be reformulated as a computational search problem.<ref>{{Cite journal
| doi = 10.1049/ip-sen:20030559
| issn = 1462-5970
| volume = 150
| issue = 3
| pages = 161–175
| last1 = Clark
| first1 = John A.
| last2 = Dolado
| first2 = José Javier
| last3 = Harman
| first3 = Mark
| last4 = Hierons
| first4 = Robert M.
| last5 = Jones
| first5 = Bryan F.
| last6 = Lumkin
| first6 = M.
| last7 = Mitchell
| first7 = Brian S.
| last8 = Mancoridis
| first8 = Spiros
| last9 = Rees
| first9 = K.
| last10 = Roper
| first10 = Marc
| last11 = Shepperd
| first11 = Martin J.
| title = Reformulating software engineering as a search problem
| journal = [[IEE Proceedings - Software]]
| year = 2003
| doi-broken-date = 12 July 2025
| citeseerx = 10.1.1.144.3059
}}</ref>
The term "[[search-based application]]", in contrast, refers to using [[search-engine technology]], rather than search techniques, in another industrial application.
==Brief history==
One of the earliest attempts to apply [[Optimization (mathematics)|optimization]] to a [[software engineering]] problem was reported by [[Webb Miller]] and David Spooner in 1976 in the area of [[software testing]].<ref>
{{Cite journal
| doi = 10.1109/TSE.1976.233818
| issn = 0098-5589
| volume = SE-2
| issue = 3
| pages = 223–226
| last1 = Miller
| first1 = Webb
| last2 = Spooner
| first2 = David L.
| title = Automatic Generation of Floating-Point Test Data
| journal = IEEE Transactions on Software Engineering
| year = 1976
| s2cid = 18875300
}}</ref> In 1992, S. Xanthakis and his colleagues applied a search technique to a [[software engineering]] problem for the first time.<ref>S. Xanthakis, C. Ellis, C. Skourlas, A. Le Gall, S. Katsikas and K. Karapoulios, "Application of genetic algorithms to software testing," in ''Proceedings of the 5th International Conference on Software Engineering and its Applications'', Toulouse, France, 1992, pp. 625–636</ref> The term SBSE was first used in 2001 by [[Mark Harman (computer scientist)|Harman]] and Jones.<ref>
{{Cite journal
| doi = 10.1016/S0950-5849(01)00189-6
| issn = 0950-5849
| volume = 43
| issue = 14
| pages = 833–839
| last1 = Harman
| first1 = Mark
| last2 = Jones
| first2 = Bryan F.
| title = Search-based software engineering
| journal = Information and Software Technology
| date = 2001-12-15
| citeseerx = 10.1.1.143.9716
}}</ref> The research community grew to include more than 800 authors by 2013, spanning approximately 270 institutions in 40 countries.<ref>{{Cite journal|last1=Harman|first1=Mark|last2=Mansouri|first2=S. Afshin|last3=Zhang|first3=Yuanyuan|date=2012-11-01|title=Search-based software engineering: Trends, techniques and applications|journal=ACM Computing Surveys|language=en|volume=45|issue=1|pages=1–61|doi=10.1145/2379776.2379787|s2cid=207198163|url=http://bura.brunel.ac.uk/handle/2438/8811}}</ref>
==Application areas==
Search-based software engineering is applicable to almost all phases of the [[software life cycle|software development process]]. [[Software testing]] has been one of the major applications.<ref>
{{Cite journal
| doi = 10.1002/stvr.294
| issn = 1099-1689
| volume = 14
| issue = 2
| pages = 105–156
| last = McMinn
| first = Phil
| title = Search-based software test data generation: a survey
| journal = Software Testing, Verification and Reliability
| year = 2004
| citeseerx = 10.1.1.122.33
| s2cid = 17408871
}}</ref> Search techniques have been applied to other [[software engineering]] activities, for instance, [[requirements analysis]],<ref>
{{Cite journal
| doi = 10.1016/j.infsof.2003.07.002
| issn = 0950-5849
| volume = 46
| issue = 4
| pages = 243–253
| last1 = Greer
| first1 = Des
| last2 = Ruhe
| first2 = Guenther
| title = Software release planning: an evolutionary and iterative approach
| journal = Information and Software Technology
| date = 2004-03-15
| citeseerx = 10.1.1.195.321
| s2cid = 710923
}}</ref><ref>{{Cite conference
| doi = 10.1109/SBES.2009.23
| conference = XXIII Brazilian Symposium on Software Engineering, 2009. SBES '09
| pages = 207–215
| last1 = Colares
| first1 = Felipe
| last2 = Souza
| first2 = Jerffeson
| last3 = Carmo
| first3 = Raphael
| last4 = Pádua
| first4 = Clarindo
| last5 = Mateus
| first5 = Geraldo R.
| title = A New Approach to the Software Release Planning
| book-title = XXIII Brazilian Symposium on Software Engineering, 2009. SBES '09
| year = 2009
}}</ref> [[software design|design]],<ref>
{{Cite journal
| doi = 10.1016/S0950-5849(01)00195-1
| issn = 0950-5849
| volume = 43
| issue = 14
| pages = 891–904
| last1 = Clark
| first1 = John A.
| last2 = Jacob
| first2 = Jeremy L.
| title = Protocols are programs too: the meta-heuristic search for security protocols
| journal = Information and Software Technology
| date = 2001-12-15
| citeseerx = 10.1.1.102.6016
}}</ref><ref>{{Cite journal|last=Räihä|first=Outi|date=2010-11-01|title=A survey on search-based software design|journal=Computer Science Review|volume=4|issue=4|pages=203–249|doi=10.1016/j.cosrev.2010.06.001|issn=1574-0137|url=https://trepo.tuni.fi/bitstream/10024/65330/1/D-2009-1.pdf|citeseerx=10.1.1.188.9036}}</ref> [[Code refactoring|refactoring]],<ref>{{Cite journal|last1=Mariani|first1=Thainá|last2=Vergilio|first2=Silvia Regina|date=2017-03-01|title=A systematic review on search-based refactoring|journal=Information and Software Technology|volume=83|pages=14–34|doi=10.1016/j.infsof.2016.11.009|issn=0950-5849}}</ref> [[software development|development]],<ref>
{{Cite journal
| doi = 10.1016/j.ins.2006.12.020
| issn = 0020-0255
| volume = 177
| issue = 11
| pages = 2380–2401
| last1 = Alba
| first1 = Enrique
| last2 = Chicano
| first2 = J. Francisco
| title = Software project management with GAs
| journal = Information Sciences
| date = 2007-06-01
| hdl = 10630/8145
| hdl-access = free
}}</ref> and [[software maintenance|maintenance]].<ref>
{{Cite conference
| doi = 10.1109/ICSM.2005.79
| conference = Proceedings of the 21st IEEE International Conference on Software Maintenance, 2005. ICSM'05
| pages = 240–249
| last1 = Antoniol
| first1 = Giuliano
| last2 = Di Penta
| first2 = Massimiliano
| last3 = Harman
| first3 = Mark
| title = Search-based techniques applied to optimization of project planning for a massive maintenance project
| book-title = Proceedings of the 21st IEEE International Conference on Software Maintenance, 2005. ICSM'05
| year = 2005
| citeseerx = 10.1.1.63.8069
}}</ref>
===Requirements engineering===
[[Requirements engineering]] is the process by which the needs of a software's users and environment are determined and managed. Search-based methods have been used for requirements selection and optimisation with the goal of finding the best possible subset of requirements that matches user requests amid constraints such as limited resources and interdependencies between requirements. This problem is often tackled as a [[MCDM|multiple-criteria decision-making]] problem and, generally involves presenting the decision maker with a set of good compromises between cost and user satisfaction as well as the requirements risk.<ref>
{{Cite thesis
| type = PhD
| publisher = University of London
| last = Zhang
| first = Yuanyuan
| title = Multi-Objective Search-based Requirements Selection and Optimisation
| ___location = Strand, London, UK
| date = February 2010
| url = http://eprints.ucl.ac.uk/170695/
}}</ref><ref>
Y. Zhang and M. Harman and S. L. Lim, "[http://www.cs.ucl.ac.uk/fileadmin/UCL-CS/images/Research_Student_Information/RN_11_12.pdf Search Based Optimization of Requirements Interaction Management]," Department of Computer Science, University College London, Research Note RN/11/12, 2011.
</ref>
<ref>{{cite book|last1=Li|first1=Lingbo|last2=Harman|first2=Mark|last3=Letier|first3=Emmanuel|last4=Zhang|first4=Yuanyuan|title=Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation |chapter=Robust next release problem |date=2014|pages=1247–1254|doi=10.1145/2576768.2598334|isbn=9781450326629|series=Gecco '14|s2cid=8423690}}</ref><ref>{{cite journal|last1=Li|first1=L.|last2=Harman|first2=M.|last3=Wu|first3=F.|last4=Zhang|first4=Y.|title=The Value of Exact Analysis in Requirements Selection|journal=IEEE Transactions on Software Engineering|date=2017|volume=43|issue=6|pages=580–596|doi=10.1109/TSE.2016.2615100|s2cid=8398275|issn=0098-5589|url=https://discovery.ucl.ac.uk/id/eprint/1554255/1/Harman_07582553.pdf}}</ref>
===Debugging and maintenance===
Identifying a [[software bug]] (or a [[code smell]]) and then [[debugging]] (or [[refactoring]]) the software is largely a manual and labor-intensive endeavor, though the process is tool-supported. One objective of SBSE is to automatically identify and fix bugs (for example via [[mutation testing]]).
[[Genetic programming]], a biologically-inspired technique that involves evolving programs through the use of crossover and mutation, has been used to search for repairs to programs by altering a few lines of source code. The [http://dijkstra.cs.virginia.edu/genprog/ GenProg Evolutionary Program Repair] software repaired 55 out of 105 bugs for approximately $8 each in one test.<ref>{{Cite conference
| doi = 10.1109/ICSE.2012.6227211
| conference = 2012 34th International Conference on Software Engineering (ICSE)
| pages = 3–13
| last1 = Le Goues
| first1 = Claire | author1-link = Claire Le Goues
| last2 = Dewey-Vogt
| first2 = Michael
| last3 = Forrest
| first3 = Stephanie
| last4 = Weimer
| first4 = Westley
| title = A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each
| book-title = 2012 34th International Conference on Software Engineering (ICSE)
| year = 2012
}}</ref>
[[Coevolution]] adopts a "predator and prey" [[metaphor]] in which a suite of programs and a suite of [[Unit Testing|unit tests]] evolve together and influence each other.<ref>{{Cite conference
| doi = 10.1109/CEC.2008.4630793
| conference = IEEE Congress on Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence)
| pages = 162–168
| last1 = Arcuri
| first1 = Andrea
| last2 = Yao
| first2 = Xin
| title = A novel co-evolutionary approach to automatic software bug fixing
| book-title = IEEE Congress on Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence)
| year = 2008
| citeseerx = 10.1.1.159.7991
}}</ref>
===Testing===
Search-based software engineering has been applied to software testing, including the automatic generation of test cases (test data), test case minimization and test case prioritization.<ref>{{Cite book|last1=Harman|first1=Mark|last2=Jia|first2=Yue|last3=Zhang|first3=Yuanyuan|title=2015 IEEE 8th International Conference on Software Testing, Verification and Validation (ICST) |chapter=Achievements, Open Problems and Challenges for Search Based Software Testing |date=April 2015|___location=Graz, Austria|publisher=IEEE|pages=1–12|doi=10.1109/ICST.2015.7102580|citeseerx=10.1.1.686.7418|isbn=978-1-4799-7125-1|s2cid=15272060}}</ref> [[Regression testing]] has also received some attention.
===Optimizing software===
The use of SBSE in [[program optimization]], or modifying a piece of software to make it more efficient in terms of speed and resource use, has been the object of successful research.<ref>{{cite journal |last1=Memeti |first1=Suejb |last2=Pllana |first2=Sabri |last3=Binotto |first3=Alecio |last4=Kolodziej |first4=Joanna |last5=Brandic |first5=Ivona |author5-link= Ivona Brandić |title=Using meta-heuristics and machine learning for software optimization of parallel computing systems: a systematic literature review |journal=Computing |volume=101 |issue=8 |date=2018 |pages=893–936 |doi=10.1007/s00607-018-0614-9 |arxiv=1801.09444 |bibcode=2018arXiv180109444M |s2cid=13868111 }}</ref> In one instance, a 50,000 line program was genetically improved, resulting in a program 70 times faster on average.<ref>
{{Cite journal
| last1 = Langdon
| first1 = William B.
| last2 = Harman
| first2 = Mark
| title = Optimising Existing Software with Genetic Programming
| journal = IEEE Transactions on Evolutionary Computation
| url = http://www0.cs.ucl.ac.uk/staff/w.langdon/ftp/papers/Langdon_2013_ieeeTEC.pdf
}}</ref>
A recent work by Basios et al. shows that by optimising the data structure, Google Guava found a 9% improvement in execution time, 13% improvement in memory consumption and 4% improvement in CPU usage separately.<ref>{{cite book|last1=Basios|first1=Michail|last2=Li|first2=Lingbo|last3=Wu|first3=Fan|last4=Kanthan|first4=Leslie|last5=Barr|first5=Earl T.|title=Search Based Software Engineering |chapter=Optimising Darwinian Data Structures on Google Guava |volume=10452|date=9 September 2017|pages=161–167|doi=10.1007/978-3-319-66299-2_14|language=en|series=Lecture Notes in Computer Science|isbn=978-3-319-66298-5|url=http://discovery.ucl.ac.uk/10062895/1/ssbse_dariwnian_guava.pdf}}</ref>
===Project management===
A number of decisions that are normally made by a project manager can be done automatically, for example, project scheduling.<ref>
{{Cite conference
| publisher = ACM
| doi = 10.1145/2330163.2330332
| isbn = 978-1-4503-1177-9
| pages = 1221–1228
| last1 = Minku
| first1 = Leandro L.
| last2 = Sudholt
| first2 = Dirk
| last3 = Yao
| first3 = Xin
| title = Evolutionary algorithms for the project scheduling problem: runtime analysis and improved design
| book-title = Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference
| ___location = New York, NY, USA
| series = GECCO '12
| year = 2012
}}</ref>
==Tools==
Tools available for SBSE include OpenPAT,<ref>
{{cite book
|last1 = Mayo
|first1 = M.
|last2 = Spacey
|first2 = S.
|title = Search Based Software Engineering
|chapter = Predicting Regression Test Failures Using Genetic Algorithm-Selected Dynamic Performance Analysis Metrics
|series = Lecture Notes in Computer Science
|volume = 8084
|pages = 158–171
|year = 2013
|doi = 10.1007/978-3-642-39742-4_13
|chapter-url= https://researchcommons.waikato.ac.nz/bitstream/10289/7763/1/SBSE13.pdf
|hdl= 10289/7763
|isbn = 978-3-642-39741-7
|hdl-access= free
}}</ref> [[EvoSuite]],<ref>{{cite web |url=http://www.evosuite.org/ |title=Home |website=evosuite.org}}</ref> and [https://coverage.readthedocs.io/ Coverage], a code coverage measurement tool for Python.<ref>{{Citation|last=others|first=Ned Batchelder and 100|title=coverage: Code coverage measurement for Python|url=https://bitbucket.org/ned/coveragepy|access-date=2018-03-14}}
</ref>
==Methods and techniques==
A number of methods and techniques are available, including:
* [[profiling (computer programming)|Profiling]]<ref>{{Cite web | url=http://java-source.net/open-source/profilers | title=Open Source Profilers in Java}}</ref> via [[instrumentation]] in order to monitor certain parts of a program as it is executed.
* Obtaining an [[abstract syntax tree]] associated with the program, which can be automatically examined to gain insights into its structure.
* Applications of [[program slicing]] relevant to SBSE include [[software maintenance]], [[Optimization (computer science)|optimization]] and [[Program analysis (computer science)|program analysis]].
* [[Code coverage]] allows measuring how much of the code is executed with a given set of input data.
* [[Static program analysis]]
==Industry acceptance==
As a relatively new area of research, SBSE does not yet experience broad industry acceptance.
Successful applications of SBSE in the industry can mostly be found within software testing, where the capability to automatically generate random test inputs for uncovering bugs at a big scale is attractive to companies. In 2017, [[Facebook]] acquired the software startup Majicke Limited that developed Sapienz, a search-based bug finding app.<ref>{{cite web
|url = https://venturebeat.com/2018/12/30/sapienz-facebooks-push-to-automate-software-testing/
|title = Sapienz: Facebook's push to automate software testing
|date = 30 December 2018
|website = VentureBeat
|access-date = 29 September 2020
}}</ref>
In other application scenarios, software engineers may be reluctant to adopt tools over which they have little control or that generate solutions that are unlike those that humans produce.<ref>
{{cite web
|url = http://shape-of-code.coding-guidelines.com/2013/10/18/programming-using-genetic-algorithms-isnt-that-what-humans-already-do/
|title = Programming using genetic algorithms: isn't that what humans already do ;-)
|last = Jones
|first = Derek
|date = 18 October 2013
|website = The Shape of Code
|access-date = 31 October 2013
}}
</ref> In the context of SBSE use in fixing or improving programs, developers need to be confident that any automatically produced modification does not generate unexpected behavior outside the scope of a system's requirements and testing environment. Considering that fully automated programming has yet to be achieved, a desirable property of such modifications would be that they need to be easily understood by humans to support maintenance activities.<ref>
{{Cite journal
| doi = 10.1007/s11219-013-9208-0
| issn = 1573-1367
| volume = 21
| issue = 3
| pages = 421–443
| last1 = Le Goues
| first1 = Claire | author1-link = Claire Le Goues
| last2 = Forrest
| first2 = Stephanie
| last3 = Weimer
| first3 = Westley
| title = Current challenges in automatic software repair
| journal = Software Quality Journal
| date = 2013-09-01
| citeseerx = 10.1.1.371.5784
| s2cid = 16435531
}}
</ref>
Another concern is that SBSE might make the software engineer redundant. Supporters claim that the motivation for SBSE is to enhance the relationship between the engineer and the program.<ref>
{{Cite conference
| publisher = IEEE Press
| conference = First International Workshop on Combining Modelling with Search-Based Software Engineering, First International Workshop on Combining Modelling with Search-Based Software Engineering
| pages = 49–50
| last = Simons
| first = Christopher L.
| title = Whither (away) software engineers in SBSE?
| ___location = San Francisco, USA
| access-date = 2013-10-31
| date = May 2013
| url = http://eprints.uwe.ac.uk/19938/
}}</ref>
==See also==
*[[Program analysis (computer science)]]
*[[Dynamic program analysis]]
*[[Genetic improvement]]
==References==
{{reflist|colwidth=30em}}
==External links==
*[http://
*[http://neo.lcc.uma.es/mase/ Metaheuristics and Software Engineering]
*[http://sir.unl.edu/portal/index.php Software-artifact Infrastructure Repository]
*[http://2013.icse-conferences.org/ International Conference on Software Engineering]
*[http://www.sigevo.org/wiki/tiki-index.php Genetic and Evolutionary Computation (GECCO)]
*[https://scholar.google.co.uk/citations?view_op=search_authors&hl=en&mauthors=label:sbse Google Scholar page on Search-based software engineering]
[[Category:Computer-related introductions in 2001]]
[[Category:Software testing]]
[[Category:Search algorithms]]
[[Category:Optimization algorithms and methods]]
[[Category:Metaheuristics]]
[[Category:Software quality]]
[[Category:Program analysis]]
| |||