Search-based software engineering
Encyclopedia
Search-based software engineering (SBSE) is an approach to apply metaheuristic
search techniques like genetic algorithms, simulated annealing
and tabu search
to software engineering
problems. It is inspired by the observation that many activities in software engineering
can be formulated as optimization
problems. Due to the computational complexity
of these problems, exactoptimization
techniques of operations research
like linear programming
or dynamic programming
are mostly impractical for large scale software engineering
problems. Because of this, researchers and practitioners have used metaheuristic
search techniques to find near optimal or good-enough solutions.
to a software engineering
problem was reported by Webb Miller
and David Spooner in 1976 in the area of software testing. Xanthakis et al. apply for the first time a search technique to a software engineering
problem in 1992. The term SBSE was first used in 2001 by Harman
and Jones.
has been one of the major applications of search techniques in software engineering
. However, search techniques have been applied to other software engineering
activities, for instance:requirements analysis
, software design
, software development
, and software maintenance
. In his FoSE paper, Harman identifies the current state of SBSE and highlights future trends in this approach to software engineering
.
The term Search-based application
, in contrast, refers to using search engine
technology, rather than search techniques, in another industrial application.
Metaheuristic
In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...
search techniques like genetic algorithms, simulated annealing
Simulated annealing
Simulated annealing is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete...
and tabu search
Tabu search
Tabu search is a mathematical optimization method, belonging to the class of trajectory based techniques. Tabu search enhances the performance of a local search method by using memory structures that describe the visited solutions: once a potential solution has been determined, it is marked as...
to software engineering
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
problems. It is inspired by the observation that many activities in software engineering
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
can be formulated as optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
problems. Due to the computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
of these problems, exactoptimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
techniques of operations research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
like linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
or dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
are mostly impractical for large scale software engineering
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
problems. Because of this, researchers and practitioners have used metaheuristic
Metaheuristic
In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces...
search techniques to find near optimal or good-enough solutions.
Brief history
One of the earliest attempts in applying optimizationOptimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
to a software engineering
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
problem was reported by Webb Miller
Webb Miller
For the Pulitzer Prize-winning war correspondent, see Webb Miller .Webb Miller is a professor in the Department of Biology and the Department of Computer Science and Engineering at The Pennsylvania State University. He received his Ph.D. in mathematics from the University of Washington in 1969. He...
and David Spooner in 1976 in the area of software testing. Xanthakis et al. apply for the first time a search technique to a software engineering
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
problem in 1992. The term SBSE was first used in 2001 by Harman
Mark Harman (computer scientist)
Mark Harman is a British computer scientist. Since 2004 he has been a Professor at King's College London, where he leads the Software Engineering Group. He is also Director of the Centre for Research on Evolution Search and Testing , a research laboratory at KCL.Harman studied software engineering...
and Jones.
Application areas
Software testingSoftware testing
Software testing is an investigation conducted to provide stakeholders with information about the quality of the product or service under test. Software testing can also provide an objective, independent view of the software to allow the business to appreciate and understand the risks of software...
has been one of the major applications of search techniques in software engineering
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
. However, search techniques have been applied to other software engineering
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
activities, for instance:requirements analysis
Requirements analysis
Requirements analysis in systems engineering and software engineering, encompasses those tasks that go into determining the needs or conditions to meet for a new or altered product, taking account of the possibly conflicting requirements of the various stakeholders, such as beneficiaries or users...
, software design
Software design
Software design is a process of problem solving and planning for a software solution. After the purpose and specifications of software are determined, software developers will design or employ designers to develop a plan for a solution...
, software development
Software development
Software development is the development of a software product...
, and software maintenance
Software maintenance
Software Maintenance in software engineering is the modification of a software product after delivery to correct faults, to improve performance or other attributes....
. In his FoSE paper, Harman identifies the current state of SBSE and highlights future trends in this approach to software engineering
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
.
The term Search-based application
Search-based application
Search-based applications are software applications in which a search engine platform is used as the core infrastructure for information access and reporting...
, in contrast, refers to using search engine
Search engine
A search engine is an information retrieval system designed to help find information stored on a computer system. The search results are usually presented in a list and are commonly called hits. Search engines help to minimize the time required to find information and the amount of information...
technology, rather than search techniques, in another industrial application.