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, exact optimization 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. A metaheuristic is a heuristic method for solving a very general class of computational problems by combining user given black-box procedures — usually heuristics themselves — in a hopefully efficient way. ... A genetic algorithm (GA) is an algorithm used to find approximate solutions to difficult-to-solve problems through application of the principles of evolutionary biology to computer science. ... Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. ... Tabu search is a mathematical optimization method, belonging to the class of local search techniques. ... e. ... e. ... In mathematics, optimization is the discipline which is concerned with finding the maxima and minima of functions, possibly subject to constraints. ... Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In mathematics, optimization is the discipline which is concerned with finding the maxima and minima of functions, possibly subject to constraints. ... It has been suggested that this article or section be merged with Operations management. ... In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ... In computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure (described below) that takes much less time than naive methods. ... e. ... A metaheuristic is a heuristic method for solving a very general class of computational problems by combining user given black-box procedures — usually heuristics themselves — in a hopefully efficient way. ...

Brief history

One of the earliest attempts in applying optimization to a software engineering problem was reported by Miller and Spooner in 1976 in the area of software testing^[1]. Xanthakis et al. ^[2] 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^[3]. In mathematics, optimization is the discipline which is concerned with finding the maxima and minima of functions, possibly subject to constraints. ... e. ... e. ...

Application areas

Software testing has been one of the major applications of search techniques in software engineering^[4]. However, search techniques have been applied to other software engineering activities, for instance: requirements analysis^[5], software design^[6], software development^[7] and software maintenance^[8]. In his FoSE paper^[9], Harman identifies the current state of SBSE and highlights future trends in this approach to software engineering. Software testing is the process to the context in which it is intended to operate. ... e. ... e. ... In systems engineering and software engineering, requirements analysis encompasses those tasks that go into determining the requirements of a new or altered system, taking account of the possibly conflicting requirements of the various stakeholders, such as users. ... Software design is the process that starts from a problem for which there is currently no acceptable (software) solution, and ends when such a solution has been created. ... Software development is the translation of a user need or marketing goal into a software product. ... In software engineering, software maintenance is the process of enhancing and optimizing deployed software (software release), as well as remedying defects. ... e. ...

References

1. ^ W. Miller and D. L. Spooner, Automatic Generation of Floating-Point Test Data, IEEE Transactions on Software Engineering, Vol. 2, No. 3, pp. 223-226 (1976)
2. ^ 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 5^th International Conference on Software Engineering and its Applications, pp. 625-636 (1992)
3. ^ M. Harman and B. F. Jones, Search-based software engineering, Information & Software Technology, Vol. 43, No. 14, pp. 833-839 (2001)
4. ^ P. McMinn, Search-based software test data generation: a survey, Software Testing, Verification and Reliability, Vol. 14, No. 2, pp. 105-156 (2004)
5. ^ D. Greer and G. Ruhe, Software release planning: an evolutionary and iterative approach, Information & Software Technology, Vol. 46, No. 4, pp. 243-253 (2004)
6. ^ J. A. Clark and J. L. Jacob, Protocols are programs too: the meta-heuristic search for security protocols, Information & Software Technology, Vol. 43, No. 14, pp. 891-904 (2001)
7. ^ E. Alba and F. Chicano, Software Project Management with GAs, Information Sciences, Vol. 177, pp. 2380-2401 (2007)
8. ^ G. Antoniol, M. Di Penta and M. Harman, Search-Based Techniques Applied to Optimization of Project Planning for a Massive Maintenance Project, In Proceedings of IEEE International Conference on Software Maintenance, pp. 240-249 (2005)
9. ^ M. Harman, The Current State and Future of Search Based Software Engineering, In Proceedings of the 29^th International Conference on Software Engineering (ICSE 2007), 20-26 May, Minneapolis, USA (2007)

External links

• Repository of publications on SBSE