ﺗﻮﻟﯿﺪ آراﯾﻪ ﭘﻮﺷﺶ ﮐﻤﯿﻨﻪ ﺑﺎ اﺳﺘﻔﺎده از اﻟﮕﻮرﯾﺘﻢ ﺗﮑﺎﻣﻞ ﺗﻔﺎﺿﻠﯽ ﺗﻄﺒﯿﻘﯽ ﻣﺒﺘﻨﯽ ﺑﺮ ﺗﺎرﯾﺨﭽﻪ ﻣﻮﻓﻘﯿﺖ و ﮐﺎﻫﺶ ﺧﻄﯽ اﻧﺪازه ﺟﻤﻌﯿﺖ

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

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

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.