روش بهینه‌سازی ازدحام ذرات
انواع الگوریتم ازدحام ذرات > الگوریتم ازدحام ذرات پیوسته > اولین الگوریتم ازدحام ذرات

در سال ۱۹۹۵ ابرهارت و کندی برای اولین بار PSO به عنوان یک روش جستجوی غیر قطعی برای بهینه‌سازی تابعی مطرح گشت این الگوریتم از حرکت دسته جمعی پرندگانی که به دنبال غذا می‌باشند، الهام گرفته شده‌است. گروهی از پرندگان در فضایی به صورت تصادفی دنبال غذا می‌گردند. تنها یک تکه غذا در فضای مورد جستجو وجود دارد. هر راه حل که به آن یک ذره گفته می‌شود، PSO در الگوریتم معادل یک پرنده در الگوریتم حرکت جمعی پرندگان می‌باشد. هر ذره یک مقدار شایستگی دارد که توسط یک تابع شایستگی محاسبه می‌شود. هر چه ذره در فضای جستجو به هدف (غذا در مدل حرکت پرندگان) نزدیکتر باشد، شایستگی بیشتری دارد. همچنین هر ذره دارای یک سرعت است که هدایت حرکت ذره را بر عهده دارد. هر ذره با دنبال کردن ذرات بهینه در حالت فعلی، به حرکت خود در فضای مسئله ادامه می‌دهد.
به ا ین شکل است که گروهٔ از ذرات در آغاز کار به صورت تصادفی به وجود می‌آیند و با به روز کردن نسل‌ها سعی در یافتن راه‌حل بهینه می‌نمایند. در هر گام، هر ذره با استفاده از دو بهترین مقدار به روز می‌شود. اولین مورد، بهترین موقعیتی است که تاکنون ذره موفق به رسیدن به آن شده‌است. موقعیت مذکور شناخته و نگهداری می‌شود که این بهترین مقدار نوستالژی آن ذره نیز گفته می‌شود که آن را با pbest نمایش می‌دهیم. بهترین مقدار دیگری که توسط الگوریتم مورد استفاده قرار می‌گیرد، بهترین موقعیتی است که تاکنون توسط جمعیت ذرات بدست آمده‌است که آن را gbest می‌گوییم (هوش جمعی).
پس از یافتن بهترین مقادیر، سرعت و مکان هر ذره با استفاده از رابطه ۶ و ۷به روز می‌شود.
رابطه 6 v(t+1)=v(t)+c1*rand(t)*(pbest(t)-position(t)+c2*rand(t)*(gbest(t)-position(t))
رابطه 7  position(t+1)=position(t)+v(t+1)
سمت راست معادله ۶ از سه قسمت تشکیل شده‌است که قسمت اول، سرعت فعلی ذره است ( v(t)) و قسمت‌های دوم ( c1*rand(t)*(pbest(t)-position(t))) و سوم ( c2*rand(t)*(gbest(t)-position(t))) میزان تغییر سرعت ذره و جهت آن به سمت بهترین تجربه شخصی (نوستالژی) و بهترین تجربه گروه (هوش جمعی) را به عهده دارند. اگر قسمت اول را در این معادله در نظر نگیریم ( v(t))، آنگاه سرعت ذرات تنها با توجه به موقعیت فعلی و بهترین تجربه ذره و بهترین تجربه جمع تعیین می‌شود و عملاً تأثیر سرعت کنونی و لختی آن حذف می‌شود. به این ترتیب، بهترین ذره گروه، در جای خود ثابت می‌ماند و سایرین به سمت آن ذره حرکت می‌کنند. در واقع حرکت دسته جمعی ذرات بدون قسمت اول معادله ۶، پروسه ای خواهد بود که طی آن فضای جستجو به تدریج کوچک می‌شود و جستجویی محلی حول بهترین ذره شکل می‌گیرد. در مقابل اگر فقط قسمت اول معادله ۶ را در نظر بگیریم، ذرات راه عادی خود را می‌روند تا به دیواره محدوده برسند و به نوعی جستجویی سراسری را انجام می‌دهند. پارامترهای c1 و c2 (مقدار آن حدود ۲ است) میزان اهمیت و وزن هوش جمعی و نوستالژی را مشخص می‌کنند. پارامتر  rand(t)
با صفر قرار دادن یا ندادن پارامترهای c1 و c2 سه حالت مختلف زیر به وجود می‌آید:
هیچ‌کدام از این دو پارامتر را صفر نگذاریم که می‌شود pso با لختی سرعت، هوش جمعی و نوستالژی.
وزن نوستالژی را صفر کنیم و فقط براساس هوش جمعی و لختی عمل کنیم.
وزن هوش جمعی را صفر کنیم و فقط براساس نوستالژی و لختی عمل کنیم.
برای مقداردهی اولیه توسط رابطه ۸ عمل می‌کنیم. سرعت اولیه نیز طبق ۹ صفر است.
رابطه 8  x(0)=x_{min}+rand(x_{max}-x_{min})
رابطه 9  v(0)=0
شبه کد الگوریتم PSO:
For each particle
    Initialize particle
End For
Do
For each particle
    Calculate fitness value of the particle fp
    /*updating particle’s best fitness value so far)*/
    If fp is better than pBest
    set current value as the new pBest
End For
/*updating population’s best fitness value so far)*/
Set gBest to the best fitness value of all particles
For each particle
    Calculate particle velocity according equation
    Update particle position according equation
End For While maximum iterations OR minimum error criteria is not attained
اما در مورد شرط توقف باید گفت که راه‌های زیر موجود است:
تعداد تکرار معین
رسیدن به یک شایستگی آستانه
یک تعداد تکرار که شایستگی تغییر نکند (مثلاً اگر بعد از ۱۰ تکرار شایستگی ثابت بود و بهتر نشد).
راه آخر بر اساس چگالی تجمیع اطراف نقطه بهینه است. به این صورت که می‌گوییم اگر ۸۰ درصد ذرات در فاصل‌های کمتر از ۲۰ درصد بیشترین فاصله نسبت به بهترین جواب قرار داشتند، الگوریتم باید متوقف شود.
روش آخر به این صورت است که طبق رابطه ۱۰ می‌توان را بدست آورد. همان‌طور که گفته شد R_{norm} یک مقدار بین ۰ و ۱ است و همین‌طور F بیشترین فاصله بین دو ذره در حالت کنونی است.
رابطه 10  R_{norm}=\left({\frac {R_{max}}{F}}\right)