پس از آن مقدار تابع به ازای هر عضو جمعیت ارزیابی می شود.
شکل ۲-۸: ارزیابی تابع هدف [۶]
اگر موقعیت ذره از بهترین موقعیت قبلی آن بهتر شد، به روز رسانی می شود.
بهترین موقعیت ذرات با در نظر گرفتن بهترین موقعیت های قبل انتخاب می شود.
شکل ۲-۹: انتخاب بهترین موقعیت ذرات [۶]
سرعت ذرات به کمک رابطه زیر به روز رسانی می شود:
و تابع Rand، مولد عدد تصادفی در بازه [۰,۱] می باشد. و ثابت های اثر نامیده می شوند.
ترم اول جمله سمت راست مربوط به جابه جایی فعلی ذره و جمله دوم نشانگر اثر حافظه ذره و در نهایت جمله سوم اثر گروه ذرات می باشد.
شکل ۲-۱۰: به روز رسانی سرعت ذرات [۶]
در ادامه مقدار مساوی مقدار اولیه هر ذره قرار داده می شود و که کمترین مقدار در میان همه ها می باشد، محاسبه می شود. سپس سرعت جدید ذرات از رابطه (۲٫۳) محاسبه می شود. موقیت جدید ذرات از رابطه زیر بدست می آید:
این مراحل تکرار می شود تا نقطه بهینه حاصل شود. شکل ۲-۱۱ زیر نحوه محاسبه سرعت و چگونگی به روز کردن موقعیت ذره در فضای جستجوی دو بعدی در الگوریتم PSO را نشان می دهد.
شکل ۲-۱۱: چگونگی به روز کردن موقعیت ذره در فضای جستجوی دو بعدی
در شکل ۲-۱۲ فلوچارت کلی الگوریتم PSO آمده است.
شکل ۲-۱۲: فلوچارت الگوریتم PSO
۲-۲-۳- الگوریتم Polytope
روش polytope یک روش از دسته روش های معروف به تپه نوردی^[۴۶] می باشد و از جمله الگوریتم های بهینه سازی است که نیازی به محاسبه مشتق ندارند. این الگوریتم اولین بار توسط Nelder و Mead در سال ۱۹۶۵ معرفی شد [۹]. این روش همان الگوریتم Hill-Climbing است که نیازی به اطلاعات مربوط به مشتق پارامترها را ندارد و گاهی اوقات با نام الگوریتم Simplex هم شناخته می شود.
این روش در یک فضای - بعدی با نقطه، کار خود را آغاز می کند. در هر مرحله متغیر های تصمیم گیری، به گونه ای مرتب می شوند که مقدار تابع هدف آن ها به ترتیب صعودی به نزولی قرار بگیرد یعنی:
ابتدا یک نقطه آزمایشی در یک گام بازتاب^[۴۷] ایجاد می شود:
که () ثابت انعکاس و مرکز نقطه می باشد و از رابطه زیر بدست می آید:
در ادامه مقدار تابع هدف به ازای نقطه جدید ، یعنی محاسبه می شود. گام بعد با توجه به مقدار به یکی از صورت های زیر خواهد بود:
اگر باشد، نقطه که در واقع بدترین نقطه می باشد، در تکرار بعد با نقطه جایگزین می گردد.
اگر باشد، آنگاه نقطه بهترین نقطه در جمعیت است. در این صورت فرض بر این می شود که انعکاس، در جهت نقطه بهینه است. بنابراین یک گام گسترش^[۴۸] انجام می شود:

( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

سپس مقدار تابع هدف در نقطه ، یعنی محاسبه می شود. لازم به ذکر است که ضریب گسترش است و مقدار آن بزرگتر از یک می باشد. در این مرحله نیز دو حالت ممکن است رخ بدهد:
اگر باشد، آنگاه گسترش موفقیت آمیز بوده است و جایگزین می شود.
اگر باشد، آنگاه گسترش موفقیت آمیز نبوده است و جایگزین می شود.
اگر باشد، الگوریم بزرگ است و باید منقبض شود.
اگر باشد، آنگاه:
اگر باشد، آنگاه:
که مقداری بین ۰ و ۱ می باشد و ضریب انقباض نام دارد. سپس مقدار تابع هدف در نقطه ، یعنی محاسبه می شود و اگر این مقدار هم از و هم از بزرگتر باشد، جایگزین می شود، در غیر صورت یک مرحله انقباض دیگر انجام می شود. در شکل ۲-۱۳ زیر ساختار الگوریتم ploytope در یک فضای جستجوی دو بعدی نشان داده شده است.
شکل ۲-۱۳: الگوریتم Polytope [9]
۲-۲-۴- الگوریتم Simplex
مبنای این روش این است که در یک فضای بعدی، یک چند ضلعی حداقل حاوی ضلع خواهد بود. به عنوان مثال در فضای دو بعدی، یک چند ضلعی که حداقل بعد را داشته باشد، مثلث است. در فضای پارامترها مثلثی را به صورت در نظر بگیرید و که تابع هدف مورد نظر برای بهینه سازی می باشد، را برای هر راس مثلث حساب کنید. هر راس که تابع آن بزرگتر باشد، نسبت به سایر اضلاع قرینه می شود. به عنوان مثال اگر از و بزرگتر باشد، نقطه نسبت به ضلع قرینه می شود، تا نقطه بدست آید. سپس الگوریتم برای نقاط تکرار می شود.
بزرگترین مشکل این روش پدیده Cycling می باشد. بدین معنی که الگوریتم بین نقاط و تکرار شود. اگر با این پدیده مواجه شویم راهکار زیر توصیه می شود:
اگر در آن صورت نقطه به مرکز ، نزدیکتر انتخاب می شود.
اگر در آن صورت نقطه به مرکز ، دورتر انتخاب می شود.
الگوریتم فوق توسط Nelder و Mead توسعه داده شده است. در زیر خلاصه گام به گام این الگوریتم برای یک مسئله مینیمم سازی در یک فضای دو بعدی آورده شده است:
مراحل الگوریتم Simplex در فضای دو بعدی برای یافتن مینیمم :
سه نقطه با فاصله مساوی انتخاب می شوند.
، و محاسبه می شوند.
نقطه ای که آن از سایرین بزرگتر می باشد، انتخاب می شود. (فرض کنید نقطه انتخاب می شود.)
قرینه نقطه نسبت به ضلع محاسبه می شود و نامیده می شود.
محاسبه می شود.
، و مقایسه شده و بزرگترین انتخاب می شود.
الگوریتم مجدداً تکرار می شود تا جایی که به یک نقطه مشخص همگرا شود یا تغییرات بسیار ناچیز باشد.
روش فوق بر مبنای محاسبه مستقیم تابع هزینه در هر نقطه می باشد و به گرادیان آن هیچ نیازی ندارد. پیشنهاد می شود تنها در مواردی که محاسبه گرادیان تابع هزینه بسیار مشکل باشد از روش فوق استفاده شود.
۲-۲-۵- الگوریتم Hook Jeeves
الگوریتم HJ یک روش بهینه سازی بر مبنای جستجوی مستقیم می باشد و بر اساس محاسبه تابع هزینه عمل می کند و به مشتق آن نیازی ندارد. ایده این روش این است که برای جستجوی مقدار بهینه در یک فضای بعدی، در بعد مستقل به دنبال جواب باشد. به عبارت دیگر این الگوریتم از نقطه اولیه شروع می کند و در یک جهت مشخص حرکت می کند تا مینیمم تابع را بیابد. اگر مقدار در راستای حرکت افزایش یافت، جهت حرکت عوض می شود و اگر تغییر چندانی نداشت گام حرکت^[۴۹] کوچک تر می شود. سپس در راستای پارامتر حرکت می کند و با ثابت شده، به گونه ای پیدا می شود که حداقل شود. این روند تا آخرین پارامتر یعنی ادامه می یابد به نحوی که به بردار برسیم. از این نقطه مجدداً الگوریتم فوق تکرار می شود. در شکل ۲-۱۴ نحوه جستجوی این الگوریتم در یک فضای جستجوی دو بعدی نمایش داده شده است.
شکل ۲-۱۴: نحوه جستجوی الگوریتم HJ در فضای جستجوی دو بعدی [۱۰]
الگوریتم HJ دارای دو نوع حرکت برای رفتن به سمت پاسخ بهینه می باشد: حرکت اکتشافی^[۵۰] و حرکت الگویی^[۵۱] . در شکل بالا حرکت اکتشافی با پیکان با رنگ سیاه و حرکت الگویی با رنگ قرمز نشان داده شده است. حرکت اکتشافی در واقع تخمینی از مشتق^[۵۲] را ارائه می دهد. همان طور که در شکل ۲-۱۴ نشان داده شده است الگوریتم از یک نقطه دلخواه (دایره با رنگ قرمز) شروع می شود و در یک جهت، حرکت اکتشافی انجام می دهد و تابع هزینه ارزیابی می شود. اگر الگوریتم بتواند به نقطه ای با تابع هدف مطلوب تر برسد، سپس حرکت اکتشافی در جهت دیگر فضای مسئله زده می شود. اگر دو حرکت اکتشافی، موفقیت آمیز باشد سپس یک حرکت الگویی انجام می شود. اگر حرکت الگویی منجر به پاسخ مطلوب تر نشد مجدداً از همان نقطه حرکت اکتشافی تکرار می شود. برای اطلاعات بیشتر در مورد الگوریتم HJ به مراجع [۱۱و۱۲] مراجعه شود.