استراتژی الگوریتم های تکاملی (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

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