repeat
for each particle i = 1, . . . , ns do
//set the personal best position
if f(xi) < f(yi) then
yi = xi;
end
//set the global best position
if f(yi) < f(yˆ) then
yˆ = yi;
end
end
for each particle i = 1, . . . , ns do
update the velocity using equation (3-2);
update the position using equation (3-1);
end
until stopping condition is true;
شکل ۲- ۸: شبه کد الگوریتم بهینهسازی ازدحام ذرات
الگوریتمهای بهینهسازی ازدحام ذرات دارای دو مدل به نامهای PSO بهترین سراسری[۲۸] و PSO بهترین محلی[۲۹] که تا اندازهای به هم شبیه هستند و تفاوت در تعریف همسایگی برای هر ذره در اجتماع ذرات است. برای مدل PSO بهترین سراسری، همسایگی برای هر ذره برابر با تمام ذرات اجتماع است. در PSO بهترین محلی همسایگی کوچکتری برای هر ذره معرفی میشود [۳۱].
( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
شکل ۲- ۹: تشریح هندسی مولفههای شخصی و اجتماعی در PSO
دو تفاوت اصلی بین این دو روش بر اساس مشخصه همگرایی آنها وجود دارد[۳۲, ۳۳]:
۱٫ به علت اتصال داخلی بزرگتر درPSO بهترین سراسری، سریعتر از PSO بهترین محلی همگرا میشود.
۲٫ به علت واگرایی بیشتر، PSO بهترین محلی کمتر در خطر گیر کردن در بهینه محلی است. به طور کلی، ساختارهای همسایهای نظیر توپولوژی حلقه که در PSO بهترین محلی استفاده میشود، کارایی را بهبود میبخشند.
۲-۵-۱- پارامترهای پایه بهینهسازی ازدحام ذرات
الگوریتم بهینهسازی ازدحام ذرات پایه از تعدادی پارامتر کنترلی نظیر تعداد ذرات، ضرایب افزایش سرعت، وزن اینرسی، اندازه همسایگی، تعداد تکرار و مقادیر تصادفی که سهم مؤلفههای ادراکی و اجتماعی را مشخص میکند، تأثیر میپذیرد. به علاوه، اگر از مقید کردن سرعت یا انقباض استفاده شود، بیشینه سرعت و ضرایب انقباض بر روی کارایی PSO پایه اثر میگذارد. در این بخش به مطالعه این پارامترها میپردازیم.
اندازه اجتماع ns (تعداد ذرات در اجتماع): هر چه ذرات در اجتماع بیشتر باشد، پراکندگی اولیه ذرات در اجتماع زیادتر است. اجتماع بزرگتر، اجازه میدهد تا فضای جستجوی بیشتری در هر تکرار پوشش داده شود. به هر حال، زیاد بودن ذرات، باعث بالا رفتن پیچیدگی محاسباتی در هر تکرار و کاهش جستجوی موازی میشود. همچنین تعداد زیاد ذرات باعث کمتر شدن تکرارها تا رسیدن به راهحل خوب نسبت به اجتماعات کم میشود. مطالعات تجربی نشان داده است که PSO دارای قابلیت پیدا کردن جواب بهینه با اندازه اجتماع کم ۱۰ تا ۳۰ ذره است [۳۴, ۳۵]. موفقیت حتی با ذرات کمتر از ۱۰ هم به دست آمده است. ولی اندازه اجتماع در هر صورت، وابسته به مسئله است. یک فضای جستجوی نرم نیاز به تعداد ذرات کمتری نسبت به یک فضای جستجوی سخت دارد، تا به راهحل بهینه برسد.
اندازه همسایگی: اندازه همسایگی معرف بزرگی تبادلات اجتماعی درون همسایگی است. همسایههای کوچکتر، تبادلات کمتری دارند و در همگرایی کندترند، ولی راه حل هایی که توسط آنها ارائه میشوند قابل اطمینان تر هستند. همسایگیهای کوچکتر مستعد در افتادن در بهینه محلی هستند. برای استفاده از مزیتهای همسایگیهای کوچک و بزرگ، میتوانیم ابتدا اندازه همسایگی را کوچک بگیریم و با افزایش شماره تکرارها اندازه همسایگی را بزرگتر کنیم [۳۶]. این روش، پراکندگی زیاد اولیه، همگرایی سریعتر اجتماع و حرکت ذرات به سمت نواحی امیدوارکننده را تضمین میکند.
تعداد تکرار: تعداد تکرار برای رسیدن به یک راهحل خوب، وابسته به مسئله است. تعداد کم تکرار ممکن است الگوریتم را پیش از رسیدن به یک راهحل بهینه پایان دهد و تعداد تکرار زیاد نیز باعث اضافه کردن پیچیدگی محاسباتی غیر لازم است.
ضرایب افزایش سرعت: ضرایب افزایش سرعت c1 و c2 همراه با بردارهای تصادفی r1 و r2 تأثیر تصادفی مؤلفههای اجتماعی و ادراکی بر سرعت عمومی یک ذره را کنترل میکنند. ضرایب c1 و c2 همچنین به پارامترهای اعتماد معروف هستند، زیرا c1 بر این که، یک ذره چقدر به خودش اعتماد دارد، دلالت میکند، در حالی که، c2 بر این که، یک ذره چقدر به همسایهاش اطمینان دارد دلالت میکند. اگر c1= c2= 0 ذرات تا رسیدن به حدود فضای جستجو به حرکت خود ادامه میدهند (فرض بر نبودن اینرسی است). اگر c1 > 0 و c2= 0 تمام ذرات به طور مستقل تپه نورد میشوند. هر ذره بهترین موقعیت در همسایگی خودش را با موقعیت جاری جایگزین میکند و ذرات یک جستجوی محلی را انجام میدهند. در مقابل اگر c2 > 0 و c1= 0 تمام اجتماع به سمت یک نقطه کشیده میشوند و تمام ذرات به یک تپه نورد اتفاقی تبدیل میشوند.
در حالی که بسیاری کاربردها از استفاده میکنند، نسبت بین این دو ثابت وابسته به مسئله است. اگر هر ذره به سمت بهترین موقعیت شخصی خود کشیده میشود که نتیجهاش سرگردانی است. در مقابل اگر ذرات به سمت بهترین موقعیت سراسری کشیده میشوند که نتیجهاش هجوم پیش از موعد به سمت بهینه است. برای مسائل تک حالتی با فضای جستجوی نرم، مؤلفه اجتماعی بزرگتر میتواند تأثیر گذار باشد. در حالی که در فضای جستجوی سخت چندحالته، مؤلفه ادراکی بزرگتر ممکن است سودمند باشد.
مقادیر کم برای c1 و c2 باعث حرکت نرم ذره میشود و به ذره اجازه سیر کردن در مناطق ممکن برای اکتشاف، قبل از کشیده شدن به یک منطقه خوب را میدهد. مقادیر زیاد باعث افزایش سرعت همراه با حرکات ناگهانی قبل و بعد از نواحی خوب میشود. مقادیر اولیه اشتباه باعث واگرایی یا رفتار چرخشی میشود.
وزن اینرسی: وزن اینرسی توسط Shi و Eberhart به عنوان مکانیزمی برای کنترل قابلیتهای استخراج و اکتشاف و مکانیزمی برای حذف نیاز به مقید کردن سرعت ارائه شد [۳۷]. وزن اینرسی در تحقق هدف اول موفق بود اما نتوانست نیاز مقید کردن سرعت را به طور کامل حذف کند [۳۸]. وزن اینرسی، ، اندازه حرکت ذره را به وسیله وزن دهی سهم سرعت قبلی کنترل میکند، که مجموعاً به چه میزان جهت حرکت قبلی در سرعت جدید تأثیر میگذارد.
مقدار در رفتار همگرایی و در تعامل اکتشاف و استخراج بسیار مؤثر است. مقدار زیاد اکتشاف را راحتتر و واگرایی را بیشتر میکند و مقدار کم استخراج محلی را از بین میبرد. همانند سرعت بیشینه، مقدار بهینه وزن اینرسی وابسته به مسئله است [۳۷]. پیادهسازیهای اولیه وزن اینرسی یک مقدار ایستا را برای تمام طول جستجو، برای تمام ذرات، در هر بعد استفاده میکردند. در پیادهسازیهای بعدی از مقادیر پویا برای مقادیر اینرسی استفاده کردند. این روشها معمولاً با مقادیر زیادی برای اینرسی شروع میشدند که در طول زمان به مقادیر کم کاهش مییافتند. بدین ترتیب، ذرات در زمانهای اولیه جستجو، به اکتشاف و در زمانهای آخر به استخراج نواحی مورد علاقه میپرداختند. قبل از بررسی بیشتر روشهای پویای وزن اینرسی، لازم است که متذکر شویم که انتخاب مقادیر بایستی همراه با انتخاب مقادیر c1 و c2 باشد.
روشهای پویای وزن اینرسی به دستهه ای زیر تقسیم میشوند.
۱٫ تنظیم تصادفی؛ که در هر تکرار یک مقدار تصادفی اینرسی انتخاب میشود. یک روش نمونهگیری از توزیع گوسی است:
(۲-۱۲)
که به اندازه کافی کوچک است تا از بزرگتر از واحد نبودن اطمینان حاصل شود. Peng از روش زیر استفاده کرد [۳۹]:
(۲-۱۳)
۲٫ کاهش خطی؛ که وزن اینرسی اولیه زیاد )معمولاً ۰٫۹) به صورت خطی کم میشود تا به مقدار ۰٫۴ برسد [۴۰, ۴۱].
(۲-۱۴)
