نحوه عملکرد الگوریتم pso

الگوریتم PSO یک الگوریتم جست و جوی اجتماعی است که از روی رفتار اجتماعی دسته های پرندگان مدل شده است. نحوه عملکرد الگوریتم pso بدین صورت است که در ابتدا این الگوریتم به منظور کشف الگوهای حاکم بر پرواز همزمان پرندگان و تغییر ناگهانی مسیر آنها و تغییر شکل بهینه ی دسته بکار گرفته شد. در PSO، Particle ها در فضای جست وجوی جاری می شوند. تغییر مکان Particle ها در فضای جست وجوی تحت تأثیر تجربه و دانش خودشان و همسایگانشان است.

بنابراین موقعیت دیگر Particle های Swarm روی چگونگی جست و جوی یک Particle اثر می گذارد. نتیجه ی مدل سازی این رفتار اجتماعی فرآیند جست جوی است که Particle ها به سمت نواحی موفق میل می کنند. Particle ها در Swarm از یکدیگر می آموزند و برمبنای دانش بدست آمده به سمت بهترین همسایگان خود می روند نحوه عملکرد الگوریتم PSO براین اصل استوار است که در هر لحظه هر Particle مکان خود را در فضای جست و جو با توجه به بهترین مکانی که تاکنون در آن قرار گرفته است و بهترین مکان که در کل همسایگی اش وجود دارد، تنظیم می کند.

الگوریتم PSO در واقع برای بهینه سازی مسائل پیوسته توسعه یافته و در آن راه حل بهینه مسئله از طریق اثر متقابل بین تعدادزیادی جزء (Particle) بدست می آید.

نحوه عملکرد الگوریتم pso

روش بهینه سازی PSO در سال ۱۹۹۵ توسط جمیز کندی و راسل ابرهارت معرفی گردید. این روش از عملکرد دسته جمعی گروه های حیوانات مانند پرندگان وماهی ها و… اقتباس شده است. حیواناتی مانند پرندگان و ماهی ها که به صورت دسته جمعی زندگی می کنند معمولاً به صورت گروهی تصمیم گیری می کنند.

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

یکی از مشخصه ها و نحوه عملکرد الگوریتم pso تأکید بر جمعی بودن تفکر و هوش است. تفاوت عمده ای که این روش با الگوریتم های دیگر چون الگوریتم های ژنتیک و یا Simulated Annealing دارد این است که اعضای جامعه از وضعیت سایر اعضا و یا بهترین عضو جامعه باخبر هستند و نتیجه ی بدست آمده توسط آنها را در تصمیم گیری های خود لحاظ می کنند.

به عنوان مثال: یک دسته از ماهی ها می خواهند خطر یک شکارچی را دفع کنند، در ابتدا گروه به دو دسته تقسیم می شود و سپس از نو ساخته می شود اما در هر حالتی نزدیکی و فشردگی کل جمع از طرف همه ی ماهی ها کنترل می شود.

در چنین مجموعه ای هر کدام از حیوانات صرفا از چند قانون تبعیت می کنند و رفتارهای پیچیده ای که در کل جمع قابل مشاهده هستند چیزی جز ترکیب این قوانین ساده نیستند هر کدام از ماهی ها در یک دسته از موقعیت، جهت حرکت و سرعت ماهی های نزدیکش خبر دارد و با استفاده ازاین اطلاعات و پیروی از چند قانون ساده خود را با جمع تطبیق می دهد به عنوان مثال:

• همواره سعی داشته باش که به طور نسبی در نزدیکی سایرین حرکت کنی.
• سعی کن در جهتي كه بقیه حرکت می کنند، حرکت بکنی.
• تقریبأ با همان سرعتی که دیگران حرکت می کنند، حرکت کن.

از قوانین ساده ای هستند که هر ماهی در یک دسته رعایت می کند و حاصل تبعیت از چنین قوانینی حرکت های پیچیده ای است که در مجموع توسط دسته ی ماهی ها انجام می گیرد.

مسائل بهینه سازی الگوریتم pso

الگوریتم PSO، یکی از روش های فراکاوشی است و این قابلیت را دارد که در بسیاری از مسائل بهینه سازی مهندسی مورد استفاده قرار می گیرد. مثلا: مسئله طراحی و بهره برداری مخازن سدها که از جمله مسائل بهینه سازی در علوم مهندسی آب می باشند تاکنون توسط انواع روش های بهینه سازی شناخته شده و مورد ارزیابی قرار گرفته است.

Hall و East در سال ۱۹۹۴ الگوریتم ژنتیک را برای مساله چهار مخزنی به کار برده اند هدف آنها حداکثر کردن سود حاصل از تولید نیرو و تأمین آب کشاورزی تحت شرایط ثابت ذخیره و آزادسازی آب از مخزن بود. از سوی دیگر در سال ۱۹۹۷ Locks و Oliveria از الگوریتم ژنتیک برای بررسی و ارزیابی قوانین بهره برداری از سیستم های چند مخزنی استفاده کردند و نشان دادند كه الگوريتم ژنتيك مي تواند براي مشخص كردن سياست هاي بهره برداري موثر استفاده شود.

همچنین Jalali و Afshar در سال ۲۰۰۵ از الگوریتم جامعه مورچه ها برای حل مسائل طراحی و بهره برداری بهینه هیدرو سیستم ها استفاده کردند. D. Nageshetall ، Meraji و Afshar نیز در سال ۲۰۰۵ پس از آزمودن الگوریتم PSO توسط چندین توابع آزمونی استاندارد و تأیید قابلیت این الگوریتم در حل مسائل بهینه سازی فراگیر، از آن برای حل مساله بهره برداری از مخزن سد استفاده نمودند.

الگوریتم بهینه سازی ازدحام ذرات (PSO) Particle Swarm Optimization

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

اولین شبیه سازی آنها که در سال ۱۹۹۵ انجام گردید آنها را به سمت شبیه سازی پرندگان برای یافتن دانه رهنمون کرد این کار تحت تأثیر کار هپنر و گرناندر بود که در سال ۱۹۹۰ برای شبیه سازی رفتار پرندگان به صورت یک سیستم غیر خطی انجام گرفته بود کارکندی و ابرهارت منجر به ایجاد الگوریتمی قوی برای یهینه سازی، به نام الگوریتم بهینه سازی گروه ذرات یا PSO شد.

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

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

در واقع انبوه ذرات که کمینه ی یک تابع را جست و جو می کنند همانند دسته ای از پرندگان عمل می کنند که به دنبال غذا می گردند.

برخی از نسخه های تغییر یافته ی PSO

طی دهه ی گذشته، تغییرات بسیار زیادی برروی الگوریتم PSO اعمال شده است. عده ای از این تغییرات منجر به بهتر شدن کلی عملکرد الگوریتم PSO شده اند. عده ای از این تغییرات نیز، منجر به بهبود عملکرد الگوریتم برای رده ی خاصی از مسائل شده اند. در این بخش به تعدادی از مهمترین تغییرات اعمال شده برروی PSO اشاره شده است.

الگوریتم PSO باینری

در این نسخه از PSO که توسط کِنِدی واِبِرهارت در سال ۱۹۹۷ معرفی گردید، تغییری کوچک بر روی الگوریتم PSO اولیه انجام گرفته است، تا بتوان برای بهینه کردن کمیت های گسسته نیز از آن استفاده کرد. دراین الگوریتم، سرعت به عنوان یک مقدار آستانه ی احتمالی استفاده شده است که معین می کند که مولفه ای ازبردار موقعیت صفر یا یک باشد.

الگوریتم PSO فازی یا FPSO

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

کاربردهای الگوریتم ازدحام ذرات یا pso

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

کاربردهایی که تاکنون برای PSO مطرح شده اند، در ۲۶ گروه مجزا تقسیم شده اند. البته برخی از کاربردها، به بیش از یک گروه متعلق می باشند. آماری که در این بخش بیان می شود، براساس مقالات موجود در پایگاه داده ی IEEE XPIore، تا اواخر سال ۲۰۰۷ می باشد.

در حدود ۱۱۰۰ مقاله در مقالات موجود در پایگاه داده وجوددارند که حدود ۳۵۰ مورد از آن ها در مورد بهبود بخشیدن به عملکرد الگوریتم PSO وتغییر دادن آن نوشته شده اند. در حدود ۷۰۰ مقاله، که ۵۵ عدد از آن ها مقالات چاپی یا ژورنال هستند، در مورد کاربردهای الگوریتم PSO هستند.

در بسیاری از این مقالات، الگوریتم PSO برای استفاده در کاربرد مورد نظر نویسندگان، به نحوی تغییر داده شده است که جواب های بهتری به دست بیایند. باقی مقالات در آماری که ارائه خواهد شد، در نظر گرفته نشده اند. این تحلیل های به صورت یک گزارش فنی توسط ریکاردوپُولی و در ۲۰ نوامبر سال ۲۰۰۷ ارائه شده است.شناسایی شاخه های اصلی کاربردها، به صورت دستی وب ا کمک گرفتن از کامپیوترهای کوچک انجام گرفته است.

فلوچارت الگوریتم pso

شبه کد الگوریتم ازدحام ذرات یا pso 

For each particle
Initialize particle
END

Do
For each particle
Calculate fitness value
If the fitness value is better than the best fitness value (pBest) in history
set current value as the new pBest
End

Choose the particle with the best fitness value of all the particles as the gBest
For each particle
Calculate particle velocity according equation (a)
Update particle position according equation (b)
End