Article

Why the virtual nature of software makes it ideal for search based optimization

Author:

Mark HarmanAuthors Info & Claims

FASE'10: Proceedings of the 13th international conference on Fundamental Approaches to Software Engineering

Pages 1 - 12

https://doi.org/10.1007/978-3-642-12029-9_1

Published: 20 March 2010 Publication History

Abstract

This paper provides a motivation for the application of search based optimization to Software Engineering, an area that has come to be known as Search Based Software Engineering (SBSE). SBSE techniques have already been applied to many problems throughout the Software Engineering lifecycle, with new application domains emerging on a regular basis. The approach is very generic and therefore finds wide application in Software Engineering. It facilitates automated and semi-automated solutions in situations typified by large complex problem spaces with multiple competing and conflicting objectives. Previous work has already discussed, in some detail, the advantages of the SBSE approach for Software Engineering. This paper summarises previous work and goes further, by arguing that Software Engineering provides the ideal set of application problems for which optimization algorithms are supremely well suited.

References

[1]

Ali, S., Briand, L.C., Hemmati, H., Panesar-Walawege, R.K.: A systematic review of the application and empirical investigation of search-based test-case generation. IEEE Transactions on Software Engineering (to appear, 2010).

Digital Library

[2]

Alba, E., Chicano, F.: Testing with Evolutionary Strategies. In: Guelfi, N., Savidis, A. (eds.) RISE 2005. LNCS, vol. 3943, pp. 50-65. Springer, Heidelberg (2006).

Digital Library

[3]

Alba, E., Chicano, F.: Software Project Management with GAs. Information Sciences 177(11), 2380-2401 (2007).

Digital Library

[4]

Alba, E., Chicano, F.: Observations in using Parallel and Sequential Evolutionary Algorithms for Automatic Software Testing. Computers S Operations Research 35(10), 3161-3183 (2008).

Digital Library

[5]

Antoniol, G., Di Penta, M., Harman, M.: Search-based Techniques for Optimizing Software Project Resource Allocation. In: Deb, K., et al. (eds.) GECCO 2004. LNCS, vol. 3103, pp. 1425-1426. Springer, Heidelberg (2004).

[6]

Afzal, W., Torkar, R., Feldt, R.: A systematic review of search-based testing for non-functional system properties. Information and Software Technology 51(6), 957-976 (2009).

Digital Library

[7]

Ramón Alvarez-Valdes, E., Crespo, J.M.: A Scatter Search Algorithm for Project Scheduling under Partially Renewable Resources. Journal of Heuristics 12(1-2), 95-113 (2006).

Digital Library

[8]

Arcuri, A., Yao, X.: A Novel Co-evolutionary Approach to Automatic Software Bug Fixing. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2008), Hongkong, China, June 1-6, pp. 162-168. IEEE Computer Society, Los Alamitos (2008).

[9]

Briand, L.C., Labiche, Y., Shousha, M.: Stress Testing Real-Time Systems with Genetic Algorithms. In: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation (GECCO 2005), Washington, D.C., USA, June 25-29, pp. 1021-1028. ACM, New York (2005).

Digital Library

[10]

Bottaci, L.: Instrumenting Programs with Flag Variables for Test Data Search by Genetic Algorithms. In: Proceedings of the 2002 Conference on Genetic and Evolutionary Computation (GECCO 2002), New York, USA, July 9-13, pp. 1337-1342. Morgan Kaufmann Publishers, San Francisco (2002).

Digital Library

[11]

Bagnall, A.J., Rayward-Smith, V.J., Whittley, I.M.: The Next Release Problem. Information and Software Technology 43(14), 883-890 (2001).

[12]

Baresel, A., Sthamer, H., Schmidt, M.: Fitness Function Design to Improve Evolutionary Structural Testing. In: Proceedings of the 2002 Conference on Genetic and Evolutionary Computation (GECCO 2002), New York, USA, July 9-13, pp. 1329-1336. Morgan Kaufmann, San Francisco (2002).

Digital Library

[13]

Blanco, R., Tuya, J., Daz, E., Adenso Daz, B.: A Scatter Search Approach for Automated Branch Coverage in Software Testing. International Journal of Engineering Intelligent Systems (EIS) 15(3), 135-142 (2007).

[14]

Bentley, P.J., Wakefield, J.P.: Generic representation of solid geometry for genetic search. Microcomputers in Civil Engineering 11(3), 153-161 (1996).

Digital Library

[15]

Chang, C.K., Chao, C., Hsieh, S.-Y., Alsalqan, Y.: SPMNet: a Formal Methodology for Software Management. In: Proceedings of the 18th Annual International Computer Software and Applications Conference (COMPSAC 1994), Taipei, Taiwan, November 9-11, p. 57. IEEE, Los Alamitos (1994).

[16]

Clark, J., Dolado, J.J., Harman, M., Hierons, R.M., Jones, B., Lumkin, M., Mitchell, B., Mancoridis, S., Rees, K., Roper, M., Shepperd, M.: Reformulating software engineering as a search problem. IEE Proceedings -- Software 150(3), 161-175 (2003).

[17]

Cordón, O., Herrera, F., Sánchez, L.: Evolutionary learning processes for data analysis in electrical engineering applications. In: Quagliarella, D., P?eriaux, J., Poloni, C., Winter, G. (eds.) Genetic Algorithms and Evolution Strategy in Engineering and Computer Science, pp. 205-224. John Wiley and Sons, Chichester (1998).

[18]

Darlington, J., Burstall, R.M.: A tranformation system for developing recursive programs. Journal of the ACM 24(1), 44-67 (1977).

Digital Library

[19]

Díaz, E., Tuya, J., Blanco, R., Dolado, J.J.: A Tabu Search Algorithm for Structural Software Testing. Computers S Operations Research 35(10), 3052-3072 (2008).

Digital Library

[20]

Foster, I.: Designing and building parallel programs: Concepts and tools for parallel software. Addison-Wesley, Reading (1995).

Digital Library

[21]

Guo, Q., Hierons, R.M., Harman, M., Derderian, K.: Constructing Multiple Unique Input/Output Sequences using Evolutionary Optimisation Techniques. IEE Proceedings - Software 152(3), 127-140 (2005).

[22]

Harman, M.: Automated test data generation using search based software engineering (keynote). In: 2nd Workshop on Automation of Software Test (AST 2007) at the 29th International Conference on Software Engineering (ICSE 2007), Minneapolis, USA (2007).

Digital Library

[23]

Harman, M.: The current state and future of search based software engineering. In: Briand, L., Wolf, A. (eds.) Future of Software Engineering 2007, pp. 342-357. IEEE Computer Society Press, Los Alamitos (2007).

Digital Library

[24]

Harman, M.: Search based software engineering for program comprehension (keynote). In: 15th International Conference on Program Comprehension (ICPC 2007), Banff, Canada (2007).

Digital Library

[25]

Harman, M.: The Current State and Future of Search Based Software Engineering. In: Briand, L., Wolf, A. (eds.) Proceedings of International Conference on Software Engineering / Future of Software Engineering 2007 (ICSE/FOSE 2007), Minneapolis, Minnesota, USA,May 20-26, pp. 342-357. IEEE Computer Society, Los Alamitos (2007).

Digital Library

[26]

Harman, M., Clark, J.A.: Metrics Are Fitness Functions Too. In: Proceedings of the 10th IEEE International Symposium on Software Metrics (METRICS 2004), Chicago, USA, September 11-17, pp. 58-69. IEEE Computer Society, Los Alamitos (2004).

Digital Library

[27]

Harman, M., Hu, L., Hierons, R.M., Wegener, J., Sthamer, H., Baresel, A., Roper, M.: Testability Transformation. IEEE Transaction on Software Engineering 30(1), 3-16 (2004).

Digital Library

[28]

Harman, M., Hierons, R., Proctor, M.: A New Representation and Crossover Operator for Search-based Optimization of Software Modularization. In: Proceedings of the 2002 Conference on Genetic and Evolutionary Computation (GECCO 2002), New York, USA, July 9-13, pp. 1351-1358. Morgan Kaufmann Publishers, San Francisco (2002).

Digital Library

[29]

Harman, M., Jones, B.F.: Search-based Software Engineering. Information S Software Technology 43(14), 833-839 (2001).

[30]

Harman, M., Mansouri, A., Zhang, Y.: Search based software engineering: A comprehensive analysis and review of trends techniques and applications. Technical Report TR-09-03, Department of Computer Science, King's College London (April 2009).

[31]

Harman, M., Tratt, L.: Pareto Optimal Search Based Refactoring at the Design Level. In: Proceedings of the 9th annual Conference on Genetic and Evolutionary Computation (GECCO 2007), London, England, July 7-11, pp. 1106-1113. ACM, New York (2007).

Digital Library

[32]

Jones, B.F., Eyres, D.E., Sthamer, H.-H.: A Strategy for using Genetic Algorithms to Automate Branch and Fault-based Testing. Computer Journal 41(2), 98-107 (1998).

[33]

Korel, B., Harman, M., Chung, S., Apirukvorapinit, P., Gupta, R., Zhang, Q.: Data Dependence Based Testability Transformation in Automated Test Generation. In: Proceedings of the 16th IEEE International Symposium on Software Reliability Engineering (ISSRE 2005), Chicago, Illinios, USA, November 2005, pp. 245-254. IEEE Computer Society, Los Alamitos (2005).

Digital Library

[34]

Kirsopp, C., Shepperd, M., Hart, J.: Search Heuristics, Case-based Reasoning And Software Project Effort Prediction. In: Proceedings of the 2002 Conference on Genetic and Evolutionary Computation (GECCO 2002), New York, July 9-13, pp. 1367-1374. Morgan Kaufmann Publishers, San Francisco (2002).

Digital Library

[35]

Langdon, W.B., Banzhaf, W.: A SIMD interpreter for genetic programming on GPU graphics cards. In: O'Neill, M., Vanneschi, L., Gustafson, S., Esparcia Alc?azar, A.I., De Falco, I., Della Cioppa, A., Tarantino, E. (eds.) EuroGP 2008. LNCS, vol. 4971, pp. 73-85. Springer, Heidelberg (2008).

Digital Library

[36]

Lefticaru, R., Ipate, F.: Functional Search-based Testing from State Machines. In: Proceedings of the First International Conference on Software Testing, Verfication and Validation (ICST 2008), Lillehammer, Norway, April 9-11, pp. 525-528. IEEE Computer Society, Los Alamitos (2008).

Digital Library

[37]

Labossiere, J.E., Turrkan, N.: On the optimization of the tensor polynomial failure theory with a genetic algorithm. Transactions of the Canadian Society for Mechanical Engineering 16(3-4), 251-265 (1992).

[38]

McMinn, P.: Search-based Software Test Data Generation: A Survey. Software Testing, Verification and Reliability 14(2), 105-156 (2004).

Digital Library

[39]

McMinn, P., Harman, M., Binkley, D., Tonella, P.: The Species per Path Approach to Search-based Test Data Generation. In: Proceedings of the 2006 International Symposium on Software Testing and Analysis (ISSTA 2006), Portland, Maine, USA, July 17-20, pp. 13-24. ACM, New York (2006).

Digital Library

[40]

Mitchell, B.S., Mancoridis, S.: On the Automatic Modularization of Software Systems using the Bunch Tool. IEEE Transactions on Software Engineering 32(3), 193-208 (2006).

Digital Library

[41]

O'Keeffe, M., Ó Cinnéide, M.: Search-based Software Maintenance. In: Proceedings of the Conference on Software Maintenance and Reengineering (CSMR 2006), Bari, Italy, March 22-24, pp. 249-260. IEEE Computer Society, Los Alamitos (2006).

Digital Library

[42]

Poli, R., Cagnoni, S., Valli, G.: Genetic design of optimum linear and nonlinear QRS detectors. IEEE Transactions on Biomedical Engineering 42(11), 1137-1141 (1995).

[43]

Räihä, O.: A Survey on Search-Based Software Design. Technical Report D-2009-1, Department of Computer Sciences University of Tampere (March 2009).

[44]

Sagarna, R.: An Optimization Approach for Software Test Data Generation: Applications of Estimation of Distribution Algorithms and Scatter Search. PhD thesis, University of the Basque Country, San Sebastian, Spain (January 2007).

[45]

Seng, O., Bauer, M., Biehl, M., Pache, G.: Search-based Improvement of Subsystem Decompositions. In: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation (GECCO 2005), Washington, D.C., USA, June 25-29, pp. 1045-1051. ACM, New York (2005).

Digital Library

[46]

Shepperd, M.J.: Foundations of software measurement. Prentice Hall, Englewood Cliffs (1995).

Digital Library

[47]

Sagarna, R., Lozano, J.A.: Dynamic Search Space Transformations for Software Test Data Generation. Computational Intelligence 24(1), 23-61 (2008).

[48]

Tracey, N., Clark, J., Mander, K.: The Way Forward for Unifying Dynamic Test-Case Generation: the Optimisation-based Approach. In: Proceedings of the IFIP International Workshop on Dependable Computing and Its Applications (DCIA 1998), Johannesburg, South Africa, January 12-14, pp. 169-180. University of the Witwatersrand (1998).

[49]

Wegener, J., Baresel, A., Sthamer, H.: Evolutionary Test Environment for Automatic Structural Testing. Information and Software Technology Special Issue on Software Engineering using Metaheuristic Innovative Algorithms 43(14), 841-854 (2001).

[50]

Weimer, W., Nguyen, T.V., Goues, C.L., Forrest, S.: Automatically finding patches using genetic programming. In: International Conference on Software Engineerign (ICSE 2009), Vancouver, Canada, pp. 364-374 (2009).

Digital Library

[51]

Windisch, A., Wappler, S., Wegener, J.: Applying Particle Swarm Optimization to Software Testing. In: Proceedings of the 9th annual Conference on Genetic and Evolutionary Computation (GECCO 2007), London, England, July 7-11, pp. 1121-1128. ACM, New York (2007).

Digital Library

[52]

Xanthakis, S., Ellis, C., Skourlas, C., Le Gall, A., Katsikas, S., Karapoulios, K.: Application of Genetic Algorithms to Software Testing. In: Proceedings of the 5th International Conference on Software Engineering and Applications, Toulouse, France, December 7-11, pp. 625-636 (1992).

[53]

Zhang, Y., Finkelstein, A., Harman, M.: Search Based Requirements Optimisation: Existing Work S Challenges. In: Paech, B., Rolland, C. (eds.) REFSQ 2008. LNCS, vol. 5025, pp. 88-94. Springer, Heidelberg (2008).

Digital Library

Cited By

Alshahwan NCiancone AHarman MJia YMao KMarginean AMols APeleg HSarro FZorin IZhang DMøller A(2019)Some challenges for software testing research (invited talk paper)Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3293882.3338991(1-3)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.1145/3293882.3338991
Pérez FFont JArcega LCetina C(2019)Collaborative feature location in models through automatic query expansionAutomated Software Engineering10.1007/s10515-019-00251-926:1(161-202)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s10515-019-00251-9
Harman MPetke JEsparcia-Alcázar A(2015)GI4GIProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2768415(793-794)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739482.2768415
Show More Cited By

Recommendations

Dynamic adaptive search based software engineering
ESEM '12: Proceedings of the ACM-IEEE international symposium on Empirical software engineering and measurement

Search Based Software Engineering (SBSE) has proved to be a very effective way of optimising software engineering problems. Nevertheless, its full potential as a means of dynamic adaptivity remains under explored. This paper sets out the agenda for ...
The Human Competitiveness of Search Based Software Engineering
SSBSE '10: Proceedings of the 2nd International Symposium on Search Based Software Engineering

This paper reports a comprehensive experimental study regarding the human competitiveness of search based software engineering (SBSE). The experiments were performed over four well-known SBSE problem formulations: next release problem, multi-objective ...
Teaching and peer-learning particle swarm optimization

The graphical illustration of the proposed teaching and peer-learning PSO (TPLPSO), consisting of the teaching phase, the peer-learning phase, and the stagnation prevention strategy (SPS). A PSO algorithm's variant, abbreviated as TPLPSO, is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

FASE'10: Proceedings of the 13th international conference on Fundamental Approaches to Software Engineering

March 2010

383 pages

ISBN:3642120288

Editors:
David S. Rosenblum
Department of Computer Science, University College London, London, UK
,
Gabriele Taentzer
Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, Marburg, Germany

Sponsors

FASE: FASE
EASST: EASST
EACTS: EACTS
ETAPS: ETAPS

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 20 March 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alshahwan NCiancone AHarman MJia YMao KMarginean AMols APeleg HSarro FZorin IZhang DMøller A(2019)Some challenges for software testing research (invited talk paper)Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3293882.3338991(1-3)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.1145/3293882.3338991
Pérez FFont JArcega LCetina C(2019)Collaborative feature location in models through automatic query expansionAutomated Software Engineering10.1007/s10515-019-00251-926:1(161-202)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s10515-019-00251-9
Harman MPetke JEsparcia-Alcázar A(2015)GI4GIProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2768415(793-794)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739482.2768415
Pitangueira AMaciel RBarros M(2015)Software requirements selection and prioritization using SBSE approachesJournal of Systems and Software10.1016/j.jss.2014.09.038103:C(267-280)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1016/j.jss.2014.09.038
Harman MJia YLangdon WPetke JMoghadam IYoo SWu FEngels GBencomo N(2014)Genetic improvement for adaptive software engineering (keynote)Proceedings of the 9th International Symposium on Software Engineering for Adaptive and Self-Managing Systems10.1145/2593929.2600116(1-4)Online publication date: 2-Jun-2014
https://dl.acm.org/doi/10.1145/2593929.2600116
Colanzi TVergilio SGuez AssunçãO WPozo A(2013)Controversy CornerJournal of Systems and Software10.1016/j.jss.2012.07.04186:4(970-984)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1016/j.jss.2012.07.041
Kelk DJalbert KBradbury J(2013)Automatically Repairing Concurrency Bugs with ARCProceedings of the International Conference on Multicore Software Engineering, Performance, and Tools - Volume 806310.1007/978-3-642-39955-8_7(73-84)Online publication date: 19-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-39955-8_7
Harman MHarrison R(2012)The role of artificial intelligence in software engineeringProceedings of the First International Workshop on Realizing AI Synergies in Software Engineering10.5555/2666527.2666528(1-6)Online publication date: 5-Jun-2012
https://dl.acm.org/doi/10.5555/2666527.2666528
Harman MMansouri SZhang Y(2012)Search-based software engineeringACM Computing Surveys10.1145/2379776.237978745:1(1-61)Online publication date: 7-Dec-2012
https://dl.acm.org/doi/10.1145/2379776.2379787
Harman MBurke EClark JYao XRuneson PHöst MMendes EAndrews AHarrison R(2012)Dynamic adaptive search based software engineeringProceedings of the ACM-IEEE international symposium on Empirical software engineering and measurement10.1145/2372251.2372253(1-8)Online publication date: 19-Sep-2012
https://dl.acm.org/doi/10.1145/2372251.2372253
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents