Application of metaheuristic search techniques to software engineering
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
problems.
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
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:
- 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.
[1]
Definition
[
edit
]
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
[2]
(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.
[3]
The term "
search-based application
", in contrast, refers to using
search-engine technology
, rather than search techniques, in another industrial application.
Brief history
[
edit
]
One of the earliest attempts to apply
optimization
to a
software engineering
problem was reported by
Webb Miller
and David Spooner in 1976 in the area of
software testing
.
[4]
In 1992, S. Xanthakis and his colleagues applied a search technique to a
software engineering
problem for the first time.
[5]
The term SBSE was first used in 2001 by
Harman
and Jones.
[6]
The research community grew to include more than 800 authors by 2013, spanning approximately 270 institutions in 40 countries.
[7]
Application areas
[
edit
]
Search-based software engineering is applicable to almost all phases of the
software development process
.
Software testing
has been one of the major applications.
[8]
Search techniques have been applied to other
software engineering
activities, for instance,
requirements analysis
,
[9]
[10]
design
,
[11]
[12]
refactoring
,
[13]
development
,
[14]
and
maintenance
.
[15]
Requirements engineering
[
edit
]
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
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.
[16]
[17]
[18]
[19]
Debugging and maintenance
[
edit
]
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
GenProg Evolutionary Program Repair
software repaired 55 out of 105 bugs for approximately $8 each in one test.
[20]
Coevolution
adopts a "predator and prey"
metaphor
in which a suite of programs and a suite of
unit tests
evolve together and influence each other.
[21]
Testing
[
edit
]
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.
[22]
Regression testing
has also received some attention.
Optimizing software
[
edit
]
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.
[23]
In one instance, a 50,000 line program was genetically improved, resulting in a program 70 times faster on average.
[24]
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.
[25]
Project management
[
edit
]
A number of decisions that are normally made by a project manager can be done automatically, for example, project scheduling.
[26]
Tools
[
edit
]
Tools available for SBSE include OpenPAT,
[27]
EvoSuite
,
[28]
and
Coverage
, a code coverage measurement tool for Python.
[29]
Methods and techniques
[
edit
]
A number of methods and techniques are available, including:
Industry acceptance
[
edit
]
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.
[31]
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.
[32]
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.
[33]
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.
[34]
See also
[
edit
]
References
[
edit
]
- ^
Harman, Mark (2010). "Why Source Code Analysis and Manipulation Will Always be Important".
10th IEEE Working Conference on Source Code Analysis and Manipulation (SCAM 2010)
. 10th IEEE Working Conference on Source Code Analysis and Manipulation (SCAM 2010). pp. 7?19.
doi
:
10.1109/SCAM.2010.28
.
- ^
Harman, Mark; John A. Clark (2004). "Metrics are fitness functions too".
Proceedings of the 10th International Symposium on Software Metrics, 2004
. 10th International Symposium on Software Metrics, 2004. pp. 58?69.
doi
:
10.1109/METRIC.2004.1357891
.
- ^
Clark, John A.; Dolado, Jose Javier; Harman, Mark; Hierons, Robert M.; Jones, Bryan F.; Lumkin, M.; Mitchell, Brian S.; Mancoridis, Spiros; Rees, K.; Roper, Marc; Shepperd, Martin J. (2003). "Reformulating software engineering as a search problem".
IEE Proceedings - Software
.
150
(3): 161?175.
CiteSeerX
10.1.1.144.3059
.
doi
:
10.1049/ip-sen:20030559
.
ISSN
1462-5970
.
- ^
Miller, Webb; Spooner, David L. (1976). "Automatic Generation of Floating-Point Test Data".
IEEE Transactions on Software Engineering
.
SE-2
(3): 223?226.
doi
:
10.1109/TSE.1976.233818
.
ISSN
0098-5589
.
S2CID
18875300
.
- ^
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
- ^
Harman, Mark; Jones, Bryan F. (15 December 2001). "Search-based software engineering".
Information and Software Technology
.
43
(14): 833?839.
CiteSeerX
10.1.1.143.9716
.
doi
:
10.1016/S0950-5849(01)00189-6
.
ISSN
0950-5849
.
- ^
Harman, Mark; Mansouri, S. Afshin; Zhang, Yuanyuan (1 November 2012).
"Search-based software engineering: Trends, techniques and applications"
.
ACM Computing Surveys
.
45
(1): 1?61.
doi
:
10.1145/2379776.2379787
.
S2CID
207198163
.
- ^
McMinn, Phil (2004). "Search-based software test data generation: a survey".
Software Testing, Verification and Reliability
.
14
(2): 105?156.
CiteSeerX
10.1.1.122.33
.
doi
:
10.1002/stvr.294
.
ISSN
1099-1689
.
S2CID
17408871
.
- ^
Greer, Des; Ruhe, Guenther (15 March 2004). "Software release planning: an evolutionary and iterative approach".
Information and Software Technology
.
46
(4): 243?253.
CiteSeerX
10.1.1.195.321
.
doi
:
10.1016/j.infsof.2003.07.002
.
ISSN
0950-5849
.
S2CID
710923
.
- ^
Colares, Felipe; Souza, Jerffeson; Carmo, Raphael; Padua, Clarindo; Mateus, Geraldo R. (2009). "A New Approach to the Software Release Planning".
XXIII Brazilian Symposium on Software Engineering, 2009. SBES '09
. XXIII Brazilian Symposium on Software Engineering, 2009. SBES '09. pp. 207?215.
doi
:
10.1109/SBES.2009.23
.
- ^
Clark, John A.; Jacob, Jeremy L. (15 December 2001). "Protocols are programs too: the meta-heuristic search for security protocols".
Information and Software Technology
.
43
(14): 891?904.
CiteSeerX
10.1.1.102.6016
.
doi
:
10.1016/S0950-5849(01)00195-1
.
ISSN
0950-5849
.
- ^
Raiha, Outi (1 November 2010).
"A survey on search-based software design"
(PDF)
.
Computer Science Review
.
4
(4): 203?249.
CiteSeerX
10.1.1.188.9036
.
doi
:
10.1016/j.cosrev.2010.06.001
.
ISSN
1574-0137
.
- ^
Mariani, Thaina; Vergilio, Silvia Regina (1 March 2017). "A systematic review on search-based refactoring".
Information and Software Technology
.
83
: 14?34.
doi
:
10.1016/j.infsof.2016.11.009
.
ISSN
0950-5849
.
- ^
Alba, Enrique; Chicano, J. Francisco (1 June 2007). "Software project management with GAs".
Information Sciences
.
177
(11): 2380?2401.
doi
:
10.1016/j.ins.2006.12.020
.
hdl
:
10630/8145
.
ISSN
0020-0255
.
- ^
Antoniol, Giuliano; Di Penta, Massimiliano; Harman, Mark (2005). "Search-based techniques applied to optimization of project planning for a massive maintenance project".
Proceedings of the 21st IEEE International Conference on Software Maintenance, 2005. ICSM'05
. Proceedings of the 21st IEEE International Conference on Software Maintenance, 2005. ICSM'05. pp. 240?249.
CiteSeerX
10.1.1.63.8069
.
doi
:
10.1109/ICSM.2005.79
.
- ^
Zhang, Yuanyuan (February 2010).
Multi-Objective Search-based Requirements Selection and Optimisation
(PhD). Strand, London, UK: University of London.
- ^
Y. Zhang and M. Harman and S. L. Lim, "
Search Based Optimization of Requirements Interaction Management
," Department of Computer Science, University College London, Research Note RN/11/12, 2011.
- ^
Li, Lingbo; Harman, Mark; Letier, Emmanuel; Zhang, Yuanyuan (2014). "Robust next release problem".
Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation
. Gecco '14. pp. 1247?1254.
doi
:
10.1145/2576768.2598334
.
ISBN
9781450326629
.
S2CID
8423690
.
- ^
Li, L.; Harman, M.; Wu, F.; Zhang, Y. (2017).
"The Value of Exact Analysis in Requirements Selection"
(PDF)
.
IEEE Transactions on Software Engineering
.
43
(6): 580?596.
doi
:
10.1109/TSE.2016.2615100
.
ISSN
0098-5589
.
S2CID
8398275
.
- ^
Le Goues, Claire; Dewey-Vogt, Michael; Forrest, Stephanie; Weimer, Westley (2012). "A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each".
2012 34th International Conference on Software Engineering (ICSE)
. 2012 34th International Conference on Software Engineering (ICSE). pp. 3?13.
doi
:
10.1109/ICSE.2012.6227211
.
- ^
Arcuri, Andrea; Yao, Xin (2008). "A novel co-evolutionary approach to automatic software bug fixing".
IEEE Congress on Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence)
. IEEE Congress on Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). pp. 162?168.
CiteSeerX
10.1.1.159.7991
.
doi
:
10.1109/CEC.2008.4630793
.
- ^
Harman, Mark; Jia, Yue; Zhang, Yuanyuan (April 2015). "Achievements, Open Problems and Challenges for Search Based Software Testing".
2015 IEEE 8th International Conference on Software Testing, Verification and Validation (ICST)
. Graz, Austria: IEEE. pp. 1?12.
CiteSeerX
10.1.1.686.7418
.
doi
:
10.1109/ICST.2015.7102580
.
ISBN
978-1-4799-7125-1
.
S2CID
15272060
.
- ^
Memeti, Suejb; Pllana, Sabri; Binotto, Alecio; Kolodziej, Joanna;
Brandic, Ivona
(2018). "Using meta-heuristics and machine learning for software optimization of parallel computing systems: a systematic literature review".
Computing
.
101
(8): 893?936.
arXiv
:
1801.09444
.
Bibcode
:
2018arXiv180109444M
.
doi
:
10.1007/s00607-018-0614-9
.
S2CID
13868111
.
- ^
Langdon, William B.; Harman, Mark.
"Optimising Existing Software with Genetic Programming"
(PDF)
.
IEEE Transactions on Evolutionary Computation
.
- ^
Basios, Michail; Li, Lingbo; Wu, Fan; Kanthan, Leslie; Barr, Earl T. (9 September 2017). "Optimising Darwinian Data Structures on Google Guava".
Search Based Software Engineering
(PDF)
. Lecture Notes in Computer Science. Vol. 10452. pp. 161?167.
doi
:
10.1007/978-3-319-66299-2_14
.
ISBN
978-3-319-66298-5
.
- ^
Minku, Leandro L.; Sudholt, Dirk; Yao, Xin (2012). "Evolutionary algorithms for the project scheduling problem: runtime analysis and improved design".
Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference
. GECCO '12. New York, NY, USA: ACM. pp. 1221?1228.
doi
:
10.1145/2330163.2330332
.
ISBN
978-1-4503-1177-9
.
- ^
Mayo, M.; Spacey, S. (2013).
"Predicting Regression Test Failures Using Genetic Algorithm-Selected Dynamic Performance Analysis Metrics"
(PDF)
.
Search Based Software Engineering
. Lecture Notes in Computer Science. Vol. 8084. pp. 158?171.
doi
:
10.1007/978-3-642-39742-4_13
.
hdl
:
10289/7763
.
ISBN
978-3-642-39741-7
.
- ^
"Home"
.
evosuite.org
.
- ^
others, Ned Batchelder and 100,
coverage: Code coverage measurement for Python
, retrieved
14 March
2018
{{
citation
}}
: CS1 maint: numeric names: authors list (
link
)
- ^
"Open Source Profilers in Java"
.
- ^
"Sapienz: Facebook's push to automate software testing"
.
VentureBeat
. 30 December 2018
. Retrieved
29 September
2020
.
- ^
Jones, Derek (18 October 2013).
"Programming using genetic algorithms: isn't that what humans already do ;-)"
.
The Shape of Code
. Retrieved
31 October
2013
.
- ^
Le Goues, Claire; Forrest, Stephanie; Weimer, Westley (1 September 2013). "Current challenges in automatic software repair".
Software Quality Journal
.
21
(3): 421?443.
CiteSeerX
10.1.1.371.5784
.
doi
:
10.1007/s11219-013-9208-0
.
ISSN
1573-1367
.
S2CID
16435531
.
- ^
Simons, Christopher L. (May 2013).
Whither (away) software engineers in SBSE?
. First International Workshop on Combining Modelling with Search-Based Software Engineering, First International Workshop on Combining Modelling with Search-Based Software Engineering. San Francisco, USA: IEEE Press. pp. 49?50
. Retrieved
31 October
2013
.
External links
[
edit
]
|
---|
Fields
| |
---|
Concepts
| |
---|
Orientations
| |
---|
Models
| Developmental
| |
---|
Other
| |
---|
Languages
| |
---|
|
---|
Related fields
| |
---|
|