Search-based software engineering: Difference between revisions

Revision as of 11:24, 1 February 2023

Latest revision as of 12:38, 12 July 2025

(14 intermediate revisions by 11 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 61:

| journal = [[IEE Proceedings - Software]]

| year = 2003

| doi-broken-date = 12 July 2025

| citeseerx = 10.1.1.144.3059

}}</ref>

Line 210 ⟶ 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 220 ⟶ 221:

| pages = 3–13

| last1 = Le Goues

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

| last2 = Dewey-Vogt

| first2 = Michael

Line 243 ⟶ 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 259 ⟶ 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 283 ⟶ 285:

==Tools==

Tools available for SBSE include OpenPAT,<ref>

{{cite journalbook

|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

Line 295 ⟶ 297:

|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

Line 309 ⟶ 311:

* [[Code coverage]] allows measuring how much of the code is executed with a given set of input data.

* [[Static program analysis]]

* [[Component engineering]] including experimental component analysis <ref>{{cite journal |last1= Nikulchev |first1=E. |last2=Ilin |first2=D. |last3=Gusev |first3=A. |date= 2021 |title=Technology Stack Selection Model for Software Design of Digital Platforms |journal=[[Mathematics]] |volume=9 |issue=4 |pages=308 |doi=10.3390/math9040308}}</ref>

==Industry acceptance==

Line 340 ⟶ 341:

| pages = 421–443

| last1 = Le Goues

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

| last2 = Forrest

| first2 = Stephanie

Line 372 ⟶ 373:

*[[Dynamic program analysis]]

*[[Genetic improvement]]

*[[Component engineering]]

==References==

Line 385:

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

*[[Component{{Software engineering]]}}

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

[[Category:Software testing]]

[[Category:Search algorithms]]

[[Category:Optimization algorithms and methods]]

[[Category:Genetic algorithmsMetaheuristics]]

[[Category:Software quality]]

[[Category:Program analysis]]