حوزه الگوریتم‌های تکاملی (EAs)

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

حوزه الگوریتم‌های تکاملی (EAs) به عنوان یک چتر عمل می‌کند که بسیاری از دسته‌‌های مختلف الگوریتم‌ها مانند الگوریتم‌های ژنتیک (GAs)، بهینه‌سازی ازدحام ذرات (PSO)، سیستم‌های دسته‌بند یادگیری (LCS)، برنامه‌ریزی ژنتیک (GP)، برنامه‌ریزی تکاملی (EP) را پوشش می‌دهد. در سال‌های اخیر بسیاری از مسائل دشوار با این رویکردها حل شده است. اگرچه یکسان نیستند، اما این الگوریتم‌ها - مبتنی بر جمعیت، هدایت شده بر اساس اصول انتخاب طبیعی، و استفاده برای مسائل بهینه‌سازی شباهت‌های زیادی دارند.

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

مزایا (و معایب) محاسبات تکاملی نسبت به سایر رویکردها

جذابیت الگوریتم‌های تکاملی از بسیاری از برنامه‌های کاربردی موفق و تعداد زیادی از انتشارات در بخش محاسبات تکاملی آشکار است. با این حال، تلاش برای یافتن حقایق سخت در مورد مزیت‌های نسبی به طور کلی، اگر غیرممکن نباشد، دشوار است. یکی از دلایل این موضوع، قضیه به اصطلاح بدون ناهار رایگان[1] (NFL) است.

قضیه بدون ناهار رایگان

از آنجایی که با توجه به قضیه ناهار بدون ناهار (NFL) (ولپرت و مک‌ردی ۱۹۹۶)، هیچ الگوریتمی برای حل مسائل (مثلاً بهینه‌سازی) وجود ندارد که به طور کلی (به طور متوسط) برتر از هر رقیبی باشد، سؤال اینکه آیا الگوریتم‌های تکاملی (EAs) نسبت به هر رویکرد جایگزین پایین‌تر یا برتر هستند، بی‌معنی است. تنها چیزی که می‌توان ادعا کرد این است که EAها نسبت به روش‌های دیگر با توجه به حل یک کلاس خاص از مسائل بهتر رفتار می‌کنند و در نتیجه برای سایر کلاس‌های مسئله بدتر رفتار می‌کنند.

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

گویش‌های تاریخی الگوریتم تکاملی

همانطور که قبلاً نقل شد، EC از منابع مستقل برخاسته است. البته هر گویش به خودی خود تنوع زیادی دارد. توضیحات کوتاه در اینجا لزوماً به یک یا دو نوع اصلی محدود می شود.

۱. الگوریتم‌های ژنتیک

GA استاندارد را می‌توان به عنوان ترکیبی از بازنمایی رشته بیت، با متقاطع تبادل بیت (که با احتمال داده شده p_c اعمال می‌شود) و جهش بیت-تغییر (برای هر بیت با احتمال p_m اعمال می‌شود) ، چرخ رولت مشاهده کرد. انتخاب به علاوه جایگزینی نسلی (اگرچه می‌توان از جایگزینی حالت پایدار نیز استفاده کرد).

توجه داشته باشید که سایر نسخه‌های EA که از موتور تکاملی یکسانی با ژنوتیپ‌های مختلف استفاده می‌کنند (و از این رو عملگرهای تنوع) اغلب GA نامیده می‌شوند.

اجزای الگوریتم‌های تکاملی

اجزای الگوریتم‌های تکاملی

1. بازنمایی[1]

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

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

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

یکی از مسائل مهم هنگام اجرای EA این است که سعی کنید تنوع ژنتیکی[2] جمعیت را تا زمانی که ممکن است حفظ کنید. برخلاف بسیاری از روش‌های بهینه‌سازی دیگر، EAها از یک جمعیت کامل از اعضا استفاده می‌کنند - و این یکی از دلایل قدرت آنهاست. با این حال، اگر آن جمعیت شروع به تمرکز در یک منطقه بسیار باریک[3] از فضای جستجو کند، تمام مزایای مدیریت اعضا مختلف از بین می‌رود، در حالی که بار محاسبه برازش آنها باقی می‌ماند. این پدیده به همگرایی زودرس[4] معروف است. دو جهت اصلی برای جلوگیری از این امر وجود دارد:

الف) تضمین پیشینی ایجاد مواد جدید، به عنوان مثال با استفاده از سطح بالایی از جهش (به بخش 4.3.3 مراجعه کنید).

ب) یا به طور پسینی دستکاری برازش همه اعضا برای ایجاد یک سوگیری علیه مشابه بودن یا نزدیک بودن به نامزدهای موجود. یک تکنیک شناخته شده به اصطلاح مکانیسم طاقچه[5] است.