الگوریتم ممتیک چیست؟

الگوریتم ممتیک چیست؟

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

شکل 1: بکارگیری دانش در چرخه تکامل

دیدگاه های مختلف الگوریتم ممتیک:

1.     الگوریتم ممتیک لامارکی:

لامارک یک زیست شناس قبل از داروین بوده است که معتقد است که تجربه ی پدران از طریق ژن به فرزندان منتقل می گردد. در الگوریتم ممتیک با الهام گرفتن از این ایده پاسخ بهبود یافته شده پس از جستجوی محلی جایگزین کروموزوم (راه حل) اولیه می شود.

2.     الگوریتم ممتیک بالدوینی:

بالدوین یک فیلسوف و روان شناس بعد از داروین است که معتقد به عدم امکان انتقال تجربه از طریق ژن می باشد. فقط تجربیات از یک فرد به فرد یا افراد دیگری آموزش و تقلید می شوند. الگوریتم ممتیک با الهام گرفتن از این ایده برازش پاسخ بهبود یافته شده از طریق فرآیند جستجوی محلی جایگزین برازش کروموزوم (راه حل) اولیه می شود. در این روش با توجه به جستجوی محلی استفاده شده، در یک شعاع همسایگی برای یک پاسخ جواب بهینه را می بابد و فقط برازشش را در یک رشته ای از کروموزوم ها به نام مم نگهداری می کند.(شکل2) در این روش راه حل ها جایگزین راه حل های فعلی نمی شوند. فقط یک دید از همسایگان برای هر پاسخ داده می شود تا در تصمیم گیری ها برای انتخاب کروموزوم ها برای تولید مثل دخالت داشته باشد. از طرفی خودِ ژن ها هم به طور مستقیم در تولید مثل مشارکت دارند.

شکل 2: نمودار یک رشته کروموزوم همراه با مم در الگوریتم ممتیک بالدوینی

همان طور که در شکل 3 نشان داده شده است نظریه لامارک بر روی کل قله انتخاب شده بهینه محلی ایجاد کرده است. ولی در نظریه بالدوینی فقط روی برازش بهینه محلی را اعمال کرده است.

شکل 3: اعمال نظریه لامارک و بالدوین برای یک مسئله فرضی

3.     الگوریتم متالامارکی:

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

مفهوم اکتشاف و بهره وری در الگوریتم های جستجو ممتیک لامارکی و بالدوینی

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

[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.