Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

Reformulating software engineering as a search problem

Reformulating software engineering as a search problem

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings - Software — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Metaheuristic techniques such as genetic algorithms, simulated annealing and tabu search have found wide application in most areas of engineering. These techniques have also been applied in business, financial and economic modelling. Metaheuristics have been applied to three areas of software engineering: test data generation, module clustering and cost/effort prediction, yet there remain many software engineering problems which have yet to be tackled using metaheuristics. It is surprising that metaheuristics have not been more widely applied to software engineering; many problems in software engineering are characterised by precisely the features which make metaheuristics search applicable. In the paper it is argued that the features which make metaheuristics applicable for engineering and business applications outside software engineering also suggest that there is great potential for the exploitation of metaheuristics within software engineering. The paper briefly reviews the principal metaheuristic search techniques and surveys existing work on the application of metaheuristics to the three software engineering areas of test data generation, module clustering and cost/effort prediction. It also shows how metaheuristic search techniques can be applied to three additional areas of software engineering: maintenance/evolution system integration and requirements scheduling. The software engineering problem areas considered thus span the range of the software development process, from initial planning, cost estimation and requirements analysis through to integration, maintenance and evolution of legacy systems. The aim is to justify the claim that many problems in software engineering can be reformulated as search problems, to which metaheuristic techniques can be applied. The goal of the paper is to stimulate greater interest in metaheuristic search as a tool of optimisation of software engineering problems and to encourage the investigation and exploitation of these technologies in finding near optimal solutions to the complex constraint-based scenarios which arise so frequently in software engineering.

References

    1. 1)
      • Mitchell, B.S., Mancoridis, S.: `Using heuristic search techniques to extract design abstractions from source code', Proc. Conf. on Genetic and evolutionary computation (GECCO), 9–13 July 2002, New York, p. 1375–1382.
    2. 2)
      • Anquetil, N.: `A comparison of graphs of concept for reverse engineering', Proc. Int. Workshop on Program comprehension, June 2000.
    3. 3)
      • A. Lakhotia , J.-C. Deprez . Restructuring programs by tucking statements into functions. Inf. Softw. Technol. , 677 - 689
    4. 4)
      • Williams, K.P.: `Evolutionary algorithms for automatic parallelization', September 1998, PhD, University of Reading, Department of Computer Science, UK.
    5. 5)
      • Bennett, K.H.: `Do program transformations help reverse engineerign?', Proc. IEEE Int. Conf. on Software maintenance (ICSM'98), Nov. 1998, Bethesda, Maryland, USA, p. 247–254.
    6. 6)
      • S.M. Sait , H. Youssef . (1999) Iterative computer algorithms with applications in engineering: solving combinatorial optimization problems.
    7. 7)
      • N. Fenton , S. Pfleeger . (1998) Software metrics: a rigorous approach.
    8. 8)
      • Williams, S.A., Fagg, G.E.: `Experience of developing codes for distributed for parallel architectures', PPECC Workshop: ‘Distributed v parallel: convergence or divergence?’, Mar 1995, p. 115–118.
    9. 9)
      • Anquetil, N., Lethbridge, T.: `Recovering software architecture from the names of source files', Proc. Working Conf. on Reverse engineering, Oct. 1999.
    10. 10)
      • D. Bjørner , A.P. Ershov , N.D. Jones . (1987) Partial evaluation and mixed computation.
    11. 11)
      • J. Darlington , R.M. Burstall . A transformation system for developing recursive programs. J. ACM , 1 , 44 - 67
    12. 12)
    13. 13)
    14. 14)
      • C.R. Reeves . (1993) Modern heuristic techniques for combinatorial problems.
    15. 15)
      • J. Wegener , H. Sthamer , B.F. Jones , D.E. Eyres . Testing real-time systems using genetic algorithms. Softw. Qual. , 127 - 135
    16. 16)
      • T. Back . (1996) Evolutionary algorithms in theory and practice.
    17. 17)
      • N. Metropolis , A. Rosenbluth , M. Rosenbluth , A. Teller , E. Teller . Equation of state calculations by fast computing machines. J. Chem. Phys. , 1087 - 1092
    18. 18)
      • Kirsopp, C., Shepperd, M., Hart, J.: `Search heuristics, case-based reasoning and software project effort prediction', Proc. Conf. on Genetic and evolutionary computation (GECCO), 9–13 July 2002, New York, p. 1367–1374.
    19. 19)
      • M. Mitchell . (1998) An introduction to genetic algorithms.
    20. 20)
      • Ward, M., Calliss, F.W., Munro, M.: `The maintainer's assistant', Proc. Int. Conf. on Software maintenance 1989, 1989, Los Alamitos, California, USA, p. 307.
    21. 21)
      • V. Belton , T.J. Stewart . (2001) Multiple criteria decision analysis: an integrated approach.
    22. 22)
      • C. Ryan . (2000) Automatic re-engineering of software using genetic programming.
    23. 23)
    24. 24)
      • Lindig, C., Snelting, G.: `Assessing modular structure of legacy code based on mathematical concept analysis', Proc. Int. Conf. on Software engineering, 1997, p. 349–359.
    25. 25)
      • R.P. Pargas , M.J. Harrold , R.R. Peck . Test-data generation using genetic algorithms. J Softw. Test. Verif. Reliab. , 263 - 282
    26. 26)
    27. 27)
      • K. Bennett . Automated support for software maintenance. J. Inf. Softw. Technol. , 1 , 74 - 85
    28. 28)
      • Ryan, C., Walsh, P.: `The evolution of provable parallel programs', Proc. 2nd Ann. Conf. on Genetic programming, 13–16 July 1997, CA, USA, Stanford University, p. 295–302.
    29. 29)
      • Williams, K.P., Williams, S.A.: `Genetic compilers: a new technique for automatic parallelisation', 2ndEuropean School of Parallel programming environments (ESPPE'96), 1996, L'Alpe d'Huez, France, p. 27–30.
    30. 30)
      • A.V. Aho , R. Sethi , J.D. Ullman . (1985) Compilers: principles, techniques and tools.
    31. 31)
    32. 32)
      • D. Hutchens , V. Basili . System structure analysis: clustering with data bindings. IEEE Trans. Softw. Eng. , 8 , 749 - 757
    33. 33)
      • Tracey, N., Clark, J., Mander, K.: `Automated program flaw finding using simulated annealing', Int. Symp. on Software testing and analysis (ACM/SIGSOFT), March 1998, p. 73–81.
    34. 34)
      • Doval, D., Mancoridis, S., Mitchell, B.S.: `Automatic clustering of software systems using a genetic algorithms', Int. Conf. on Software tools and engineering practice (STEP), 30–2 August–September 1999, Pittsburgh, PA.
    35. 35)
      • Ward, M.: `Assembler to ', IEEE Int. Conf. on Software maintenance (ICSM'99), Aug 1999, Oxford, UK.
    36. 36)
      • H. Müller , M. Orgun , S. Tilley , J. Uhl . A reverse engineering approach to subsystem structure identification. J. Softw. Maint. Res. Pract. , 181 - 204
    37. 37)
      • M. Shaw , D. Garlan . (1996) Software architecture: perspectives on an emerging discipline.
    38. 38)
      • Wegener, J., Grimm, K., Grochtmann, M., Sthamer, H., Jones, B.F.: `Systematic testing of real-time systems', 4thInt. Conf. on Software testing analysis and review (EuroSTAR), 1996.
    39. 39)
      • van Deursen, A., Kuipers, T.: `Identifying objects using cluster and concept analysis', SEN-R9814, Technical, Sept. 1998.
    40. 40)
      • Harman, M., Hu, L., Hierons, R.M., Zhang, X., Munro, M., Dolado, J.J., Otero, M.C., Wegener, J.: `A post-placement side-effect removal algorithm', IEEE Int. Conf. on Software maintenance (ICSM), Oct 2002, Montreal, Canada, p. 2–11.
    41. 41)
    42. 42)
      • M.J. Shepperd . (1995) Foundations of software measurement.
    43. 43)
      • Whitley, D., Beveridge, J.R., Guerra-Salcedo, C., Graves, C.: `Messy genetic algorithms for subset feature selection', Proc. 7th Int. Conf. on Genetic algorithms, 19–23 July 1997, San Francisco, p. 568–575.
    44. 44)
      • C. Consel , L. Hornop , R. Marlet , G. Muller , S. Thibault , E.-N. Volanschi . Partial evaluation for software engineering. ACM Comput. Surv. , 3
    45. 45)
      • Harman, M., Hierons, R., Proctor, M.: `A new representation and crossover operator for search-based optimization of software modularization', Proc. Conf. on Genetic and evolutionary computation (GECCO), 9–13 July 2002, New York, p. 1351–1358.
    46. 46)
    47. 47)
      • Ashcroft, E.A., Manna, Z.: `The translation of got programs into whil programs', Proc. of IFIP Congress 71, 1972, 1, North-Holland, p. 250–255.
    48. 48)
      • D.E. Goldberg . (1989) Genetic algorithms in search, optimization & machinelearning.
    49. 49)
      • Tracey, N., Clark, J., Mander, K.: `The way forward for unifying dynamic test-case generation: The optimisation-based approach', Int. Workshop on Dependable computing and its applications (DCIA), January 1998, IFIP, p. 169–180.
    50. 50)
      • C.J. Burgess , M. Lefley . Can genetic programming improve software effort estimation? A comparative evaluation. Inf. Softw. Technol. , 14 , 863 - 873
    51. 51)
      • Mitchell, B.S.: `A heuristic search approach to solving the software clustering problem', Jan 2002, PhD, Drexel University, Philadelphia, PA.
    52. 52)
      • B.F. Jones , D.E. Eyres , H.H. Sthamer . A strategy for using genetic algorithms to automate branch and fault-based testing. Comput. J. , 2 , 98 - 107
    53. 53)
    54. 54)
      • G. Winter , J. Periaux , M. Galan , P. Cuesta . (1995) Genetic algorithms in engineering and computer science.
    55. 55)
      • R.G. Michael , S.J. David . (1979) Computers and intractability: a guide to the theory of NP-completeness.
    56. 56)
    57. 57)
      • J.H. Holland . (1992) Adaption in natural and artificial systems.
    58. 58)
      • The Drexel University Software Engineering Research Group (SERG). http://serg.mes.drexel.edu.
    59. 59)
      • Mancoridis, S., Mitchell, B., Rorres, C., Chen, Y., Gansner, E.: `Using automatic clustering to produce high-level system organizations of source code', Proc. 6th Int. Workshop on Program comprehension, June 1998.
    60. 60)
      • J.R. Koza . (1992) Genetic programming: on the programming of computers by means of natural selection.
    61. 61)
      • Schwanke, R.W.: `An intelligent tool for re-engineering software modularity', Proc. 13th Int. Conf. on Software engineering, May 1991, p. 83–92.
    62. 62)
      • F. Glover . Tabu search: a tutorial. Interfaces , 74 - 94
    63. 63)
      • Bennett, K., Bull, T., Younger, E., Luo, Z.: `Bylands: reverse engineering safety-critical systems', IEEE Int. Conf. on Software maintenance, 1995, IEEE Computer Society Press, Los Alamitos, California, USA, p. 358–366.
    64. 64)
      • P.J.M. van Larrhoven , E.H.L. Aarts . (1987) Simulated annealing: theory and practice.
    65. 65)
      • De Jong, K.: `On using genetic algorithms to search program spaces', Genetic algorithms and their applications. Proc. 2nd Int. Conf. on Genetic algorithms, 28–31 July 1987, MIT, Cambridge, MA, USA, p. 210–216.
    66. 66)
    67. 67)
      • C.E. Shannon . A mathematical theory of communication. Bell Syst. Tech. J. , 379 - 423, 623–656
    68. 68)
      • B. Jones , H.-H. Sthamer , D. Eyres . Automatic structural testing using genetic algorithms. Softw. Eng. J. , 299 - 306
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-sen_20030559
Loading

Related content

content/journals/10.1049/ip-sen_20030559
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address