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

جذابیت الگوریتم‌های تکاملی از بسیاری از برنامه‌های کاربردی موفق و تعداد زیادی از انتشارات در بخش محاسبات تکاملی آشکار است. با این حال، تلاش برای یافتن حقایق سخت در مورد مزیت‌های نسبی به طور کلی، اگر غیرممکن نباشد، دشوار است. یکی از دلایل این موضوع، قضیه به اصطلاح بدون ناهار رایگان[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] است.

الگوریتم تکاملی چیست؟

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