بخشی از پاورپوینت
اسلاید 2 :
الگوریتم بهینه سازی توده ذرات Particle Swarm Optimization
اسلاید 3 :
درس:
پردازش تکاملی
اسلاید 4 :
مقدمه
الگوریتم PSO
Pseudo code
منابع
فهرست
تاریخچه
هوش جمعی
پارامترها
مثال
پیاده سازی
اسلاید 5 :
هوش جمعی
هوش جمعی خاصیتی است سیستماتیک که در این سیستم، عامل ها به طور محلی با هم همکاري می نمایند و رفتار جمعی تمام عامل ها، باعث یک همگرایی در نقطه اي نزدیک به جواب بهینه سراسري می شود. نقطه قوت این الگوریتم عدم نیاز به یک کنترل سراسري می باشد. هر ذره(عامل) خود مختاري نسبی داردکه می تواند در سراسر فضاي جواب ها حرکت کند و می بایست با سایرذرات(عامل ها) همکاري داشته باشد. یکی از الگوریتم های مشهور هوش جمعی، بهینه سازي توده ذرات می باشند
Swarm Intelligence
اسلاید 6 :
هوش جمعی
در كاربردهاي محاسباتي، از موجوداتي مانند مورچه ها، زنبورها، موريانه ها، دسته هاي ماهيان و دسته ي پرندگان، الگو برداري مي شود. در اين نوع اجتماعات، هر يك از موجودات ساختار نستباً ساده اي دارند ولي رفتار جمعي آنها بي نهايت پيچيده است.
براي مثال در كولوني مورچه ها، هر يك از مورچه ها يك كار ساده ي مخصوص را انجام مي دهد ولي به طور جمعي عمل و رفتار مورچه ها، ساختن بهينه ي لايه محافظت از ملكه و نوزادان، تميزكردن لانه، يافتن بهترين منابع غذايي و بهينه سازي استراتژي حمله را تضمين مي كند.
اسلاید 7 :
مثال همياري:
هوش جمعی
اسلاید 8 :
تاریخچه
ابداع كنندة 1:
اسلاید 10 :
تاریخچه
در سال 1995 براي اولين بار ارائه شد.
Kennedy, J. and Eberhart, R., “Particle Swarm Optimization,” Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia 1995, pp. 1942-1945.
اولين مقاله در زمينة PSO:
اسلاید 11 :
این الگوریتم اولین بار توسط Kennedy و Eberhart مطرح شد. آنها نام این الگوریتم را PSO نهادند.
تاریخچه
يك الگوريتم جستجوي اجتماعي است كه از روي رفتار اجتماعي دسته هاي پرندگان مدل شده است. در ابتدا اين الگوريتم به منظور كشف الگوهاي حاكم بر پرواز همزمان پرندگان و تغيير ناگهاني مسيرها در فضاي جستجو بود.
اسلاید 12 :
در دسته پرندگان همیشه حرکت هر پرنده متمایل به سمت سردسته پرندگان است. اگر سردسته، انحرافی داشته باشد، بقیه هم همان انحراف را دارند. سردسته بهترین موقعیت را دارد.
مقدمه
اسلاید 13 :
هر ذره در حال جستجو براي نقطة بهينه است.
به همین دلیل در حال جابجایی است
به دليل اين جابجايي، داراي سرعت است.
مانند سایر الگوریتم های جمعیتی، الگوریتم PSO از مجموعه ای از پاسخهای ممکن استفاده می کند که این پاسخها تا زمانیکه یک پاسخ بهینه یافت شود و یا شرایط پایان الگوریتم محقق شود به حرکت خود ادامه می دهد.
در این روش هر پاسخ x به صورت یک ذره نمایش داده می شود. (همچنانکه در الگوریتم ژنتیک به هر پاسخ، کروموزم گفته می شود)
اسلاید 14 :
مانند بقیه الگوریتم ها باید یک جمعیت اولیه تشکیل گردد. در این روش معادله سرعت، ضامن حرکت ذرات به سمت ناحیه بهینه است. این معادله معمولا براساس سه عنصر اصلی ارائه می شود که عبارتند از:
مولفه شناختی pbest: بهترین وضعیت ذره
مولفه جمعی gbest: بهترین ذره ای که تابحال داشتیم
سرعت
اسلاید 15 :
در شبیه سازی این الگوریتم، رفتار هر ذره می تواند تحت تاثیر بهترین ذره محلی(Peronal Best)(در داخل یک همسایگی مشخص یا همان بهترین وضعیتی که آن ذره تابحال داشته است) و یا بهترین ذره عمومی(Global Best)(بهترین ذره در میان ذرات) باشد.
اسلاید 16 :
الگوریتم
اسلاید 17 :
C1 و C2 مقادیر ثابت و مثبت و R1 و R2 اعداد تصادفی هستند که به صورت نرمال در بازه [0,1] تولید می شوند.
Vnew=Vold+C1*R1*(Plocal best -Pold)+C2*R2*(Pglobal best -Pold)
Pnew = Pold + Vnew
برای قابلیت بهتر جستجو، پارامتری به نام وزن اینرسی به شکل زیر و به صورت ضریبی در پارامتر سرعت الگوریتم اضافه می گردد:
Vnew=W*Vold+C1*R1*(Plocal best-Pold)+C2*R2*(Pglobal best-Pold)
اسلاید 18 :
وزن اینرسی تاثیر سرعت ذرات در گام قبل را بر سرعت فعلی تعیین می نماید. به این ترتیب که با مقادیر بزرگی از وزن اینرسی، قابلیت جستجوی عمومی الگوریتم بهبود یافته و فضای بیشتری مورد بررسی قرار می گیرد. حال آنکه با مقادیر کوچک وزن اینرسی فضای مورد بررسی محدود شده و جستجو در این فضای محدود شده صورت می گیرد.
اسلاید 19 :
به همین دلیل، معمولا الگوریتم با مقدار بزرگی از وزن اینرسی شروع به حرکت می کند که سبب جستجوی گسترده فضا در ابتدای اجرای الگوریتم شده و این وزن به مرور در طول زمان کاهش می یابد که سبب تمرکز جستجو در فضای کوچک در گام های پایانی می شود.
اسلاید 20 :
همه الگوریتم ها از دو مکانیسم تنوع و تمرکز استفاده می کنند
تنوع یعنی ما دوست داریم در ابتدای الگوریتم فضای بیشتری از فضای جستجو، موردجستجو قراردهیم و هرچه به پایان الگوریتم نزدیکتر می شویم این تنوع را کم کنیم و به سمت ناحیه بهینه تمرکز پیدا کنیم.
w(وزن اینرسی) همان میزان تنوع است که در ابتدا زیاد و در مراحل پایانی میزان آن کم و کمتر می شود.
