روش جدیدجهت بهبود کارایی جستجوی محلی سریع در حل مسایل تخصیص درجه دو بمنظوراکتشاف بهینه فضای حالت

مساله تخصیص درجه دوم یکی از مسایل بهینه سازی ترکیبی است که به اختصاص تعدادی تسهیل به تعدادی مکان می پردازد وهدف به حداقل رساندن هزینه است.این مسیله یکی از مسایل با درجه پیچیدگی سخت می باشد که الگوریتمهای قطعی تنها قادر به حل نمونه های کوچکتر این مسیله می باشند. روش جستجوی محلی سریع از روشهایی است که برای حل اینگونه مسایل کاربرد زیادی دارد . اماباوجود قابلیت جستجوی فضای پهناورتر در این میان دیدگاه خاصی برای جستجوی بهتر ارایه نشده است که منجر به کاهش کارایی روش می شود یعنی درمواردی که فاصله بین نقاط جستجو شده دارای گپ زیادبود ازاین طریق مناطقی ازمحدوده جستجو را که بررسی نشده اندتا حدامکان پیدا نموده وموردارزیابی قرارداد. هدف ارایه روشی است که بتوان دیدشهودی نسبت به فضای جستجو پیدانمود. روش پیشنهادی جدیدقادر می باشد میانگین بهترین جوابها درالگوریتم جستجوی محلی سریع را از 65/0 درصد به 26/0 درصد کاهش داده و به این ترتیب اکتشاف بهتری از فضای جستجورا داشته باشد. بررسی کارایی این روش روی توابع آزمون استاندارد و مقایسه آن با الگوریتم جستجوی محلی سریع بیانگر کیفیتمطلوب و برتری آن میباشد که نتایج خوبی را بر روی بازه وسیعی از مسایل جایگشتی ارایه میکند. مساله تخصیص درجه دوم یکی از مسایل بهینه سازی ترکیبی است که به اختصاص تعدادی تسهیل به تعدادی مکان می پردازد وهدف به حداقل رساندن هزینه است.این مسیله یکی از مسایل با درجه پیچیدگی سخت می باشد که الگوریتمهای قطعی تنها قادر به حل نمونه های کوچکتر این مسیله می باشند. روش جستجوی محلی سریع از روشهایی است که برای حل اینگونه مسایل کاربرد زیادی دارد . اماباوجود قابلیت جستجوی فضای پهناورتر در این میان دیدگاه خاصی برای جستجوی بهتر ارایه نشده است که منجر به کاهش کارایی روش می شود یعنی درمواردی که فاصله بین نقاط جستجو شده دارای گپ زیادبود ازاین طریق مناطقی ازمحدوده جستجو را که بررسی نشده اندتا حدامکان پیدا نموده وموردارزیابی قرارداد. هدف ارایه روشی است که بتوان دیدشهودی نسبت به فضای جستجو پیدانمود. روش پیشنهادی جدیدقادر می باشدمیانگین بهترین جوابها درالگوریتم جستجوی محلی سریع را از 65/0 درصد به 26/0 درصد کاهش داده و به این ترتیب اکتشاف بهتری از فضای جستجورا داشته باشد. بررسی کارایی این روش روی توابع آزمون استاندارد و مقایسه آن با الگوریتم جستجوی محلی سریع بیانگر کیفیتمطلوب و برتری آن میباشد که نتایج خوبی را بر روی بازه وسیعی از مسایل جایگشتی ارایه میکند.

کلیدواژه ها:

اکتشاف ، الگوریتمهای متاهیوریستیک ، جستجوی فضای حالت ، جستجوی محلی سریع ، مسیله تخصیص درجه دو