No Access

Metaheuristics and Software Engineering: Past, Present, and Future

Enrique Alba

Universidad de Málaga, Málaga, Spain

E-mail Address: [email protected]

Search for more papers by this author

Javier Ferrer

Universidad de Málaga, Málaga, Spain

E-mail Address: [email protected]

Corresponding author.

Search for more papers by this author

, and

Ignacio Villalobos

Universidad de Málaga, Málaga, Spain

E-mail Address: [email protected]

Search for more papers by this author

https://doi.org/10.1142/S0218194021500443Cited by:3 (Source: Crossref)

Abstract

This work aims at giving an updated vision on the successful combination between Metaheuristics and Software Engineering (SE). Mostly during the 90s, varied groups of researchers dealing with search, optimization, and learning (SOL) met SE researchers, all of them looking for a quantified manner of modeling and solving problems in the software field. This paper will discuss on the construction, assessment, and exploitation tasks that help in making software programs a scientific object, subject to automatic study and control. We also want to show with several case studies how the quantification of software features and the automatic search for bugs can improve the software quality process, which eases compliance to ISO/IEEE standards. In short, we want to build intelligent automatic tools that will upgrade the quality of software products and services. Since we approach this new field as a cross-fertilization between two research domains, we then need to talk not only on metaheuristics for SE (well known by now), but also on SE for metaheuristics (not so well known nowadays). In summary, we will discuss here with three time horizons in mind: the old times [before the term search-based SE (SBSE) was used for this], the recent years on SBSE, and the many avenues for future research/development. A new body of knowledge in SOL and SE exists internationally, which is resulting in a new class of researchers able of building intelligent techniques for the benefit of software, that is, of modern societies.

Keywords:

References

1. B. W. Boelun, Software engineering economics, IEEE Trans. Softw. Eng. 10(1) (1981) 4–21. Google Scholar
2. C. Hitch, Sub-optimization in operations problems, J. Oper. Res. Soc. Am. 1(3) (1953) 87–99. Web of Science, Google Scholar
3. E. Alba and J. M. Troya, Genetic algorithms for protocol validation, in Proc. IV Int. Conf. Parallel Problem Solving from Nature, 1996, pp. 870–879. Crossref, Google Scholar
4. B. Jones, H.-H. Sthamer and D. Eyres, Automatic structural testing using genetic algorithms, Softw. Eng. J. 11(5) (1996) 299. Crossref, Web of Science, Google Scholar
5. O. Räihä, A survey on search-based software design, Comput. Sci. Rev. 4(4) (2010) 203–249. Crossref, Google Scholar
6. M. Harman, S. Afshin Mansouri and Y. Zhang, Search-based software engineering: Trends, techniques and applications, ACM Comput. Surv. 45 (2012) 1–64. Crossref, Web of Science, Google Scholar
7. P. McMinn, Search-based software testing: Past, present and future, in Proc. 4th Int. Workshop on Search-Based Software Testing, 2011, pp. 153–163. Crossref, Google Scholar
8. C. L. Goues, M. Dewey-Vogt, S. Forrest and W. Weimer, A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each, in Proc. 34th Int. Conf. Software Engineering, 2012, pp. 3–13. Crossref, Google Scholar
9. X. Zhang, N. Gupta and R. Gupta, Locating faults through automated predicate switching, in Proc. 28th Int. Conf. Software Engineering, 2006, p. 272. Crossref, Google Scholar
10. F. Glover and G. Kochenberger, Handbook of Metaheuristics (Kluwer, 2003). Crossref, Google Scholar
11. I. H. Osman and G. Laporte, Metaheuristics: A bibliography, Ann. Oper. Res. 63 (1996) 513–623. Crossref, Web of Science, Google Scholar
12. J. Clarke, J. Dolado, M. Harman, R. Hierons, B. Jones, M. Lumkin, B. Mitchell, S. Mancoridis, K. Rees, M. Roper and M. Shepperd, Reformulating software engineering as a search problem, IEE Proc. Softw. 150(3) (2003) 161. Crossref, Google Scholar
13. C. Blum and A. Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison, ACM Comput. Surv. 5(3) (2003) 189–213. Google Scholar
14. M. R. Garey and D. S. Johnson, A Guide to the Theory of NP-Completeness (W. H. Freeman, 1979). Google Scholar
15. E. Alba, How can metaheuristics help software engineers?, in 10th Int. Symp. Search-Based Software Engineering, LNCS Vol. 11036, 2018, pp. 89–105. Crossref, Google Scholar
16. T. Weise, Global Optimization Algorithms — Theory and Application (2008). Google Scholar
17. G. J. Woeginger, Exact algorithms for NP-hard problems: A survey, in Combinatorial Optimization — Eureka, You Shrink!, LNCS Vol. 2570 (Springer, 2003), pp. 185–207. Crossref, Google Scholar
18. R. F. Resende and C. Ribeiro, Greedy Randomized Adaptive Search Procedures (Springer, Boston, MA, 2003). Crossref, Google Scholar
19. T. G. Stützle, Local Search Algorithms for Combinatorial Problems: Analysis, Improvements, and New Applications (1998). Google Scholar
20. F. Glover, Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res. 13 (1986) 533–549. Crossref, Web of Science, Google Scholar
21. C. Reeves, Modern Heuristic Techniques (Wiley, 1996). Google Scholar
22. F. J. Ferrer, Optimization techniques for automated software test data generation, PhD thesis, Universidad de Málaga (2016). Google Scholar
23. N. Mladenovic and P. V. N. S. Hansen, Variable neighborhood search, Comput. Oper. Res. 24(11) (1997) 1097–1100. Crossref, Web of Science, Google Scholar
24. S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science 4598 (1983) 671–680. Crossref, Web of Science, Google Scholar
25. M. Dorigo, Learning and natural algorithms, PhD thesis, Politecnico di Milano (1992). Google Scholar
26. M. Dorigo, M. Oca and A. Engelbrecht, Particle swarm optimization, Scholarpedia 3(11) (2008) 1486. Crossref, Google Scholar
27. T. Bäck, D. B. Fogel and Z. Michalewicz, Handbook of Evolutionary Computation (Institute of Physics Publishing, Bristol, 1997). Crossref, Google Scholar
28. A. Villagra, E. Alba and G. Leguizamón, A methodology for the hybridization based in active components: The case of cGA and scatter search, Comput. Intell. Neurosci. 2016 (2016) 8289237. Crossref, Web of Science, Google Scholar
29. F. Chicano, J. Ferrer and E. Alba, Elementary landscape decomposition of the test suite minimization problem, in Int. Symp. Search Based Software Engineering, LNCS Vol. 6956, 2011, pp. 48–63. Crossref, Google Scholar
30. G. Luque and E. Alba, Math oracles: A new day of designing efficient self-adaptive algorithms, in Proc. GECCO (Companion), 2013, pp. 217–218. Crossref, Google Scholar
31. C. A. C. Coello, D. A. Van Veldhuizen and G. B. Lamont, Evolutionary Algorithms for Solving Multi-Objective Problems (Springer-Verlag, 2002). Crossref, Google Scholar
32. E. Alba, Parallel Metaheuristic A New Class of Algorithms (Wiley, 2005). Crossref, Google Scholar
33. L. Calvet, J. D. Armas, D. Masip and A. A. Juan, Learnheuristics: Hybridizing metaheuristics with machine learning for optimization with dynamic inputs, Open Math. 15 (2017) 261–280. Crossref, Web of Science, Google Scholar
34. S. Memeti, S. Pllana, A. Binotto, J. Kołodziej and I. Brandic, Using metaheuristics and machine learning for software optimization of parallel computing systems: A systematic literature review, Computing 101 (2019) 893–936. Crossref, Web of Science, Google Scholar
35. Y. Zhang, Search Based Software Engineering Repository, http://crestweb.cs.ucl.ac.uk/resources/sbse_repository/. Google Scholar
36. N. J. Van Eck and L. Waltman, How to normalize co-occurrence data? An analysis of some well-known similarity measures, J. Am. Soc. Inf. Sci. Technol. 60 (2009) 1635–1651. Crossref, Web of Science, Google Scholar
37. M. Harman and B. F. Jones, Software engineering using metaheuristic innovative algorithms: Workshop report, Inf. Softw. Technol. 43(14) (2001) 762–763. Crossref, Web of Science, Google Scholar
38. M. Harman and B. Jones, Search-based software engineering, Inf. Softw. Technol. 43(14) (2001) 833–839. Crossref, Web of Science, Google Scholar
39. B. W. Boehm, J. R. Brown and M. Lipow, Quantitative evaluation of software quality, in Proc. 2nd Int. Conf. Software Engineering, 1976, pp. 592–605. Google Scholar
40. A. I. Forrester and A. J. Keane, Recent advances in surrogate-based optimization, Prog. Aerosp. Sci. 45(1–3) (2009) 50–79. Crossref, Web of Science, Google Scholar
41. S. Nesmachnow, F. Luna and E. Alba, An empirical time analysis of evolutionary algorithms as C programs, Softw. — Pract. Exp. 45(1) (2015) 111–142. Crossref, Web of Science, Google Scholar
42. S. Luke, ECJ evolutionary computation library (1998), http://cs.gmu.edu/ $\sim$ eclab/projects/ecj/. Google Scholar
43. S. Ventura, C. Romero, A. Zafra, J. A. Delgado and C. Hervás, JCLEC: A Java framework for evolutionary computation, Soft Comput. 12(4) (2008) 381–392. Crossref, Web of Science, Google Scholar
44. L. Troiano, D. De Pasquale and P. Marinaro, Jenes genetic algorithms in Java (2006), http://jenes.intelligentia.it. Google Scholar
45. J. J. Durillo and A. J. Nebro, JMetal: A Java framework for multi-objective optimization, Adv. Eng. Softw. 42(10) (2011) 760–771. Crossref, Web of Science, Google Scholar
46. J. Alcalá-Fdez, A. Fernández, J. Luengo, J. Derrac, S. García, L. Sánchez and F. Herrera, KEEL data-mining software tool: Data set repository, integration of algorithms and experimental analysis framework, J. Mult.-Valued Log. Soft Comput. 17(2–3) (2011) 255–287. Web of Science, Google Scholar
47. The Apache Software Foundation, Apache Mahout Project (2014), https://mahout.apache.org. Google Scholar
48. D. Hadka and P. Reed, Borg: An auto-adaptive many-objective evolutionary computing framework, Evol. Comput. 21(2) (2013) 231–259. Crossref, Web of Science, Google Scholar
49. E. Alba, ssGA: Steady state GA (2000), http://neo.lcc.uma.es/software/ssga. Google Scholar
50. D. W. Dyer, Watchmaker framework for evolutionary computation (2006), https://watchmaker.uncommons.org/. Google Scholar
51. M. A. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann and I. H. Witten, The WEKA data mining software: An update, SIGKDD Explor. 11 (2009) 10–18. Crossref, Google Scholar
52. A. Gigleux and A. Campbell, SonarQube Documentation (2016), https://docs.sonarqube.org/latest/. Google Scholar
53. M. Safe, J. Carballido, I. Ponzoni and N. Brignole, On stopping criteria for genetic algorithms, in Advances in Artificial Intelligence — SBIA 2004, 2004, pp. 405–413. Crossref, Google Scholar
54. A. Inselberg, Parallel Coordinates Visual Multidimensional Applications and Its Applications (Springer, 2009). Google Scholar
55. G. Ochoa and N. Veerapen, Mapping the global structure of TSP fitness landscapes, J. Heuristics 24(3) (2018) 265–294. Crossref, Web of Science, Google Scholar
56. T. Jones and S. Forrest, Fitness distance correlation as a measure of problem difficulty for genetic algorithms, in Proc. 6th Int. Conf. Genetic Algorithms, 1995, pp. 184–192. Google Scholar
57. J. R. Koza, Human-competitive results produced by genetic programming, Genet. Program. Evol. Mach. 11 (2010) 251–284. Crossref, Web of Science, Google Scholar
58. K. Deb, Multi-objective optimization, in Search Methodologies (Springer, 2005), pp. 273–316. Crossref, Google Scholar
59. A. Ramirez, J. R. Romero and C. Simons, A systematic review of interaction in search-based software engineering, IEEE Trans. Softw. Eng. 45 (2019) 760–781. Crossref, Web of Science, Google Scholar
60. Z.-W. Zhang, X.-Y. Jing and T.-J. Wang, Label propagation based semi-supervised learning for software defect prediction, Autom. Softw. Eng. 24 (2017) 47–69. Crossref, Web of Science, Google Scholar
61. J. Ferrer, F. Chicano and E. Alba, Hybrid algorithms based on integer programming for the search of prioritized test data in software product lines, in European Conf. Applications of Evolutionary Computation, LNCS Vol. 10200, 2017, pp. 3–19. Crossref, Google Scholar
62. S. Yang, Evolutionary computation for dynamic optimization problems, in Proc. Companion Publication of the 2015 on Genetic and Evolutionary Computation Conf., 2015, pp. 629–649. Crossref, Google Scholar
63. W. B. Langdon, B. Y. H. Lam, M. Modat, J. Petke and M. Harman, Genetic improvement of GPU software, Genet. Program. Evol. Mach. 18(1) (2017) 5–44. Crossref, Web of Science, Google Scholar
64. I. Villalobos, J. Ferrer and E. Alba, Measuring the quality of machine learning and optimization frameworks, in Advances in Artificial Intelligence: 18th Conf. Spanish Association for Artificial Intelligence, 2018, pp. 128–139. Crossref, Google Scholar
65. V. Jayapaul, S. Jo, R. Raman, V. Raman and S. R. Satti, Space efficient data structures for nearest larger neighbor, J. Discret. Algorithms 36 (2016) 63–75. Crossref, Web of Science, Google Scholar
66. A. Hassan, Source code profiling for line-level latency and energy consumption estimation, US Patent Reference No.: 2018002491 (2018). Google Scholar
67. G. Karafotias, M. Hoogendoorn and A. E. Eiben, Parameter control in evolutionary algorithms: Trends and challenges, IEEE Trans. Evol. Comput. 19(2) (2015) 167–187. Crossref, Web of Science, Google Scholar
68. E. Alba, G. Luque and S. Nesmachnow, Parallel metaheuristics: Recent advances and new trends, Int. Trans. Oper. Res. 20 (2013) 1–48. Crossref, Web of Science, Google Scholar
69. N. Fenton, S. Ii and S. Iii, Software measurement — A necessary scientific basis, IEEE Trans. Softw. Eng. 20(3) (1994) 199–206. Crossref, Web of Science, Google Scholar