یک الگوریتم ژنتیک بهبودیافته با گوناگونی و جستجوی محلی برای حل مسئله مکان یابی بدون ظرفیت هاب با تخصیص تکی

هدف این مقاله ارایه یک الگوریتم ژنتیک بهبودیافته برای حل مسئله مکان یابی بدون ظرفیت هاب با تخصیص تکی است. روش های پیشین حل مسئله کمتر به گوناگونی جواب ها در جمعیت توجه داشته اند و به دلیل عدم تنوع کافی در عملگرهای جهش تنها در برخی اجراها عملکرد مطلوبی دارند و در سایر اجراها در بهینه محلی گرفتار می شوند.

 روش پیشنهادی از عملگرهای ژنتیک مناسب برای افزایش گوناگونی جمعیت و از جستجوی همسایگی محلی در اطراف بهترین جواب برای افزایش سرعت همگرایی استفاده می کند. استفاده از عملگرهای جهش هاب در کنار عملگرهای جهش تخصیص در الگوریتم پیشنهادی باعث کاوش بهتر فضای جستجو، افزایش کارایی و دستیابی به جواب بهینه در اکثر اجراها در مسایل با اندازه بزرگ شد. همچنین، جستجوی همسایگی محلی در اطراف بهترین جواب، باعث همگرایی سریع تر روش پیشنهادی شد و زمان حل مسئله را درمجموع برای مسایل بزرگ کاهش داد.

 ارزیابی روش پیشنهادی و الگوریتم پایه روی مجموعه داده پست استرالیا (AP) نشان داد که بهبودهای انجام شده ضمن حفظ سرعت اجرا، کارایی الگوریتم ژنتیک را در دستیابی به جواب بهینه برای مسایلی به بزرگی 200 گره از %2 به بیش از %85 افزایش می دهد.

 این مطالعه نشان داد که الگوریتم های فرا ابتکاری و نسخه های بهبودیافته آن ها می توانند روش های مناسبی برای حل انواع مسایل مکان یابی هاب در زمان کوتاه و محدود باشند