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

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

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

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

مقالات رایگان

مطالعه 20 الی 100% رایگان مقالات ترجمه شده

1- قابلیت مطالعه رایگان 20 الی 100 درصدی مقالات 2- قابلیت سفارش فایل های این ترجمه با قیمتی مناسب مشتمل بر 3 فایل: pdf انگیسی و فارسی مقاله همراه با msword فارسی -- تذکر: برای استفاده گسترده تر کاربران گرامی از مقالات آماده ترجمه شده، قیمت خرید این مقالات بسیار کمتر از قیمت سفارش ترجمه می باشد.  

چگونگی سفارش

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

www.irantarjomeh.com

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

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

چکیده

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

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

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

1- مقدمه

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

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

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

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

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

ذیلاً ما بر روی ES تمرکز نموده و توجه خوانندگان علاقمند به مسایل تاریخی را به اطلاعات مندرج در خصوص تاریخچه EA در کتاب های ارتباطات تکاملی جلب می نماییم (De Jong و همکاران، 1997). حتی در این رابطه می توان به تاریخچه مشخصی اشاره داشت که به اواخر دهه 50  قرن گذشته اشاره دارد (Fogel، 1998).

2ـ1. بهینه سازی سیر تکامل آزمایشی

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

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

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

2ـ3. بهینه سازی سیر تکاملی عددی تحمیل شده بر روی روشهای شبیه سازی

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

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

این بخش ارائه دهنده اجزای لاینفک سیستم نوین ES می باشد که قابلیت خودتطبیقی (در ارتباط با معنی خودتطبیقی، به بخش 4ـ2 رجوع کنید) را خواهد داشت. در بخش 3ـ1 استاندارد ایده  ارائه شده و الگوریتم کلی ES ترسیم می شود. بخش 3ـ2 به عملگر انتخاب تخصیص داده شده است و بخش 3ـ3 در ارتباط با عملگر جهش می باشد و بخش 3ـ4 تشریح کننده عملگرهای بازترکیبی خواهد بود.

3ـ1. ایده و الگوریتم

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

3ـ2. انتخاب

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

3ـ3. جهش

3ـ3ـ1. ویژگی های کلی

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

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

2. عدم سوگیری

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

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

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

3ـ3ـ2. مثال ها

در این ارتباط ما عملگرهای استاندارد جهشی را برای پارامترهای آبجکت ارائه می نماییم (یعنی عملگر در خط شماره 10، شکل 1)، عملگرها برای پارامترهای استراتژی جهش درون زاد نیز در بخش 4 ـ2 ارائه خواهند شد.

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

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

3ـ4. بازترکیبی

3ـ4ـ1. عملگرهای بازترکیبی ES استاندارد

در عین آنکه جهش قابلیت انجام مراحل جستجو بر مبنای اطلاعات تنها یک جفت را دارد و در صورت امکان پذیر بودن، این عمل را بر مبنای پارامترهای استراتژی درون زاد خود انجام می دهد، فرآیند بازترکیبی اقدام به به اشتراک گذاری اطلاعات از بیش از  فرد والد می نماید (Schwefel، 1975؛ Rechenberg، 1978؛ Rechenberg، 1994). در صورتی که  صادق باشد، ما در ارتباط با فرآیند بازترکیبی متعدد صحبت می نماییم. بر خلاف کراس اور استاندارد در مبحث GA (Goldberg، 1989) که در آن دو والد یا جفت اقدام به تولید دو نوزاد می نمایند، کاربرد عملگر بازترکیبی ES استاندارد برای یک خانواده والد یا جفت به اندازه  تنها قابلیت تولید یک نوازد را خواهد داشت (شکل 6).

3ـ4ـ2. در خصوص مزیت های بازترکیبی و اصول طراحی

3ـ4ـ2ـ1. بلوک های اصلی این فرضیه

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

3ـ4ـ2ـ2. بازیابی ژنتیکی و استخراج مشابهت. در طی دهه 1990، تحقیقات تئوری ES مکانیسم کاربردی قابل توجه دیگر فرآیند بازترکیبی را مشخص نمود ـ تأثیر بازیابی ژنتیکی (GR) (Beyer، 1995)، که خود سبب ارائه فرضیه GR شده است (Beyer، 1997). این فرضیه در نقطه مقابل با BBH قرار دارد: که در آن ویژگی های متفاوت (مطلوب) جریان والدهای مختلف در امتداد کاربرد عملگر بازترکیبی در نوزادها دیده نمی شود، بلکه آنچه قابل توجه است ویژگی های مشترک آنها می باشد. این بدان معنا است که، فرآیند بازترکیبی قابلیت استخراج مشابهت ها از والدهای مختلف را خواهد داشت.

4- پذيرش پارامترهاي استراتژي درون زاد

اين بخش به فرآيند پذيرش پارامترهاي استراتژي كه قابليت كنترل خواص آماري عملگرهاي گوناگوني را دارند، مخصوصاً عملگرهاي جهش، اختصاص يافته است. در بخش 4-1، ما پارامترهايي نظير انگيزه و شهرت، يعني قاعده يك پنجم را براي كنترل توان جهش در(1+1)-ES  را ارائه مي نمائيم. بخش دوم ايده خود تطبيقي را ارائه مي نمايد – تكنيك پذيرش سير تكاملي استاندارد بر مبناي (تمپرو) اطلاعات جمعيت محلي مشخص مي شود. بخش 4-3 مقدمه كوتاهي در ارتباط با تكنيك هاي پذيرش پيشرفته با استفاده از اطلاعات فضاي جستجوي غير محلي را عرضه مي نمايد.

4-1. انگيزه و قاعده يك پنجم

4-1-1. اكتشاف پنجره تكامل

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

4ـ1ـ2. قاعده یک پنجم

بر مبنای این حقیقت که هردوی عملکرد  و احتمال موفقیت P_s منوط به σ می باشد، یک قاعده کنترل σ را می توان مدنظر قرار داد. شکل 10 نشان دهنده P_s و نرخ پیشرفت به هنجار شده می باشد که برای مدل کروی (16) در مورد محدوده مجانبی  محاسبه شده است (Rechenberg، 1973؛ Beyer، 2001ب).

4ـ2. خود تطبیقی

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

4ـ2ـ1. ایده اصلی

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

4ـ2ـ2. جزئیات پیاده سازی

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

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

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

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

4ـ3. رویکردهای تطبیقی غیرمحلی

4ـ3ـ1. انگیزش

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

4-3-2. Meta-ES

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

4ـ3ـ3. کنترل طول مسیر انباشته ـ CSA-ES

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

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

5ـ1. انگیزش

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

5ـ2. هدف: پیش بینی دینامیک تکاملی

5ـ2ـ1. انگیزش

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

5ـ2ـ2. مثالها

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

5ـ3. فضاهای جستجوی دارای ارزش حقیقی

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

5ـ3ـ1. برآوردهای عملکرد محلی

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

5ـ3ـ1ـ1. تعریف نرخ پیشرفت. پیشرفت بهبودی را می توان بر مبنای فضای برازندگی و همچنین فضای پارامتر آبجکت مورد سنجش قرار داد. مورد آخری تحت عنوان “نرخ پیشرفت” خوانده می شود در حالی که مورد اولی غالباً تحت عنوان “بهره کیفیت” خوانده می شود (برای بررسی جامع تر به مبحث Beyer، 2001 مراجعه کنید). در اینجا ما تنها سرعت پیشرفت ϕ را مدنظر قرار می دهیم . این مورد در شکل 13 به عنوان تغییر فاصله مورد انتظار Dr جمعیت والدینی که در بخش مرکزی فضای پارامتر آبجکت قرار دارند (فضای جستجو) به وسیله بهینه ساز  مدنظر است. 

5ـ3ـ1ـ2. مثال: مدل کروی. قابل توجه ترین تابع تست مدل کروی می باشد که قبلاً در معادله (16) ارائه شده است. این مدل معرف یک کلاس تابع متقارن است که دربردارنده ارزش های مختلف مربوط به توابع مشخص است و صرفاً وابسته به فاصله R مرتبط با y در ارتباط با بهینه شدگی خواهد بود. بر این مبنا R را می توان به عنوان حالت انباشته در نظر داشت که اجازه کاهش دینامیک N بعدی برای حصول یک دینامیک ـ R تک بعدی را خواهد داد. با توجه به ES همراه با جهش های گاوسی ایزوتروپیک مرتبط با توان σ و حالت والدینی R، سرعت پیشرفت ϕ صرفاً منوط به سه پارامتر R، و N و σ می باشد. با استفاده از این فرآیند به هنجارسازی خواهیم داشت:

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

5ـ3ـ2. ویژگی های دینامیکی

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

5ـ3ـ2ـ2. معیار تکاملی و عدم همگرایی. همگرایی به سمت وضعیت مطلوب و بهینه تا زمانی تضمین خواهد شد که فاصله باقیمانده R با زمان کاهش یابد. با استفاده از معادله (43) می توان ملاحظه نمود که چنین موردی به صورت متناظر با  است. به عنوان یک مثال، اجازه دهید تا مجددا (µ/µ, λ)-ES را بر روی مدل کروی مدنظر قرار دهیم. با توجه به معادله (40) می توان نسبت به مشخص نمودن معیار تکاملی که از طریق آن همگرایی تضمین می شود اقدام نمود:

5ـ4. فضاهای جستجوی باینری

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

5ـ4ـ1. عملکرد کلی (1+1)-ES

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

5ـ4ـ2. افزایش عملکرد به وسیله بازترکیبی در (µ/2+1)-ES

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

6- چشم انداز

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

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

دو دلیل خوب منجر به حصول نوع مختلف الگوریتم سیر تکاملی بدون گذاره صرف به سمت نسل های بعدی شده است. دلیل اول بیکار بودن غیرقابل اجتناب پردازنده های یک کامپیوتر موازی به واسطه این حقیقت است که چنین شبیه سازیهایی قابلیت فراهم آوردن مقادیر برازندگی یک نوزاد مرتبط با یک نسل خاص را خواهد داشت (احتمالاً قابلیت تست ویژگی های امکان پذیری آن نیز فراهم می باشد) که غالباً به صورت مدت های بسیار متمایز مشخص می گردند. همگام سازی کمتر این انتخاب و فازهای تولید می بایست قابلیت ارتقای کارایی جستجوی تکاملی به طور اساسی در برخی از مواقع را داشته باشد. دلیل دوم برای یک رویکرد شکارچی ـ شکار (Laumanns و همکاران، 1998، Laumanns و همکاران، 2000) در خصوص مدلسازی ویژگی های مورد بررسی و فرآیندهای اکتشافی موارد راحتی یا آسایشی می باشد که موضوعات متعدد که قابلیت کار با آن را خواهند داشت و برای این موضوع صرفاً کافی خواهد بود تا اجازه داده شود تا شکارچیان مختلف قابلیت انتخاب بر مبنای معیارهای مختلف در زمان های یکسان را داشته باشند. به منظور پیاده سازی این استراتژی این مورد کاملاً طبیعی به نظر می رسد تا به شکار، که دارای متغیرهای آبجکت می باشد، و همچنین پارامترهای استراتژی، اجازه سکنی پذیری در برخی از بخش های شبکه (ویژگی های گردابی) داده شود. شکارچیان اقدام به انجام فرآیند شکار تصادفی در یک شبکه یکسان نموده و متعاقباً قابلیت خوردن ضعیف ترین شکارچی در یک ناحیه مجاور خاص را به دست آورده و از این طریق موقعیت های جدیدی را برای نسل های تازه متولد شده به وجود می آورند. خوشبختانه، شکار در نهایت قابلیت سکنی پذیری در مجاورت مجموعه پارتو راه حل های بهنجار شده را خواهد داشت. همانند موارد غالب، کنترل توان تنوع به عنوان یک مبحث حیاتی برای کاربرد این رویکرد مدنظر خواهد بود (Rudolph و Agapie، 2000).

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

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