Abstract
Random number generators are a core component of heuristic search algorithms. They are used to build candidate solutions and to reduce bias while transforming these solutions during the search. Despite of their usefulness, random numbers also have drawbacks, as one cannot guarantee that all portions of the search space are covered and must run an algorithm many times to statistically evaluate its behavior. In this paper we present a study in which a Hill Climbing search with random restart was applied to the software clustering problem under two configurations. First, the algorithm used pseudo-random numbers to create the initial and restart solutions. Then, the algorithm was executed again but the initial and restart solutions were built according to a quasi-random sequence. Contrary to previous findings with other heuristic algorithms, we observed that the quasi-random search could not outperform the pseudo-random search for two distinct fitness functions and fourteen instances.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arcuri, A., Briand, L.: A Practical Guide for Using Statistical Tests to Assess Randomized Algorithms in Software Engineering. In: Proc. of the 33th International Conference on Software Engineering, ICSE 2011, Hawaii, EUA (2011)
Barros, M.O.: An Analysis of the Effects of Composite Objectives in Multiobjective Software Module Clustering. In: Proceedings of the Genetic and Evolutionary Computing Conference (GECCO 2012), Philadelphia, USA (2012)
Barros, M.O., Dias-Neto, A.C.: Threats to Validity in Search-based Software Engineering Empirical Studies, Technical Report DIA/UNIRIO, No. 6, Rio de Janeiro, Brazil (2011), http://www.seer.unirio.br/index.php/monografiasppgi/article/viewFile/1479/1307
Briand, L.C., Morasca, S., Basili, V.R.: Defining and Validating Measures for Object-based High-Level Design. IEEE Trans. on Software Engineering 25(5) (1999)
Doval, D., Mancoridis, S., Mitchell, B.: Automatic Clustering of Software Systems using a Genetic Algorithm. In: Proc. of the International Conference on Software Tools and Engineering Practice, STEP 1999 (1999)
Durillo, J.J., Nebro, A.J., Luna, F., Doronsoro, B., Alba, E.: JMetal: A Java Framework for Developing Multi-objective Optimization Metaheuristics. TR ITI-2006-10, Dept. de Lenguajes y Ciencias de Computacion, Univ. Málaga (2006)
Georgieva, A., Jordanov, I.: Global optimization based on novel heuristics, low-discrepancy sequences and genetic algorithms. European Journal of Operational Research (196), 413–422 (2009)
Gibbs, S., Tsichritzis, D., et al.: Class Management for Software Communities. Communications of the ACM 33(9), 90–103 (1990)
Harman, M., Swift, S., Mahdavi, K.: An Empirical Study of the Robustness of two Module Clustering Fitness Functions. In: Proceedings of the Genetic and Evolutionary Computing Conference (GECCO 2005), Washington DC, USA (2005)
Harman, M., Masouri, S.A., Zhang, Y.: Search Based Software Engineering: A Comprehensive Analysis and Review of Trends Techniques and Applications, Dept. of Computer Science, King’s College London, Technical Report TR-09-03 (April 2009)
Kimura, S., Matsumura, K.: Genetic Algorithms using Low-Discrepancy Sequences. In: Proceedings of GECCO 2005, Washington DC, USA (2005)
Larman, C.: Applying UML and Patterns: An Introduction to Object-Oriented Analysis and the Unified Process. Prentice Hall, Upper Saddle River (2002)
Levy, G.: An introduction to quasi-random numbers. Numerical Algorithms Group Ltd., http://www.nag.co.uk/IndustryArticles/introduction_to_quasi_random_numbers.pdf (last accessed in April 10, 2012)
Maaranen, H., Miettinen, K., Makela, M.M.: Quasi-Random Initial Population for Genetic Algorithms. Computers and Mathematics w/ Applications (47), 1885–1895 (2004)
Mahdavi, K., Harman, M., Hierons, R.M.: A Multiple Hill Climbing Approach to Software Module Clustering. In: Proceedings of the International Conference on Software Maintenance, Amsterdan, pp. 315–324 (2003)
Mancoridis, S., Mitchell, B.S., Chen, Y., Gansner, E.R.: Bunch: A Clustering Tool for the Recovery and Maintenance of Software System Structures. In: Proceedings of the IEEE International Conference on Software Maintenance, pp. 50–59 (1999)
McConnell, S.: Code Complete, 2nd edn. Microsoft Press (2004)
Morokoff, W.J., Caflish, R.E.: Quasi-random Sequences and their Discrepancies. SIAM Journal of Scientific Computing 15(6), 1251–1279 (1994)
Niederreiter, H.G.: Quasi-Monte Carlo methods and pseudo-random numbers. Bulletin of the American Mathematical Society 84(6), 957–1041 (1978)
Pant, M., Thangaraj, R., Grosan, C., Abraham, A.: Improved Particle Swarm Optimization with Low-Discrepancy Sequences. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2008), Hong Kong, pp. 3011–3018 (2008)
Praditwong, K., Harman, M., Yao, X.: Software Module Clustering as a Multiobjective Search Problem. IEEE Transactions on Software Engineering 37(2), 262–284 (201)
Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical Recipes: The Art of Scientific Computing, 2nd edn. Cambridge University Press, NY (1992)
Räihä, O.: A Survey on Search-Based Software Design. Technical Report D-2009-1, Department of Computer Sciences University Of Tampere (March 2007)
Thangaraj, R., Pant, M., Abraham, A., Badr, Y.: Hybrid Evolutionary Algorithm for Solving Global Optimization Problems. In: Corchado, E., Wu, X., Oja, E., Herrero, Á., Baruque, B. (eds.) HAIS 2009. LNCS, vol. 5572, pp. 310–318. Springer, Heidelberg (2009)
Tucker, A., Swift, S., Liu, X.: Grouping Multivariate Time Series via Correlation. IEEE Transactions on Systems, Man, & Cybernetics, Part B: Cybernetics 31(2), 235–245 (2001)
Wohlin, C., Runeson, P., Höst, M., Ohlsson, M., Regnell, B., Wesslén, A.: Experimentation in Software Engineering. Kluwer Academic Publishers, Norwell (2000)
Yourdon, E., Constantine, L.L.: Structured Design: Fundamentals of a Discipline of Computer Program and Systems Design. Yourdon Press (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barros, M.d.O. (2012). Evaluating the Importance of Randomness in Search-Based Software Engineering. In: Fraser, G., Teixeira de Souza, J. (eds) Search Based Software Engineering. SSBSE 2012. Lecture Notes in Computer Science, vol 7515. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33119-0_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-33119-0_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33118-3
Online ISBN: 978-3-642-33119-0
eBook Packages: Computer ScienceComputer Science (R0)