An agent-based hyper-heuristic for software systems modularization

Document Type : Original Article

Authors

Department of Computer Science, University of Tabriz, Tabriz, Iran.

Abstract

Modularization algorithms are used to recover the software architecture. These algorithms divide the source code of the software system into smaller and more understandable modules. Since software modularization is an NP-hard problem, search-based methods are usually used to solve it. In recent years, the use of hyper-heuristics with intelligent search approaches has increased to achieve a higher level of generality. In this paper, a general agent-based hyper-heuristic, using the concept of multi-agent systems, is presented for software modularization. In the proposed algorithm, agents with diversification and intensification search perspectives are used, and agents with the same perspective are placed in a coalition. In each step of the search, the most appropriate coalition is automatically selected using reinforcement learning, and its agents are executed in parallel. Also, in the design of some agents, to maintain diversity, the concept of chaos theory is used. To demonstrate the applicability of the proposed algorithm, eleven real-world software systems with small and medium sizes, along with ten folders of Mozilla Firefox with different functionalities and sizes are selected. The results of the experiments show that the proposed hyper-heuristic, in most cases, produces higher-quality modularizations in less time than the compared algorithms. The average numerical improvement of the proposed algorithm in terms of modularization quality and execution time on ten folders of Mozilla Firefox is 77.607 and 59.448%, respectively.

Keywords

Main Subjects

References

[1] B. Pourasghar, H. Izadkhah, A. Isazadeh, and S. Lotfi, “A graph-based clustering algorithm for software systems modularization,” Inf. Softw. Technol., vol. 133, p. 106469, 2021, doi: 10.1016/j.infsof.2020.106469.
[2] H. Izadkhah and M. Tajgardan, “Information theoretic objective function for genetic software clustering,” Multidisciplinary Digit. Pub. Instit. Proc., vol. 46, no. 1, p. 18, 2019, doi: 10.3390/ecea-5-06681.
[3] M. Tajgardan and H. Izadkhah, “Critical Review of the Bunch: A Well-Known Tool for the Recovery and Maintenance of Software System Structures,” Critical Rev., vol. 6, no. 3, pp. 363-367, 2017, doi: 10.17148/IJARCCE.2017.6383.
[4] S. Gholamshahi and S.M.H. Hasheminejad, “A method for identifying software components based on Non-dominated Sorting Genetic Algorithm,” Soft Comput. J., vol. 7, no. 2, pp. 47-64, 2019, dor: 20.1001.1.23223707.1397.7.2.4.5 [In Persian].
[5] M. Nabiloo and N. Daneshpour, “A clustering algorithm for categorical data with combining measures,” Soft Comput. J., vol. 5, no. 1, pp. 14-25, 2017 [In Persain].
[6] A. Isazadeh, H. Izadkhah, and I. Elgedawy, Source Code Modularization Theory and Techniques, Springer International Publishing, 2017.
[7] S. Asta, Machine learning for improving heuristic optimisation, Doctoral dissertation, University of Nottingham, 2015.
[8] M.A.L. Silva, S.R. de Souza, M.J.F. Souza, and M.F. de Franca Filho, “Hybrid metaheuristics and multi-agent systems for solving optimization problems: A review of frameworks and a comparative analysis,” Appl. Soft Comput., vol. 71, pp. 433-459, 2018, doi: 10.1016/j.asoc.2018.06.050.
[9] R. Malek, “An agent-based hyper-heuristic approach to combinatorial optimization problems,” in IEEE Int. Conf. Intell. Comput. Intell. Syst., 2010, pp. 428-434.
[10] A. Hassan and N. Pillay, “Hybrid metaheuristics: An automated approach,” Expert Syst. Appl., vol. 130, pp. 132-144, 2019, doi: 10.1016/j.eswa.2019.04.027.
[11] D. Meignan, A. Koukam, and J.-C. Creput, “Coalition-based metaheuristic: a self-adaptive metaheuristic using reinforcement learning and mimetism,” J. Heuristics, vol. 16, no. 6, pp. 859-879, 2010, doi: 10.1007/s10732-009-9121-7.
[12] J.    Huang, J. Liu, and X. Yao, “A multi-agent evolutionary algorithm for software module clustering problems,” Soft Comput., vol. 21, no. 12, pp. 3415-3428, 2017,  doi: 10.1007/s00500-015-2018-5.
[13] A.C. Kumari and K. Srinivas, “Hyper-heuristic approach for multi-objective software module clustering,” J. Syst. Softw., vol. 117, pp. 384-401, 2016, doi: 10.1016/j.jss.2016.04.007.
[14] M. Tajgardan, H. Izadkhah, and S. Lotfi, “A Reinforcement Learning-based Iterated Local Search for Software Modularization,” in 8th Iranian Conf. Signal Process. Intell. Syst. (ICSPIS), 2022, pp. 1-6, doi: 10.1109/ICSPIS56952.2022.10043949.
[15] M. Tajgardan, H. Izadkhah, and S. Lotfi, “An Iterated Local Search Strengthened by a Q-learning-based Hyper-heuristic for Software Modularization,” Soft Comput. J., 2023, 10.22052/SCJ.2023.252654.1135.
[16] M. Saeed, O. Maqbool, H.A. Babri, S.Z. Hassan, and S.M. Sarwar, “Software clustering techniques and the use of combined algorithm,” in 7th European Conf. Soft. Maintenan. Reeng., 2003, pp. 301-306, doi: 10.1109/CSMR.2003.1192438.
[17] O. Maqbool and H. Babri, “Hierarchical clustering for software architecture recovery,” IEEE Trans. Softw. Eng. vol. 33, no. 11, pp. 759-780, 2007, doi: 10.1109/TSE.2007.70732.
[18] R. Naseem, O. Maqbool, and S. Muhammad, “Cooperative clustering for software modularization,” J. Syst. Softw., vol. 86, no. 8, pp. 2045-2062, 2013,  doi: 10.1016/j.jss.2013.03.080.
[19] B.S. Mitchell, A heuristic search approach to solving the software clustering problem, Ph.D. Thesis, Drexel University, 2002.
[20] S. Parsa and O. Bushehrian, “A New Encoding Scheme and a Framework to Investigate Genetic Clustering Algorithms,” J. Res. Pract. Inf. Technol., vol. 37, no. 1, pp. 127-143, 2005.
[21] M. Harman and X. Yao, “Software module clustering as a multi-objective search problem,” IEEE Trans. Softw. Eng., vol. 37, no. 2, pp. 264-282, 2010, doi: 10.1109/TSE.2010.26.
[22] M. Tajgardan and H. Izadkhah, “Software Systems Clustering Using Estimation of Distribution Approach,” J. Appl. Comput. Sci. Methods., vol. 8, no. 2, pp. 99-113, 2016, dx.doi: 10.1515/jacsm-2016-0007.
[23] J. Huang and J. Liu, “A similarity-based modularization quality measure for software module clustering problems,” Inf. Sci., vol. 342, pp. 96-110, 2016, doi: 10.1016/j.ins.2016.01.030.
[24] B.S. Mitchell and S. Mancoridis, “On the automatic modularization of software systems using the bunch tool,” IEEE Trans. Softw. Eng., vol. 32, no. 3, pp. 193-208, 2006, doi: 10.1109/TSE.2006.31.
[25] N. Sadat Jalali, H. Izadkhah, and S. Lotfi, “Multi-objective search-based software modularization: structural and non-structural features,” Soft Comput., vol. 23, no. 21, pp. 11141-11165, 2019, doi: 10.1007/s00500-018-3666-z.
[26] M. Kargar, A. Isazadeh, and H. Izadkhah, “Semantic-based software clustering using hill climbing,” in Int. Symp. Comput. Sci. Soft. Eng. Conf. (CSSE), 2017, pp. 55-60, doi: 10.1109/CSICSSE.2017.8320117.
[27] B. Arasteh, A. Seyyedabbasi, J. Rasheed, and A. Abu-Mahfouz, “Program Source-Code Re-Modularization Using a Discretized and Modified Sand Cat Swarm Optimization Algorithm,” Symmetry, vol. 15, no. 2, p. 401, 2023,‏ doi: 10.3390/sym15020401.
[28] N. Teymourian, H. Izadkhah, and A. Isazadeh, “A fast clustering algorithm for modularization of large-scale software systems,” IEEE Trans. Softw. Eng., vol. 48, no. 4, pp. 1451-1462, 2020, doi: 10.1109/TSE.2020.3022212.
[29] V. Tzerpos and R.C. Holt, “Accd: an algorithm for comprehension-driven clustering,” in Proc. 7th Work. Conf. Rev. Eng., 2000, pp. 258-267, doi: 10.1109/WCRE.2000.891477.
[30] B. Zarei, M.R. Meybodi, and B. Masoumi, “Chaotic memetic algorithm and its application for detecting community structure in complex networks,” Chaos: Interdisciplinary J. Nonlinear Sci., vol. 30, no. 1, p. 13125, 2020, doi: 10.1063/1.5120094.
[31] S.S. Choong, L.P. Wong, and C.P. Lim, “Automatic design of hyper-heuristic based on reinforcement learning,” Inf. Sci., vol. 436, pp. 89-107, 2018, doi: 10.1016/j.ins.2018.01.005.
[32] H. Izadkhah, I. Elgedawy, and A. Isazadeh, “E-CDGM: An Evolutionary Call-Dependency Graph Modularization Approach for Software Systems,” Cybern. Inf. Technol., vol. 16, no. 3, 2016, dx.doi: 10.1515/cait-2016-0035.
[33] K.A. Mahdavi, Clustering genetic algorithm for software modularisation with a multiple hill climbing approach, Ph.D. Thesis, Brunel University, 2005.

Files

History

  • Receive Date: 21 October 2022
  • Revise Date: 12 September 2023
  • Accept Date: 12 October 2023

Share

How to cite

Statistics