ترکیب الگوریتم های ژنتیک و بهینه سازی لانه مورچگان برای حل مساله انتخاب عرضه کننده

ترکیب الگوریتم‌های ژنتیک و بهینه‌سازی لانه مورچگان برای حل مساله انتخاب عرضه کننده

الگوریتم ژنتیک در سال 1980 بر اساس نظریه تکاملی داروین برای حل مسائل بهینه‌سازی ابداع شد. در واقع الگوریتم ژنتیک بر اساس اصل " ادامه حیات بهترین‌ها " و " تکثیر نوع برتر" پی ریزی شده است. عملگرهای اصلی الگوریتم ژنتیک شامل: کدگذاری، انتخاب، عملگر ادغام و عملگر جهش است. عملکرد الگوریتم ژنتیک در چند تکرار اول بسیار خوب است اما با ادامه روند و افزایش تعداد تکرارها با انبوهی از جواب‌ها و نتایج زائد رو به رو می‌شویم که باعث افزایش تعداد تکرارها تا رسیدن به جواب بهینه می‌شود. روش بهینه‌سازی کلونی مورچگان بر گرفته از حرکت واقعی مورچگان در طبیعت برای یافتن غذا است که در پایان نامه دکترای مارکو دوریگو در سال 1992 تحت عنوان سیستم مورچگان برای اولین بار معرفی شد.

الگوریتم معرفی شده توسط دوریگو بر اساس دو اصل پایه‌ای 1- تزریق و تبخیر فرومون 2- گرایش احتمالی مورچگان به مسیر پر فرومون بنا شده است. الگوریتم بهینه‌سازی لانه مورچگان به علت عدم وجود فرومون در تکرارهای ابتدایی دارای یک سرعت همگرایی کُند است. اما با ادامه روند جستجو و افزایش میزان غلظت فرومون ریخته شده عملکرد بسیار خوبی در مراحل پایانی دارد. الگوریتم ترکیبی با ترکیب دو الگوریتم ژنتیک و بهینه‌سازی کلونی مورچگان، از مزایای هر دو الگوریتم استفاده می‌کند.

در الگوریتم ترکیبی ابتدا از چند تکرار الگوریتم ژنتیک استفاده می‌کنیم سپس کروموزوم به دست آمده از الگوریتم ژنتیک را به عنوان جواب ابتدایی الگوریتم مورچگان در نظر می‌گیریم و تکرارهای بعدی تا رسیدن به جواب بهینه را با الگوریتم مورچگان ادامه می‌دهیم. الگوریتم ترکیبی از نظر سرعت همگرایی و کارآیی، بهتر از الگوریتم‌های ژنتیک و بهینه‌سازی لانه مورچگان عمل می‌کند.