تفاوت الگوریتم های ابتکاری و فراابتکاری

برای اینکه تفاوت الگوریتم های ابتکاری (هیوریستک) و فراابتکاری (متاهیوریستیک) را بهتر درک کنیم، ابتدا بهتر است با یک سری مفاهیم آشنا شویم.

الگوریتم های جستجو و فرآیند بهینه سازی

یکی از روش های حل مسئله، تبدیل آن به یک فرآیند جستجو است. یعنی اینکه مسئله را به صورت مجموعه ای از حالات (فضای حالت) در نظر بگیریم که در آن از یک حالت اولیه شروع کرده و به دنبال رسیدن به یک حالت خاص باشیم. مسائل بهینه سازی معمولا از این نوع هستند. به عنوان مثال در مسئله فروشنده دوره گرد ما به دنبال یافتن مسیری بین کل شهرها هستیم که کمترین مسافت را داشته باشد. مسیری که با شروع از یک شهر خاص و عبور از تمام شهرها دوباره به شهر اول برگردد.

اشتباه نکنید؛ اینجا شهرها حالات مسئله ما را تشکیل نمی دهند. با فرض اینکه n شهر داشته باشیم، هر جایگشت از کل شهر ها می تواند یک حالت از مسئله باشد و اندازه فضای حالت !n خواهد بود. حال ما باید از بین کل حالات دنبال مسیری باشیم که کمترین مجموع فاصله را داشته باشد. یک راه حل این است که بیاییم تمام مسیرهای موجود را شناسایی کنیم و مجموع فاصله هر کدام را محاسبه کنیم. در نهایت هر مسیری که کمترین فاصله را داشته باشد به عنوان مسیر بهینه در نظر گرفته شود. اما می دانید که اگر n زیاد شود، این راه حل اصلا قابل اجرا روی هیچ کامپیوتری نخواهد بود. زیرا ابر کامپیوترها نیز برای چنین مسئله ای از لحاظ حافظه و حجم پردازش، کم خواهند آورد. اینجاست که به سراغ الگوریتم های ابتکاری و فراابتکاری می رویم.

الگوریتم های ابتکاری

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

الگوریتم های فراابتکاری

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