fa ارائه یک الگوریتم ابتکاری جدید برای حل مساله مکان‌یابی پوشش کلی تخصصي Special پژوهشي Research <p dir="RTL">مساله پوشش مجموعه، از دسته مسائل سخت محسوب می‌شود که در کاربردهای مختلفی مانند سیستم اورژانس، مکانیابی تسهیلات خرده<span dir="LTR">‌</span>فروشی، بیمارستان<span dir="LTR">‌</span>ها، واحدهای دفاعی کشوری، پایگاه<span dir="LTR">‌</span>های نظامی، دستگاه<span dir="LTR">‌</span>های رادار و ... مورد استفاده قرار می‌گیرد. هدف از پوشش مجموعه، یافتن یک زیرمجموعه به گونه‌ایست که اجتماع اعضای این زیر مجموعه، کل مجموعه را پوشش دهد. در این مقاله یک الگوریتم ابتکاری برای حل مساله پوشش مجموعه پیشنهاد شده است. در الگوریتم پیشنهادی، برای هر یک از رئوس گراف، یک مقدار منسوب به میزان بهبود محاسبه می‌شود که بر اساس آن تصمیم برحضور یا عدم حضور راس متناظر در مجموعه پوشش گرفته می‌شود. با توجه به تخصیص تسهیل و اثر متقابل بر پوشش یا عدم پوشش رئوس مجاور، در هر مرحله مقادیر بهبود به روز می‌شود و این روند به طور تکراری ادامه می&shy;یابد تا آنکه در خاتمه‌ی الگوریتم، مجموعه پوشش نزدیک به بهینه بدست آید. جهت ارزیابی الگوریتم پیشنهادی در مقایسه با سایر روش‌های متداول، یک الگوریتم شبیه‌سازی تبرید جهت حل ارائه شد و پارامترهای آن به روش تاگوچی تنظیم گردید. نتایج بدست آمده در مقایسه با نتایج بدست آمده از الگوریتم شبیه‌سازی تبریدی برای آزمایش‌های مختلف حاکی از موفقیت الگوریتم پیشنهادی به ویژه در مسائل با ابعاد بالا در مهار رشد زمان حل از <em><span dir="LTR">O(2ⁿ)</span></em> به زمان حل چند جمله&shy;ای <em><span dir="LTR">O(2n)</span></em> است.</p> <p class="EnglishAbstract" style="margin-top:6.0pt;margin-right:0cm;margin-bottom: 6.0pt;margin-left:0cm">Set covering problem has many applications such as emergency systems, retailers&rsquo; facilities, hospitals, radar devices, and military logistics, and it is considered as Np-Hard problems. The goal of set covering problem is to find a subset such that :::::::::union::::::::: of the subset members covered the whole set. In this paper, we present a new heuristic algorithm to solve the set covering problem. In the heuristic algorithm, the amounts of improvement are calculated for any of vertices in the graph. Based on the improvement we consider vertices in the subset. The amounts of improvement updated in each iteration to find near optimal solution. A simulated annealing algorithm, which its parameters tuned with Taguchi method, is presented to compare with our suggested heuristic algorithm. The computational results show that the heuristic algorithm works better than the simulated annealing algorithm in both quality of solution, and time view.</p> مساله پوشش, الگوریتم ابتکاری, الگوریتم شبیه‌سازی تبرید, روش تاگوچی Covering problem, Heuristic algorithm, Simulated annealing algorithm, Taguchi method 69 88 http://jamlu.lahijan.iau.ir/browse.php?a_code=A-11-1046-1&slc_lang=fa&sid=1 Sattar Rajabpour sanati ستار رجب پور صنعتی sanati.sattar@gmail.com 10031947532846005031 10031947532846005031 No Iran University of Science and Technology دانشگاه علم و صنعت ایران Ali Naimi Sadigh علی نعیمی صدیق naimi@irandoc.ac.ir 10031947532846005032 10031947532846005032 Yes Iranian Research Institute for Information Science and Technology (IRANDOC) پژوهشگاه علوم و فناوری اطلاعات ایران (ایرانداک)