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

تست جامع سیستم های نرم افزاری با تعداد زیادی پارامتر ورودی و ترکیبات بین آنها اغلب باعث وقوع مشکل انفجار ترکیبی می شود. تست ترکیبی t-ستونی تکنیکی است که با تولید آرایه ای از نمونه های تست به پوشش حداکثری ترکیبات ما بین پارامترهای ورودی می پردازد. تولید آرایه پوشش کمینه یک مساله بهینه سازی است که الگوریتم های فراابتکاری زیادی از جمله بهینه سازی مبتنی بر آموزش و یادگیری، ازدحام توده ذرات، ژنتیک و الگوریتم جستجوی فاخته برای حل آن به کار رفته اند. اگر چه این الگوریتم ها توانسته اند آرایه های پوشش با اندازه های کوچک‌تر را تولید کنند ولی هنوز کمینه سازی کامل انجام نشده است. در این مقاله، یک استراتژی جدیدی برپایه الگوریتم تکامل تفاضلی تطبیقی مبتنی بر تاریخچه موفقیت و کاهش خطی اندازه جمعیت (معروف به lshade) که جزو برندگان کنگره ieee در محاسبات تکاملی است، جهت تولید آرایه پوشش کمینه ارائه می کنیم. نتایج آزمون فریدمن نشان می دهند که استراتژی lshade دارای اولین رتبه از نظر معیارهای تولید آرایه پوشش با کمترین اندازه و کمترین تعداد متوسط فراخوانی های الگوریتمی در مقایسه با استراتژی های مبتنی بر ریاضی از جمله tconfig، حریصانه از جمله ipog، jenny وpict و فراابتکاری از جمله gs، tlbo،hc-bat، pstg، woa، bapso و gstg است. در حالی که، از نظر معیارهای تعداد متوسط ارزیابی های تابع محاسبه وزن و متوسط زمان اجرا، این استراتژی بعد از استراتژی gs، دارای اولین رتبه است. ضمناً، نمودارهای همگرایی سرعت همگرایی بالایِ این استراتژی را در مقایسه با استراتژی های فراابتکاری دیگر تایید می کنند.

minimum covering array generation using success-history and linear population size reduction based adaptive differential evolution algorithm

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.