An iterated local search strengthened by a Q-learning-based hyper-heuristic for software modularization

نوع مقاله : مقاله پژوهشی

نویسندگان

دانشکده ریاضی، آمار و علوم کامپیوتر، دانشگاه تبریز، تبریز، ایران.

چکیده

Software comprehension plays an important role during its improvement and maintenance process. Software modularization is a key activity for recovering the software architecture, which improves software understanding. Since the software modularization problem is NP-hard, meta-heuristics such as evolutionary algorithms (EAs) are usually used to solve it. EAs are problem-dependent, and they also require considerable space and time. Recently, the use of hyper-heuristic approaches growing to obtain more generality. This paper proposes an iterated local search (ILS) strengthened by a Q-learning-based hyper-heuristic for software modularization that overcomes the limitations of EAs.  In the proposed algorithm, two main components of ILS, i.e., perturbation and local search components, are intelligently selected using a Q-learning-based hyper-heuristic in each iteration. The performance of the proposed algorithm is evaluated on eleven real-world software systems of small and medium sizes. The results of the experiments demonstrate that the proposed ILS produces modularizations that have higher or equal quality compared to the quality of the modularizations obtained by selected algorithms.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

An iterated local search strengthened by a Q-learning-based hyper-heuristic for software modularization

نویسندگان [English]

  • Mahjoubeh Tajgardan
  • Habib Izadkhah
  • Shahriar Lotfi
Faculty of Mathematics, Statistics, and Computer Science, University of Tabriz, Tabriz, Iran.
چکیده [English]

Software comprehension plays an important role during its improvement and maintenance process. Software modularization is a key activity for recovering the software architecture, which improves software understanding. Since the software modularization problem is NP-hard, meta-heuristics such as evolutionary algorithms (EAs) are usually used to solve it. EAs are problem-dependent, and they also require considerable space and time. Recently, the use of hyper-heuristic approaches growing to obtain more generality. This paper proposes an iterated local search (ILS) strengthened by a Q-learning-based hyper-heuristic for software modularization that overcomes the limitations of EAs.  In the proposed algorithm, two main components of ILS, i.e., perturbation and local search components, are intelligently selected using a Q-learning-based hyper-heuristic in each iteration. The performance of the proposed algorithm is evaluated on eleven real-world software systems of small and medium sizes. The results of the experiments demonstrate that the proposed ILS produces modularizations that have higher or equal quality compared to the quality of the modularizations obtained by selected algorithms.

کلیدواژه‌ها [English]

  • Software modularization
  • Iterated local search
  • Hyper-heuristic
  • Q-learning
  • Evolutionary algorithms
[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] A. Isazadeh, H. Izadkhah, and I. Elgedawy, Source Code Modularization - Theory and Techniques. Springer, 2017, doi: 10.1007/978-3-319-63346-6.
[3] M. Aghdasifam, H. Izadkhah, and A. Isazadeh, “A new metaheuristic-based hierarchical clustering algorithm for software modularization,” Complex., vol. 2020, pp. 1 794 947:1–1 794 947:25, 2020, doi: 10.1155/2020/1794947.
[4] 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, 2005.
[5] H. Izadkhah and M. Tajgardan, “Information theoretic objective function for genetic software clustering,” Proceedings, vol. 46, no. 1, p. 18, 2020, doi: 10.3390/ecea-5-06681.
[6] K. Praditwong, M. Harman, and X. Yao, “Software module clustering as a multi-objective search problem,” IEEE Trans. Software Eng., vol. 37, no. 2, pp. 264–282, 2011, doi: 10.1109/TSE.2010.26.
[7] 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.
[8] 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.
[9] B. S. Mitchell, “A heuristic search approach to solving the software clustering problem,” Ph.D. dissertation, Drexel University, Philadelphia, PA, USA, 2002.
[10] N. S. Jalali, H. Izadkhah, and S. Lotfi, “Multi objective search-based software modularization: structural and non-structural features,” Soft Comput., vol. 23, no. 21, pp. 11 141–11 165, 2019, doi: 10.1007/S00500-018-3666-Z.
[11] N. Teymourian, H. Izadkhah, and A. Isazadeh, “A fast clustering algorithm for modularization of large-scale software systems,” IEEE Trans. Software Eng., vol. 48, no. 4, pp. 1451–1462, 2022, doi: 10.1109/TSE.2020.3022212.
[12] M. Kargar, A. Isazadeh, and H. Izadkhah, “Semantic-based software clustering using hill climbing,” in International Symposium on Computer Science and Software Engineering Conference (CSSE), 2017, pp. 55–60, doi: 10.1109/CSICSSE.2017.8320117.
[13] M. K. Mamaghan, M. Mohammadi, P. Meyer, A. M. Karimi-Mamaghan, and E. Talbi, “Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art,” Eur. J. Oper. Res., vol. 296, no. 2, pp. 393–422, 2022, doi: 10.1016/J.EJOR.2021.04.032.
[14] M. Chiarandini and T. Stützle, “An application of iterated local search to graph coloring problem,” in Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, Ithaca, NY, USA, 2002, pp. 112–125.
[15] M. Tajgardan, H. Izadkhah, and S. Lotfi, “A reinforcement learning-based iterated local search for software modularization,” in 8th Iranian Conference on Signal Processing and Intelligent Systems (ICSPIS), 2022, pp. 1–6, doi: 10.1109/ICSPIS56952.2022.10043949.
[16] I. Sghir, I. B. Jaâfar, and K. Ghédira, “A multiagent based optimization method for combinatorial optimization problems,” Int. J. Artif. Intell. Tools, vol. 27, no. 5, pp. 1 850 021:1–1 850 021:25, 2018, doi: 10.1142/S0218213018500215.
[17] I. Sghir, J. Hao, I. B. Jaâfar, and K. Ghédira, “A multi-agent based optimization method applied to the quadratic assignment problem,” Expert Syst. Appl., vol. 42, no. 23, pp. 9252–9262, 2015, doi: 10.1016/J.ESWA.2015.07.070.
[18] S. Asta, “Machine learning for improving heuristic optimisation,” Ph.D. dissertation, University of Nottingham, Nottingham, UK, 2015.
[19] D. Meignan, A. Koukam, and J. Créput, “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.
[20] E. Özcan, M. Misir, G. Ochoa, and E. K. Burke, “A reinforcement learning - great-deluge hyperheuristic for examination timetabling,” Int. J. Appl. Metaheuristic Comput., vol. 1, no. 1, pp. 39–59, 2010, doi: 10.4018/JAMC.2010102603.
[21] S. S. Choong, L. Wong, and C. P. Lim, “Automatic design of hyper-heuristic based on reinforcement learning,” Inf. Sci., vol. 436-437, pp. 89–107, 2018, doi: 10.1016/J.INS.2018.01.005.
[22] B. S. Ahmed, E. Enoiu, W. Afzal, and K. Z. Zamli, “An evaluation of monte carlo-based hyper-heuristic for interaction testing of industrial embedded software applications,” Soft Comput., vol. 24, no. 18, pp. 13 929–13 954, 2020, doi: 10.1007/S00500-020-04769-Z.
[23] L. Cheng, Q. Tang, L. Zhang, and C. Yu, “Scheduling flexible manufacturing cell with noidle flow-lines and job-shop via q-learning-based genetic algorithm,” Comput. Ind. Eng., vol. 169, p. 108293, 2022, doi: 10.1016/J.CIE.2022.108293.
[24] 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 Persian].
[25] 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 Conference on Software Maintenance and Reengineering (CSMR 2003), 26-28 March 2003, Benevento, Italy, Proceedings. IEEE Computer Society, 2003, pp. 301–306, doi: 10.1109/CSMR.2003.1192438.
[26] O. Maqbool and H. A. Babri, “Hierarchical clustering for software architecture recovery,” IEEE Trans. Software Eng., vol. 33, no. 11, pp. 759–780, 2007, doi: 10.1109/TSE.2007.70732.
[27] P. Andritsos and V. Tzerpos, “Informationtheoretic software clustering,” IEEE Trans. Software Eng., vol. 31, no. 2, pp. 150–165, 2005, doi: 10.1109/TSE.2005.25.
[28] 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.
[29] M. Tajgardan and H. Izadkhah, “Critical review of the bunch: A well-known tool for the recovery and maintenance of software system structures,” Int. J. Adv. Res. Comput. Commun. Eng. (IJARCCE), vol. 6, no. 3, pp. 363–367, 2017, doi: 10.17148/IJARCCE.2017.6383.
[30] M. Tajgardan, H. Izadkhah, and S. Lotfi, “Software systems clustering using estimation of distribution approach,” J. Appl. Comput. Sci. Methods, vol. 8, no. 2, pp. 99–113, 2016, doi: 10.1515/jacsm-2016-0007.
[31] A. Prajapati, A. Parashar, and A. Rathee, “Multi-dimensional information-driven manyobjective software remodularization approach,” Frontiers Comput. Sci., vol. 17, no. 3, p. 173209, 2023, doi: 10.1007/S11704-022-1449-2.
[32] B. Arasteh, A. Seyyedabbasi, J. Rasheed, and A. M. Abu-Mahfouz, “Program source-code remodularization using a discretized and modified sand cat swarm optimization algorithm,” Symmetry, vol. 15, no. 2, p. 401, 2023, doi: 10.3390/SYM15020401.
[33] V. Tzerpos and R. C. Holt, “Accd: an algorithm for comprehension-driven clustering,” in Proceedings 7th Working Conference on Reverse Engineering, 2000, pp. 258–267, doi: 10.1109/WCRE.2000.891477.
[34] A. Rasoolzadegan and M. Basiri, “The quantitative measurement of quality in service-oriented software engineering: Methods, applications, and issues,” Soft Comput. J., vol. 3, no. 1, pp. 2–19, 2014, dor: 20.1001.1.23223707.1393.3.1.54.5 [In Persian].
[35] 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].
[36] H. Izadkhah, I. Elgedawy, and A. Isazadeh, “Ecdgm: An evolutionary call-dependency graph modularization approach for software systems,” Cybern. Inf. Technol., vol. 16, no. 3, pp. 52–71, 2016, doi: 10.1515/cait-2016-0035.
[37] S. Mohammadi and H. Izadkhah, “A new algorithm for software clustering considering the knowledge of dependency between artifacts in the source code,” Inf. Softw. Technol., vol. 105, pp. 252–256, 2019, doi: 10.1016/J.INFSOF.2018.09.001.