تشریح جامع الگوریتم ممتیک — Memetic Algorithm

مقدمه مقاله تشریح جامع الگوریتم ممتیک

در ابتدا باید به اطلاعتان برسانم که این آموزش چکیده‌ای از فصل ۲۹ کتاب Handbook of Natural Computing تحت عنوان Memetic Algorithms که صفحات ۹۰۵ تا ۹۳۵ را شامل شده و نوشته Natalio Krasnogor می‌باشد. این فصل تأیید شده توسط Interdisciplinary Optimisation Laboratory, The Automated Scheduling, Optimisation and Planning Research Group, School of Computer Science, University of Nottingham, UK بوده و از منبع معتبر Springer قابل تهیه است.

الگوریتم‌ ممتیک توسط دانشمند برتر حوزه کامپیوتر، Moscato در سال ۱۹۸۹ میلادی، به کلاسی از تکنیک‌های جستجوی سراسری تصادفی، اطلاق شد که به‌طور کلی، در چارچوب الگوریتم های تکاملی (EA) مزایای جستجوی اکتشافی محلی خاص و چند عاملی را ترکیب می‌کنند.

عزیزان، می‌توان به جرات، ادعا کرد که برخلاف سایر الگوریتم‌های الهام گرفته از طبیعت، مانند بهینه سازی کلونی مورچه (ACO) ارائه شده در سال ۱۹۹۷ توسط Dorigo et al، الگوریتم بازپخت نوشته Kirkpatrick et al در سال ۱۹۸۳، الگوریتم شبکه های عصبی (McCulloch and Pitts) سال ۱۹۴۳و الگوریتم‌های تکاملی Holland در سال ۱۹۷۶، الگوریتم‌های ممتیک در هسته خود، فاقد یک استعاره طبیعی واضح هستند و برای یک ارائه کاربردی در بخش مهندسی نرم افزار، بر روی فناوری جستجوی انعطاف پذیر، تمرکز می‌کند.

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

• الگوریتم‌های بهینه سازی هوشمند — کلیک کنید.

مراحل تعریف یک زبان الگو (A Pattern Language)

محققان علوم کامپیوتر، از جمله آقای الکساندر و همکارانش در سال ۱۹۷۷ میلادی، در چارچوب معماری و شهرسازی، مفهوم «الگوها یا Patterns» و «زبان‌‎های الگو یا Pattern Languages» را تشریح نمود. به طور خلاصه، هر الگو، مسئله یا مشکلی را توصیف می‌کند که بارها و بارها در محیط پیرامون ما اتفاق افتاده است و سپس هسته، شروع می‌کند به تشریح راه حل آن مسئله.

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

۱- نام الگو (The pattern name)

نام الگو، یک کنترل کننده جزئی (Concise handler) برای اشاره به یک مسئله خاص و یک راه حل آزمایش شده (Tested solution) است. هر چه مجموعه‌ای از نام‌های الگو مانند مکانیسم انتخاب (Selection mechanism)، استراتژی متقاطع (Crossover strategy)، استراتژی اکتشاف (Exploration strategy)، طرح تنوع (Diversification plan)، و غیره دقیق باشد؛ زبان الگو (Pattern language) کامل‌تر خواهد بود.

از طرف دیگر، هر چه اندازه واژگان (Size of a vocabulary) را در زبان الگو افزایش دهیم؛ راه برای تحقیقات اساسی و آزمایش‌های عملی بازتر خواهد بود. اهمیت این مشاهدات، زمانی آشکار می‌شود که الگوریتم ممتیک خودساز را توصیف کنیم.

۲- بیان صورت مسئله (The problem statement)

بیان مسئله یعنی توضیح کامل مسئله یا مشکلی که الگو تلاش می‌کند تا یک جواب بهینه (Optimal Solution) برای آن ارائه دهد. به عنوان مثال، حفظ تنوع جبهه پارتو (Maintaining pareto front diversity) و غیره. بیان صورت مسئله، علاوه بر خود مسئله، شامل بایدها و نبایدهای الگو هم می‌شود که در قالب شرط یا شروط به آن اضافه خواهند شد. این شروط یا در حین استفاده از الگو باید رعایت شده یا حتی گروهی از آن ها باید به صورت متقارن (Symmetrically)، قبل از استفاده از الگو برآورده شوند.

۳- راه حل یا راه حل های ارائه شده (The solution)

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

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

۴- شناسایی و رفع پیامدهای اعمال الگو (The consequences of applying the pattern)

دوستان گرامی، سال ها پیش، زمانی که دانشجو بودم؛ یک ضرب المثل جالب اقتصادی، توجه مرا به خود جلب کرد و آن هم این بود: “.There are no free lunches” بله عزیزان! بنده سال‌ها بعد به این نتیجه رسیدم که در هیچ کجای دنیا، چیزی به نام ناهار مجانی وجود ندارد و به قول ما ایرانی‌ها: “نابرده رنج، گنج میسر نمی‌شود.”

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

برای مثال، الگویی که خواستار شروع مجدد جمعیت، به دلیل بحران تنوع جمعیتی می‌باشد؛ ممکن است با مشکل اساسی از دست دادن اطلاعات (Loss of information) مواجه باشد و با به کارگیری یک الگوی اولیه سازی مجدد و محافظت از راه حل‌های جزئی (Partial solutions)، به برطرف نمودن این مشکل بپردازد.

۵- نمونه های نماینده یا موارد استفاده شده از الگو (Representative examples)

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

حال که با محتوا و عناصر زبان الگو آشنا شدید؛ به شبه کدهای زیر توجه کنید:

شبه کد a در سال ۲۰۰۹ توسط محققان زبان ماشین و علوم کامپیوتر Bacardit و Krasnogor برای سیستم طبقه‌بندی کننده یادگیری ممتیک تولید شده و شبه کد b در سال ۲۰۰۳ توسط دانشمند Merz برای تخمین الگوریتم ممتیک مشابه توزیع ارائه گردیده است.

کاربرد شبه کد c، برای بهینه سازی ازدحام ذرات ممتیک می‌باشد که در سال ۲۰۰۷ میلادی، توسط دانشمند حوزه علوم کامپیوتر و زبان ماشین، Petalas و همکارانش ارائه شده است اما شبه کد d، نماینده فراابتکاری بهینه سازی کلونی مورچه‌ها است که توسط آقای کوردون و همکارانش در سال ۲۰۰۲ ارائه گردیده و تاکنون هم بسیار پرکاربرد بوده و نظر صاحب نظران را در این زمینه به خود جلب کرده است.

شبه کد e، نشانگر استراتژی پالایش راه حل از طریق جستجوی محلی، برای الگوریتم فراابتکاری بهینه سازی کلونی مورچه ها (ACO) بوده و شکل f نمودار جریان الگوریتم ممتیک الهام گرفته از سیستم ایمنی مصنوعی (AIS) می‌باشد که توسط دانشمند و مبتکر علوم کامپیوتر آقای Yanga و همکارانش در سال ۲۰۰۸ برای اولین بار، ارائه شده است.

تشریح الگوی الگوریتم ممتیک (MAP)

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

پاورپوینت الگوریتم کلونی مورچه ها

کلیک کنید

بیان مسئله Memetic Algorithm

یک الگوریتم ممتیک، الگوهای راه حل را برای مسائل بهینه سازی، ارائه کرده و نشان می‌دهد که چگونه می‌توان یک تعادل متوازن بین اکتشاف (Exploration) در فضای جستجو و بهره برداری (Exploitation) از راه حل های جزئی موجود را تنظیم کرد. این مرحله یک قدم اساسی برای حل مسائل پیچیده است.

البته در نظر داشته باشید که در طی آن، از روش های استاندارد و کارآمد مثل الگوریتم های تقریبی (Approximation algorithms)، الگوریتم های دقیق (Exact algorithms) و غیره استفاده نمی‌شود. همواره الگوریتم ممتیک، فضای جستجو را از طریق تکنیک جستجوی سراسری (Global search) کاوش می‌کند. در حالی که بهره برداری از طریق جستجوی محلی (Local search) به دست می‌آید.

راه حل ها در Memetic Algorithm

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

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

پیامدهای اعمال الگو در MA

همواره در کلاس‌های درس به ما آموزش داده‌اند که ترکیب کردن یک روش جستجوی سراسری از هر نوع با جستجوی محلی و (And) یا (Or) روش‌های اکتشافی در دامنه خاص (Domain-specific)، معمولاً نتایج نهایی بهتری را به همراه خواهد داشت اما اگر نظر من را هم در این زمینه بخواهید؛ به شما خواهم گفت که این روند باعث افزایش زمان محاسباتی حل مسئله بهینه سازی شده و نتیجه را به تعویق می‌اندازد.

در الگوی الگوریتم ممتیک، معاوضه صحیح بین اکتشاف و بهره برداری باید به گونه‌ای باشد که اگر جستجوگر سراسری همان Budget یا بودجه CPU را به عنوان الگوریتم ممتیک در نظر بگیرد؛ در این صورت، راه حل‌های ایجاد شده، به مراتب بدتر از راه حل‌های مشتق شده از MA باشند. یکی دیگر از پیامدهای احتمالی هم این است که جستجوی محلی و اکتشاف‌های خاص دامنه معمولاً منجر به همگرایی زودرس (Premature convergence) می‌شود. به همگرایی زودرس، بحران تنوع یا Diversity crisis نیز گفته می‌شود.

نمودار کلاس الگوریتم ممتیک

شکل زیر، یک نمودار کلاس را نشان می‌دهد که به کمک آن می‌توان الگوی الگوریتم ممتیک را پیاده سازی کرد. کلاس Abstract که اصطلاحاً چکیده الگوریتم نامیده می‌شود؛ یک متد الگو (Method pattern) را تعریف می‌نماید که در طی آن، چارچوب کلی الگوریتم برای یک عملکرد خاص، فراهم خواهد شد.

برای دستیابی به عملکرد بهینه، متد الگو، یک یا چند عملیات ابتدایی را که به صورت انتزاعی در (Abstract class) تعریف شده‌اند؛ فراخوانی می‌کند. لازم به ذکر است که هر کدام از این عملیات ابتدایی می‌توانند در زیرکلاس‌های تخصصی‌تر (Concrete class) دوباره تعریف شوند. در ادامه، یک نمودار کلاس UML که ساختار پیاده سازی متد الگو، به نمایش گذاشته شده است.

الگوی الگوریتم ممتیک تکاملی (EMATP)

EMATP مسیر مناسبی را برای حل این مشکل که چگونه می‌توان روش‌های جستجوی سراسری و محلی را از درون الگوریتم های تکاملی هماهنگ کرد؛ فراهم می‌سازد. اگرچه در اصل، کاوش هم زمان فضای جستجو، توسط فرآیند تکاملی و بهره برداری از راه حل‌های کاندید، باید منجر به الگوریتم بهبودیافته شود؛ همیشه اینطور نیست. انتظار این است که ترکیبی از یک EA منجر به یک اثر خالص هم افزایی شود که به طور مولد جستجوی محلی و سراسری را متعادل کند.

چرخه تکاملی استاندارد بالا، با عملگرهای اختصاصی دامنه گسترش یافته است که می‌تواند این چرخه را اصلاح کند. فرآیندهای پالایش می‌تواند برای عناصر مختلف خط لوله هسته EA متفاوت باشد و همچنین می‌تواند از طریق روش‌های دقیق، تقریبی یا حتی اکتشافی، اجرا شود. عملیات خاص دامنه اغلب به شکل اولیه سازی‌های هوشمند، رویه‌های جستجوی محلی و غیره اجرا شده و راه حل‌های ورودی را برای فرآیندهای mate و (And)/ یا (Or) جهش آماده ساخته و اغلب خروجی‌های آن‌ها را اصلاح می‌نماید.

اصلاحات، همچنین می‌تواند در فرآیندهای انتخاب، مقداردهی اولیه و مدیریت جمعیت، از طریق اشتراک‌گذاری تناسب اندام (Fitness sharing)، ازدحام (Crowding)، ساختار جمعیت (Population structuring) مانند ساختارهای سلولی/شبکه‌ای (Cellular/lattice structures) و استراتژی‌های مدیریت تنوع (Diversity management strategies) و غیره اعمال شود.

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

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

کلام آخر مقاله تشریح جامع الگوریتم ممتیک

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