• صفحه اصلی
  • بهبود فرایند تولید خودکار داده آزمون نرم‌افزار مبتنی بر معیار پوشش مسیر و با استفاده از ترکیب الگوریتم بهینه سازی کواتی و الگوریتم یادگیری Q

اشتراک گذاری

آدرس مقاله


کد مقاله : 1403020346471 بازدید : 129 صفحه: 99 - 110

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

بهبود فرایند تولید خودکار داده آزمون نرم‌افزار مبتنی بر معیار پوشش مسیر و با استفاده از ترکیب الگوریتم بهینه سازی کواتی و الگوریتم یادگیری Q

محورهای موضوعی : مهندسی برق و کامپیوتر

مرضیه سپهوند 1 , مجتبی صالحی 2 *

1 - گروه کامپیوتر، واحد خرم‌آباد، دانشگاه آزاد اسلامی، خرم‌آباد، ايران
2 - گروه کامپیوتر، واحد خرم‌آباد، دانشگاه آزاد اسلامی، خرم‌آباد، ايران

تاریخ دریافت : 1403/02/03 تاریخ پذیرش : 1403/07/21 تاریخ انتشار : 1404/07/26

کلید واژه: آزمون نرم‌افزار, تولید داده آزمون, آزمون ساختاری, الگوریتم‌های فرامکاشفه‌ای, الگوریتم یادگیری‌ Q.,

چکیده مقاله :

آزمون نرم‌افزار یکی از مهم‌ترین روش‌های تحلیل میزان اطمینان کیفیت نرم‌افزار است. این فرایند بسیار زمان‌بر و پرهزینه است و تقریباً نیمی از هزینه تولید نرم‌افزار را به خود اختصاص داده است. از این رو به دنبال استفاده از روش‌های خودکار به منظور کاستن هزینه و زمان آزمون هستیم. مسأله عمده در فرایند تولید داده آزمون، تعیین داده‌های ورودی برنامه، به گونه‌ای است که معیار آزمون مشخص‌شده را برآورده سازد. در این تحقیق از روش ساختاری به منظور فرایند خودکارسازی تولید داده آزمون با تمرکز بر معیار پوشش همه مسیرهای متناهی استفاده شده است. در روش ساختاری، مسأله به یک مسأله جستجو تبدیل شده و از الگوریتم‌های فرامکاشفه‌ای برای حل آن استفاده می‌شود. روش پیشنهادی یک الگوریتم ترکیبی است که در آن الگوریتم یادگیری q به‌عنوان یک روش جستجوی محلی در درون ساختار الگوریتم جستجوی کواتی مورد استفاده قرار می‏گیرد. به طور متوسط، الگوریتم پیشنهادی ما در مقایسه با سایر الگوریتم‌ها حدود 25 تا 30 درصد بهبود را در پوشش نشان می‌دهد که آن را به طور قابل توجهی نسبت به دیگر الگوریتم ها مؤثرتر می‌کند. نتایج آزمایش‌ها نشان می‌دهد که الگوریتم پیشنهادی به‌دلیل رویکرد بهینه در جست‌وجوی مسیرهای آزمون، در مقایسه با سایر الگوریتم‌ها، پوشش مسیر بالاتری حاصل کرده است.

چکیده انگلیسی:

The software testing process is very time-consuming and expensive and accounts for almost half of the cost of software production. The main issue in the test data generation process is determining the program's input data in such a way that it meets the specified test criteria. In this research, the structural method has been used to automate the process of generating test data, focusing on the criterion of covering all finite paths. In the structural method, the problem becomes a search problem, and metaheuristic algorithms can be used to solve it. The proposed method is a hybrid algorithm in which the q-learning algorithm is used as a local search method within the structure of the Coati search algorithm. The results of the tests have shown that this method for generating test data is faster than many metaheuristic algorithms and can provide better coverage with fewer evaluations. On average, our proposed algorithm shows about 25-30% improvement in coverage compared to other algorithms, which makes it significantly more effective than other algorithms. This shows that our algorithm achieves superiority over other compared algorithms due to its more efficient and optimal path coverage approach.

منابع و مأخذ:

[1] P. Ammann and J. Offutt, Introduction to Software Testing, Cambridge University Press, 2016.
[2] F. Lonetti and E. Marchetti, "Emerging software testing technologies," Advances in Computers, Elsevier, vol. 108, pp. 91-143, 2018.
[3] S. Parsa, "Automatic test data generation symbolic and concolic executions," In S. Parsa (ed.), Software Testing Automation: Testability Evaluation, Refactoring, Test Data Generation and Fault Localization, pp. 503-542, Springer, 2023.
[4] G. Zhang, et al.,"FDSE: enhance symbolic execution by fuzzing-based pre-analysis (competition contribution)," in Proc. 27th Int. Conf. on Fundamental Approaches to Software Engineering, pp. 304-308, Luxembourg City, Luxembourg, 6-11 Apr. 2024.

[5] O. Sahin and B. Akay, "Comparisons of metaheuristic algorithms and fitness functions on software test data generation," Applied Soft Computing, vol. 49, pp. 1202-1214, Dec. 2016. [6] M. Harman and P. McMinn, "A theoretical and empirical study of search-based testing: local, global, and hybrid search," IEEE Trans. on Software Engineering, vol. 36, no. 2, pp. 226-247, Mar./Apr. 2009.
[7] M. Dehghani, Z. Montazeri, E. Trojovská, and P. Trojovský, "Coati optimization algorithm: a new bio-inspired metaheuristic algorithm for solving optimization problems," Knowledge-Based Systems, vol. 259, Article ID: pp. 110011, Jan. 2023.
[8] N. Soffair and S. Mannor, \Textit {MinMaxMin} $Q$-Learning, arXiv preprint arXiv:2402.05951, 2024.
[9] N. Khoshniat, A. Jamarani, A. Ahmadzadeh, M. Haghi Kashani, and E. Mahdipour, "Nature-inspired metaheuristic methods in software testing," Soft Computing, vol. 28, no. 2, pp. 1503-1544, 2024.
[10] P. Ashwini, B. Rajani, and B. Vijitha, "An efficient early software reliability prediction using particle swarm optimization (PSO)," In K. Venkata Murali Mohan, M. Suresh Babu (eds). Disruptive Technologies in Computing and Communication Systems, pp. 52-58, CRC Press, 2024.
[11] T. Avdeenko and K. Serdyukov, "Automated test data generation based on a genetic algorithm with maximum code coverage and population diversity," Applied Sciences, vol. 11, no. 10, Article ID: 4673, May-2 2021.
[12] M. Nosrati, H. Haghighi, and M. V. Asl, "Test data generation using genetic programming," Information and Software Technology, vol. 130, Article ID: 106446, 2021.
[13] M. Angelova, K. Atanassov, and T. Pencheva, "Multi-population genetic algorithm quality assessment implementing intuitionistic fuzzy logic," in Proc. Federated Conf. on Computer Science and Information Systems, pp. 365-370, Wroclaw, Poland, 9-12 Sept. 2012.
[14] M. Alshraideh, B. A. Mahafzah, and S. Al-Sharaeh, "A multiple-population genetic algorithm for branch coverage test data generation," Software Quality J., vol. 19, pp. 489-513, 2011.
[15] N. Zhang, B. Wu, and X. Bao, "Automatic generation of test cases based on multi-population genetic algorithm," Int. J. Multimedia Ubiquitous Eng., vol. 10, no. 6, pp. 113-122, 2015.
[16] X. Bao, Z. Xiong, N. Zhang, J. Qian, B. Wu, and W. Zhang, "Path-oriented test cases generation based adaptive genetic algorithm," PloS One, vol. 12, no. 11, Article ID: e0187471, 2017.
[17] A. Damia, M. Esnaashari, and M. Parvizimosaed, "Software testing using an adaptive genetic algorithm," J. of AI and Data Mining, vol. 9, no. 4, pp. 465-474, Oct. 2021.
[18] M. Mann, P. Tomar, and O. P. Sangwan, "Test data generation using optimization algorithm: an empirical evaluation," in Proc. of Soft Computing: Theories and Applications, vol. 2, pp. 679-686, Jaipur, India, 28-30 Dec. 2018.
[19] M. Mann, O. P. Sangwan, P. Tomar, and S. Singh, "Automatic goal-oriented test data generation using a genetic algorithm and simulated annealing," in Proc. 6th Int. Conf.-Cloud System and Big Data Engineering, pp. 83-87, Noida, India, 14-15 Jan. 2016.
[20] X. M. Zhu and X. F. Yang, "Software test data generation automatically based on improved adaptive particle swarm optimizer," in Proc. Int. Conf. on Computational and Information Sciences, pp. 1300-1303, Chengdu, China, 17-19 Dec. 2010.
[21] S. Singla, D. Kumar, H. Rai, and P. Singla, "A hybrid PSO approach to automate test data generation for data flow coverage with dominance concepts," International J. of Advanced Science and Technology, vol. 37, no. 11, pp. 15-26, 2011.
[22] S. Jiang, J. Shi, Y. Zhang, and H. Han, "Automatic test data generation based on reduced adaptive particle swarm optimization algorithm," Neurocomputing, vol. 158, pp. 109-116, Jun. 2015.
[23] H. Sharifipour, M. Shakeri, and H. Haghighi, "Structural test data generation using a memetic ant colony optimization based on evolution strategies," Swarm and Evolutionary Computation, vol. 40, no. 40, pp. 76-91, Jun. 2018.
[24] A. H. Damia and M. M. Esnaashari, "Automated test data generation using a combination of firefly algorithm and asexual reproduction optimization algorithm," International J. of Web Research, vol. 3, no. 1, pp. 19-28, Jun. 2020.
[25] A. Damia, M. Esnaashari, and M. Parvizimosaed, "Automatic web-based software structural testing using an adaptive particle swarm optimization algorithm for test data generation," in Proc. 7th Int. Conf. on Web Research, pp. 282-286, Tehran, Iran, 19-20 May 2021.
[26] O. Al-Masri and W. A. Al-Sorori, "Object-oriented test case generation using teaching learning-based optimization (TLBO) algorithm," IEEE Access, vol. 10, pp. 110879-110888, 2022.
[27] M. Saadtjoo and S. Babamir, "Optimizing cost function in imperialist competitive algorithm for path coverage problem in software testing," J. of AI and Data Mining, vol. 6, no. 2, pp. 375-385, Jul. 2018.
[28] X. Dai, W. Gong, and Q. Gu, "Automated test case generation based on differential evolution with node branch archive," Computers & Industrial Engineering, vol. 156, Article ID: 107290, Jun. 2021.
[29] R. R. Sahoo and M. Ray, "Forest optimization-based test case generation for multiple paths with metamorphic relations," International J. of Applied Metaheuristic Computing, vol. 13, no. 1, pp. 1-18, Jan. 2022.
[30] F. Feyzi and S. Parsa, "Bayes‐TDG: effective test data generation using Bayesian belief network: toward failure‐detection effectiveness and maximum coverage," IET Software, vol. 12, no. 3, pp. 225-235, Jun. 2018.
[31] M. Esnaashari and A. H. Damia, "Automation of software test data generation using genetic algorithm and reinforcement learning," Expert Systems with Applications, vol. 183, Article ID: 115446, Nov. 2021.
[32] M. Malkauthekar, "Analysis of euclidean distance and manhattan distance measure in face recognition," in 3rd Int. Conf. on Computational Intelligence and Information Technology, pp. 503-507, Chennai, India, 27 Jul. 2013.
[33] Y. Duan, et al., "CAPSO: chaos adaptive particle swarm optimization algorithm," IEEE Access, vol. 10, pp. 29393-29405, 2022.
[34] P. Trojovský and M. Dehghani, "Pelican optimization algorithm: a novel nature-inspired algorithm for engineering applications," Sensors, vol. 22, no. 3, Article ID: 855, 2022.
[35] S. H. S. Moosavi and V. K. Bardsiri, "Poor and rich optimization algorithm: a new human-based and multi populations algorithm," Engineering Applications of Artificial Intelligence, vol. 86, pp. 165-181, Nov. 2019.
[36] S. Zhao, T. Zhang, S. Ma, and M. Chen, "Dandelion optimizer: a nature-inspired metaheuristic algorithm for engineering applications," Engineering Applications of Artificial Intelligence, vol. 114, Article ID: 105075, Sept. 2022.
[37] I. Fister, I. Fister Jr, X. S. Yang, and J. Brest, "A comprehensive review of firefly algorithms," Swarm and Evolutionary Computation, vol. 13, pp. 34-46, Dec. 2013.
متن کامل:
معرفي يک روش جديد خوشه‌يابي خودکار

نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 23، شماره 2، تابستان 1404                                                                                           99

مقاله پژوهشی

بهبود فرایند تولید خودکار داده آزمون نرم‌افزار مبتنی بر 
معیار پوشش مسیر و با استفاده از ترکیب الگوریتم 
بهینه‌سازی کواتی و الگوریتم یادگیری Q

مرضیه سپهوند و مجتبی صالحی

 

1 

چکیده: آزمون نرم‌افزار یکی از مهم‌ترین روش‌های تحلیل میزان اطمینان کیفیت نرم‌افزار است. این فرایند بسیار زمان‌بر و پرهزینه است و تقریباً نیمی از هزینه تولید نرم‌افزار را به خود اختصاص داده است. از این رو به دنبال استفاده از روش‌های خودکار به منظور کاستن هزینه و زمان آزمون هستیم. مسأله عمده در فرایند تولید داده آزمون، تعیین داده‌های ورودی برنامه، به گونه‌ای است که معیار آزمون مشخص‌شده را برآورده سازد. در این تحقیق از روش ساختاری به منظور فرایند خودکارسازی تولید داده آزمون با تمرکز بر معیار پوشش همه مسیرهای متناهی استفاده شده است. در روش ساختاری، مسأله به یک مسأله جستجو تبدیل شده و از الگوریتم‌های فرامکاشفه‌ای برای حل آن استفاده می‌شود. روش پیشنهادی یک الگوریتم ترکیبی است که در آن الگوریتم یادگیری Q به‌عنوان یک روش جستجوی محلی در درون ساختار الگوریتم جستجوی کواتی مورد استفاده قرار می‏گیرد. به طور متوسط، الگوریتم پیشنهادی ما در مقایسه با سایر الگوریتم‌ها حدود 25 تا 30 درصد بهبود را در پوشش نشان می‌دهد که آن را به طور قابل توجهی نسبت به دیگر الگوریتم ها مؤثرتر می‌کند. نتایج آزمایش‌ها نشان می‌دهد که الگوریتم پیشنهادی به‌دلیل رویکرد بهینه در جست‌وجوی مسیرهای آزمون، در مقایسه با سایر الگوریتم‌ها، پوشش مسیر بالاتری حاصل کرده است.

 

کلیدواژه: آزمون نرم‌افزار، تولید داده آزمون، آزمون ساختاری، الگوریتم‌های فرامکاشفه‌ای، الگوریتم یادگیری‌ Q.

1-       مقدمه

مسأله عمده در فرایند تولید داده آزمون نرم‌افزار، تعیین داده‌های ورودی برای پارامترهای برنامه تحت آزمون است. هدف در این مسأله، تولید داده آزمون است به گونه‌ای که معیار آزمون مشخص‌شده را برآورده کند [1]. این معیارها بر اساس ساختار برنامه تعریف می‌شوند. به عنوان مثال معیار پوشش شاخه از معیارهایی است که هدف در آن، پوشش تمامی شاخه‌های برنامه است. یکی دیگر از این معیارها، پوشش عبارت است که هدف آن اجرای تمامی عبارت‌های برنامه است. از دیگر معیارها، پوشش همه مسیرهای متناهی2 است که هدف، پوشش تمامی مسیرهای متناهی موجود در برنامه تحت آزمون است [2]. برای تحقق این معیارها نیاز به گراف جریان برنامه داریم که برای ایجاد این گراف می‌توان به‌صورت دستی و یا از روش‌های خودکار ایجاد گراف جریان استفاده کرد. بعد از ایجاد این گراف می‌توان این مسیرها را از گراف استخراج کرد. روش‌های آزمون نرم‌افزار به دو دسته عملیاتی و ساختاری تقسیم می‌شوند. روش عملیاتی از ویژگی‌های برنامه برای تولید داده آزمون به‌منظور آزمون رفتار منطقی سیستم‌ها بهره می‌گیرد. در روش ساختاری عملیات مورد نظر بر اساس ساختار داخلی برنامه در حال آزمون انجام می‌گیرد. بعد از انتخاب معیار کیفیت می‌توان به تعیین میزان پوشش برنامه توسط داده‌های تولیدشده پرداخت. به طور کلی روش‌های خودکار آزمون ساختاری به دو دسته پویا و ایستا تقسیم می‌شوند. در روش ایستا به‌منظور تولید خودکار داده‌های آزمون، نمی‌توان به‌صورت مستقیم از کد منبع برنامه استفاده کرد و باید آن را به شکلی تبدیل نمود که استاندارد است و حاوی اطلاعات خاصی جهت تولید هر چه مؤثرتر داده‌های آزمون باشد که معمولاً بر پایه اجرای نمادین برنامه بنا شده‌اند [3]. بنابراین به‌منظور آماده‌سازی، کد منبع برنامه باید مراحلی را طی کرده و به شکل خاصی تبدیل شود. همچنین در روش‌های مبتنی بر ساختار، به‌دلیل پیچیدگی در تحلیل و ردیابی آرایه‌ها و اشاره‌گرها، مشکلاتی در استخراج دقیق مسیرهای اجرایی برنامه وجود دارد [4]. در روش پویا مشکلات مربوط به روش ایستا حل شده و مسأله تولید داده آزمون به مسأله بهینه‌سازی تبدیل می‌گردد. در بسیاری از روش‌های پویای پیشین از الگوریتم‌های فرامکاشفه‌ای بدین منظور استفاده شده است [5] و [6]. الگوریتم بهینه‌سازی کواتی یک الگوریتم جدید، سریع و همچنین دارای قابلیت اکتشاف و قابلیت استفاده خوب است که به منظور تولید خودکار داده آزمون در این مقاله مورد استفاده قرار گرفته شده است [7]. یكی از عیب‌های عمده الگوریتم‌های فرامکاشفه‌ای این است که هر راه‌حل به تنهایی یك بردار img0بعدی را نمایش می‌دهد که معرف یك پاسخ یا راه‌حل برای مسأله است. گاهی امكان دارد که قسمت‌هایی از این بردار به پاسخ‌های صحیح نزدیك شده باشند؛ در حالی که قسمت‌های دیگر بردار از پاسخ صحیح دور باشند. بنابراین در کل این راه‌حل مناسب به نظر نمی‌رسد و باید به موقعیت بهتری برود. امكان دارد که آن قسمت‌هایی از بردار راه‌حل که به جواب نزدیك بوده‌اند طی آپدیت راه‌حل جدید، از پاسخ جدید فاصله بگیرند؛ بنابراین اطلاعات مفید راه‌حل از بین می‌رود. لذا برای رفع این مشکل از الگوریتم یادگیری Q به‌عنوان الگوریتم جستجوی محلی در داخل الگوریتم بهینه‌سازی کواتی استفاده شده است [8]. در این مقاله از این ایده به این صورت استفاده شده که به جزئیات داخل راه‌حل‌ها توجه می‌کند. در الگوریتم بهینه‌سازی کوآتی، تمرکز بر بهترین راه‌حل‌های به‌دست‌آمده است و از طریق اعمال تغییرات جزئی و جابه‌جایی‌های هدفمند در اجزای راه‌حل، کیفیت آن‌ها بهبود داده می‌شود. دستکاری و جابه‌جایی جزئیات داخلی راه‌حل‌ها در روش پیشنهادی از طریق الگوریتم یادگیری Q انجام می‌شود. در واقع، یک عامل یادگیر مسئول بهبود راه‏حل می‏شود. این عامل اقدام‏هایی دارد که از طریق آنها می‏تواند تغییرات کوچک و محلی روی راه‌حل‌ها ایجاد نماید. در یک چرخه یادگیری، آن قدر سعی و خطا انجام می‏گردد تا نهایتاً راه‌حل مزبور بهبود یابد و یا اینکه تعداد تکرار مشخصی از چرخه یادگیری انجام پذیرد. پس از آن، راه‌حل بهبودیافته به چرخه الگوریتم بهینه‌سازی کواتی بازگردانده می‏شود. جهت ارزیابی کارایی روش پیشنهادی، این روش برای تولید خودکار داده آزمون روی تعدادی برنامه مختلف مورد استفاده قرار گرفته و نتایج حاصل از آن با نتایج چندین الگوریتم فراابتکاری معروف مورد مقایسه قرار گرفته شده است، نتایج نشان از برتری مشهود روش پیشنهادی دارند.

2-       کارهای انجام‌گرفته

در روش آزمون پویا برنامه تحت آزمون باید اجرا شود؛ به همین خاطر باید ورودی‌هایی برای برنامه تحت آزمون تولید کنیم. در این روش با استفاده از الگوریتم‌های جستجو می‌توان این ورودی‌ها را تولید کرد. تاکنون الگوریتم‌های مختلفی برای این کار به کار گرفته شده که در این بخش مهم‌ترین این کارها بررسی شده است [9].

آشوینی و همکاران با استفاده از الگوریتم بهینه‌سازی ذرات و ارتباط بین زمان اجرا و تعداد خطاها تولید داده آزمون و پیش‌بینی خطا را انجام داده‌اند [10]. آودنیکو و سردیکو [11] از دو نسخه الگوریتم ژنتیک با معیار پوشش جملات استفاده کرده‌اند. نصرتی و همکاران از برنامه‌نویسی ژنتیک نیز به‌عنوان یک الگوریتم مکاشفه‌ای برای جستجوی داده‌های آزمون استفاده کردند [12]. به‌منظور بهبود بیشتر توانایی جستجوی سراسری در الگوریتم ژنتیک، روش‌های بهبودیافته مختلفی معرفی شده است. الگوریتم ژنتیک چندجمعیتی در سال‌های اخیر به‌عنوان نوعی الگوریتم ژنتیک بهبودیافته معرفی شده که عملکرد خوبی از خود نشان داده است [13] و [14]. مدل چندجمعیتی می‌تواند از گیرافتادن الگوریتم در مینیمم‌های محلی و همگرایی زودرس جلوگیری کند. از طرف دیگر، مدل چندجمعیتی می‌تواند کیفیت راه‌حل‌ها و سرعت تکامل الگوریتم ژنتیک را بهبود بخشد. در [15] از الگوریتم ژنتیک چندجمعیتی برای به دست آوردن راه‌حل بهینه استفاده شده است. در این روش از دو جمعیت فرزند و یک جمعیت اصلی استفاده شده و جمعیت‌های فرزند به‌صورت موازی اجرا می‌شوند. همچنین در این روش از یک تابع برازندگی جدید استفاده شده است. آزمایش‌ها نشان داده‌اند که این روش در سرعت همگرایی، زمان جستجو و درصد پوشش باعث بهبود شده و کارایی آن نسبت به الگوریتم ژنتیک تک‌جمعیتی و جستجوی تصادفی بهتر است.
دو روش مختلف برای تنظیم مقادیر پارامترهای (نرخ بازترکیبی و نرخ جهش) الگوریتم ژنتیک وجود دارد: تنظیم مقادیر پارامترها قبل از فرایند بهینه‌سازی یا تنظیم دینامیکی پارامترها در حین اجرا. در [16] و [17] از الگوریتم ژنتیک بهبود داده شده به‌وسیله نگهداری تنوع جمعیت برای تولید داده آزمون استفاده شده که به‌صورت پویا در حین اجرا نرخ عملگر بازترکیبی و عملگر جهش را با شباهت بین کروموزوم‌ها و مقدار برازندگی کروموزوم‌ها در هر مرحله از الگوریتم به دست می‌آورد. ماکش و پرادیپ تامار در سال 2018 روشی مبتنی بر الگوریتم ژنتیک برای تولید خودکار داده آزمون نرم‌افزار معرفی کردند و نتایج آنها با روش تصادفی مورد مقایسه قرار گرفت. در این مقاله تأثیر جمعیت اولیه در کارایی الگوریتم ژنتیک مورد بررسی قرار گرفت. نتایج آنها نشان داد که روش پیشنهادی آنها نسبت به روش تصادفی مؤثرتر است و به زمان کمتری برای تولید داده آزمون نرم‌افزار نیاز دارد و همچنین با افزایش اندازه اولیه جمعیت، می‌توان فضای جستجوی بیشتری را با افزایش تنوع ایجاد کرد که باعث می‌شود با احتمال کمتری الگوریتم در بهینه‌های محلی قرار گیرد [18]. در [19] از الگوریتم ژنتیک و الگوریتم تبرید شبیه‌سازی‌شده برای خودکارسازی تولید داده آزمون مبتنی بر معیار پوشش مسیر استفاده شده و نتایج آنها با هم مقایسه گردیده است. نتایج آنها نشان داده که الگوریتم ژنتیک با تنظیم درست پارامترها، مؤثرتر از الگوریتم تبرید شبیه‌سازی شده است و در تعداد تکرار کمتری به جواب رسیده و حداکثر پوشش را به دست آورده است. ژیو و همکاران از الگوریتم بهینه‌سازی ازدحام ذرات تطبیقی برای تولید خودکار داده آزمون استفاده کردند. آنها وزن ایستایی را بر اساس مقدار برازندگی هر ذره محاسبه کردند. نتایج آزمایش آنها نشان داد که کارایی روش پیشنهادی آنها از الگوریتم ژنتیک معمولی و الگوریتم ازدحام ذرات معمولی بهتر است [20]. سانجی سینگلا و همکاران با استفاده از ترکیبی از الگوریتم ژنتیک و بهینه‌سازی ازدحام ذرات، رویکردی برای تولید خودکار داده‌های آزمون ارائه دادند. عملکرد روش پیشنهادی در مقایسه با الگوریتم ژنتیک معمولی و الگوریتم بهینه‌سازی ازدحام ذرات برای تولید خودکار داده آزمون حاکی از برتری روش پیشنهادی آنها داشت [21]. جیانگ و همکاران با استفاده از الگوریتم بهینه‌سازی ازدحام ذرات، رویکردی برای تولید داده آزمون ارائه دادند. آنها یک تنظیم انطباقی را بر اساس وزن ایستایی پیشنهاد دادند که قابلیت جستجو بین جستجوی سراسری و جستجوی محلی را متعادل می‌کند. نتایج روش‌های آنها با دیگر نسخه‌های بهبود داده شده الگوریتم ازدحام ذرات مقایسه شد. نتایج آزمایش بهبود سرعت همگرایی و اثربخشی روش پیشنهادی آنها را نشان داد [22]. شریف­پور و همکاران در سال 2018 یک روش با استفاده از الگوریتم کلونی مورچه‌ها به روش تقلیدی برای تولید خودکار داده آزمون ارائه دادند. نتایج تجربی برتری الگوریتم پیشنهادی آنها نسبت به تکنیک‌های تولید داده آزمون موجود از نظر پوشش شاخه و سرعت همگرایی در مقایسه با الگوریتم تکاملی ژنتیک و الگوریتم تکامل ازدحام ذرات را نشان می‌دهد [23]. دمیا و همکاران در سال 2020 روش جدیدی برای تولید داده آزمون استفاده کردند. آنها از الگوریتم تولید مثل غیرجنسی برای تنظیم تنوع جمعیت و کمک به جستجوی محلی در الگوریتم کرم شبتاب استفاده کردند. نتایج آنها نشان داد که این روش ترکیبی از هر کدام از الگوریتم‌ها به‌صورت جداگانه بهتر است [24]. در [25] از الگوریتم بهینه‌سازی ازدحام ذرات به‌منظور تولید خودکار داده آزمون نرم‌افزار استفاده شده است. در این روش وزن اینرسی به‌صورت دینامیکی در هر دور از الگوریتم با توجه به برازندگی هر ذره محاسبه می‌شود. آزمایش‌ها بر روی برنامه‌های مختلف انجام شده و نتایج آزمایش‌ها نشان می‌دهد که روش پیشنهادی آنها نسبت به چندین روش انجام‌شده توسط انواع دیگر PSO، نرخ هم‌گرایی بهتری دارد. در [26] از یک الگوریتم بهینه‌سازی مبتنی بر یادگیری- آموزش برای برای تولید خودکار داده آزمون استفاده شده است. آنها نتایج خود را با سایر روش‌های پیشرفته بر اساس پوشش مسیر برای ده برنامه جاوا مقایسه کرده‌اند. نتایج به‌دست‌آمده حاکی از برتری روش پیشنهادی آنها دارد. سعادت‌جو، بابامیر و همکاران در سال 2018 از الگوریتم رقابت استعماری به‌منظور تولید خودکار داده آزمون استفاده کردند. روش آنها با الگوریتم ژنتیک و الگوریتم بهینه‌سازی ازدحام ذرات برای سه برنامه نرم‌افزاری با اندازه‌های فضای جستجوی مختلف پیاده‌سازی مورد مقایسه قرار گرفت. روش پیشنهادی نتایج بهتری نسبت به سایر الگوریتم‌ها در یافتن تعداد مسیرهای غیرتکراری، سرعت همگرایی و زمان محاسباتی با افزایش فضای جستجوی به دست آورد [27]. در [28] یک روش تولید خودکار داده آزمون نرم افزار مبتنی بر الگوریتم تکامل تفاضلی معرفی شده است. نتایج تجربی نشان می‌دهد که در مقایسه با سایر الگوریتم‌های پیشرفته، تکامل تفاضلی با معیار پوشش شاخه می‌تواند به طور قابل توجهی سرعت همگرایی را بهبود بخشد. ساهو و همکاران [29] در پژوهش خود، با بهره‌گیری از الگوریتم بهینه‌سازی جنگل، رویکردی نوین برای تولید داده‌های آزمون ارائه کردند که قادر است در یک اجرای واحد، چندین مسیر از برنامه تحت آزمون را به‌طور هم‌زمان پوشش دهد. این الگوریتم در متلب پیاده‌سازی شده و عملکرد آن با استفاده از شش برنامه ارزیابی شد و نتایج نشان می‌دهند که نتایج خوبی کسب کرده است. بنابراین با توجه به بررسی کارهای انجام‌شده می‌توان گفت که الگوریتم‌های فرامکاشفه‌ای گاهی در بهبود جزئیات راه‌حل‌ها ناکارآمد هستند؛ به طوری که بخش‌هایی از راه‌حل به جواب صحیح نزدیک و بخش‌های دیگر دور می‌شوند. برای رفع این مشکل، از الگوریتم یادگیری q به‌عنوان جستجوی محلی در کنار الگوریتم بهینه‌سازی کوآنتی استفاده شده است. این الگوریتم با تمرکز بر بهترین راه‌حل فعلی و ایجاد تغییرات جزئی در آن، به بهبود راه‌حل کمک می‌کند. نتایج نشان می‌دهند که روش پیشنهادی در مقایسه با سایر الگوریتم‌های فرامکاشفه‌ای عملکرد بهتری دارد.

3-       روش پیشنهادی

3-1 مقدمه

مسأله مورد نظر در این مقاله، شناسایی خودکار ورودی‌هایی است که تمامی مسیرهای متناهی موجود در برنامه تحت آزمون را مورد آزمون قرار دهند و هدف، کمینه‌کردن میزان محاسبات لازم برای شناسایی این ورودی‌هاست؛ چرا که با بزرگ‌شدن برنامه و افزایش تعداد توابع در آن، زمان زیادی برای تولید این موارد آزمون نیاز خواهد بود و هرچه راهکار خودکار سریع‌تر و با محاسبات کمتری بتواند تمامی مسیرها را پوشش دهد، بهتر خواهد بود. روش پیشنهادی یک الگوریتم فراابتکاری جدید به نام الگوریتم بهینه‌سازی کواتی (COA) است که در آن یادگیری q به‌عنوان یک روش جستجوی محلی در درون ساختار این الگوریتم مورد استفاده قرار می‏گیرد. تا جایی که نگارنده جستجو کرده است، این رویکرد ترکیبی تاکنون در خصوص خودکارسازی تولید داده آزمون نرم‌افزار استفاده نشده است. ایده اساسی COA شبیه‌سازی دو رفتار طبیعی کواتی‌ها است: 1) رفتار آنها هنگام حمله و شکار ایگوانا و 2) فرار آنها از دست شکارچیان. در این الگوریتم هر عضو جمعیت به‌عنوان یک کواتی شناخته می‌شود. (همان طور که در الگوریتم ژنتیک هر عضو جمعیت یک کروموزوم است.)

به طور کلی روش انجام کار به این صورت است که ابتدا مسأله مورد نظر فرموله‌سازی می‌شود و سپس گراف جریان برنامه ایجاد می‌شود و مسیرهای این گراف تولید می‌شود. (هدف پوشش تمامی مسیرهای متناهی موجود در متد تحت آزمون است.) بعد از ایجاد جمعیت اولیه به‌صورت تصادفی، مقدار برازندگی هر کواتی محاسبه می‌شود و در نتیجه وارد فاز تکرار می‌شوند. در این قسمت اگر برازندگی بهترین کواتی از یک حد از پیش تعیین‌شده بهتر بود، وارد مرحله جستجوی محلی (عملیات بهبود) می‌شویم. در این مرحله ابتدا یک سری پیش‌پردازش روی مسیرها برای به دست آوردن شبیه‌ترین زیربخش به زیربخش مربوط به مسیر پوشش داده نشده، انجام می‌شود و با به‌کارگیری فرآیند یادگیری تقویتی، مجموعه‌ای از حالت‌ها و اعمال تعریف می‌شود تا عامل یادگیرنده بتواند با استفاده از پاداش‌های دریافتی، زیر‌بخش مربوط به بهبود راه‌حل‌ها را بهینه‌سازی کند. بعد از این مرحله، دو فاز اصلی الگوریتم کواتی انجام می‌شود. در این الگوریتم فاز اول استراتژی شکار و حمله به ایگوانا (مرحله اکتشاف) و فاز دوم فرایند فرار از دست شکارچیان (مرحله بهره‌برداری) است. این چرخه تکرار می‌شود تا الگوریتم به جواب پایانی همگرا شود. شرط توقف در الگوریتم‌ها، رسیدن به یک تعداد مشخص ارزیابی است.

3-2 فرموله‌سازی مسأله

در روش آزمون مسیر سعی می‌گردد تا تمامی مسیرهای کنترلی متد تحت آزمون حداقل یک بار اجرا شوند تا بدین صورت، تمامی دستورهای برنامه اجرا شده باشند. برای انجام این آزمون، ساختار جریان کنترلی متد تحت آزمون به‌صورت گراف جریان در نظر گرفته می‌شود. این گراف جریان کنترلی، منطق درون برنامه را نشان می‌دهد و ساختار برنامه را می‌توان به‌صورت چنین گرافی بیان کرد. در این روش برای استخراج حالات آزمون، با استفاده از طراحی و یا کد منبع گراف، جریان متناظر آن رسم می‌گردد. میزان پیچیدگی منطق درون متد برای گراف جریان تعیین می‌شود و برای هر کدام از مسیرهای مستقل، یک حالت آزمون آماده می‌گردد تا تضمین کند که آن حالت، حتماً اجرا می‌شود. آزمون مبتنی بر پوشش مسیر، جامع‌ترین نوع آزمون ساختاری محسوب می‌شود، زیرا با بررسی تمامی مسیرهای اجرایی برنامه، قادر است خطاهای بیشتری را نسبت به سایر روش‌های پوشش شناسایی کند. تا به امروز، تحقیقات موجود در مورد تولید داده‌های آزمایشی برای پوشش مسیر یا بر اساس رویکردهای تکاملی بوده است یا اجرای نمادین [30]. آزمایش مسیرهای متناهی با در نظر گرفتن کل توالی از عبارات فراتر می‌رود؛ در حالی که دیگر معیارها این گونه نیست. به عنوان مثال در معیار آزمون پوشش شاخه، بر آزمایش هر نقطه تصمیم تمرکز می‌کند و یا همچنین در معیار پوشش جملات بر روی یک جمله تمرکز دارد که ممکن است برخی از جریان‌های منطقی برنامه را از دست بدهد؛ ولی در روش مسیرهای متناهی کل جملات را در نظر می‌گیرد و به طور بالقوه تعاملات پیچیده بین بخش‌های مختلف کد را آشکار می‌کند. در این مقاله از معیار پوشش همه مسیرهای متناهی استفاده شده که هدف، پوشش تمامی مسیرهای متناهی موجود در برنامه تحت آزمون است.

گراف جریان برنامه، جریان کنترل منطقی متد را با استفاده از مسیرها به نمایش می‌گذارد که این مسیرها در حقیقت همان مسیر حرکت ورودی به خروجی هستند. یعنی یك گراف جریان برنامه همه اجراهای یك قطعه كد را با توصیف ساختارهای كنترلی آن مدل‌سازی می‌كند. شکل 1 گراف جریان برنامه قطعه کد مثال شکل 2 را نشان می‌دهد.

مسأله‌ای که در اینجا مورد نظر می‌باشد، تعیین‌کردن خودکار مجموعه ورودی‏ها برای آزمون یک متد مشخص است تا اینکه بتواند تمامی مسیرهای img0 را پوشش دهد. بدین منظور از جستجوی روی فضای پارامترهای ورودی متد استفاده می‏شود. یک متد به‌صورت کلی به شکل [return type] method_name ([input parameter list]) معرفی می‌شود. فضای ورودی‏های این متد که باید جستجو روی آن انجام پذیرد 

img0 

شکل 1:  گراف جریان برنامه قطعه کد مثال 1.

 

img0 

شکل 3:  نمونه‌ای از کواتی‌های جمعیت.

 

با توجه به لیست پارامترهای ورودی متد تعریف می‏شود. یعنی اگر متد دارای مثلاً ۲ پارامتر ورودی باشد، فضای ورودی‏ها متشکل از زوج‏های دوتایی img0 خواهد بود که img0 مقدار منتسب‌شده به پارامتر اول و img0 مقدار منتسب‌شده به پارامتر دوم را نشان می‏دهد. هدف اصلی در این جستجو  کمینه‌کردن  میزان  محاسبات  لازم  برای  شناسایی  ورودی‌هاست؛ چرا که با بزرگ‌شدن برنامه و افزایش تعداد توابع در آن، زمان زیادی برای تولید این موارد تست نیاز خواهد بود و هرچه راهکار خودکار سریع‌تر و با محاسبات کمتری بتواند تمامی مسیرها را پوشش دهد، بهتر خواهد بود.

3-3 به دست آوردن گراف جریان برنامه

برای به دست آوردن گراف جریان برنامه می‌توانیم با استفاده از نرم‌افزاری مثل visustin یا با استفاده از کتابخانه pycfg یا staticfg در زبان برنامه‌نویسی پایتون، گراف جریان برنامه تحت آزمون را به دست بیاوریم و سپس مسیرهای این گراف را از گراف مورد نظر استخراج کنیم.

3-4 ایجاد جمعیت اولیه

پس از تولید گراف جریان برنامه و سپس به دست آوردن مسیرهای این گراف، یک جمعیت اولیه تصادفی تولید می‌شود. اندازه هر کواتی (راه‌حل) این جمعیت به تعداد متغیرهای متد تحت آزمون و تعداد مسیرها بستگی دارد. به طور کلی در متدی که تعداد متغیرهای ورودی آن img0 و تعداد مسیرهای گراف جریان آن img0 است، هر کواتی این جمعیت img0 زیربخش دارد و اندازه هر زیربخش برابر img0 است. شکل 3 یک نمونه از این کواتی‌ها را نشان می‌دهد.

3-5 محاسبه برازندگی جمعیت کواتی‌ها

بعد از ایجاد جمعیت تصادفی اولیه، برای تعیین میزان برازندگی هر عضو جمعیت، لازم است که img0 بار متد تحت آزمون اجرا شود تا مشخص شود که چه مسیرهایی توسط مجموعه آزمون ورودی پوشش 

img0 

شکل 2:  قطعه کد گراف جریان برنامه شکل 1.

 

داده شده‏اند. مقدار برازندگی هر کواتی طبق (1) محاسبه می‌شود

img0        (1)

در (1)، img0 برابر با تعداد مسیرهای پوشش داده شده توسط کواتی img0ام و img0 برابر با تعداد کل مسیرهاست.

 

3-6 عملیات بهبود

در این قسمت بعد از شناسایی بهترین کواتی، مسیرهای این کواتی بررسی می‌شود و یکی از مسیرهای پوشش داده نشده در این کواتی را به‌صورت تصادفی از لیست مسیرهای پوشش داده نشده انتخاب می‌کنیم. سپس شبیه‌ترین مسیر از مسیرهای پوشش داده شده توسط کواتی نسبت به مسیر پوشش داده نشده را با استفاده از معیار شباهت جاکارد3 پیدا می‌کنیم و زیربخش مرتبط با آن را از کواتی بیرون می‌کشیم. نهایتاً این زیربخش را با استفاده از رویکرد یادگیری q و با تعریف عمل‌هایی روی این زیربخش بهبود می‌دهیم.

3-7 پیش‌پردازش مسیرها

معیار شباهت جاکارد، معیاری برای مقایسه شباهت یا تفاوت مجموعه نمونه‌های آماری است. میزان شباهت دو مجموعه نمونه با توجه به معیار شباهت جاکارد، از تقسیم تعداد اشتراک دو مجموعه بر تعداد اجتماع دو مجموعه به دست می‌آید. بنابراین این معیار اطلاعات زیادی راجع به وضعیت مسیرها به ما می‌دهد. شاخص تشابه جاکارد دو مجموعه img0 و img0 طبق (2) محاسبه می‌گردد

img0        (2)

img0 

شکل 4:  برنامه نمونه.

 

همچنین فاصله جاکارد که میزان تفاوت دو مجموعه نمونه را می‌سنجد، با کم‌کردن میزان شباهت جاکارد از یک طبق (3) به دست می‌آید

img0        (3)

در این مرحله بررسی می‌شود که آیا مقدار برازندگی بهترین کواتی جمعیت img0 از یک حد از پیش تعیین‌شده بیشتر است یا نه. اگر بیشتر نبود، الگوریتم به روند عادی خودش ادامه می‌دهد و در غیر این صورت فرایند بهبود کواتی img0 شروع می‌شود. به منظور بهبود، ابتدا یکی از مسیرهای پوشش داده نشده در img0 را به‌صورت تصادفی از کل مسیرهای پوشش داده نشده توسط این کواتی انتخاب می‌کنیم. فرض کنید که این مسیر img0 نام دارد. سپس شبیه‌ترین مسیر در بین مسیرهای پوشش داده شده توسط img0 را نسبت به img0 به دست می‏آوریم و بدین منظور از معیار شباهت ‌جاکارد استفاده می‏کنیم. آن گاه زیربخش مربوط به این مسیر را از کواتی img0 بیرون می‌کشیم و عملیات بهبود را بر روی این زیربخش انجام می‌دهیم. معیار شباهت جاکارد که در [31] مورد استفاده قرار گرفته است، برای حلقه‌ها دچار مشکل می‌شود و نمی‌تواند به‌صورت دقیق شبیه‌ترین مسیر را به دست آورد. به‌عنوان مثال قطعه کد زیر را در نظر بگیرید

 

img0 

 

در این کد برای به دست آوردن اطلاعات مسیر مثلاً 0-4-11 به اطلاعات مسیر 0-3-11 نیاز است که معیار شباهت جاکارد این اطلاعات را نمی‌تواند به دست بیاورد و برای هر سه مسیر 0-1-11، 0-2-11 و 
0-3-11 مقدار شباهت یکسانی به دست می‌آورد و وجه تمایزی قائل نمی‌شود. برای رفع این مشکل ما برای حلقه‌ها در این مقاله از معیار شباهت منهتن استفاده کرده‌ایم [32].

3-8 بهبود زیربخش‌های کواتی با رویکرد یادگیری Q

بعد از اینکه شبیه‌ترین زیربخش نسبت به مسیر پوشش داده نشده به دست آمد، عملیات یادگیری Q شروع به کار می‌کند. در الگوریتم‌های یادگیری تقویتی، قبل از انجام هر کاری باید ما حالت‌ها4 و عمل‌هایی5 
را که قرار است روی این حالت‌ها به کار روند، تعریف کنیم. در روش پیشنهادی اگر تعداد متغیرهای ورودی برنامه تحت آزمون برابر img0 باشد، تعداد حالت‌ها هم برابر img0 است و عمل‌ها به گونه‌ای تعریف شده که تا حد امکان بین همه برنامه‌ها مشترک باشد. هرچند با توجه به تنوع و ساختار بین برنامه‌ها، عمل‌ها می‌تواند بسته به نوع برنامه از این تعداد بیشتر باشد. در واقع عمل‌هایی که تعریف شده عبارت است از:

-        کم‌کردن از مقدار متغیر: متد شکل 4 را در نظر بگیرید. فرض کنید مقدار شبیه‌ترین زیربخش با توجه به مسیرهای پوشش داده شده برابر img0 است؛ در این صورت اگر مقدار متغیر سوم یعنی 6 را یک واحد کاهش بدهیم، مسیر جدیدی ایجاد خواهد شد.

-        اضافه‌کردن به مقدار متغیر: متد شکل 4 را در نظر بگیرید. فرض کنید مقدار شبیه‌ترین زیربخش با توجه به مسیرهای پوشش داده شده برابر img0 است؛ در این صورت اگر مقدار متغیر سوم یعنی 4 را یک واحد افزایش بدهیم، مسیر جدیدی ایجاد خواهد شد.

-        ثابت‌ماندن مقدار متغیر: متد شکل 4 را در نظر بگیرید. فرض کنید مقدار شبیه‌ترین زیربخش با توجه به مسیرهای پوشش داده شده برابر img0 است؛ در این صورت اگر در متغیرهای (حالت‌های) اول و دوم، این عمل انجام شود بهتر است؛ چرا که اگر عمل دیگری انتخاب شود، باعث خرابی این زیربخش می‌شود.

-        تنظیم مقدار متغیر با مقدار متغیر بعدی: متد شکل 4 را در نظر بگیرید. فرض کنید مقدار شبیه‌ترین زیربخش با توجه به مسیرهای پوشش داده شده برابر img0 است؛ در این صورت اگر مقدار متغیر سوم یعنی 6 را برابر مقدار متغیر بعدی یعنی 5 قرار بدهیم، آن گاه مسیر جدیدی ایجاد خواهد شد.

-        صفرکردن مقدار متغیر: به‌عنوان مثال، در متدی با روابط زیر، اگر مقدار متغیر 6 var برابر صفر شود، شرط مورد نظر ارضا می‌شود و مقادیر متغیرهای 5 var و 6 var متناسب با قواعد یادگیری Q به‌روزرسانی خواهند شد

img0        

        اگر در این دستور img0، img0، img0 و img0 باشد و مقدار img0 برابر 0 شود، این دستور ارضا می‌شود. از جهتی دیگر با صفرکردن متغیرهای  img0و img0  باز هم می‌توانیم به جواب نزدیک‌تر شویم. (یکی از کاربردهایش این است که به جواب نزدیک شویم و هر دو طرف شرط در نزدیکی هم قرار بگیرند و وقتی که در نزدیگی یکدیگر قرار بگیرند با انجام‌دادن سایر عمل‌ها می‌توان به جواب نهایی رسید.)

-        جابه‌جایی مقدار متغیر با متغیر بعدی یا قبلی: فرض کنید متدی داریم که دستورات آن به این صورت است

 

img0 

 

        در این متد دو مسیر وجود دارد. مسیر اول به ازای img0 و img0 پوشش داده می‌شود. اکنون اگر مقادیر این دو متغیر با 

img0 

شکل 5:  فرایند یادگیری تقویتی برای برنامه مثال شکل 4.

 

هم تعویض گردد مسیر دوم هم از روی مسیر اول ایجاد می‌گردد.

شکل 5 فرایند یادگیری تقویتی برای مثال برنامه شکل 4 را نشان می‌دهد. به‌عنوان نمونه، در برنامه‌ی ارائه‌شده در شکل 4، تعداد حالات img0 برابر با 3 و تعداد اعمال 6 در نظر گرفته شده است؛ به‌طوری‌که در هر حالت، تمامی شش عمل تعریف‌شده قابلیت اجرا دارند. مثلاً در حالت img0 با انجام هر عمل و با احتمال img0 به هر حالت ممکن برویم و برای سایر حالات هم همین روند انجام می‌شود. برای برآوردکردن عملیات  یادگیری  تقویتی  از  یکی  از  معروف‌ترین  الگوریتم‌های  این  حوزه که یادگیری‌کیو6 است، استفاده شده است. اکنون در این مرحله باید جدول ‌کیو7 را ایجاد کنیم که این جدول img0 سطر و 6 ستون دارد.

وقتی که الگوریتم شروع به کار می‌کند با یک جدول با مقدار تصادفی شروع به کار می‌کند و بعد از انجام یک عمل در یک حالت عملی که انتخاب شده باعث تغییری در مقدار آن حالت (متغیر ورودی آن تکه از زیربخش) می‌شود. در هر مرحله این اعمال در حالت‌های مختلف ما رخ می‌دهد و بعد از اعمال‌کردن این عمل‌ها روی حالت‌ها، اگر به هدف رسیدیم جایزه8 مثبت و در غیر این صورت جایزه منفی می‌گیریم تا زمانی که به یک زیربخش خوب تبدیل شود یا تعداد مرحله‌ها از یک مقدار از پیش تعریف شده بیشتر شود. سپس وقتی که یک زیربخش خوب پیدا شد یا تعداد مرحله‌ها از یک مقداری بیشتر شد، مقدار زیربخش بازگشت داده می‌شود به کواتی و کواتی به جمعیت اصلی انتقال داده می‌شود.

3-9 فاز اول الگوریتم کواتی

مرحله اول به‌روزرسانی جمعیت کواتی‌ها در فضای جستجو بر اساس شبیه‌سازی استراتژی آنها هنگام حمله به ایگواناها مدل‌سازی شده است. در این استراتژی، گروهی از کواتی‌ها از درخت بالا می‌روند تا به یک ایگوانا برسند و آن را بترسانند. در طبیعت، تعدادی از کوآتی‌ها در زیر درخت منتظر می‌مانند تا ایگوانا از درخت سقوط کند؛ پس از آن، فرآیند شکار آغاز می‌شود. این رفتار به‌عنوان الگوی الهام‌بخش در طراحی فاز جست‌وجوی الگوریتم COA به‌کار گرفته شده است.

در طراحی COA، موقعیت بهترین عضو جمعیت، موقعیت ایگوانا9 در نظر گرفته شده است. همچنین فرض بر این است که نیمی از کواتی‌ها از درخت بالا می‌روند و نیمی دیگر منتظر می‌مانند تا ایگوانا روی زمین بیفتد. بنابراین موقعیت کواتی برآمده از درخت به صورت ریاضی با استفاده از (4) شبیه‌سازی می‌شود

img0        (4)

در (۵) و (۶)، موقعیت‌های جدید اعضای جمعیت (کوآتی‌ها) بر اساس موقعیت ایگوانا و محدوده جست‌وجو محاسبه می‌شود. رابطه موقعیت اولیه ایگوانا در فضای جست‌وجو از طریق (۵) تعیین می‌شود، در حالی که (۶) فرآیند به‌روزرسانی موقعیت کوآتی‌ها را براساس مقایسه برازندگی و رفتار حمله یا تعقیب مدل می‌کند. این دو رابطه در واقع بیانگر فاز اکتشاف و بهره‌برداری الگوریتم بهینه‌سازی کوآتی هستند که موجب تعادل میان جست‌وجوی سراسری و محلی می‌شود

img0        (5)

img0        (6)

رابطه (۷) مرحله‌ی انتخاب نهایی را در الگوریتم COA مدل‌سازی می‌کند. در این مرحله، کوآتی‌ها تنها در صورتی موقعیت جدید خود را می‌پذیرند که برازندگی آن از موقعیت فعلی بهتر باشد. این فرآیند باعث می‌شود الگوریتم از افت کیفیت پاسخ‌ها جلوگیری کرده و به‌تدریج به سمت بهترین راه‌حل‌ها همگرا شود. به‌عبارتی، این رابطه نقش «مکانیزم انتخاب طبیعی» در الگوریتم را ایفا می‌کند و تضمین‌کننده‌ی پایداری همگرایی است.

img0        (7)

در اینجا img0 موقعیت جدید محاسبه‌شده برای کواتی img0ام است، img0 بعد img0ام آن است، img0 مقدار تابع هدف آن است، img0 یک عدد واقعی تصادفی در بازه img0 است، در الگوریتم COA، بردار Iguana موقعیت بهترین عضو جمعیت را در فضای جست‌وجو نشان می‌دهد که به‌عنوان نقطه‌ی مرجع برای هدایت سایر کوآتی‌ها در فرآیند بهینه‌سازی به‌کار می‌رود، Iguanaj بعد img0ام آن است، img0 یک عدد صحیح است که به طور تصادفی از بین اعداد 1 یا 2 انتخاب می‌شود، IguanaG موقعیت ایگوانا روی زمین است که به طور تصادفی تولید می‌شود، IguanaGj بعد img0ام آن، FIguanaG مقدار تابع هدف آن و img0  تابع کف است.

3-10 فاز دوم الگوریتم کواتی

مرحله دوم فرایند به‌روزرسانی موقعیت کواتی‌ها در فضای جستجو به صورت ریاضی بر اساس رفتار طبیعی کواتی‌ها در هنگام مواجهه با شکارچیان و فرار از شکارچیان مدل‌سازی شده است. هنگامی که یک شکارچی به کواتی حمله می‌کند، این حیوان از موقعیت خود فرار می‌کند. حرکات کواتی در این استراتژی منجر به قرارگرفتن آن در موقعیت امن نزدیک به موقعیت فعلی می‌شود که نشان‌دهنده توانایی بهره‌برداری COA در جستجوی محلی است. برای شبیه‌سازی این رفتار، یک موقعیت تصادفی در نزدیکی موقعیتی که هر پوشش در آن قرار دارد بر اساس (8)

img0 

(الف)

img0 

(ب)

شکل 6:  (الف) برنامه دسته‌بندی مثلث و (ب) گراف جریان متناظر آن.

 

و (9) شبیه‌سازی می‌شود. موقعیت بهتر طبق (7) جایگزین می‌شود

img0        (8)

img0        (9)

3-11 شبه‌کد الگوریتم پیشنهادی

1)        تهیه گراف جریان متد تحت آزمون و به دست آوردن تعداد مسیرهای آن

2)        ایجاد یک جمعیت تصادفی اولیه از راه‌حل‌ها

3)        ارزیابی جمعیت

4)        تا زمانی که به هدف نرسیده‌ایم تکرار کن:

.a        انتخاب راه‌حل‌های مناسب‏تر از جمعیت

.b        اگر در بهترین راه‌حل به‌دست‌آمده، مقدار برازندگی از حد مشخصی بهتر بود، آن را انتخاب کن و برو به مرحله h

.c        فاز اول الگوریتم

.d        فاز دوم الگوریتم

.e        ترکیب راه‌حل به‌دست‌آمده از مرحله b در صورت اجرای آن و جمعیت فعلی در d

.f        ارزیابی جمعیت

.g        انجام جستجو بین همه مسیرهای به‌دست‌آمده تکرار فعلی

.h        با استفاده از معیار شباهت جاکارد، شبیه‌ترین مسیر به مسیر 

جدول 1: تنظیم پارامتر الگوریتم‌ها.

 

Value

Parameter

Algorithms

Adaptive

Crossover Rate

AGA

IGA

Mutation Rate

Selection

Adaptive

1C

APSO

Adaptive

2C

Adaptive

W

[1،2]

I

POA

2/0

R

06/0

Mutation

PRO

[0،1]

img0 

DO

[0،1]

k

5/0

alpha

FA

1

gamma

1

img0 

 

 

محقق‌نشده داخل مجموعه مسیرهای راه‌حل را به دست بیاور و زیربخش مربوط به شبیه‌ترین مسیر را انتخاب کن و برو به مرحله i.

.i        به کار بردن الگوریتم یادگیری کیو برای بهبود آن زیربخش و بازگشت نتیجه

4-       آزمایش و نتایج

آزمایش‌ها به ازای برنامه‌های معروف و مختلفی که در اکثر مقالات مهم در این حوزه وجود دارد، صورت گرفته و سعی گردیده که تمام ساختارهای برنامه‌نویسی در فرآیند تحلیل ساختار برنامه، اجزای کنترلی مانند حلقه‌ها10 و شرط‌ها11 شناسایی ‌شوند تا مسیرهای ممکن اجرای برنامه برای تولید داده‌های آزمون استخراج گردند. هر برنامه ساختارهای شرطی و تودرتویی متفاوتی نسبت به سایر برنامه‌ها دارد. برای انجام ارزیابی‏ها از دو معیار زیر استفاده شده است:

-        میانگین تعداد دفعات فراخوانی تابع برازندگی

-        نرخ موفقیت12 که بر اساس (10) محاسبه می‌شود

img0        (10)

در (10) img0 تعداد اجرای الگوریتم و img0 هم یک پرچم13 بولین است که اگر الگوریتم از یک حد ثابت فراخوانی تابع برازندگی جواب به حداکثر پوشش رسید، این پرچم برابر یک می‌شود و در غیر این صورت برابر صفر است. الگوریتم پیشنهادی 14 (QLCOA) با نتایج حاصل از دو الگوریتم ژنتیک تطبیقی (IGA و AGA) [16] و [17]، (بهبودیافته با به دست آوردن نرخ جهش و بازترکیبی به صورت پویا در حین اجرای الگوریتم)، الگوریتم بهینه‌سازی ازدحام ذرات تطبیقی (APSO) [33]، الگوریتم بهینه‌سازی پلیکان [34]، الگوریتم بهینه‌سازی ضعیف و غنی (PRO) 

img0 

شکل 7:  نرخ موفقیت الگوریتم‌ها برای برنامه دسته‌بندی مثلث.

 

img0 

                  (الف) (ب)

شکل 8:  (الف) دنباله فیبوناچی و (ب) گراف جریان متناظر آن.

 

[35]، الگوریتم بهینه‌سازی قاصدک (DO) [36]، الگوریتم بهینه‌سازی کرم شبتاب (FA) [37] و الگوریتم کواتی استاندارد (COA) مورد مقایسه قرار گرفته است.

تنظیم پارامتر این الگوریتم‌ها در جدول 1 نشان داده شده است. در این مقاله نمایش اعداد صحیح در بازه 100- و 100 در نظر گرفته شده و تعداد اجرا برای هر الگوریتم 50 و حداکثر تعداد فراخوانی تابع برازش هم 100000 در نظر گرفته شده است.

4-1 برنامه تحت تست 1

برنامه دسته‌بندی مثلث که یکی از برنامه‌های معروف در این حوزه است به زبان برنامه‌نویسی پایتون نوشته شده و گراف جریان مربوط به آن در شکل 6 را در نظر بگیرید. در گراف جریان شکل 6 تعداد مسیرها برابر 3 و تعداد متغیرها برابر 3 است. برای مثال، چند نمونه داده تولیدشده توسط الگوریتم پیشنهادی برای این برنامه به صورت زیر است

[23،78،12،5،5،5،66،66،89]

[1،1،1،55،55،8،45،79،12]

[34،34،5،90،90،90،7،34،41]

[60،60،60،5،77،82،45،45،98]

[67،89،45،6،6،80، 3-، 3-،3-]

 

جدول 2: نتایج برنامه دسته‌بندی مثلث.

 

pc

worst

best

p-value

std

MNFE

Algorithms

%100

7175

95

0/0

1/1758

5/1779

IGA

%100

5645

215

0/0

3/1186

9/1367

AGA

%100

8506

580

0/0

4/2037

56/3835

APSO

%100

6420

440

0/0

4/1433

4/2186

POA

%100

3900

180

0/0

7/779

4/1278

PRO

%100

2920

340

0/0

5/518

8/1238

DO

%100

11435

556

0/0

1/2510

02/2966

FA

%100

12640

180

0/0

5/2654

8/2905

COA

%100

87

41

0/0

06/9

16/69

QLCOA

 

جدول 3: نتایج برنامه فیبوناچی.

 

pc

worst

best

p-value

std

MNFE

Algorithms

%100

2315

95

0/0

8/505

4/676

IGA

%100

1760

90

0/0

1/493

6/725

AGA

%100

5255

185

0/0

0/988

2/999

APSO

%100

2735

140

0/0

9/632

7/919

POA

%100

1700

110

0/0

6/356

1/535

PRO

%100

2525

155

0/0

4/603

0/875

DO

%100

2690

80

0/0

9/678

9/920

FA

%100

2255

80

0/0

3/497

8/627

COA

%100

841

72

0/0

7/133

62/207

QLCOA

 

جدول 4: نتایج برنامه محاسبه ریشه‌های رابطه درجه دوم.

 

pc

worst

best

p-value

std

MNFE

Algorithms

%100

5615

140

0/0

5/1244

2/1347

IGA

%100

4610

140

0/0

3/947

8/1044

AGA

%100

27228

1279

0/0

4/6694

48/8797

APSO

%100

2380

40

0/0

9/592

2/729

POA

%100

1400

40

0/0

7/290

8/304

PRO

%100

2880

260

0/0

5/559

2/1235

DO

%100

34047

612

0/0

1/7473

16/7649

FA

%100

3220

100

0/0

0/482

2/663

COA

%100

99

62

0/1

11/11

6/74

QLCOA

 

جدول 5: نتایج برنامه تحت تست 4.

 

pc

worst

best

p-value

std

MNFE

Algorithms

100%

5615

140

0/0

5/1244

2/1347

IGA

100%

4610

160

0/0

3/947

8/1044

AGA

100%

27228

1279

0/0

4/6694

48/8797

APSO

100%

2380

40

0/0

9/592

2/729

POA

100%

1400

40

0/0

7/290

8/304

PRO

100%

2880

260

0/0

5/559

2/1235

DO

100%

34047

612

0/0

1/7473

16/7649

FA

100%

3220

100

8×10-6

0/682

2/663

COA

100%

110

50

0/1

1/11

6/74

QLCOA

 

جدول 2 نتایج حاصل و شکل 7 نرخ موفقیت را برای این الگوریتم‌ها نشان می‌دهد. در جداول 2 تا 5 ستون اول معرف الگوریتم‌ها، ستون دوم میانگین  تعداد  ارزیابی‌ها  در  50 بار  اجرا  به ازای  هر الگوریتم (MNFE)، 

img0 

شکل 9:  نرخ موفقیت الگوریتم‌ها برای برنامه فیبوناچی.

 

ستون سوم انحراف معیار (std)، ستون چهارم مقدار p_value، ستون پنجم بهترین تعداد ارزیابی (best)، ستون ششم بدترین تعداد ارزیابی (worst) و ستون هفتم درصد پوشش مسیرها (pc) را نشان می‌دهد.

4-2 برنامه تحت تست 2

برنامه بعدی که می‌خواهیم مورد آزمون قرار دهیم دنباله فیبوناچی است. این برنامه یک بنچمارک معروف است که در اکثر مقالات مهم به کار رفته است. در این مقاله هدف از آزمون این برنامه، آزمون حلقه است. دنباله یا سری فیبوناچی دنباله‌ای از اعداد به شکل زیر است

...،0،1،1،2،3،5،8،13،21

در این دنباله عدد بعدی با جمع دو عدد ماقبل خود به دست می‌آید و بقیه اعدد نیز به همین ترتیب محاسبه می‌شوند. این برنامه به همراه گراف جریان متناظر آن در شکل 8 نشان داده شده است. در شکل 8 تعداد مسیرها  بستگی  به  متغیر  ورودی  برنامه  یعنی img0 دارد.  در  این  مقاله  هر 

حلقه حداکثر دو مسیر آن پوشش داده شده است. جدول 3 نتایج حاصل 
از این الگوریتم‌ها و شکل 9 نرخ موفقیت را برای این الگوریتم‌ها نشان می‌دهد.

4-3 برنامه تحت تست 3

در این بخش برنامه محاسبه ریشه‌های رابطه درجه دوم15 را می‌خواهیم مورد آزمون قرار دهیم. هدف از آزمون این برنامه، آزمودن شروطی است که در شرط آنها عبارت محاسباتی وجود دارد. برای حل رابطه درجه دوم img0 می‌توان از (11) استفاده کرد

img0        (11)

ابتدا باید جذر img0 را محاسبه کرده و بعد از آن سه حالت زیر برقرار خواهد بود:

-        اگر img0 باشد، آن گاه رابطه دارای دو جواب (ریشه) حقیقی متمایز (12) است

img0        (12)

-        اگر img0 باشد، آنگاه رابطه دارای یک جواب حقیقی مضاعف است که با استفاده از (13) به دست می‌آید

img0 

(الف)

img0 

(ب)

شکل 10:  (الف) برنامه محاسبه ریشه‌های رابطه درجه دوم و (ب) گراف جریان متناظر آن.

img0        (13)

-        اگر img0 باشد، آنگاه رابطه دارای جواب حقیقی نیست.

برنامه این رابطه به همراه گراف جریان آن در شکل 10 نشان داده شده که این برنامه دارای 3 متغیر و 4 مسیر است. جدول 4 نتایج حاصل از این الگوریتم‌ها را نشان می‌دهد.

4-4 برنامه تحت تست 4

هدف از این آزمون، آزمودن شرط‌های تودرتو و پوشش مسیرهای زیاد است. کد و گراف این برنامه در شکل 11 نشان داده شده است.

4-5 برنامه تحت تست 5

در این برنامه مسیرهای پیچیده‌تر و مشکل‌تری مورد آزمون قرار گرفته‌اند. با توجه به اینکه یک حد ثابت تعداد ارزیابی برنامه تحت تست در نظر گرفته شده است، پیداکردن این مسیرها برای این الگوریتم‌ها زمانگیر و مشکل است. شکل 12- الف برنامه نوشته‌شده به زبان پایتون این برنامه را نشان می‌دهد. نمودار جریان کنترل (CFG)  مربوط به این برنامه در شکل ۱۲- ب ارائه شده است که ارتباط بین بلوک‌های کد و مسیرهای ممکن اجرای برنامه را نشان می‌دهد. در این شکل مسیر 1-3-4-6 (با رنگ تیره برجسته شده است) یک مسیر سخت و مشکل است؛ چرا که عبارات محاسباتی زیادی در آن وجود دارد و همچنین عباراتی در

img0 

(الف)

img0 

(ب)

شکل 11:  (الف) برنامه محاسبه ریشه‌های رابطه درجه دوم و (ب) گراف جریان متناظر آن.

 

img0 

(الف)

img0 

(ب)

شکل 12:  (الف) کد برنامه تحت تست و (ب) گراف جریان مربوط به آن.

img0 

شکل 13:  درصد پوشش مسیر برای الگوریتم‌های مورد مقایسه.

 

Untitled 

شکل 14:  روند همگرایی الگوریتم یادگیری تقویتی.

 

آن وجود دارد که فقط به ازای یک مقدار ثابت ارضاپذیر هستند. شکل ۱۳ درصد پوشش مسیر حاصل از اجرای الگوریتم پیشنهادی(QLCOA)  و سایر الگوریتم‌های مقایسه‌ای را نشان می‌دهد. همان‌طور که دیده می‌شود، QLCOA بیشترین میزان پوشش مسیر را در بین روش‌های بررسی‌شده به‌دست آورده است.

همه الگوریتم‌های مورد مقایسه 70 درصد مسیرها را بعد از 100000 ارزیابی، پوشش داده‌اند؛ در صورتی که الگوریتم پیشنهادی 100 درصد مسیرها را با 19240 ارزیابی پوشش داده است. الگوریتم پیشنهادی به دلیل اینکه ساختار درون راه‌حل‌ها را با روش هوشمندانه‌تری به‌روزرسانی می‌کند، از کارایی بیشتر و بهتری نسبت به سایر الگوریتم‌ها برخوردار است.

5-       همگرایی

نمودار همگرایی الگوریتم یادگیری تقویتی نشان می‌دهد که در ابتدا پاداش‌ها نزدیک به صفر بوده و به تدریج با افزایش تعداد اپیزودها کاهش می‌یابد؛ به طوری که تا اپیزود ۱۰۰ به حدود منفی ۲۰ و تا اپیزود ۱۷۵ به حدود منفی ۴۰ می‌رسد. این روند نشان‌دهنده ضعف عملکرد عامل است. اما پس از اپیزود ۱۷۵، افزایش قابل توجهی در پاداش مشاهده می‌شود که نشان‌دهنده بهبود و همگرایی به سمت یک استراتژی بهتر است. به طور کلی، عامل برای همگرایی به یک راه‌حل بهینه به حدود ۱۷۵ اپیزود نیاز دارد. شکل ۱۴ روند تغییر مقدار برازندگی الگوریتم پیشنهادی (QLCOA)  را در طول تکرارها نشان می‌دهد. کاهش تدریجی مقدار خطا بیانگر همگرایی مناسب الگوریتم و پایداری فرآیند یادگیری است.

6-       نتیجه‌گیری و کارهای آینده

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

مراجع

[1]       P. Ammann and J. Offutt, Introduction to Software Testing, Cambridge University Press, 2016.

[2]       F. Lonetti and E. Marchetti, "Emerging software testing technologies," Advances in Computers, Elsevier, vol. 108, pp. 91-143, 2018.

[3]       S. Parsa, "Automatic test data generation symbolic and concolic executions," In S. Parsa (ed.), Software Testing Automation: Testability Evaluation, Refactoring, Test Data Generation and Fault Localization, pp. 503-542, Springer, 2023.

[4]       G. Zhang, et al.,"FDSE: enhance symbolic execution by fuzzing-based pre-analysis (competition contribution)," in Proc. 27th Int. Conf. on Fundamental Approaches to Software Engineering, pp. 304-308, Luxembourg City, Luxembourg, 6-11 Apr. 2024.

[5]       O. Sahin and B. Akay, "Comparisons of metaheuristic algorithms and fitness functions on software test data generation," Applied Soft Computing, vol. 49, pp. 1202-1214, Dec. 2016.

[6]       M. Harman and P. McMinn, "A theoretical and empirical study of search-based testing: local, global, and hybrid search," IEEE Trans. on Software Engineering, vol. 36, no. 2, pp. 226-247, Mar./Apr. 2009.

[7]       M. Dehghani, Z. Montazeri, E. Trojovská, and P. Trojovský, "Coati optimization algorithm: a new bio-inspired metaheuristic algorithm for solving optimization problems," Knowledge-Based Systems,
vol. 259, Article ID: pp. 110011, Jan. 2023.

[8]       N. Soffair and S. Mannor, \Textit {MinMaxMin} $Q$-Learning, arXiv preprint arXiv:2402.05951, 2024.

[9]       N. Khoshniat, A. Jamarani, A. Ahmadzadeh, M. Haghi Kashani, and E. Mahdipour, "Nature-inspired metaheuristic methods in software testing," Soft Computing, vol. 28, no. 2, pp. 1503-1544, 2024.

[10]       P. Ashwini, B. Rajani, and B. Vijitha, "An efficient early software reliability prediction using particle swarm optimization (PSO)," In K. Venkata Murali Mohan, M. Suresh Babu (eds). Disruptive Technologies in Computing and Communication Systems, pp. 52-58, CRC Press, 2024.

[11]       T. Avdeenko and K. Serdyukov, "Automated test data generation based on a genetic algorithm with maximum code coverage and population diversity," Applied Sciences, vol. 11, no. 10, Article ID: 4673, May-2 2021.

[12]       M. Nosrati, H. Haghighi, and M. V. Asl, "Test data generation using genetic programming," Information and Software Technology,
vol. 130, Article ID: 106446, 2021.

[13]       M. Angelova, K. Atanassov, and T. Pencheva, "Multi-population genetic algorithm quality assessment implementing intuitionistic fuzzy logic," in Proc. Federated Conf. on Computer Science and Information Systems, pp. 365-370, Wroclaw, Poland, 9-12 Sept. 2012.

[14]       M. Alshraideh, B. A. Mahafzah, and S. Al-Sharaeh, "A multiple-population genetic algorithm for branch coverage test data generation," Software Quality J., vol. 19, pp. 489-513, 2011.

[15]       N. Zhang, B. Wu, and X. Bao, "Automatic generation of test cases based on multi-population genetic algorithm," Int. J. Multimedia Ubiquitous Eng., vol. 10, no. 6, pp. 113-122, 2015.

[16]       X. Bao, Z. Xiong, N. Zhang, J. Qian, B. Wu, and W. Zhang, "Path-oriented test cases generation based adaptive genetic algorithm," PloS One, vol. 12, no. 11, Article ID: e0187471, 2017.

[17]       A. Damia, M. Esnaashari, and M. Parvizimosaed, "Software testing using an adaptive genetic algorithm," J. of AI and Data Mining,
vol. 9, no. 4, pp. 465-474, Oct. 2021.

[18]       M. Mann, P. Tomar, and O. P. Sangwan, "Test data generation using optimization algorithm: an empirical evaluation," in Proc. of Soft Computing: Theories and Applications, vol. 2, pp. 679-686, Jaipur, India, 28-30 Dec. 2018.

[19]       M. Mann, O. P. Sangwan, P. Tomar, and S. Singh, "Automatic goal-oriented test data generation using a genetic algorithm and simulated annealing," in Proc. 6th Int. Conf.-Cloud System and Big Data Engineering, pp. 83-87, Noida, India, 14-15 Jan. 2016.

[20]       X. M. Zhu and X. F. Yang, "Software test data generation automatically based on improved adaptive particle swarm optimizer," in Proc. Int. Conf. on Computational and Information Sciences, pp. 1300-1303, Chengdu, China, 17-19 Dec. 2010.

[21]       S. Singla, D. Kumar, H. Rai, and P. Singla, "A hybrid PSO approach to automate test data generation for data flow coverage with dominance concepts," International J. of Advanced Science and Technology, vol. 37, no. 11, pp. 15-26, 2011.

[22]       S. Jiang, J. Shi, Y. Zhang, and H. Han, "Automatic test data generation based on reduced adaptive particle swarm optimization algorithm," Neurocomputing, vol. 158, pp. 109-116, Jun. 2015.

[23]       H. Sharifipour, M. Shakeri, and H. Haghighi, "Structural test data generation using a memetic ant colony optimization based on evolution strategies," Swarm and Evolutionary Computation, vol. 40, no. 40, pp. 76-91, Jun. 2018.

[24]       A. H. Damia and M. M. Esnaashari, "Automated test data generation using a combination of firefly algorithm and asexual reproduction optimization algorithm," International J. of Web Research, vol. 3, no. 1, pp. 19-28, Jun. 2020.

[25]       A. Damia, M. Esnaashari, and M. Parvizimosaed, "Automatic web-based software structural testing using an adaptive particle swarm optimization algorithm for test data generation," in Proc. 7th Int. Conf. on Web Research, pp. 282-286, Tehran, Iran, 19-20 May 2021.

[26]       O. Al-Masri and W. A. Al-Sorori, "Object-oriented test case generation using teaching learning-based optimization (TLBO) algorithm," IEEE Access, vol. 10, pp. 110879-110888, 2022.

[27]       M. Saadtjoo and S. Babamir, "Optimizing cost function in imperialist competitive algorithm for path coverage problem in software testing," J. of AI and Data Mining, vol. 6, no. 2, pp. 375-385, Jul. 2018.

[28]       X. Dai, W. Gong, and Q. Gu, "Automated test case generation based on differential evolution with node branch archive," Computers & Industrial Engineering, vol. 156, Article ID: 107290, Jun. 2021.

[29]       R. R. Sahoo and M. Ray, "Forest optimization-based test case generation for multiple paths with metamorphic relations," International J. of Applied Metaheuristic Computing,
vol. 13, no. 1, pp. 1-18, Jan. 2022.

[30]       F. Feyzi and S. Parsa, "Bayes‐TDG: effective test data generation using Bayesian belief network: toward failure‐detection effectiveness and maximum coverage," IET Software, vol. 12, no. 3, pp. 225-235, Jun. 2018.

[31]       M. Esnaashari and A. H. Damia, "Automation of software test data generation using genetic algorithm and reinforcement learning," Expert Systems with Applications, vol. 183, Article ID: 115446, Nov. 2021.

[32]       M. Malkauthekar, "Analysis of euclidean distance and manhattan distance measure in face recognition," in 3rd Int. Conf. on Computational Intelligence and Information Technology, pp. 503-507, Chennai, India, 27 Jul. 2013.

[33]       Y. Duan, et al., "CAPSO: chaos adaptive particle swarm optimization algorithm," IEEE Access, vol. 10, pp. 29393-29405, 2022.

[34]       P. Trojovský and M. Dehghani, "Pelican optimization algorithm: a novel nature-inspired algorithm for engineering applications," Sensors, vol. 22, no. 3, Article ID: 855, 2022.

[35]       S. H. S. Moosavi and V. K. Bardsiri, "Poor and rich optimization algorithm: a new human-based and multi populations algorithm," Engineering Applications of Artificial Intelligence, vol. 86, pp. 165-181, Nov. 2019.

[36]       S. Zhao, T. Zhang, S. Ma, and M. Chen, "Dandelion optimizer: a nature-inspired metaheuristic algorithm for engineering applications," Engineering Applications of Artificial Intelligence, vol. 114, Article ID: 105075, Sept. 2022.

[37]       I. Fister, I. Fister Jr, X. S. Yang, and J. Brest, "A comprehensive review of firefly algorithms," Swarm and Evolutionary Computation, vol. 13, pp. 34-46, Dec. 2013.

مرضیه سپهوند تحصيلات خود را در مقطع كارشناسي رشته نرم افزار کامپیوتر در سال ۱۳۸۹ از دانشکده تربیت دبیر شریعتی تهران و  مقطع كارشناسي ارشد نرم افزار در سال‌ ۱۴۰۲ از دانشگاه آزاد اسلامی واحد خرم آباد ادامه داد ،  از دهه ۱۳۸۰ تا کنون دبیر آموزش و پرورش و زمینه تدریس ایشان دروس هنرستان رشته نرم­افزار می باشد، زمينه‎هاي تحقيقاتي مورد علاقه ايشان عبارتند از: آزمون نرم­افزار و مهندسي نرم­افزار.

 

 

 

 

 

مجتبی صالحی در سال ۲۰۰۷ م. مدرک کارشناسی مهندسی نرم‌افزار را از دانشگاه آزاد اسلامی دریافت نمود. وی سپس در سال ۲۰۱۰ م. موفق به اخذ مدرک کارشناسی ارشد در رشته مهندسی کامپیوتر دانشگاه آزاد اسلامی شد. ایشان هم‌اکنون دانشجوی دکتری مهندسی کامپیوتر در دانشگاه آزاد اسلامی می­باشد. زمینه‌های پژوهشی وی عمدتاً حول محور توسعه و بهبود روش‌ها و تکنیک‌های آزمون نرم­افزار است.

 

 

 

 

 

 

 

[1] این مقاله در تاریخ 3 ارديبهشت ماه 1403 دریافت و در تاریخ 3 مهر ماه 1403 بازنگری شد.

مرضیه سپهوند، گروه کامپیوتر، واحد خرم‌آباد، دانشگاه آزاد اسلامی، خرم‌آباد، ايران، (email: marzieh.sepahvand@gmail.com).

مجتبی صالحی (نویسنده مسئول)، گروه کامپیوتر، واحد خرم‌آباد، دانشگاه آزاد اسلامی، خرم‌آباد، ايران، (email: mo.salehi@iau.ac.ir).

[2] . All Finite Path Coverage

[3] . Jaccard

[4] . State

[5] . Action

[6] . QLearning

[7] . Qtable

[8] . Reward

[9] . Iguana

[10] . Loop

[11] . Conditions

[12] . Success Rate

[13] . Flag

[14] . Q-Learning-Based Coati Optimization Algorithm

[15] . Quadratic Equation

 


مقالات مرتبط

حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات رایمگ است.
حق نشر © 1404-1396

صفحه اصلی| عضویت/ ورود| درباره رایمگ| تماس با ما|
[English] [العربية] [en] [ar]