تصمیم گیری و تحقیق در عملیات (Feb 2022)
یک الگوریتم ژنتیک بهبودیافته با گوناگونی و جستجوی محلی برای حل مسئله مکان‌یابی بدون ظرفیت هاب با تخصیص تکی
Abstract
هدف: هدف این مقاله ارائه یک الگوریتم ژنتیک بهبودیافته برای حل مسئله مکان‌یابی بدون ظرفیت هاب با تخصیص تکی است. روش‌های پیشین حل مسئله کمتر به گوناگونی جواب‌ها در جمعیت توجه داشته‌اند و به دلیل عدم تنوع کافی در عملگرهای جهش تنها در برخی اجراها عملکرد مطلوبی دارند و در سایر اجراها در بهینه محلی گرفتار می‌شوند.روش‌شناسی پژوهش: روش پیشنهادی از عملگرهای ژنتیک مناسب برای افزایش گوناگونی جمعیت و از جستجوی همسایگی محلی در اطراف بهترین جواب برای افزایش سرعت همگرایی استفاده می‌کند. استفاده از عملگرهای جهش هاب در کنار عملگرهای جهش تخصیص در الگوریتم پیشنهادی باعث کاوش بهتر فضای جستجو، افزایش کارایی و دستیابی به جواب بهینه در اکثر اجراها در مسائل با اندازه بزرگ شد. همچنین، جستجوی همسایگی محلی در اطراف بهترین جواب، باعث همگرایی سریع‌تر روش پیشنهادی شد و زمان حل مسئله را درمجموع برای مسائل بزرگ کاهش داد.یافته‌ها: ارزیابی روش پیشنهادی و الگوریتم پایه روی مجموعه داده پست استرالیا (AP) نشان داد که بهبودهای انجام‌شده ضمن حفظ سرعت اجرا، کارایی الگوریتم ژنتیک را در دستیابی به جواب بهینه برای مسائلی به بزرگی 200 گره از %2 به بیش از %85 افزایش می‌دهد.اصالت/ارزش افزوده علمی: این مطالعه نشان داد که الگوریتم‌های فرا ابتکاری و نسخه‌های بهبودیافته آن‌ها می‌توانند روش‌های مناسبی برای حل انواع مسائل مکان‌یابی هاب در زمان کوتاه و محدود باشند
Keywords
