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

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

Keywords:

تست جامع , انفجار ترکیبی , آزمون t-ستونی , آرایه پوشش کمینه , الگوریتم تکامل تفاضلی