الگوریتم میمتیک
الگوریتم میمتیک (به انگلیسی: Memetic algorithm) یک رویکرد بهینهسازی ترکیبی هستند که قابلیتهای جستجوی جهانی الگوریتمهای تکاملی (EAs) را با تکنیکهای جستجوی محلی برای بهبود کیفیت راهحلها ترکیب میکنند. این الگوریتمها که در اواخر دهه ۱۹۸۰ توسط پابلو موسکاتو معرفی شدند[۱]، از مفهوم میم (Meme) ریچارد داوکینز در تکامل فرهنگی الهام گرفتهاند[۲]. این الگوریتم با هدف ترکیب روشهای متفاوت بهینهسازی، از جمله الگوریتمهای تکاملی، شبیهسازی تبرید و جستجوی تابو، توسعه یافت. در ادبیات علمی، MA اغلب به عنوان الگوریتمهای تکاملی بالدوینی (Baldwinian)، لامارکی (Lamarckian)، الگوریتمهای فرهنگی (Cultural Algorithms)، یا جستجوی محلی ژنتیکی (Genetic Local Search) نیز شناخته میشود.
مقدمه
ایدهی استفاده از اصول داروینی برای حل خودکار مسائل به دههی 1940 بازمیگردد، یعنی مدتها پیش از پیشرفت کامپیوترها. در سال 1948، تورینگ مفهوم "جستجوی ژنتیکی یا تکاملی" را پیشنهاد داد و بعد از آن هم تلاشهای قابل توجهی برای توسعهی الگوریتمهای تکاملی صورت گرفت [۳]. در سال در سال ۱۹۸۷، پابلو موسکاتو الگوریتمهای میتیک را با الهام گرفتن از مفهوم میم که توسط داوکینز در سال ۱۹۷۶ به عنوان معادلی برای ژن در تکامل فرهنگی مطرح شد، در مقالهای[۱] معرفی کرد. میمها نشاندهندهی عناصری فرهنگی مانند ایدهها، روشها یا مهارتهایی هستند که از فردی به فرد دیگر انتقال مییابند [۴] . در الگوریتمهای میمتیک، این مفهوم به شکلی استعاری استفاده شده است تا ارتباط بین تکامل داروینی و روشهای جستجوی محلی در زمینه حل مسائل پیچیده بهینهسازی را به تصویر بکشد.
بهطور کلی، استفاده از مفاهیم میمتیک در رایانش بهعنوان محاسبات میمتیک (Memetic Computing یا MC) شناخته میشود. الگوریتمهای میمتیک بهعنوان زیرمجموعهای از این حوزه، ترکیبی از الگوریتمهای تکاملی و روشهای بهبود قطعی برای حل مسائل بهینهسازی هستند. این رویکرد به دلیل تواناییاش در تعادل بین کلیت و ویژگیهای خاص مسئله، به ابزاری قدرتمند برای حل مسائل پیچیده تبدیل شده است.
روش [۳]
ایدهی اصلی مشترک بین الگوریتمهای تکاملی مختلف یکسان است: با داشتن یک جمعیت از افراد، از مکانیزمهایی برگرفته از انتخاب طبیعی و تنوع ژنتیکی استفاده میشود تا افرادی با تناسب (fitness) بالاتر تکامل یابند. با در دست داشتن یک تابع کیفیت برای بیشینهسازی، میتوان مجموعهای از راهحلهای کاندید، یعنی عناصر دامنه تابع، بهطور تصادفی ایجاد کرد و از تابع کیفیت بهعنوان یک معیار انتزاعی برای تناسب استفاده نمود.
بر اساس این تناسب، برخی از کاندیدهای بهتر برای تولید نسل بعدی انتخاب میشوند، بهطوریکه بازترکیب (recombination) و یا جهش (mutation) روی آنها اعمال میشود. بازترکیب یک عملگر است که روی دو یا چند کاندید منتخب (بهاصطلاح والدین) اعمال میشود و به تولید یک یا چند کاندید جدید (فرزندان) میانجامد. جهش روی یک کاندید اعمال میشود و منجر به تولید یک کاندید جدید میگردد. اجرای بازترکیب و جهش منجر به مجموعهای از کاندیدهای جدید (فرزندان) میشود که بر اساس تناسبشان (و احتمالاً سنشان) با افراد قدیمی برای جایگاه در نسل بعد رقابت میکنند. این فرآیند میتواند تکرار شود تا زمانی که یک کاندید با کیفیت کافی (یک راهحل) پیدا شود یا یک محدودیت محاسباتی از پیش تعیینشده برآورده گردد.
جمعیت
جمعیت مجموعهای از راهحلهای ممکن است. جمعیت اولیه به صورت تصادفی تولید میشود، اما میتوان از روشهای غیرتصادفی نیز استفاده کرد.
تابع ارزیابی
تابع ارزیابی کیفیت یک فرد را نشان میدهد و مبنای انتخاب را فراهم میکند، در نتیجه به بهبودها کمک میکند. این تابع در EC معمولاً تابع برازش نامیده میشود. در مسائل بهینهسازی، که غالباً توسط EA حل میشوند، این تابع به عنوان معیاری برای مقایسه راهحلهای جایگزین عمل میکند.
عملگرها
در این فرآیند، دو نیروی اساسی که پایه سیستمهای تکاملی را تشکیل میدهند عبارتاند از:
- عملگرهای تنوع که تنوع لازم را ایجاد میکنند و امکان نوآوری را فراهم مینمایند. عملگرهای تنوع دو نوعاند:
- جهش: این عملگر به صورت تصادفی فرد را تغییر میدهد.
- ترکیب (تلاقی): این عملگر اطلاعات والدین را ترکیب میکند تا فرزندانی با ویژگیهای جدید تولید کند.
- عمگرهای انتخاب که کاندیدهای راهحل را فیلتر کرده و محدودیتهایی بر آنها اعمال میکند. عملگرهای انتخاب خود به دو صورت عمل میکنند:
- انتخاب والدین: والدین براساس کیفیتشان انتخاب میشوند تا فرزندان نسل بعد را تولید کنند. این فرآیند معمولاً احتمالی است.
- انتخاب بازماندگان: این انتخاب پس از تولید فرزندان صورت میگیرد و تصمیم میگیرد کدام افراد به نسل بعد منتقل شوند. این انتخاب معمولاً قطعی و براساس مقادیر برازندگی است.
در طول انتخاب، افراد با تناسب بالاتر شانس بیشتری برای انتخاب شدن نسبت به افراد کمتر تناسبیافته دارند، اما معمولاً حتی افراد ضعیف نیز شانس والد شدن یا زنده ماندن را دارند. برای بازترکیب افراد، انتخاب بخشهایی که ترکیب خواهند شد تصادفی است. بهطور مشابه، برای جهش، بخشهایی که در یک راهحل کاندید جهش میکنند و بخشهای جدیدی که جایگزین آنها میشوند نیز بهصورت تصادفی انتخاب میشوند.
کاربرد ترکیبی تنوع و انتخاب معمولاً منجر به بهبود مقادیر تناسب در جمعیتهای متوالی میشود. بهآسانی میتوان این فرآیند تکاملی را بهعنوان بهینهسازی در نظر گرفت که با تولید مکرر راهحلهایی با مقادیر بهتر انجام میشود. تکامل اغلب بهعنوان فرآیندی از سازگاری دیده میشود. از این دیدگاه، تناسب بهعنوان یک تابع هدف برای بهینهسازی در نظر گرفته نمیشود، بلکه بهعنوان یک بیان از نیازهای محیطی دیده میشود. انطباق بیشتر با این نیازها به معنای افزایش قابلیت بقا است که در تعداد فرزندان بیشتر منعکس میشود. فرآیند تکاملی جمعیت را بهطور فزایندهای در سازگاری با محیط بهتر میکند[۳].
- طرح کلی یک الگوریتم تکاملی به صورت شبهکد[۳].
شروع جمعیت را با راهحلهای تصادفی مقداردهی اولیه کن؛ هر کاندیدا را ارزیابی کن؛ تا زمانی که (شرط توقف برآورده شود) تکرار کن 1 والدین را انتخاب کن؛ 2 جفتهای والدین را ترکیب کن؛ 3 فرزندان حاصل را جهش بده؛ 4 کاندیداهای جدید را ارزیابی کن؛ 5 افراد را برای نسل بعدی انتخاب کن؛ پایان تکرار پایان.
منابع
- 1 2 Moscato, P. (1989). On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms. Caltech Concurrent Computation Program 158-79, California Institute of Technology, Pasadena, CA. Available at: ResearchGate.
- ↑ Dawkins, R. (1976). The Selfish Gene. Oxford University Press, Oxford.
- 1 2 3 4 Hart, William E.; Krasnogor, Natalio; Smith, J. E. (2004). Recent Advances in Memetic Algorithms. Springer.
- ↑ Lewens, T. & Buskell, A. (2023). "Cultural Evolution." *Stanford Encyclopedia of Philosophy*. First published Dec 23, 2007; substantive revision May 22, 2023. Retrieved from https://plato.stanford.edu/entries/evolution-cultural/#StroAnalMemeMeme.