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

مسئله تخصیص درجه دو ١ یکی از مهمترین مسائل سخت بهینه سازی ترکیبیاتی است و جزو دسته مسائل سخت غیرچند جمله ای ‐ زمانی ٢ بشمارمیرود.بسیاری از مسائل دنیای واقعی پس از فرمولبندی به شکل این مسئله تبدیل میگردند.از جمله این مسائل ،مسئله مکانیابی ،مسئله استقرار تاسیسات،محل استقرار اتاق عمل ، محل برپایی غرفه های نمایشگاه ها و.... . در میان روشهای ابتکاری و فراابتکاری برای حل این مسئله ،روش الگوریتم ژنتیک تقریبا متداولترین آنها میباشد.آنچه در این مقاله ارائه میشود ،الگوریتمی حریصانه ٣ است که با بهسازی و اعمال تغییراتی در فرایند ا و الگوریتم بدست آمده است .این تغییرات عبارتند از : ۱‐ روش ابتکاری با ساختار تصادفی ۲‐الگوی ترکیب ٤ جدید ۳‐الگوی مهاجرت ٥ هدفمند ۴‐ بهینه سازی موضعی زیر مجموعه ای از جمعیت ۵‐ایجاد فضای رقابت در جمعیت های مختلف

کلیدواژه ها:

مسئله تخصیصدرجه دو ، الگوریتم ژنتیک ، الگوریتم حریصانه ، مسئله سخت ، شبیه سازی تبرئیدی ، جستجوی ممنوع