موضوع مقاله: الگوریتم میمتیک | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم میمتیک | مقدمه: الگوریتم میمتیک یک رویکرد بهینه‌سازی ترکیبی هستند که قابلیت‌های جستجوی جهانی الگوریتم‌های تکاملی (EAs) را با تکنیک‌های جستجوی محلی برای بهبود کیفیت راه‌حل‌ها ترکیب می‌کنند. | ## بخش 1: الگوریتم میمتیک | این الگوریتم با هدف ترکیب روش‌های متفاوت بهینه‌سازی، از جمله الگوریتم‌های تکاملی، شبیه‌سازی تبرید و جستجوی تابو، توسعه یافت. مقدمه ایده‌ی استفاده از اصول داروینی برای حل خودکار مسائل به دهه‌ی 1940 بازمی‌گردد، یعنی مدت‌ها پیش از پیشرفت کامپیوترها. در سال 1948، تورینگ مفهوم "جستجوی ژنتیکی یا تکاملی" را پیشنهاد داد و بعد از آن هم تلاشهای قابل توجهی برای توسعه‌ی الگوریتمهای تکاملی صورت گرفت . در سال در سال ۱۹۸۷، پابلو موسکاتو الگوریتمهای میتیک را با الهام گرفتن از مفهوم میم که توسط داوکینز در سال ۱۹۷۶ به عنوان معادلی برای ژن در تکامل فرهنگی مطرح شد، در مقاله‌ای معرفی کرد. میم‌ها نشان‌دهنده‌ی عناصری فرهنگی مانند ایده‌ها، روش‌ها یا مهارت‌هایی هستند که از فردی به فرد دیگر انتقال می‌یابند Lewens, T. در الگوریتم‌های میمتیک، این مفهوم به شکلی استعاری استفاده شده است تا ارتباط بین تکامل داروینی و روش‌های جستجوی محلی در زمینه حل مسائل پیچیده بهینه‌سازی را به تصویر بکشد. الگوریتم‌های میمتیک به‌عنوان زیرمجموعه‌ای از این حوزه، ترکیبی از الگوریتم‌های تکاملی و روش‌های بهبود قطعی برای حل مسائل بهینه‌سازی هستند. این رویکرد به دلیل توانایی‌اش در تعادل بین کلیت و ویژگی‌های خاص مسئله، به ابزاری قدرتمند برای حل مسائل پیچیده تبدیل شده است. روش ایده‌ی اصلی مشترک بین الگوریتم‌های تکاملی مختلف یکسان است: با داشتن یک جمعیت از افراد، از مکانیزم‌هایی برگرفته از انتخاب طبیعی و تنوع ژنتیکی استفاده می‌شود تا افرادی با تناسب (fitness) بالاتر تکامل یابند. | ## بخش 2: الگوریتم میمتیک | با در دست داشتن یک تابع کیفیت برای بیشینه‌سازی، می‌توان مجموعه‌ای از راه‌حل‌های کاندید، یعنی عناصر دامنه تابع، به‌طور تصادفی ایجاد کرد و از تابع کیفیت به‌عنوان یک معیار انتزاعی برای تناسب استفاده نمود. بازترکیب یک عملگر است که روی دو یا چند کاندید منتخب (به‌اصطلاح والدین) اعمال می‌شود و به تولید یک یا چند کاندید جدید (فرزندان) می‌انجامد. اجرای بازترکیب و جهش منجر به مجموعه‌ای از کاندیدهای جدید (فرزندان) می‌شود که بر اساس تناسب‌شان (و احتمالاً سن‌شان) با افراد قدیمی برای جایگاه در نسل بعد رقابت می‌کنند. این فرآیند می‌تواند تکرار شود تا زمانی که یک کاندید با کیفیت کافی (یک راه‌حل) پیدا شود یا یک محدودیت محاسباتی از پیش تعیین‌شده برآورده گردد. جمعیت اولیه به صورت تصادفی تولید می‌شود، اما می‌توان از روش‌های غیرتصادفی نیز استفاده کرد. تابع ارزیابی تابع ارزیابی کیفیت یک فرد را نشان می‌دهد و مبنای انتخاب را فراهم می‌کند، در نتیجه به بهبودها کمک می‌کند. در مسائل بهینه‌سازی، که غالباً توسط EA حل می‌شوند، این تابع به عنوان معیاری برای مقایسه راه‌حل‌های جایگزین عمل می‌کند. عملگرها در این فرآیند، دو نیروی اساسی که پایه سیستم‌های تکاملی را تشکیل می‌دهند عبارت‌اند از: عملگرهای تنوع که تنوع لازم را ایجاد می‌کنند و امکان نوآوری را فراهم می‌نمایند. ترکیب (تلاقی): این عملگر اطلاعات والدین را ترکیب می‌کند تا فرزندانی با ویژگی‌های جدید تولید کند. | ## بخش 3: الگوریتم میمتیک | عمگرهای انتخاب که کاندیدهای راه‌حل را فیلتر کرده و محدودیت‌هایی بر آن‌ها اعمال می‌کند. عملگرهای انتخاب خود به دو صورت عمل می‌کنند: انتخاب والدین: والدین براساس کیفیتشان انتخاب می‌شوند تا فرزندان نسل بعد را تولید کنند. انتخاب بازماندگان: این انتخاب پس از تولید فرزندان صورت می‌گیرد و تصمیم می‌گیرد کدام افراد به نسل بعد منتقل شوند. در طول انتخاب، افراد با تناسب بالاتر شانس بیشتری برای انتخاب شدن نسبت به افراد کمتر تناسب‌یافته دارند، اما معمولاً حتی افراد ضعیف نیز شانس والد شدن یا زنده ماندن را دارند. به‌طور مشابه، برای جهش، بخش‌هایی که در یک راه‌حل کاندید جهش می‌کنند و بخش‌های جدیدی که جایگزین آن‌ها می‌شوند نیز به‌صورت تصادفی انتخاب می‌شوند. کاربرد ترکیبی تنوع و انتخاب معمولاً منجر به بهبود مقادیر تناسب در جمعیت‌های متوالی می‌شود. به‌آسانی می‌توان این فرآیند تکاملی را به‌عنوان بهینه‌سازی در نظر گرفت که با تولید مکرر راه‌حل‌هایی با مقادیر بهتر انجام می‌شود. از این دیدگاه، تناسب به‌عنوان یک تابع هدف برای بهینه‌سازی در نظر گرفته نمی‌شود، بلکه به‌عنوان یک بیان از نیازهای محیطی دیده می‌شود. انطباق بیشتر با این نیازها به معنای افزایش قابلیت بقا است که در تعداد فرزندان بیشتر منعکس می‌شود. | ## جمع‌بندی | شروع جمعیت را با راه‌حل‌های تصادفی مقداردهی اولیه کن؛ هر کاندیدا را ارزیابی کن؛ تا زمانی که (شرط توقف برآورده شود) تکرار کن 1 والدین را انتخاب کن؛ 2 جفت‌های والدین را ترکیب کن؛ 3 فرزندان حاصل را جهش بده؛ 4 کاندیداهای جدید را ارزیابی کن؛ 5 افراد را برای نسل بعدی انتخاب کن؛ پایان تکرار پایان.