یک ابراکتشافی مبتنی بر عامل برای پیمانه‌بندی سامانه‌های نرم‌افزاری

تاج گردان, محجوبه; ایزدخواه, حبیب; لطفی, شهریار

doi:10.22052/scj.2024.248472.1109

یک ابراکتشافی مبتنی بر عامل برای پیمانه‌بندی سامانه‌های نرم‌افزاری

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

نویسندگان

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

10.22052/scj.2024.248472.1109

چکیده

الگوریتم‌های پیمانه‌بندی برای بازیابی معماری نرم‌افزار استفاده می‌شوند. این الگوریتم‌ها کد منبع سامانه نرم‌افزاری را به پیمانه‌های کوچک‌تر و قابل فهم‌تر تقسیم می‌کنند. از آنجایی که پیمانه‌بندی نرم‌افزار یک مساله چندجمله‌ای غیرقطعی‌سخت است، به طور معمول از روش‌های مبتنی بر جستجو برای حل آن استفاده می‌شود. در سال‌های اخیر، استفاده از ابراکتشافی‌ها با رویکردهای جستجوی هوشمند، برای دستیابی به سطح بالاتری از عمومیت رو به افزایش است. در این مقاله، یک ابراکتشافی عمومی مبتنی بر عامل، با استفاده از مفهوم سامانه‌های چندعاملی، برای پیمانه‌بندی نرم‌افزار ارائه می‌شود. در الگوریتم پیشنهادی، از عامل‌هایی با دیدگاه‌های جستجوی تقویتی و تنوعی استفاده می‌شود و عامل‌های دارای دیدگاه یکسان در یک اجتماع قرار می‌گیرند. در هر گام از جستجو، مناسب‌ترین اجتماع با استفاده از یادگیری تقویتی به طور خودکار انتخاب و عامل‌های آن به صورت موازی اجرا می‌شوند. همچنین، در طراحی برخی از عامل‌ها، برای حفظ تنوع، از مفهوم نظریه آشوب استفاده می‌شود. برای نشان‌ دادن قابلیت اجرای الگوریتم پیشنهادی یازده سامانه نرم‌افزاری دنیای واقعی با اندازه کوچک و متوسط و ده پوشه از موزیلا فایرفاکس با دامنه‌ها و قابلیت‌های متفاوت انتخاب شده‌اند. نتایج آزمایش‌ها نشان می‌دهند که ابراکتشافی پیشنهادی در بیشتر موارد پیمانه‌بندی‌هایی با کیفیت بالاتر را در زمان کمتری نسبت به الگوریتم‌های مقایسه شده تولید می‌کند. میانگین بهبود عددی الگوریتم پیشنهادی از نظر کیفیت پیمانه‌بندی و زمان اجرا روی ده پوشه از موزیلا فایرفاکس به ترتیب 77.607 و 59.448 درصد می‌باشد.

کلیدواژه‌ها

موضوعات

معماری نرم افزار

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

An Agent-based Hyper-heuristic for Software Systems Modularization

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

Mahjoubeh Tajgardan
Habib Izadkhah
Shahriar Lotfi

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

چکیده [English]

Modularization methods are utilized to divide program artifacts into comprehensible modules to extract software architecture. Software modularization problem is NP-hard, so search-based techniques are commonly used to address 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 hyper-heuristic based on the multi-agent systems is proposed 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 indicate the applicability of the suggested algorithm, we selected eleven real-world applications of small and medium sizes, along with ten folders of Mozilla Firefox that have various functionalities and sizes. The findings of the experiments demonstrate that the suggested 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.

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

Software modularization
Architecture recovery
Hyper - heuristic
Multi-agent systems
Reinforcement learning

مراجع

[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.