اجزای الگوریتم‌های تکاملی
اجزای الگوریتم‌های تکاملی
1. بازنمایی[1]
حل یک مسئله معین با یک EA با مشخص کردن بازنمایی از راه‌حل‌های کاندید شروع می‌شود. چنین راه‌حل‌های نامزدی به عنوان فنوتیپ‌هایی دیده می‌شوند که می‌توانند ساختارهای بسیار پیچیده‌ای داشته باشند. استفاده از عملگرهای تغییر به طور مستقیم در این ساختارها ممکن است ممکن نباشد یا آسان باشد. بنابراین این فنوتیپ‌ها با ژنوتیپ‌های مربوطه نشان داده می‌شوند. ماشین آلات استاندارد EC شامل بسیاری از اپراتورهای تغییرات خارج از قفسه است که روی یک فضای ژنوتیپ خاص عمل می‌کنند، به عنوان مثال رشته بیت، بردارهای با ارزش واقعی، جایگشت اعداد صحیح یا درختان. بنابراین، طراحی یک EA اغلب به انتخاب یکی از نمایش‌های استاندارد با در نظر گرفتن عملگرهای تغییرات مربوطه است. با این حال، یکی از نقاط قوت EAها توانایی آنها برای مقابله با هر فضای جستجو است به شرطی که عملگرهای اولیه و تغییرات در دسترس باشند. بنابراین، انتخاب یک گزینه استاندارد ضروری نیست.
2. تابع برازش یا ارزیابی
انتخاب مبتنی بر برازش نیرویی است که نشان دهنده حرکت به سمت بهبود کیفیت در یک EA است. بنابراین طراحی تابع برازش (یا تابع ارزیابی) بسیار مهم است.
اولین ویژگی مهم در مورد محاسبات برازش این است که 99٪ از کل هزینه محاسباتی تکامل در اکثر مسائل دنیای واقعی را نشان می‌دهد. دوم، تابع برازش اغلب تنها اطلاعات مربوط به مسئله در الگوریتم است: هر دانش موجود و قابل استفاده در مورد دامنه مسئله باید استفاده شود.
3. وابسته به بازنمایی
3.1. مقداردهی اولیه
جمعیت اولیه معمولاً با نمونه‌برداری تصادفی از فضای جستجو ایجاد می‌شود که عموماً تا حد امکان یکنواخت انجام می‌شود. با این حال، در برخی موارد، نمونه‌گیری یکنواخت ممکن است به خوبی تعریف نشده باشد، به عنوان مثال، در فضاهای درخت تجزیه[2]، یا در فواصل نامحدود برای اعداد ممیز شناور.
یک روش معمول نیز تلقیح[3] برخی از راه‌حل‌های خوب شناخته شده به جمعیت اولیه است. اما مراقب باشید که هیچ سوگیری بهتر از سوگیری اشتباه نیست!
3.2. تقاطع
اپراتورهای متقاطع دو (یا چند) والدین را می‌گیرند و با تبادل اطلاعات بین والدین فرزندانی تولید می‌کنند. ایده اساسی برای توضیح عملکرد متقاطع این است که برازش خوب والدین به نحوی به دلیل بخش‌های دقیق ماده ژنتیکی آنهاست (که بلوک‌های ساختمانی[4] نامیده می‌شوند)، و ترکیب مجدد آن بلوک‌های سازنده منجر به افزایش برازش می‌شود.
با این وجود، روش‌های متعدد دیگری برای انجام تقاطع وجود دارد. به عنوان مثال، تلاقی دو بردار از مقادیر ممیز شناور را می‌توان با ترکیب خطی (با وزن‌های یکنواخت ترسیم شده) مقادیر والد انجام داد. ایده این است که اطلاعات مربوط به مسئله مورد نظر باید به نحوی رد و بدل شود.
توجه داشته باشید که اثر متقاطع از اکتشاف زمانی که جمعیت بسیار متنوع است تا بهره‌برداری زمانی که شروع به فروپاشی در منطقه کوچکی از فضای جستجو می‌کند متفاوت است.
3.3. جهش
عملگرهای جهش تبدیلات تصادفی یک فرد هستند. مصالحه معمول بین اکتشاف و بهره‌برداری باید حفظ شود: جهش‌های بزرگ به دلایل نظری ضروری هستند (این امر ارگودیک[5] بودن فرآیند تصادفی زیربنایی را تضمین می‌کند) که به طور عملی ترجمه می‌شود (این تنها راه برای معرفی مجدد تنوع ژنتیکی در پایان تکامل است). اما مسلماً جهش‌های بیش از حد بزرگ، الگوریتم را به یک پیاده‌روی تصادفی تبدیل می‌کنند - بنابراین اغلب جهش‌ها باید فرزندانی نزدیک به والدین خود ایجاد کنند. هیچ جهش عمومی استانداردی وجود ندارد، اما روندهای کلی عبارتند از تغییر مقدار یک جزء از ژنوتیپ با احتمال کمی (به عنوان مثال، یک بیت از یک رشته بیت را برگردانید، یا، در مورد اجزای با ارزش واقعی، نویز متوسط گاوسی صفر را اضافه کنید. با انحراف استاندارد با دقت تنظیم شده).
3.4. بحث تاریخی
مدتهاست که بحث شدیدی در مورد سودمندی تقاطع وجود دارد. جامعه GA متقاطع را عملگر تغییرات اساسی می‌داند، در حالی که جهش تنها یک ضرورت پس زمینه است. از سوی دیگر، محققان تاریخی ES و EP اصلاً از هیچ متقاطع استفاده نکردند و حتی بعداً ادعا کردند که می‌تواند مضر باشد.
امروزه توافق کلی این است که پاسخ به مسئله وابسته است: اگر یک متقاطع "از لحاظ معنایی معنادار[6]" برای مشکل موجود وجود داشته باشد، احتمالاً استفاده از آن ایده خوبی است. اما در غیر این صورت جهش به تنهایی ممکن است برای یافتن راه‌حل‌های خوب کافی باشد - و الگوریتم حاصل هنوز می‌تواند یک الگوریتم تکاملی نامیده شود.
4. مستقل از بازنمایی
4.1. داروینیسم مصنوعی
نظریه داروین بیان می‌کند که افراد شایسته تولید مثل می‌کنند و زنده می‌مانند[7]. موتور تکامل[8]، یعنی دو مرحله انتخاب (برخی از والدین برای تبدیل شدن به ژنیتور[9]) و جایگزینی[10] (برخی از والدین توسط فرزندان تازه متولد شده) پیاده‌سازی مصنوعی این دو فرآیند انتخابی است. آنها به طور اساسی با هم تفاوت دارند: در مرحله انتخاب، همان والد را می‌توان بارها انتخاب کرد. در مرحله جایگزینی، هر فرد (در بین والدین و فرزندان) یا انتخاب می‌شود یا برای همیشه ناپدید می‌شود.
انتخاب متناسب[11] (با نام مستعار چرخ رولت) مدتهاست که محبوب‌ترین اپراتور انتخاب بوده است: هر والدین احتمال انتخاب شدن متناسب با برازش آن را دارند. با این حال، دشواری این است که برازش را برای تنظیم فشار انتخاب کنید: حتی بیشترین دقت مانع از آن نمی‌شود که برخی افراد فوق العاده در مدت زمان بسیار کوتاهی جمعیت را تصاحب کنند. از این رو امروزه پرکاربردترین مورد، انتخاب مسابقات[12] است: برای انتخاب یک فرد، افراد T به طور یکنواخت انتخاب می‌شوند و بهترین آنها برگردانده می‌شود. البته، هم چرخ رولت و هم مسابقات به طور مکرر روی یک جمعیت فعلی عمل می‌کنند تا امکان انتخاب چندگانه از بهترین افراد را فراهم کنند.
دو دسته کلی از روش‌های جایگزینی وجود دارد: یا والدین و فرزندان برای بقا «جنگ[13]» می‌کنند، یا فقط برخی از فرزندان اجازه زنده ماندن دارند. با نشان دادن μ (به ترتیب λ) تعداد والدین (به ترتیب فرزندان) مانند تاریخچه ES، استراتژی اول (µ+λ) و دومی (µ, λ) نامیده می‌شود. وقتی μ = λ، استراتژی کاما به عنوان جایگزینی نسل[14] نیز شناخته می‌شود: همه فرزندان به سادگی جایگزین همه والدین می‌شوند. هنگامی که λ = 1، استراتژی (به علاوه!) سپس حالت پایدار نامیده می‌شود و به معنای انتخاب یکی از والدین برای جایگزینی است.
یک نکته مهم در مورد موتور تکامل، یکنواختی بهترین برازش در طول تکامل است: برای مثال، استراتژی‌های ES plus نخبه‌گرا[15] هستند، یعنی اطمینان حاصل شود که بهترین برازش فقط می‌تواند از نسلی به نسل دیگر افزایش یابد، در حالی که استراتژی‌های کاما[16] نخبه‌گرا نیستند. اگر چه زمانی که کاهش برازش پیش بینی می‌شود، نخبه‌گرایی می‌تواند با حفظ بهترین والد به صورت پسینی اضافه شود.
4.2. ملاک فسخ
مطالعات نظری بسیار کمی در مورد زمان توقف الگوریتم تکاملی انجام شده است. معیار توقف معمول مقدار ثابتی از زمان محاسباتی (یا تقریباً معادل آن، محاسبات برازش) است. یک معیار کمی ظریف‌تر این است که وقتی مدت زمان تعیین شده توسط کاربر بدون بهبود بهترین برازش در جمعیت سپری شده است، متوقف شود.
۵. تنظیم پارامترها
EAها معمولاً تعداد زیادی پارامتر دارند (به عنوان مثال، اندازه جمعیت، فراوانی نوترکیب، اندازه مرحله جهش، فشار انتخابی، ...). مسئله اصلی در این رابطه این است که حتی تأثیر فردی یک پارامتر اغلب غیرقابل پیش بینی است، چه رسد به تأثیر ترکیبی همه پارامترها. اکثر نویسندگان برای کالیبره کردن الگوریتم‌های خود به آزمایش‌های فشرده (ده‌ها اجرا مستقل برای هر تنظیم پارامتر احتمالی) تکیه می‌کنند - گزینه‌ای که به وضوح بسیار زمان‌بر است. امکان دیگر استفاده از تکنیک‌های آماری قدیمی مانند ANOVA است. یک روند تکاملی خاص این است که به EA اجازه دهیم خودش را برای یک مسئله معین کالیبره کند، در حالی که آن مسئله را حل می‌کند [7].
۶. تجزیه و تحلیل نتایج
مانند هر الگوریتم تصادفی، نتایج یک اجرای واحد EA بی معنی است. یک تحلیل تجربی معمولی بیش از 15 اجرا مستقل (همه چیز به جز جمعیت اولیه برابر است) اجرا می‌شود و میانگین‌ها، انحرافات استاندارد و آزمون T را در مورد آزمایش‌های مقایسه‌ای ارائه می‌کند.
با این حال، باید مسائل طراحی[17] را که در آن هدف یافتن حداقل یک راه‌حل بسیار خوب یک بار، از بهینه‌سازی روزانه (مانند کنترل، زمان‌بندی،...) که هدف آن یافتن مداوم یک راه‌حل خوب است، متمایز کرد. راه‌حل برای ورودی‌های مختلف در زمینه طراحی، انحراف استاندارد بالا مطلوب است به شرطی که میانگین نتیجه خیلی بد نباشد. در زمینه بهینه‌سازی، یک میانگین خوب و یک انحراف استاندارد کوچک الزامی است.
[1] Representation
[2] Parse-tree Spaces
[3] Inoculate
[4] Building Blocks
[5] Ergodicity
[6] Semantically Meaningful
[7] The fittest individuals reproduce and survive
[8] Evolution Engine
[9] Genitors
[10] Replacement
[11] Proportional Selection
[12] Tournament Selection
[13] Fight
[14] Generational Replacement
[15] Elitist
[16] Comma Strategies
[17] Design Problems
