استراتژی های تکاملی: معرفی جامع

استراتژی های تکاملی: معرفی جامع – ایران ترجمه – Irantarjomeh

مقالات ترجمه شده آماده گروه کامپیوتر

مقالات ترجمه شده آماده کل گروه های دانشگاهی

مقالات

چگونگی سفارش مقاله

الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.

www.irantarjomeh.com

استراتژی های تکاملی یک معرفی جامع

چکیده

این مقاله مقدمه جامعی در ارتباط با یکی از شاخه های اصلی محاسبات تکاملی ـ یعنی استراتژی های تکاملی (ES) ـ را ارائه می نماید که تاریخچه  آن  به دهه ۱۹۶۰ در آلمان بر می گردد. برای آغاز بررسی از یک مقاله تحقیقاتی در باب سابقه فلسفی چنین مضمونی استفاده می شود که مشخص کننده این موضوع خواهد بود که چرا ES به روشی که هم اکنون به کار گرفته می شود شناخته شده است. به علاوه الگوریتم های ES و اصول طراحی برای عملگرهای گوناگونی و انتخاب و همچنین مسایل تئوریکی مورد خطاب قرار گرفته و شاخه های متعاقب تحقیقات ES نیز به بحث گذاشته می شوند.

کلمات کلیدی: هوشمندی محاسباتی، تئوری سیر تکامل داروین، اصول طراحی برای عملگرهای ژنتیک یا عملگرهای ژنتیکی، محاسبه تکاملی، استراتژی های تکاملی، بهینه سازی

اختصارات: BBH ـ فرضیه بلوک اصلی، CMA ـ تطبیق ماتریس کوواریانس، CSA ـ تطبیق اندازه گام انباشته، EA ـ الگوریتم تکاملی، EC ـ محاسبات تکاملی، ES ـ استراتژی تکامل، EP ـ برنامه نویسی سیر تکاملی، GA ـ الگوریتم ژنتیک، GR ـ بازسازی ژنتیکی، TSP ـ مشکل فروشنده دوره گرد، TUB ـ دانشگاه فنی برلین

استراتژی های تکاملی: معرفی جامع

۱- مقدمه

فرآیند الهام بیولوژیکی در علوم کامپیوتر، مخصوصاً در مهندسی الگوریتم، را می توان به اوایل پیشرفت این رشته مرتبط دانست. در این ارتباط شاهد وجود اسامی ممتازی نظیر John von Neumann می باشیم که فراتر از صرف یک برنامه محاسباتی بزرگ، ویژگیهای مرتبط با اعداد را در فکر خود می پرورانید. این افراد پیشروی علوم کامپیوتر بسیار فراتر از آنچه فناوری های آن دوره در اختیار آنها می گذاشتند تفکرات خود را به کار گرفته و حتی ماشین هایی را در نظر می آوردند که قابلیت خود تکثیری داشتند.

سه الگو در ارتباط با رشته قدرتمند هوش مصنوعی همچنان در خلال سه الی چهار دهه اخیر به حیات خود ادامه داده و اخیراً تحت نام های قابل توجهی نظیر هوشمندی محاسباتی (Michalewicz و همکاران، ۱۹۹۴؛ Fogel و همکاران، ۱۹۹۸)، محاسبات نرم، یا محاسبه طبیعی به پیشرفت خود ادامه داده اند. دو الگو از این بین سعی در تقلید فرآیند مغز انسان از طریق شبکه های عصبی مصنوعی یا تعقل مرتبط با منطق فازی نموده اند. سومین الگو، محاسبه تکاملی (EC)، سعی در کسب سود از پدیده انباشتگی در جمعیت های تطبیقی حل مشکلات با توجه به مفاهیمی چون تولد و مرگ، گوناگونی و انتخاب، در یک حلقه تکراری و بترتیب توارثی، نموده است.

مجددا، سه مورد از منابع معاصر در ارتباط با الگوریتم های تکاملی (EA) همچنان در خلال سه دهه گذشته به حیات خود ادامه داده و شاهد یک افزایش قابل توجه در این زمینه در طی پانزده سال اخیر بوده ایم. دو مورد از آنها در ایالات متحده، منبع برنامه نویسی سیر تکاملی (EP) در ساندیوگو (Fogel، ۱۹۶۲؛ Fogel و همکاران، ۱۹۶۶)، منبع الگوریتم های ژنتیک (GA) در Ann Arbor (Holland، ۱۹۶۲؛ Holland، ۱۹۷۵) در این محدوده قرار دارند. استراتژی های تکاملی (ES)، به عنوان سومین مؤلفه مهم EA، به وسیله دانشجویان دانشگاه فنی برلین (TUB) به وجود آمد (Rechenberg، ۱۹۶۵؛ Rechenberg، ۱۹۷۱؛ Schwefel، ۱۹۶۵؛ Schwefel، ۱۹۷۵).

این مقاله نسبت به بررسی ES، اطلاعات مربوط به تولد و تاریخچه آن، همراه با ایده ها و فلسفه اصلی مرتبط و ویژگی های نوین مطرح شده اقدام می نماید. مقاله جاری به شرح ذیل سازماندهی شده است: بخش ۲ فراهم آورنده بینشی عمیق تر در ارتباط با تاریخچه مربوط به تحقیقات ES می باشد که خود مشخص کننده مبنا و فلسفه ES معاصر است. ایده ها و اصول اصلی و همچنین اجزای تشکیل دهنده طراحی الگوریتم های ES، نظیر جهش، بازترکیبی و عملگرهای انتخاب در بخش ۳ ارائه و تشریح می شوند. به علاوه ما مشاهده خواهیم نمود که ویژگی های عملکرد در ارتباط نزدیکی با رفتار تطبیقی عملگرهای ذکر شده هستند. بخش ۴ به رویکردهای مختلف در ارتباط با فرآیند تطبیق و پذیرش اختصاص داده شده است. ویژگی های تئوریکی تحقیقات ES نظیر دینامیک سیر تکاملی، همگرایی، عملکرد محلی و عمومی در فضاهای دارای ارزش حقیقی و فضاهای جستجوی گسسته، و پیچیدگی زمانی نیز جزء مباحث بخش ۵ به حساب می آیند. در نهایت این مقاله با بررسی برخی از ایده های مربوط به تکامل آتی تحقیقات ES به کار خود پایان می دهد.

استراتژی های تکاملی: معرفی جامع

۲- تاریخچه کوتاه در ارتباط با تحقیقات استراتژی تکاملی

ذیلاً ما بر روی ES تمرکز نموده و توجه خوانندگان علاقمند به مسایل تاریخی را به اطلاعات مندرج در خصوص تاریخچه EA در کتاب های ارتباطات تکاملی جلب می نماییم (De Jong و همکاران، ۱۹۹۷). حتی در این رابطه می توان به تاریخچه مشخصی اشاره داشت که به اواخر دهه ۵۰  قرن گذشته اشاره دارد (Fogel، ۱۹۹۸).

۲ـ۱٫ بهینه سازی سیر تکامل آزمایشی

در شروع، استراتژی های تکاملی به گونه ای طراحی نشده اند تا قابلیت محاسبه حداقلی یا حداکثری توابع ثابت دارای ارزش حقیقی با تعداد ثابت متغیرها و بدون نویز در طی سیر تکاملی خود وجود داشته باشد. در مقابل، آنها به عنوان مجموعه ای از قواعد برای طراحی اتوماتیک و تحلیل آزمایشات متوالی با توجه به تعدیلات گام به گام متغیرها مدنظر هستند که خود حاصل آمده از یک سیستم / آبجکت انعطاف پذیر متناسب در وضعیت بهینه آن علیرغم نویز محیطی است، همانند یک مجموعه سه بعدی باریک در یک جریان تونل باد که به صورت شکلی با یک ویژگی حجمی حداقلی خود را نشان می دهد. در این ارتباط آزمایش تعیین کننده ای در ژوئن سال ۱۹۶۴ با استفاده از یک صفحه متصل دو بعدی در جریان هوای آشفته انجام شده و نشان داد که یک وضعیت ابتکاری تصادفی ساده می تواند از عملکرد بهتری در مقایسه با استراتژی های تک متغیری و همچنین استراتژی های گرادیان مبنای گسسته برخوردار باشد، که برای بیان ویژگی های ریاضیات عددی مورد استفاده قرار می گیرند. تحت شرایط چند وجهی آشکار و توام با نویز، استراتژی جدید کارآمدی خود را نشان داده است و بنابراین از کارایی مکفی جهت به کار گرفته شدن برای یک جفت دیگر از راهکارهای بهینه سازی آزمایشی برخوردار است، همانند طراحی نازل فلش یا افشانک آب گرم به صورت همگرا یا واگرا و سه بعدی (Schwefel، ۱۹۶۸؛ Klockgether و Schwefel، ۱۹۷۰).

۲ـ۲٫ از متغیرهای تصمیم گسسته به پیوسته و اولین نتایج تئوریکی

یک مبحث (Schwefel، ۱۹۶۵) اقدام به بررسی (۱+۱)-ES با جهش های توزیع شده دو جمله ای بر روی یک لبه / مرز سهموی دو بعدی نمود. این مطالعه در می یابد که چنین فرآیندی را می توان در موقعیت های خاص اعمال داشت، چرا که نزدیک ترین موقعیت های مجاور / همسایه همگی تحت شرایط وخیمی هستند، در حالی که برای ارتقاء نیازمند جهش های بزرگی می باشیم که تحت توزیع جهشی استفاده شده، اگر نگوییم غیرممکن است، غیرمحتمل خواهد بود. این مورد منجر به ارائه ایده کاربرد متغیرهای پیوسته و توزیع گاوسی برای تغییرات متغیرها شده است.

۲ـ۳٫ بهینه سازی سیر تکاملی عددی تحمیل شده بر روی روشهای شبیه سازی

از زمانی که کامپیوترهای (مین فریم) وارد فرآیند محاسبات شدند، تمایلی جهت پذیرش نوعی استراتژی جدید در خصوص مشکلات جستجو برای پارامترهای بهینه در داخل مدلهای شبیه سازی وجود داشت، همانند مدلهایی که قابلیت شبیه سازی تنش و انحراف ساختارهای مهندسی ساختمان تحت بار را داشته باشند (Hartmann، ۱۹۷۴). چنین وظایفی به عنوان حوزه ای جهت فرآیندهای بهینه سازی عددی به شمار آمد که در نهایت شاهد نوعی ارتقاء در دهه ۱۹۶۰ بود، که این ارتقاء عمدتاً تحت عنوان جستجوی عملیاتی به وجود آمد که به دشواری قابلیت حصول آن در علوم مهندسی تصور می شد. به طور آشکار، نیاز جهت مقایسه کارایی استراتژی های تکاملی با استراتژی های رقبا در این عرصه احساس می شد، مخصوصاً آن دسته از استراتژی هایی که نیازی به ارائه ویژگی های مرتبط با مشتقات مرتبط به صورت سریع را نداشتند. نتایج این مطالعه در رساله دیگری در TUB به سال ۱۹۷۴ مطرح شد (Schwefel، ۱۹۷۵). همانند روش های کلاسیک، عملکرد استراتژی های تکاملی به میزان زیادی منوط به تعدیل پارامترهای داخلی می باشد، که عمدتاً شامل توان جهش مدنظر است. این مشاهده که مورد ES چند عضوی فوق الذکر دارای یک تمایل ذاتی به سمت کاهش توان جهش می باشد یا خیر، البته با توجه به آنکه چنین موردی می تواند مناسب تلقی گردد یا خیر، منجر بر آن شد تا Schwefel اقدام به ارائه دو نگارش متعاقب ES چند عضوی به شرح ذیل نماید:

استراتژی های تکاملی: معرفی جامع

۳- الگوریتم اصلی ES

این بخش ارائه دهنده اجزای لاینفک سیستم نوین ES می باشد که قابلیت خودتطبیقی (در ارتباط با معنی خودتطبیقی، به بخش ۴ـ۲ رجوع کنید) را خواهد داشت. در بخش ۳ـ۱ استاندارد ایده  ارائه شده و الگوریتم کلی ES ترسیم می شود. بخش ۳ـ۲ به عملگر انتخاب تخصیص داده شده است و بخش ۳ـ۳ در ارتباط با عملگر جهش می باشد و بخش ۳ـ۴ تشریح کننده عملگرهای بازترکیبی خواهد بود.

۳ـ۱٫ ایده و الگوریتم

هدف مفید یک استراتژی تکاملی بهینه سازی (برخی) توابع اهداف خاص یا توابع کیفی خاص (s)F با توجه به مجموعه از متغیرهای تصمیم یا پارامترهای کنترل y:= (y₁,y₂,…)–  در محتوای ES می باشد که غالباً تحت عنوان پارامترهای آبجکت خوانده می شود:

۳ـ۲٫ انتخاب

هر الگوریتم تکاملی نیازمند یک عملگر انتخاب هدف-مبنا می باشد تا قابلیت راهنمائی جستجو در نواحی محتمل فضای پارامتر آبجکت وجود داشته باشد. بر این مبنا انتخاب به صورت انتاگونیست یا متضاد عملگرهای گوناگونی (که تحت عنوان عملگرهای ژنتیک نیز خوانده می شود) جهش و بازترکیبی می باشد. چنین موردی سبب می شود تا فرآیند تکاملی دارای یک مسیر مشخصی باشد. انتخاب در ES دقیقاً همانند پرورش حیوانات یا گیاهان است: تنها آن دسته از افرادی که دارای خواص قابل توجهی هستند، همانند مقادیر برازندگی سطح بالا (مقادیر تابع هدف)، فرصت تولید مثل پیدا می نمایند. این بدان معنا خواهد بود که یک جمعیت والد جدید در (g + 1) به وسیله فرآیند قطعی حاصل می شود که تنها تضمین کننده بهترین افراد µ مرتبط با a از استخر انتخاب نسل (g) بوده که آنها بدین طریق به  انتقال می یابند (این تکنیک انتخاب تحت عنوان انتخاب “کوتاه سازی یا برش” یا “پرورش / تولید مثل” خوانده می شود)

۳ـ۳٫ جهش

۳ـ۳ـ۱٫ ویژگی های کلی

عملگر جهت غالباً یک عملگر گوناگونی پایه در ES می باشد. این بدان معنا خواهد بود که چنین موردی به عنوان منبع اولیه گوناگونی ژنتیک به حساب می آید. طراحی عملگرهای جهشی به صورت مشکل مبنا هستند. در عین آنکه هیچگونه روش طراحی مشخصی تا به امروز وجود ندارد، برخی از قواعد پیشنهاد شده اند (Beyer، ۲۰۰۱ب) آن هم از طریق تعدیل رویه های پیاده سازی توأم با موفقیت ES به وسیله ملاحظات تئوریکی:

1. قابلیت دسترسی یا دسترس پذیری

2. عدم سوگیری

3. مقیاس پذیری

۳ـ۳ـ۱ـ۱٫ دسترس پذیری. با توجه به یک حالت والدینی (y_p,s_p)، اولین ضروریت تضمین این موضوع خواهد بود که هر حالت دیگر (محدود) به صورت  را بتوان در داخل یک تعداد مراحل جهشی نسل ها حاصل آورد. چنین موردی همچنین به عنوان شرط ضروری برای فراهم آوردن همگرایی کلی می باشد.

۳ـ۳ـ۱ـ۲٫ عدم سوگیری. این ضروریت را می توان از فلسفه تکامل داروینی ما حاصل آورد. انتخاب و گوناگونی مشخص کننده تفاوتها و در برخی از مواقع اهداف ضد و نقیض می باشد: انتخاب دربردارنده اطلاعات برازندگی به منظور راهنمایی جستجو در یک جهت مطلوب و در نواحی فضای جستجوی مناسب می باشد، در حالیکه گوناگونی خود قابلیت بررسی فضای جستجو را خواهد داشت، یعنی آنکه این مورد الزامی برای استفاده از هر گونه اطلاعات برازندگی نخواهد داشت چرا که اطلاعات فضای جستجو از جمعیت والد موجود است. بنابراین هیچگونه تدرجیحی در ارتباط با هر کدام از افراد انتخاب شده (والدین) در ES وجود ندارد، اما عملگرهای گوناگونی نباید هیچگونه سوگیری یا حالت اریبی را القا نمایند.

۳ـ۳ـ۲٫ مثال ها

در این ارتباط ما عملگرهای استاندارد جهشی را برای پارامترهای آبجکت ارائه می نماییم (یعنی عملگر در خط شماره ۱۰، شکل ۱)، عملگرها برای پارامترهای استراتژی جهش درون زاد نیز در بخش ۴ ـ۲ ارائه خواهند شد.

۳ـ۳ـ۲ـ۲٫ فضاهای جستجوی باینری. در فضاهای جستجوی دودویی یا باینری ، فرآیند جهش به وسیله فیلیپ های بیزی تصادفی بردار والد باینری y مشخص می گردد. ویژگی عدم سوداری در اینجا به وسیله “معکوس پذیری میکروسکوبی” اعمال خواهد شد، یعنی آنکه احتمال p_m معکوس سازی در ۱ـ بیت مساوی با فرآیند متضاد می باشد. نرخ جهش p_m را می توان به عنوان ویژگی نامعلوم استحکام یا قدرت جهش قلمداد نمود.

۳ـ۳ـ۲ـ۳٫ فضاهای جستجوی ترکیبی. حوزه وظایف بهینه سازی ترکیبی کاملاً به صورت متنوع و چند بعدی می باشد. بر این مبنا ما ویژگی مورد نظر خود را به مشکلات مرتبه بندی ساده مقید نمودیم که در آن برازندگی یک فرد به وسیله مرتبه خاص مؤلفه های آن مشخص می شود. حالت های آبجکتیو مختلف به وسیله مرتبه جای گشت یا تبدیل مرتبط با این مؤلفه ها حاصل می شود. یک مثال نوعی مشکل فروشنده دوره گرد (TSP) است. جهش ها به وسیله جای گشت مرتبه والدینی مشخص می گردند. چنین موردی را می توان به طرق مختلف حاصل آورد. شکل ۵ نشان دهنده یک مجموعه ای از مراحل حرکت اولیه جمع آوری شده می شود. این عملگرهای مرحله جستجوی اولیه مشخص کننده برخی از نواحی مجاور خاص است، یعنی تعداد حالت هایی که قابلیت حاصل آوردن آنها از حالت والدینی در داخل یک مرحله وجود دارد.

۳ـ۴٫ بازترکیبی

۳ـ۴ـ۱٫ عملگرهای بازترکیبی ES استاندارد

در عین آنکه جهش قابلیت انجام مراحل جستجو بر مبنای اطلاعات تنها یک جفت را دارد و در صورت امکان پذیر بودن، این عمل را بر مبنای پارامترهای استراتژی درون زاد خود انجام می دهد، فرآیند بازترکیبی اقدام به به اشتراک گذاری اطلاعات از بیش از  فرد والد می نماید (Schwefel، ۱۹۷۵؛ Rechenberg، ۱۹۷۸؛ Rechenberg، ۱۹۹۴). در صورتی که  صادق باشد، ما در ارتباط با فرآیند بازترکیبی متعدد صحبت می نماییم. بر خلاف کراس اور استاندارد در مبحث GA (Goldberg، ۱۹۸۹) که در آن دو والد یا جفت اقدام به تولید دو نوزاد می نمایند، کاربرد عملگر بازترکیبی ES استاندارد برای یک خانواده والد یا جفت به اندازه  تنها قابلیت تولید یک نوازد را خواهد داشت (شکل ۶).

۳ـ۴ـ۲٫ در خصوص مزیت های بازترکیبی و اصول طراحی

۳ـ۴ـ۲ـ۱٫ بلوک های اصلی این فرضیه

در این مبحث همچنان گفتگوهای اساسی در ارتباط با مفید بودن و کاربرد اصول بازترکیبی به چشم می خورد. در تحقیقات GA این فرضیه ها (BBH) (Goldberg، ۱۹۸۹؛ Holland، ۱۹۹۵) به منظور توصیف مکانیسم کاری کراس اور ارائه شده است: انواع بلوک های ساختاری مناسب مختلف از والدهای مختلف با یکدیگر ترکیب شده، و از این طریق قابلیت ترکیب خواص خوب والدها در نوزادها را به وجود می آورند. در عین آنکه این توصیف از نقطه نظر شهودی قابل توجه می باشد، یافتن توابع آزمایشی جهت پشتیبانی از این فرضیه به نظر بسیار مشکل می باشد (Mitchell و همکاران، ۱۹۹۴). تنها اخیراً Jansen و Wegener (2001) قابلیت ایجاد یک تابع آزمایش مصنوعی را یافته اند که در آن یک کراس اور تک نقطه ای به طور الزامی قابلیت ارتقا پیچیدگی زمانی را خواهد داشت، و از این طریق می تواند نکات کلیدی را در زمینه کاربردپذیری BBH در این نوع از موقعیت های خاص فراهم آورد.

۳ـ۴ـ۲ـ۲٫ بازیابی ژنتیکی و استخراج مشابهت. در طی دهه ۱۹۹۰، تحقیقات تئوری ES مکانیسم کاربردی قابل توجه دیگر فرآیند بازترکیبی را مشخص نمود ـ تأثیر بازیابی ژنتیکی (GR) (Beyer، ۱۹۹۵)، که خود سبب ارائه فرضیه GR شده است (Beyer، ۱۹۹۷). این فرضیه در نقطه مقابل با BBH قرار دارد: که در آن ویژگی های متفاوت (مطلوب) جریان والدهای مختلف در امتداد کاربرد عملگر بازترکیبی در نوزادها دیده نمی شود، بلکه آنچه قابل توجه است ویژگی های مشترک آنها می باشد. این بدان معنا است که، فرآیند بازترکیبی قابلیت استخراج مشابهت ها از والدهای مختلف را خواهد داشت.

استراتژی های تکاملی: معرفی جامع

۴- پذیرش پارامترهای استراتژی درون زاد

این بخش به فرآیند پذیرش پارامترهای استراتژی که قابلیت کنترل خواص آماری عملگرهای گوناگونی را دارند، مخصوصاً عملگرهای جهش، اختصاص یافته است. در بخش ۴-۱، ما پارامترهایی نظیر انگیزه و شهرت، یعنی قاعده یک پنجم را برای کنترل توان جهش در(۱+۱)-ES  را ارائه می نمائیم. بخش دوم ایده خود تطبیقی را ارائه می نماید – تکنیک پذیرش سیر تکاملی استاندارد بر مبنای (تمپرو) اطلاعات جمعیت محلی مشخص می شود. بخش ۴-۳ مقدمه کوتاهی در ارتباط با تکنیک های پذیرش پیشرفته با استفاده از اطلاعات فضای جستجوی غیر محلی را عرضه می نماید.

۴-۱٫ انگیزه و قاعده یک پنجم

۴-۱-۱٫ اکتشاف پنجره تکامل

نیاز جهت کنترل پارامترهای استراتژی درون زاد به هنگامی مشهود شد که اقدام به اجرای یک (۱+۱)-ES  ساده با جهش های گاوسی ایزوتروپیک (۶) و مشخص سازی طول جهش ثابت σ بر روی یک تابع هدف ساده F(y) شده است. چنین قاعده به حداقل رسانی، با استفاده از مدل کروی F_sp(y) به شرح ذیل خواهد بود:

۴ـ۱ـ۲٫ قاعده یک پنجم

بر مبنای این حقیقت که هردوی عملکرد  و احتمال موفقیت P_s منوط به σ می باشد، یک قاعده کنترل σ را می توان مدنظر قرار داد. شکل ۱۰ نشان دهنده P_s و نرخ پیشرفت به هنجار شده می باشد که برای مدل کروی (۱۶) در مورد محدوده مجانبی  محاسبه شده است (Rechenberg، ۱۹۷۳؛ Beyer، ۲۰۰۱ب).

۴ـ۲٫ خود تطبیقی

در بخش ۴ـ۱ ما انگیزه مرتبط با تعدیل پارامتر استراتژی درون زاد σ به منظور حصول عملکرد نزدیک به بهینه (محلی) (۱ + ۱)-ES در فضاهای جستجوی دارای ارزش حقیقی را ارائه نمودیم. در عین آنکه مباحث مرتبط با پذیرش σ به طور کلی مدنظر قرار گرفته اند، قاعده پذیرش ارائه شده در اینجا یعنی قاعده یک پنجم، به عنوان یک قاعده کاملاً مخصوص می باشد: کنترل موارد ابتکاری ارائه شده به عنوان ساده ترین نگارش پذیرش غیرمحلی قطعی در این رابطه مدنظر خواهد بود. این مورد از اطلاعات کلی احتمال موفقیت استفاده می نماید که قابلیت جمع آوری آن از طریق داده های آماری در ارتباط با تعداد G نسلها وجود دارد تا آنکه بتوان به صورت قطعی نسبت به تغییر توان جهشی اقدام نمود. این موضوع کاملاً آشکار می باشد که قاعده یک پنجم دارای کاربردهای خاص خود می باشد:

۴ـ۲ـ۱٫ ایده اصلی

ایده اصلی خودتطبیقی در ES وابسته به پارامترهای استراتژی جفت شدگی افراد به صورت درون زاد (در یک حالت تکاملی) با توجه به پارامترهای آبجکت می باشد. این بدان معنا است که همانگونه که در معادله ۲ بیان شد، هر فرد دارای مجموعه پارامترهای استراتژی خاص خود می باشد. این پارامترهای استراتژی درون زاد در معرض تغییر خواهند بود. این مورد ویژگی های شبه کد  را نیز باید در نظر آورد، بر اساس شکل ۱٫ پارامترهای استراتژی ممکن است فرآیند بازترکیبی را در نظر داشته و غالباً بر این مبنا تحت جهش قرار داشته باشند.

۴ـ۲ـ۲٫ جزئیات پیاده سازی

درک مفهومی ES خودتطبیقی منوط به انواع پارامترهای استراتژی مورد پذیرش خواهد بود. در موارد ذیل ما پذیرش نوعی پارامتر توان جهش واحد σ را به تفصیل مورد بررسی قرار می دهیم. ویژگی های عمومی بیش از یک پارامتر جهشی نیز به طور خلاصه مورد بحث قرار می گیرد. با توجه به انواع دیگر پارامترهای استراتژی و همچنین رفتار خودتطبیقی در GA کد شده ـ حقیقی، خوانندگان می بایست به مبحث Beyer و Deb (2001) و مراجع لیست شده در آن رجوع نمایند.

۴ـ۲ـ۱٫ چگونگی تغییر توان جهش σ. اصول طراحی بخش ۳ـ۳ برای عملگرهای پارامتر استراتژی نیز صحت خواهد داشت. با این وجود، تجربه عملی نشان دهنده آن می باشد که برخی از اصول مربوطه ممکن است تا اندازه ای بدون پیامدهای جدی نقض شوند. احتمالاً ضروری ترین نیاز در ارتباط با ثبات پذیری در فضاهای جستجوی R^N می باشد.

۴ـ۲ـ۲ـ۲٫ قواعد جهش برای مجموعه ای از پارامترهای استراتژی. تکنیک جهش σ ضربی را می توان برای موردی گسترش داد که در آن ما از یک بردار پارامترهای استراتژیs =σ =(σ۱,…,σN) ، که در معادل (۸) نیاز است، برخوردار باشیم. Schwefel (1977) به کارگیری یک لگاریتم ـ نرمال گسترش یافته را پیشنهاد نمود که در بردارنده مورد ذیل (دفع کننده شاخص اولاد) می باشد:

۴ـ۲ـ۲ـ۳٫ چگونگی بازترکیبی پارامترهای استراتژی درون زاد. همانگونه که در بخش ۳ـ۴ بحث شد یک تاثیر اصلی بازترکیبی استخراج مشابهت ها می باشد. با توجه به پذیرش پارامتر استراتژی، چنین موردی به عنوان یک تأثیر مطلوب به حساب می آید. همانگونه که در این آزمایشات مشاهده شده است، دینامیک تکاملی پارامترهای استراتژی غالباً به عنوان یک فرآیند نویزدار با نوسانات زیاد تلقی می شود. این نوسانات غالباً سبب تنزل عملکرد ES خواهد شد. بنابراین، تکنیک هایی که قابلیت کاهش نوسانات را دارند مورد نیاز می باشند. به همین دلیل است که چرا بازترکیب سطح میانی (µ/µ) کاملاً توصیه می شود.

۴ـ۳٫ رویکردهای تطبیقی غیرمحلی

۴ـ۳ـ۱٫ انگیزش

خودتطبیقی بر روی سطح افراد همانگونه که در بخش ۴ـ۲ نشان داده شده است ممکن است با شکست روبرو شود. دلیل این شکستهای احتمالی غالباً رفتاری می باشد که می توان آن را تحت عنوان “رفتار فرصت طلبانه” ذکر نمود: بدان صورت که سیر تکاملی اقدام به پاداش دادن موفقیت های کوتاه مدت می نماید، یعنی آنکه در صورتی که پیشرفت محلی و پیشرفت کلی دارای همبستگی مثبتی نباشند، سیر تکاملی ممکن است اقدام به انتخاب آن دسته از حالت های نوزادهایی نماید که در نهایت در یک ویژگی بهینه موضعی به اتمام رسیده یا حتی ممکن است آنچه تحت عنوان همگرایی نارس یا زودهنگام می باشد را از خود نشان دهند.

۴-۳-۲٫ Meta-ES

Meta-ES یا ” nested ES” مترادف یا “ ES سازماندهی سلسله مراتبی” به عنوان آن دسته از استراتژی هایی به حساب می آیند که می بایست آنها را برحسب مورد ذیل توصیف نمود:

۴ـ۳ـ۳٫ کنترل طول مسیر انباشته ـ CSA-ES

نوعی کلاس تکنیک های غیرمحلی قطعی برای پذیرش عملگرهای جهشی در Rⁿ وجود دارد که این ایده را می توان در ارتباط با مباحث مطرح شده Ostermeier و همکاران دانست (۱۹۹۴): کنترل طول مسیر انباشته. به منظور حصول نوعی احساس شهودی در این ارتباط و یافتن معانی چنین عباراتی اجازه دهید تا در رابطه با آنچه تحت عنوان مسیر تکاملی v خوانده می شود، یعنی در ساده ترین شکل، مجموع بردار مراحل تکاملی مشخص شده حقیقی در ارتباط با تعداد نسل های G، تفکر کنیم.

استراتژی های تکاملی: معرفی جامع

۵- ویژگی های تئوریکی

۵ـ۱٫ انگیزش

این مورد غالباً در جامعه EC مشخص می شود که مفید بودن تئوری در این رشته نسبتاً پرسش برانگیز می باشد (همانند Eiben و همکاران، ۱۹۹۹، صفحه ۱۲۶). با این وجود، با بازگشت به عقب و داشتن یک دیدگاه بسیار گسترده تر، این موضوع آشکار می گردد که هر فرد شرکت کننده در EA از “برخی از” یا “ویژگی های مربوط به” تئوری استفاده می نماید. تئوری در این مفهوم را می بایست به عنوان ویژگی های جمع آوری شده و تجارب حاصله یا دانش های مفید برای ایجاد پیش بینی ها در ارتباط با رفتار سیستم مورد نظر مشخص ساخت. چنین موردی شامل تئوری های ریاضیاتی و اثباتی می باشد، اما در عین حال این مورد متشکل از “دانش نرم تر” نیز است که صحت آن اثبات نشده است یا آنکه اعتبار آن می بایست به خودی خود به اثبات رسد آن هم به صورت مقید به ویژگی های خاص با توجه به پیشرفت تئوریهای ریاضیاتی صفر در آینده. از این نکته نظر، غالب مواد ارائه شده در این مقاله غالباً متعلق به دسته بندی دوم هستند. چنین موردی الزاماً سبب مستثنی نمودن این موضوع نخواهد شد که برخی از نکات و ویژگی های کلیدی خاص از تئوری جاری وجود دارد. برخی از اصول ارائه شده در بخش ۳ و۴ را می توان به عنوان موارد قیاسی یا برآورد برونی از تئوری ریاضیاتی مدنظر قرار داد که شامل الگوریتم تکاملی و تابع برازندگی و همچنین این موضوع می باشد که یک سیستم تکاملی از دینامیک تکاملی خاص پیروی خواهد داشت. از این نکته نظر مرتبط با اهداف تئوری ریاضیاتی الگوریتم های تکاملی (EA) قابلیت پیش بینی دینامیکی EA وجود خواهد داشت.

۵ـ۲٫ هدف: پیش بینی دینامیک تکاملی

۵ـ۲ـ۱٫ انگیزش

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

۵ـ۲ـ۲٫ مثالها

حال اجازه دهید تا دو مثال مربوط به فرآیندهای بهبودی را در فضای جستجوی دارای ارزش حقیقی و ترکیبی مورد بررسی قرار دهیم. شکل ۱۲ نشان دهنده نمونه های نوعی دینامیک بهترین نوع حاصله تاکنون از نقطه نظر برازندگی (یعنی مقادیر تابع برازندگی F با توجه به تعداد g مربوط به نسلها) می باشد.

۵ـ۳٫ فضاهای جستجوی دارای ارزش حقیقی

در تحقیقات ES تئوریکی شاهد نوعی سنت قابل توجه هستیم که به اوایل دوره ES بر می گردد. Schwefel (1965) اقدام به ارائه تحلیل (۱+۱)-ES بر روی یک لبه سهموی گسسته شده و همچنین بر روی ابر صفحه و مدل کروی با استفاده از جهش های گاوسی ایزوتروپیک نموده است. این کار به وسیله Rechenberg (1973) و Schwefel (1975) نیز تداوم یافته و منجر به ارائه مفاهیمی نظیر نرخ پیشرفت و احتمالات موفقیت شده است. در این بخش، ما مفهوم ساده نرخ پیشرفت را ارائه نموده و متعاقباً برخی از مثالها در این ارتباط را عرضه داشته و همچنین ارتباطات دینامیک تکاملی را نشان می دهیم.

۵ـ۳ـ۱٫ برآوردهای عملکرد محلی

برآوردهای عملکرد محلی به عنوان مقادیر مورد انتظار حالت های جمعیت (انباشته) می باشد. آنها غالباً به گونه ای تعریف می شوند که قابلیت کاربرد آنها جهت ارزیابی توان بهبودی ES به صورت محلی وجود داشته باشد. به هنگامی که ما از “محلی” صحبت می کنیم به معنی وضعیت محلی از نظر زمان است، یعنی این برآوردها تشریح کننده موفقیت بین دو نسل متوالی (g) و (g+1) می باشد.

۵ـ۳ـ۱ـ۱٫ تعریف نرخ پیشرفت. پیشرفت بهبودی را می توان بر مبنای فضای برازندگی و همچنین فضای پارامتر آبجکت مورد سنجش قرار داد. مورد آخری تحت عنوان “نرخ پیشرفت” خوانده می شود در حالی که مورد اولی غالباً تحت عنوان “بهره کیفیت” خوانده می شود (برای بررسی جامع تر به مبحث Beyer، ۲۰۰۱ مراجعه کنید). در اینجا ما تنها سرعت پیشرفت ϕ را مدنظر قرار می دهیم . این مورد در شکل ۱۳ به عنوان تغییر فاصله مورد انتظار Dr جمعیت والدینی که در بخش مرکزی فضای پارامتر آبجکت قرار دارند (فضای جستجو) به وسیله بهینه ساز  مدنظر است. 

۵ـ۳ـ۱ـ۲٫ مثال: مدل کروی. قابل توجه ترین تابع تست مدل کروی می باشد که قبلاً در معادله (۱۶) ارائه شده است. این مدل معرف یک کلاس تابع متقارن است که دربردارنده ارزش های مختلف مربوط به توابع مشخص است و صرفاً وابسته به فاصله R مرتبط با y در ارتباط با بهینه شدگی خواهد بود. بر این مبنا R را می توان به عنوان حالت انباشته در نظر داشت که اجازه کاهش دینامیک N بعدی برای حصول یک دینامیک ـ R تک بعدی را خواهد داد. با توجه به ES همراه با جهش های گاوسی ایزوتروپیک مرتبط با توان σ و حالت والدینی R، سرعت پیشرفت ϕ صرفاً منوط به سه پارامتر R، و N و σ می باشد. با استفاده از این فرآیند به هنجارسازی خواهیم داشت:

۵ـ۳ـ۱ـ۳٫ مثال: کره نویزدار. برای یک مدت مدیدی یافتن یک تابع آزمایش ساده که قابلیت نشان دادن آن به وسیله تئوری برحسب کارایی (µ/µ, λ) وجود داشته باشد و فراتر از (۱+۱)-ES باشد به عنوان یک مورد مشکل آفرین مطرح بوده است. اخیراً، دو پیشرفت بدون ترک حوزه مدلهای کروی ایجاد شده است. در ابتدا، یک مدل کروی دو مودی در B^N در بخش ۵ـ۴ گزارش شده است، و دوماً مدل کروی نویزدار در R^N مشخص گردیده است.

۵ـ۳ـ۲٫ ویژگی های دینامیکی

دینامیک مقدار میانگین حالت های جمعیت انباشته غالباً بر مبنای یک سیستم معادلات تفاضلی N+N_s است، که در آن N_s به صورت بعدی به عنوان مجموعه پارامتر استراتژی بشمار می آید. تحت شرایط خاص و فرضیه های خاص این سیستم به یک معادله تفاضلی واحد کاهش خواهد یافت.

۵ـ۳ـ۲ـ۲٫ معیار تکاملی و عدم همگرایی. همگرایی به سمت وضعیت مطلوب و بهینه تا زمانی تضمین خواهد شد که فاصله باقیمانده R با زمان کاهش یابد. با استفاده از معادله (۴۳) می توان ملاحظه نمود که چنین موردی به صورت متناظر با  است. به عنوان یک مثال، اجازه دهید تا مجددا (µ/µ, λ)-ES را بر روی مدل کروی مدنظر قرار دهیم. با توجه به معادله (۴۰) می توان نسبت به مشخص نمودن معیار تکاملی که از طریق آن همگرایی تضمین می شود اقدام نمود:

۵ـ۴٫ فضاهای جستجوی باینری

بررسی های تئوریکی در ارتباط با رفتار دینامیکی ES در فضاهای جستجوی B^N با توجه به توابع شبه بولی همچنان اعمال می گردند. با این وجود، پیشرفت قابل توجهی در ارتباط با زمان اجرای مورد نظر و احتمال موفقیت کلی ES با انتخاب پلاس مدنظر خواهد بود. ما تنها برخی از این نتایج را مورد بررسی قرار داده و خوانندگان را به تحقیق اصلی انجام شده به وسیله Wegener و همکاران هدایت می نماییم (به موارد ذیل رجوع شود).

۵ـ۴ـ۱٫ عملکرد کلی (۱+۱)-ES

غالب نتایج حاصل آمده تاکنون در ارتباط با عملکرد (۱+۱)-ES هستند. برای توابع خطی:

۵ـ۴ـ۲٫ افزایش عملکرد به وسیله بازترکیبی در (µ/۲+۱)-ES

پس از یک دوره طولانی از تلاشهای ناموفق (Mitchell و همکاران، ۱۹۹۴، Horn و همکاران، ۱۹۹۴) جهت نشان دادن مزیت های عملکرد بازترکیبی در B^N، Jansen و Wegener (1994) یک تابع آزمایشی را ارائه دادند که در آن فرآیند بازترکیبی  گسسته (۱۱) قابلیت کاهش زمان اجرای مورد انتظار در مقایسه با ES با استفاده از فرآیند جهش با نرخ صرفاً p_m=1/N را خواهد داشت.

استراتژی های تکاملی: معرفی جامع

۶- چشم انداز

در موارد فوق، ما تنها جریان اصلی ES را مدنظر قرار دادیم، یعنی نمونه های قدیمی تر مشخص شده استراتژی های تکاملی که تقلید کننده صرف چندین اصل کلی حاصل آمده از طبیعت می باشند. تکامل ارگانیک دارای ویژگی های بسیاری می باشد، برخی از این ویژگی ها را می توان مورد توجه قرار داد چرا که آنها به عنوان منابع اضافه حصول اطلاعات در زمینه ایجاد ویژگی های مصنوعی در ارتباط با بهینه سازی و راهکارهای تطبیقی می باشند. در این زمینه برخی از پیشنهادات وجود دارند که البته هنوز تحت بررسی های کاملی قرار نگرفته و به صورت تجربی نیز آزمایش نشده اند که ذیلاً مشخص خواهند شد.

طول حداکثری عمر یک فرد الزاماً نباید به صورت نامحدود باشد همانگونه که در نگارش پلاس الگوریتم استاندارد مطرح گردیده یا محدود به صرف یک دوره یا یک تکرار خاص (نظم) نیز نمی تواند باشد همانگونه که به وسیله نگارش کاما مشخص شده است. هر نوع ویژگی k صحیح مثبت را می توان جهت کنترل تعداد حداکثری تکرارها (که هم اکنون چرخه های تولیدی بهتر را تشکیل می دهند) به کار گرفت و بر این مبنا افراد قابلیت ماندن در داخل جمعیت مورد نظر را خواهند داشت. تنها پس از k چرخه چنین موردی از استخر ژنی یا مخزن ژنی حذف گردیده با این حال می توان آن را جایگزین یک اولاد بهتر یا حداقل مساوی با مورد قبلی نمود. این نگارش تحت عنوان (µ,κ,λ,ρ)-ES خوانده می شود (Schwefel و Rudolph، ۱۹۹۵)، که در آن  همانند معمول، به عنوان تعداد اجداد یک نسل یا اولاد جدید به شمار می آید که متشکل از فرآیند بازترکیبی است. بر این مبنا می توان انتظار داشت که مقادیر κ خاص بهتر از موارد دیگر در زمینه پشتیبانی از خودتطبیقی پارامترهای استراتژی عمل خواهند نمود.

…

متعاقباً و همچنان به عنوان بیشترین گزینه غیرمترقبه ES/EA ارتقا یافته ارائه ویژگی دو پیلوئیدی و حتی چند پیلوئیدی می باشد (Kursawe، ۱۹۹۲) و به علاوه شاهد ویژگی چندسلولی همراه با جهش های سماتیک نیز خواهیم بود (Schwefel و Kursawe، ۱۹۹۸). پیشرفت های بیشتری در این خصوص و موارد متعاقب را می توان در آینده انتظار داشت که در آن ژورنال های مرتبط در زمینه محاسبه تکاملی اقدام به انتشار مطالب خود نموده و در کنار آنها کنفرانس های متعددی نیز به صورت سالیانه در گوشه و کنار جهان چنین موضوعی را به بحث می گذارند.