Search-based software engineering: Difference between revisions

Revision as of 11:56, 29 September 2020

Latest revision as of 12:38, 12 July 2025

(31 intermediate revisions by 21 users not shown)

Line 1:

{{Short description|Application of metaheuristic search techniques to software engineering}}

{{Use dmy dates|date=NovemberDecember 20112020}}

'''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:

Line 14:

| first = Mark

| title = Why Source Code Analysis and Manipulation Will Always be Important

| booktitlebook-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

Line 28:

|author2=John A. Clark

| title = Metrics are fitness functions too

| booktitlebook-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

Line 61:

| 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==

Line 114 ⟶ 115:

| 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

Line 129 ⟶ 131:

| date = 2004-03-15

| citeseerx = 10.1.1.195.321

| s2cid = 710923

}}</ref><ref>{{Cite conference

| doi = 10.1109/SBES.2009.23

Line 144 ⟶ 147:

| first5 = Geraldo R.

| title = A New Approach to the Software Release Planning

| booktitlebook-title = XXIII Brazilian Symposium on Software Engineering, 2009. SBES '09

| year = 2009

}}</ref> [[software design|design]],<ref>

Line 161 ⟶ 164:

| 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

Line 189 ⟶ 192:

| first3 = Mark

| title = Search-based techniques applied to optimization of project planning for a massive maintenance project

| booktitlebook-title = Proceedings of the 21st IEEE International Conference on Software Maintenance, 2005. ICSM'05

| year = 2005

| citeseerx = 10.1.1.63.8069

Line 197 ⟶ 200:

[[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 = Ph.D.PhD

| publisher = University of London

| last = Zhang

Line 208 ⟶ 211:

Y.&nbsp;Zhang and M.&nbsp;Harman and S.&nbsp;L.&nbsp;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=Robust Next Release Problem: Handling Uncertainty During Optimization|journal=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===

Line 218 ⟶ 221:

| pages = 3–13

| last1 = Le Goues

| first1 = Claire | author1-link = Claire Le Goues

| last2 = Dewey-Vogt

| first2 = Michael

Line 226 ⟶ 229:

| first4 = Westley

| title = A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each

| booktitlebook-title = 2012 34th International Conference on Software Engineering (ICSE)

| year = 2012

}}</ref>

Line 239 ⟶ 242:

| first2 = Xin

| title = A novel co-evolutionary approach to automatic software bug fixing

| booktitlebook-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 journalbook|last1=Harman|first1=Mark|last2=Jia|first2=Yue|last3=Zhang|first3=Yuanyuan|date=April 2015|title=Achievements, Open Problems and Challenges for Search Based Software Testing|journal=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===

Line 257 ⟶ 261:

| 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 onin execution time, 13% improvement onin memory consumption and 4% improvement onin 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|journal=Search Based Software Engineering|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===

Line 273 ⟶ 277:

| first3 = Xin

| title = Evolutionary algorithms for the project scheduling problem: runtime analysis and improved design

| booktitlebook-title = Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference

| ___location = New York, NY, USA

| series = GECCO '12

Line 280 ⟶ 284:

==Tools==

Tools available for SBSE include OpenPAT.,<ref>

{{cite conferencebook

|ref = harv

|last1 = Mayo

|first1 = M.

|last2 = Spacey

|first2 = S.

|title = Search Based Software Engineering

|title chapter = Predicting Regression Test Failures Using Genetic Algorithm-Selected Dynamic Performance Analysis Metrics

|journal = Proceedings of the 5th International Symposium on Search-Based Software Engineering (SSBSE)

|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

}}</ref> and [[EvoSuite]] <ref>(http://www.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|accessdate=2018-03-14}}

|isbn = 978-3-642-39741-7

|hdl-access= free

}}</ref> and [[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|accessdateaccess-date=2018-03-14}}

</ref>

Line 310 ⟶ 317:

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’sFacebook's push to automate software testing

|date = 30 December 2018

|website = VentureBeat

|accessdateaccess-date = 29 September 2020

}}</ref>

Line 324 ⟶ 331:

|date = 18 October 2013

|website = The Shape of Code

|accessdateaccess-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>

Line 334 ⟶ 341:

| pages = 421–443

| last1 = Le Goues

| first1 = Claire | author1-link = Claire Le Goues

| last2 = Forrest

| first2 = Stephanie

Line 350 ⟶ 357:

{{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

Line 356 ⟶ 363:

| title = Whither (away) software engineers in SBSE?

| ___location = San Francisco, USA

| accessdateaccess-date = 2013-10-31

| date = May 2013

| url = http://eprints.uwe.ac.uk/19938/

Line 378 ⟶ 385:

*[https://scholar.google.co.uk/citations?view_op=search_authors&hl=en&mauthors=label:sbse Google Scholar page on Search-based software engineering]

[[Category:{{Software engineering]]}}

[[Category:Computer-related introductions in 2001]]

[[Category:Software engineering]]

[[Category:Software testing]]

[[Category:Search algorithms]]

[[Category:Optimization algorithms and methods]]

[[Category:Genetic algorithmsMetaheuristics]]

[[Category:Software articles needing expert attention]]

[[Category:Software quality]]

[[Category:Program analysis]]