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

یا  الگوریتم بهینه‌سازی حافظه

الگوریتم ممتیک که نام اصلی آن بهینه‌سازی حافظه می باشد از رفتار الگوریتم ژنتیک الهام گرفته‌شده است. این الگوریتم از الگوریتم‌های بسیار کارآمد در حل مسائل بهینه‌سازی ترکیبی است. الگوریتم ممتیک در حوزه‌های مختلف مسائل بهینه‌سازی کاربرد دارد.  مفهوم ((مم)) به‌عنوان واحد انتقال فرهنگ یا تقلید در ابتدا توسط Richard dawkins در سال 1976 مطرح گردید. و سپس Moscato الگوریتم ممتیک را برای اولین بار در سال 1989 ارائه کرد.  

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

بهینه‌سازی فرآیندی برای تعیین بهترین راه‌حل است. این الگوریتم از روش به کمینه یا به حداکثر رساندن پارامترهای درگیر در مسائل استفاده می‌کند. به‌طورکلی مسائل بهینه‌سازی از مسائل محاسباتی‌اند که به دنبال پیدا کردن بهترین راه‌حل‌های ممکن هستند. الگوریتم‌های بهینه‌سازی، به دنبال یافتن راه‌حل در منطقه‌ای هستند که دارای حداقل (یا حداکثر) ارزش عملکرد هدف باشد.

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

تعریف کلی الگوریتم ممتیک

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

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

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

درواقع الگوریتمِ تپه نوردی مانند این است که ابتدا یک راه‌حل برای مسئله پیدا کنیم، سپس با تغییرات کم در این راه‌حل (پیدا کردن همسایه‌ها – همان کاری که در الگوریتم جستجوی ممنوعه انجام می­دهیم)، به دنبال بهبود آن به‌صورت محلی باشیم و این کار را تا زمانی ادامه دهیم که الگوریتم در یک حالت بهینه محلی (نسبت به حالات همسایه خود) قرار بگیرد.

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

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

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

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

پیشینه الگوریتم بهینه‌سازی ممتیک

الگوریتم‌های حافظه از اثر متقابل تکامل ژنتیکی و تکامل ممتیک الهام گرفته‌شده‌اند. داروینیسم جهانی عبارت است از تعمیم ژن‌ها در ورای سیستمهای مبتنی بر بیولوژیکی به هر سیستمی که واحدهای گسسته از اطلاعات را می‌توان به ارث برد و در معرض نیروهای تکاملی انتخاب و تنوع قرار گیرد. اصطلاح meme برای اشاره به بخشی از اطلاعات فرهنگی گسسته استفاده می‌شود.meme نشانگر تعامل ژنتیکی و تکامل فرهنگی است.

روند کلی الگوریتم فرا ابتکاری ممتیک

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

مدل فرآیندی برای ممتیک

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

مراحل ایجاد الگوریتم ممتیک یا الگوریتم بهینه‌سازی حافظه

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

الگوریتم ممتیک، یک لیست شبه کد از الگوریتم بهینه‌سازی  ممتیک را برای به حداقل رساندن یک عملکرد هزینه فراهم می‌کند. این روش یک الگوریتم ممتیک Meme یا مرتبه اول را توصیف می‌کند این روش بهبود راه‌حل‌های جداگانه از یک جستجوی جهانی را نشان می‌دهد. هرچند که تکامل مستقل پورها را نشان نمی‌دهد. سه الگوریتم در این زمینه ارائه‌شده است.

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

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

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

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

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

مسئله فروشنده دوره‌گرد یک از مسائل شناخته‌شده از نوع هارد در کامپیوتر است. در این مسئله یک فروشنده دوره‌گرد با شروع از یک مبدأ و گذشتن از همه شهرها به مقصد می‌رسد. هدف آن است که این فروشنده کمترین مسیر رابین مسیرهای موجود بیابد. حل دقیق این مسئله از مسائل دشوار و زمان‌بر است. استفاده از روش‌های هوشمند ازجمله الگوریتم ممتیک می‌تواند منجر به تسریع رسیدن به جواب شود.

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

شبه کد یک الگوریتم ممتیک ساده در ادامه آورده شده است:

BEGIN        INITIALSE population;        EVALUATE each candidate;        REPEAT UNTIL ( TERMINATION CONDITION is satisfied ) DO            SELECT parents;            RECOMBINE to produce offspring;            MUTATE offspring;            EVALUATE offspring;            IMPROVE offspring via Local Search;            SELECT individuals for next generation;       DO END

[1] Memetic Algorithm

[2] Hill Climbing