استراتژی الگوریتم های تکاملی (evolutionary strategy) (ES)

۱−۱مقدمه

ES یکی از روش های تکاملی می باشد. که با یک جمعیت اولیه شروع می شود در این روش بعد از انتخاب والدین از روش های تکثیر برای تولید نسل جدید استفاده می شود که در برنامه های حاضر از روش Discrete Recombination استفاده شده است. جهش نیز در یافتن مکان های جدید و جستجوی بهتر فضای جستجو کمک می کند.

۱−۲شرح الگوریتم ES

۱−۲−۱تعیین جمعیت اولیه :

ابتدا یک جمعیت اولیه در بازه مورد نظر تعیین می کنیم. این جمعیت به صورت یک ماتریس با تعداد سطر برابر با تعداد جمعیت، و تعداد ستون برابر با تعداد متغیرهای مساله می باشد.

۱−۲−۲تولید مثل Recombination:

در اینجا از روش Discrete Recombination استفاده شده است.

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

در انتها از روش (µ+λ) یعنی افزودن تعداد فرزندان تولیدی به نسل قبل و انتخاب بهترین آنها برای نسل بعد استفاده شده است.

۱−۲−۳ جهش (mutation)

انجام این عمل ما را در رسیدن به نقطه جدید کمک می کند. اصولا جهش با اضافه نمودن یک عدد گوسی به جمعیت مورد نظر صورت می گیرد.

را می توان در هر مرحله آبدیت نمود. بدین منظور در این برنامه از روش Additive  استفاده شده است که روابط آن به صورت زیر می باشد.

σij(t + 1) = σij(t) + ησij(t)Nij(0, 1)

و در نهایت جهش به صورت زیر انجام می گیرد:

۱−۲−۴ انتخاب (selection)

حال مجموعه ای از والدین و فرزندان را داریم که بهترین آنها را با توجه به مساله مورد بررسی برای تولید نسل بعد انتخاب می کنیم.

۲– برنامه ریزی تکاملی (evolutionary programming)(EP)

۲-۱ مقدمه

الگوریتم EP بسیار شبیه الگوریتم ES می باشد تنها تفاوت این دو الگوریتم در مرحله Recombination و Selection  می باشد. EP دارای  هیچگونه  Recombination نمی باشد و اعضا تنها از طریق جهش تغییر پیدا می کنند.

۲−۲ جهش(mutation)

برای انجام این عمل  از روش Additive  استفاده شده است که روابط آن به صورت زیر بوده و توضیحات کامل تر آن در قسمت ES  آورده شد.

σij(t + 1) = σij(t) + ησij(t)Nij(0, 1)

۲−۳ انتخاب(selection)

در الگوریتم EP برای انتخاب نسل بعد چندین روش وجود دارد که دو روش متداول ان در زیر توضیح داده شده است:

۲−۳−۱ انتخاب به روش مسابقه ای Selection  Tournament

در این روش دو عضو از جمعیت موجود( مجموع جمعیت اولیه و جمعیت جهش یافته) به صورت تصادفی انتخاب شده و مقدار شایستگی آنها با هم مقایسه شده و فرد شایسته تر برای حضور در نسل بعد انتخاب می شود. در الگوریتم EP نوشته شده فرد پیروز از جمعیت اولیه خارج شده و به فرد بازنده شانس دوباره داده می شود.

۲−۳−۲ انتخاب بر اساس امتیاز Rank based Selection

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