مقایسه الگوریتم ژنتیک و ممتیک

مقایسه الگوریتم ژنتیک و ممتیک

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

الگوریتم ممتیک با کمک گرفتن از ایده "مم" و پیاده کردن این مفهوم در جستجوهای محلی در ارائه جواب های فعلی در هر نسل سعی بر بهبود محلی این جواب ها می نماید حاصل این عملیات سرعت و کارائی بهتر در فرآیند جستجو می باشد. یکی از ایرادات الگوریتم های تکاملی بدون جستجوی محلی عدم بکارگیری دانش در فرآیند جستجو می باشد. الگوریتم های ترکیبی از جمله ممتیک این ویژگی را دارند که فرآیند جستجوی محلی آنها همراه با دانش می باشد.

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

 

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

جدول 1: مقایسه الگوریتم های ژنتیک و جستجوی محلی از نظر مفاهیم استخراج و اکتشاف

نام الگوریتم	اکتشاف(Exploration)	استخراج(Exploitation)	سرعت همگرائی
الگوریتم ژنتیک	زیاد	کم	کم
جستجوی محلی	کم	زیاد	زیاد

[1]:http://cdn.persiangig.com/download/Ja08GbstgK/e7fc60b9269830ff24ab321f2162204eea11.pdf/dl.

[2]: http://cdn.persiangig.com/download/5IBjSeZD9W/Alizadeh-Meybodi-Rezvanian-CSI Journal-2013.pdf/dl.

[3]: http://cdn.persiangig.com/download/ldEkhm5NOF/Report-Memetic-Algorithms.pdf/dl.