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

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

نویسندگان

1 استادیار، دانشکده فناوری اطلاعات و مهندسی کامپیوتر، دانشگاه شهیدمدنی آذربایجان، تبریز، ایران

2 دانشیار، دانشکده فنی‌مهندسی، دانشگاه اراک، ایران

3 دکتری کامپیوتر، دانشکده فنی‌مهندسی، دانشگاه اراک، ایران

چکیده

تست جامع سیستم­های نرم­افزاری با تعداد زیادی پارامتر ورودی و ترکیبات بین آنها اغلب باعث وقوع مشکل انفجار ترکیبی می­شود. تست ترکیبی t-ستونی تکنیکی است که با تولید آرایه­ای از نمونه­های تست به پوشش حداکثری ترکیبات ما بین پارامترهای ورودی می­پردازد. تولید آرایه پوشش کمینه یک مساله بهینه­سازی است که الگوریتم­های فراابتکاری زیادی از جمله بهینه­سازی مبتنی بر آموزش و یادگیری، ازدحام توده ذرات، ژنتیک و الگوریتم جستجوی فاخته برای حل آن به کار رفته­­اند. اگر چه این الگوریتم­ها توانسته­اند آرایه­های پوشش با اندازه­های کوچک‌تر را تولید کنند ولی هنوز کمینه­سازی کامل انجام نشده است. در این مقاله، یک استراتژی جدیدی برپایه الگوریتم تکامل تفاضلی تطبیقی مبتنی بر تاریخچه موفقیت و کاهش خطی اندازه جمعیت (معروف به LSHADE) که جزو برندگان کنگره IEEE در محاسبات تکاملی است، جهت تولید آرایه پوشش کمینه ارائه می­کنیم. نتایج آزمون فریدمن نشان می­دهند که استراتژی LSHADE دارای اولین رتبه از نظر معیارهای تولید آرایه پوشش با کمترین اندازه و کمترین تعداد متوسط فراخوانی­های الگوریتمی در مقایسه با استراتژی­های مبتنی بر ریاضی از جمله TConfig، حریصانه از جمله IPOG، Jenny وPICT و فراابتکاری از جمله GS، TLBO،HC-BAT، PSTG، WOA، BAPSO و GSTG است. در حالی­که، از نظر معیارهای تعداد متوسط ارزیابی­های تابع محاسبه وزن و متوسط زمان اجرا، این استراتژی بعد از استراتژی GS، دارای اولین رتبه است. ضمناً، نمودارهای همگرایی سرعت همگرایی بالایِ این استراتژی را در مقایسه با استراتژی­های فراابتکاری دیگر تایید می­کنند.

کلیدواژه‌ها

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

Minimum Covering Array Generation Using Success-History and Linear Population Size Reduction based Adaptive Differential Evolution Algorithm

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

  • E. Pira 1
  • V. Rafe 2
  • S. Esfandyari 3
1 Faculty of Information Technology and Computer Engineering, Azarbaijan Shahid Madani University, Tabriz, Iran
2 Department of Computer Engineering, Faculty of Engineering, Arak University, Arak, Iran
3 Department of Computer Engineering, Faculty of Engineering, Arak University, Arak, Iran
چکیده [English]

Exhaustive testing of software systems with a large number of input parameters and combinations between them often causes the problem of combinatorial explosion. Combinatorial t-way testing is a technique that generates an array of test cases to maximize combinations covering of between input parameters. Generating a minimum covering array is an optimization problem that many strategies based on metaheuristic algorithms such as teaching and learning based optimization, particle swarm optimization, and genetic and cuckoo search algorithms have been used for solving it. Although these strategies have produced smaller covering arrays, complete minimization has not yet been performed. In this paper, we propose a new strategy based on the success-history and linear population size reduction based adaptive differential evolution algorithm (so-called LSHADE), which is one of winners of IEEE CEC competitions, to generate minimum covering array. The results of Friedman mean rank show that the LSHADE strategy has the first rank in terms of generating the covering array with the lowest size and the lowest average number of algorithmic calls, compared to mathematics based strategies such as TConfig, greedy strategies such as IPOG, Jenny and PICT and meta-heuristics such as GS, TLBO, HC-BAT, PSTG, WOA , BAPSO and GSTG. While, in terms of the average number of fitness function evaluations and the average runtime, this strategy has the first rank after the GS strategy. Moreover, the convergence diagrams confirm the high convergence speed of this strategy compared to the other meta-heuristic strategies.

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

  • Exhaustive testing
  • combinatorial explosion
  • t-way testing
  • minimum covering array
  • differential evolution

مراجع

[1] B. S. Ahmed, T. S. Abdulsamad, and M. Y. Potrus, "Achievement of minimized combinatorial test suite for configuration-aware software functional testing using the cuckoo search algorithm," Information and Software Technology, vol. 66, pp. 13-29, 2015.
[2] L. Luo, "Software testing techniques," Institute for software research international Carnegie mellon university Pittsburgh, PA, vol. 15232, no. 1-19, p. 19, 2001.
[3] D. R. Kuhn and M. J. Reilly, "An investigation of the applicability of design of experiments to software testing," in 27th Annual NASA Goddard/IEEE Software Engineering Workshop, 2002. Proceedings.: IEEE, pp. 91-95, 2002.
[4] C. Yilmaz, M. B. Cohen, and A. A. Porter, "Covering arrays for efficient fault characterization in complex configuration spaces," IEEE Transactions on Software Engineering, vol. 32, no. 1, pp. 20-34, 2006.
[5] A. W. Williams, "Determination of test configurations for pair-wise interaction coverage," in Testing of Communicating Systems: Springer, pp. 59-74, 2002.
[6] A. W. Williams and R. L. Probert, "A practical strategy for testing pair-wise coverage of network interfaces," in Proceedings of ISSRE'96: 7th International Symposium on Software Reliability Engineering: IEEE, pp. 246-254, 1996.
[7] C. Nie, H. Wu, X. Niu, F.-C. Kuo, H. Leung, and C. J. Colbourn, "Combinatorial testing, random testing, and adaptive random testing for detecting interaction triggered failures," Information and Software Technology, vol. 62, pp. 198-213, 2015.
[8] C. Nie and H. Leung, "A survey of combinatorial testing," ACM Computing Surveys (CSUR), vol. 43, no. 2, pp. 1-29, 2011.
[9] Y. Lei, R. Kacker, D. R. Kuhn, V. Okun, and J. Lawrence, "IPOG: A general strategy for t-way software testing," in 14th Annual IEEE International Conference and Workshops on the Engineering of Computer-Based Systems (ECBS'07), IEEE, pp. 549-556, 2007.
[10] Y. Lei, R. Kacker, D. R. Kuhn, V. Okun, and J. Lawrence, "IPOG/IPOG‐D: efficient test generation for multi‐way combinatorial testing," Software Testing, Verification and Reliability, vol. 18, no. 3, pp. 125-148, 2008.
[11] M. Forbes, J. Lawrence, Y. Lei, R. N. Kacker, and D. R. Kuhn, "Refining the in-parameter-order strategy for constructing covering arrays," Journal of Research of the National Institute of Standards and Technology, vol. 113, no. 5, p. 287, 2008.
[12] Y.-W. Tung and W. S. Aldiwan, "Automating test case generation for the new generation mission software system," in 2000 IEEE Aerospace Conference. Proceedings (Cat. No. 00TH8484), vol. 1: IEEE, pp. 431-437, 2000.
[13] K. Z. Zamli, M. F. Klaib, M. I. Younis, N. A. M. Isa, and R. Abdullah, "Design and implementation of a t-way test data generation strategy with automated execution tool support," Information Sciences, vol. 181, no. 9, pp. 1741-1758, 2011.
[14] B. S. Ahmed, M. A. Sahib, and M. Y. Potrus, "Generating combinatorial test cases using Simplified Swarm Optimization (SSO) algorithm for automated GUI functional testing," Engineering Science and Technology, an International Journal, vol. 17, no. 4, pp. 218-226, 2014.
[15] J. Czerwonka, "Pairwise testing in the real world: Practical extensions to test-case scenarios," Microsoft Corporation, Software Testing Technical Articles, 2008.
[16] B. Jenkins, "Jenny download web page," Bob Jenkin’s website, 2005.
[17] S. Esfandyari and V. Rafe, "A tuned version of genetic algorithm for efficient test suite generation in interactive t-way testing strategy," Information and Software Technology, vol. 94, pp. 165-185, 2018.
[18] H. Zakaria, K. Zamli, and F. Din, "Hybrid Migrating Birds Optimization Strategy for t-way Test Suite Generation," in Journal of Physics: Conference Series, vol. 1830, no. 1: IOP Publishing, p. 012013, 2021.
[19] زهرا عباسی، سجاد اسفندیاری، وحید رافع «ساخت آرایه پوشش با استفاده از الگوریتم بهینه‌سازی مبتنی برآموزش و یادگیری»، مجله مهندسی برق دانشگاه تبریز، دوره­ی 48، شماره­ی 1، صفحه­ی 161 تا 171، بهار 1397.
[20] B. S. Ahmed, K. Z. Zamli, and C. P. Lim, "Constructing a t-way interaction test suite using the particle swarm optimization approach," International Journal of Innovative Computing, Information and Control, vol. 8, no. 1, pp. 431-452, 2012.
[21] B. S. Ahmed, K. Z. Zamli, and C. P. Lim, "Application of particle swarm optimization to uniform and variable strength covering array construction," Applied soft computing, vol. 12, no. 4, pp. 1330-1347, 2012.
[22] H. Wu, C. Nie, F.-C. Kuo, H. Leung, and C. J. Colbourn, "A discrete particle swarm optimization for covering array generation," IEEE Transactions on Evolutionary Computation, vol. 19, no. 4, pp. 575-591, 2014.
[23] Y. A. Alsariera, A. H. Al Omari, M. A. Albawaleez, Y. K. Sanjalawe, and K. Z. Zamli, "Hybridized BA & PSO t-way Algorithm for Test Case Generation," IJCSNS, vol. 21, no. 10, p. 343, 2021.
[24] D. Karaboga, "Artificial bee colony algorithm," scholarpedia, vol. 5, no. 3, p. 6915, 2010.
[25] A. K. Alazzawi, A. A. B. Homaid, A. A. Alomoush, and A. A. Alsewari, "Artificial bee colony algorithm for pairwise test generation," Journal of Telecommunication, Electronic and Computer Engineering (JTEC), vol. 9, no. 1-2, pp. 103-108, 2017.
[26] A. K. Alazzawi, H. M. Rais, and S. Basri, "Artificial bee colony algorithm for t-way test suite generation," in 2018 4th International Conference on Computer and Information Sciences (ICCOINS), IEEE, pp. 1-6, 2018.
[27] A. K. Alazzawi et al., "HABCSm: a hamming based t-way strategy based on hybrid artificial bee colony for variable strength test sets generation," arXiv preprint arXiv:2110.03728, 2021.
[28] N. Ramli, R. R. Othman, and M. S. A. R. Ali, "Optimizing combinatorial input-output based relations testing using Ant Colony algorithm," in 2016 3rd International Conference on Electronic Design (ICED), IEEE, pp. 586-590, 2016.
[29]  M. Z. Z. Ahmad, R. R. Othman, M. S. A. R. Ali, and N. Ramli, "A Self-Adapting Ant Colony Optimization Algorithm Using Fuzzy Logic (ACOF) for Combinatorial Test Suite Generation," in IOP Conference Series: Materials Science and Engineering, vol. 767, no. 1: IOP Publishing, p. 012017, 2020.
[30] وحید رافع, سجاد اسفندیاری، «راهکاری نوین جهت تولید دنباله آزمون کمینه در فرآیند آزمون نرم افزار با ترکیب الگوریتم های جستجوی تپه نوردی و جستجوی خفاش»، مجله مهندسی برق دانشگاه تبریز، دوره­ی 46، شماره­ی 3، صفحه­ی 25 تا 35،  پائیز 1395.
[31] A. A. Alsewari, L. M. Xuan, and K. Z. Zamli, "Firefly combinatorial testing strategy," in Science and Information Conference, Springer, pp. 936-944, 2018,
[32] H. N. N. Al-Sammarraie and D. N. Jawawi, "Multiple black hole inspired meta-heuristic searching optimization for combinatorial testing," Ieee Access, vol. 8, pp. 33406-33418, 2020.
[33] R. Storn and K. Price, "Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces," Journal of global optimization, vol. 11, no. 4, pp. 341-359, 1997.
[34] R. Tanabe and A. Fukunaga, "Success-history based parameter adaptation for differential evolution," in 2013 IEEE congress on evolutionary computation, IEEE, pp. 71-78., 2013,
[35] R. Tanabe and A. S. Fukunaga, "Improving the search performance of SHADE using linear population size reduction," in 2014 IEEE congress on evolutionary computation (CEC), IEEE, pp. 1658-1665, 2014.
[36] B. S. Ahmed and K. Z. Zamli, "A variable strength interaction test suites generation strategy using particle swarm optimization," Journal of Systems and Software, vol. 84, no. 12, pp. 2171-2185, 2011.
[37] J. Zhang and A. C. Sanderson, "JADE: adaptive differential evolution with optional external archive," IEEE Transactions on evolutionary computation, vol. 13, no. 5, pp. 945-958, 2009.
[38] M. Friedman, "A comparison of alternative tests of significance for the problem of m rankings," The Annals of Mathematical Statistics, vol. 11, no. 1, pp. 86-92, 1940.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار