الگوریتم ممتیک (Memetic) بر اساس الگوهای رفتاری

مدرس: مسعود کاویانی

MasoudKaviani.ir

الگوریتم ممتیک یا همان Memetic Algorithm را نمی‌توان یک الگوریتم ثابث فرض کنید. در واقع الگوریتم‌های ممتیک را می‌توان از دسته‌ی الگوریتم‌ها داسنت که به نوعی بهبود یافته‌ی الگوریتم ژنتیک (Genetic Algorithm) هستند. در این درس ما به یکی از معروف‌ترین این الگوریتم‌ها اشاره می‌کنیم. این الگوریتم در واقع ترکیبی از الگوریتم ژنتیک و الگوریتم جستجوی تپه‌نوردی است که در دروس گذشته‌ی دوره‌ی جاری به این دو الگوریتم پرداختیم.

توصیه می‌کنم اگر درس الگوریتمِ ژنتیک را نخوانده‌اید این کار را انجام دهید، زیرا این درس بر پایه‌ی مثالِ درس الگوریتم ژنتیک و همچنین درس الگوریتم تپه‌نوردی بنا نهاده شده است.

الگوریتم ژنتیک را به یاد بیاورید. به صورت خلاصه، این الگوریتم با تولید افراد نسل‌های مختلف و ترکیب (Crossover) و جهش (Mutation) در نسل‌ها، می‌توانست به یک حالت بهینه‌ی خوب دست پیدا کند. اما جالب این‌جاست در الگوریتم ژنتیک هر کدام از افراد (ژن‌ها) تلاشی برای بهبود خود نمی‌کنند. در واقع در الگوریتمِ ژنتیک، هر کدام از افراد (ژن‌ها) در نسل‌های مختلف فقط منتظر عملیات Crossover و Mutation هستند تا شاید بهبود حاصل شود، و نکته‌ی اصلی در الگوریتم ممتیک در این‌جا نهفته است. این الگوریتم مانند الگوریتم ژنتیک عمل می‌کند با این تفاوت که هر کدام از افراد (ژن‌ها) بعد از تولد (به وجود آمدن از نسل قبلیِ خود) به بهبود وضعیت خویش به صورت نسبی و محلی می‌پردازند. آن‌ها این کار با الگوریتم تپه‌نوردی (Hill Climbing) انجام می‌دهند.

اگر بخواهیم با مثالی شهودی الگوریتم ممتیک را متوجه شویم، به این صورت است که فرض کنید افراد مختلف (همان ژن‌ها) در جهان گسترده شده‌اند و به دنبال رشد و شکوفایی هستند. آن‌ها با عملیاتی مانند تبادل فرهنگی (Crossover در الگوریتم ژنتیک) قسمتی از فرهنگ خود را می‌دهند و قسمتی از فرهنگ دیگران را دریافت می‌کنند تا با ترکیب آن فرهنگ با فرهنگِ خود، بتوانند شاید به یک حالت بهینه‌تر و رشد و شکوفایی بیشتر دست پیدا کنند. حالا آن‌هایی که بهینه‌تر از بقیه هستند شانس بیشتری برای زنده ماندن و سپس ازدواج با بقیه‌ی بازماندگان دارند! این افرادی که زنده مانده‌اند با افراد دیگر از نقاط جغرافیاییِ دیگر ازدواج کرده و فرزندانی را به وجود می‌آورند و با این‌کار امید دارند که فرزندانشان بهتر از خودشان شوند. تا این‌جای کار الگوریتم ژنتیک بود. الگوریتم ممتیک مانند این است که فرزند متولد شده، در مکانی که قرار دارد، به دنبال بهبود و رشد و شکوفایی خویش (بدون توجه به ترکیب و جهش) باشد. مثلاً خودش به صورت حریصانه هر روز خود را بهبود دهد. سپس دوباره به چرخه‌ی ژنتیک برگردد و با عملیات Crossover و Mutation با کمک هم نسل‌های خود، فرآیند بهبود را در ادامه دهد.

شکل زیر می‌تواند در درکِ مفهوم الگوریتم ممتیک (Memetic Algorithm) بیشتر کمک کند:

در شکل بالا، هر کدام از نقاط قرمز یک فرد (یک ژن – یعنی یک راه‌حل) در الگوریتم ژنتیک هستند. الگوریتم ممتیک این افراد با استفاده از الگوریتم تپه‌نوردی، به دنبال پیدا کردن یک بهینه‌ی محلی برای خود هستند تا بتواند خود را بهبود دهند. در واقع اگر هر فرد را یک راه‌حل در نظر بگیریم، باید هر کدام از آن‌ها، راه‌حل‌های همسایه‌ی خود را (با کمی تغییر در وضعیت فعلی) پیدا کنند و از بین آن‌ها بهترینشان را انتخاب کنند (با ساختن راه‌حل‌های همسایه در درس الگوریتم جستجوی ممنوعه آشنا شدید). بعد از بهبود و رسیدن به بهینه‌ی محلی (نقاط قله‌ی محلی)، دوباره الگوریتم عملیات Crossover و Mutation در ژنتیک را برای هر فرد ادامه می‌دهند.