Search-based software engineering: Difference between revisions

Revision as of 21:32, 6 May 2021

Latest revision as of 12:38, 12 July 2025

(28 intermediate revisions by 18 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>

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

SBSE problems can be divided into two types:

Line 19:

==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 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 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 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 241 ⟶ 244:

| 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 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 280 ⟶ 284:

==Tools==

Tools available for SBSE include OpenPAT.,<ref>

{{cite conferencebook

|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

|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|access-date=2018-03-14}}

</ref>

Line 311 ⟶ 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

Line 335 ⟶ 341:

| pages = 421–443

| last1 = Le Goues

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

| last2 = Forrest

| first2 = Stephanie

Line 351 ⟶ 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 379 ⟶ 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]]