روش بهینهسازی ازدحام ذرات (Particle swarm optimization) یا به اختصار PSO، یک روش سراسری بهینهسازی است که با استفاده از آن میتوان با مسائلی که جواب آنها یک نقطه یا سطح در فضای n بعدی میباشد، برخورد نمود. در اینچنین فضایی، فرضیاتی مطرح میشود و یک سرعت ابتدایی به آنها اختصاص داده میشود، همچنین کانالهای ارتباطی بین ذرات در نظر گرفته میشود. سپس این ذرات در فضای پاسخ حرکت میکنند، و نتایج حاصله بر مبنای یک «ملاک شایستگی» پس از هر بازهٔ زمانی محاسبه میشود. با گذشت زمان، ذرات به سمت ذراتی که دارای ملاک شایستگی بالاتری هستند و در گروه ارتباطی یکسانی قرار دارند، شتاب میگیرند. علیرغم اینکه هر روش در محدودهای از مسائل به خوبی کار میکند، این روش در حل مسائل بهینهسازی پیوسته موفقیت بسیاری از خود نشان دادهاست.
مقدمه
الگوریتم PSO یک الگوریتم جستجوی جمعی است که از روی رفتار اجتماعی دستههای پرندگان مدل شدهاست. در ابتدا این الگوریتم به منظور کشف الگوهای حاکم بر پرواز همزمان پرندگان و تغییر ناگهانی مسیر آنها و تغییر شکل بهینهٔ دسته به کار گرفته شد. در PSO، ذرات در فضای جستجو جاری میشوند. تغییر مکان ذرات در فضای جستجو تحت تأثیر تجربه و دانش خودشان و همسایگانشان است؛ بنابراین موقعیت دیگر توده ذرات روی چگونگی جستجوی یک ذره اثر میگذارد. نتیجهٔ مدلسازی این رفتار اجتماعی فرایند جستجویی است که ذرات به سمت نواحی موفق میل میکنند. ذرات از یکدیگر میآموزند و بر مبنای دانش بدست آمده به سمت بهترین همسایگان خود میروند اساس کار PSO بر این اصل استوار است که در هر لحظه هر ذره مکان خود را در فضای جستجو با توجه به بهترین مکانی که تاکنون در آن قرار گرفتهاست و بهترین مکانی که در کل همسایگیاش وجود دارد، تنظیم میکند.
اولین الگوریتم ازدحام ذرات
در سال ۱۹۹۵ ابرهارت و کندی برای اولین بار PSO به عنوان یک روش جستجوی غیر قطعی برای بهینهسازی تابعی مطرح گشت این الگوریتم از حرکت دسته جمعی پرندگانی که به دنبال غذا میباشند، الهام گرفته شدهاست. گروهی از پرندگان در فضایی به صورت تصادفی دنبال غذا میگردند. تنها یک تکه غذا در فضای مورد جستجو وجود دارد. هر راه حل که به آن یک ذره گفته میشود، PSO در الگوریتم معادل یک پرنده در الگوریتم حرکت جمعی پرندگان میباشد. هر ذره یک مقدار شایستگی دارد که توسط یک تابع شایستگی محاسبه میشود. هر چه ذره در فضای جستجو به هدف (غذا در مدل حرکت پرندگان) نزدیکتر باشد، شایستگی بیشتری دارد. همچنین هر ذره دارای یک سرعت است که هدایت حرکت ذره را بر عهده دارد. هر ذره با دنبال کردن ذرات بهینه در حالت فعلی، به حرکت خود در فضای مسئله ادامه میدهد.
به ا ین شکل است که گروهٔ از ذرات در آغاز کار به صورت تصادفی به وجود میآیند و با به روز کردن نسلها سعی در یافتن راهحل بهینه مینمایند. در هر گام، هر ذره با استفاده از دو بهترین مقدار به روز میشود. اولین مورد، بهترین موقعیتی است که تاکنون ذره موفق به رسیدن به آن شدهاست. موقعیت مذکور شناخته و نگهداری میشود که این بهترین مقدار نوستالژی آن ذره نیز گفته میشود که آن را با pbest نمایش میدهیم. بهترین مقدار دیگری که توسط الگوریتم مورد استفاده قرار میگیرد، بهترین موقعیتی است که تا کنون توسط جمعیت ذرات بدست آمدهاست که آن را gbest میگوییم (هوش جمعی).
الگوریتم بهینه سازی ازدحام ذرات و رفتار گروهی حیوانات
دسته پرندگانی (گروه پرندگان | ازدحام پرندگان) که بر فراز یک منطقه در حال حرکت هستند، باید یک نقطه را برای فرود پیدا کنند. در این حالت، تعریف اینکه همه پرندگان در کدام نقطه باید فرود بیایند، مسئله پیچیدهای است. زیرا پاسخ این مسئله، وابسته به موضوعات مختلفی یعنی بیشینه کردن منابع غذایی در دسترس و کمینه کردن خطر وجود شکارچیان است در نقطه محل فرود است. در این شرایط، ناظر میتواند حرکت پرندگان را به صورت رقصپردازی ببیند. پرندگان به طور همزمان در یک برهه از زمان حرکت میکنند تا بهترین محل برای فرود آمدن تعیین شود و همه دسته (گروه) به طور همزمان فرود بیایند.
در مثال بیان شده پیرامون حرکت ازدحامی پرندگان و فرود همزمان آنها، اعضای دسته پرندگان (گروه پرندگان) یا همان ازدحام پرندگان، امکان به اشتراکگذاری اطلاعات با یکدیگر را دارند. در صورتی که پرندگان امکان به اشتراکگذاری اطلاعات با یکدیگر را در گروههای خودشان نداشته باشند، هر پرندهای از گروه (دسته) در محل (نقطه) و در زمان متفاوتی فرود میآید.
پژوهشهایی که از سال ۱۹۹۰ پیرامون رفتار پرندگان انجام شد، حاکی از آن است که همه پرندگان یک ازدحام (گروه | دسته) که به دنبال نقطه خوبی برای فرود هستند، قادر به آن هستند که از بهترین نقطه برای فرود در هنگامی که آن نقطه توسط یکی از اعضای ازدحام پیدا شد، آگاه شوند. با استفاده از این آگاهی، هر یک از اعضای این ازدحام، تجربه دانش شخصی و ازدحامی خود را متوازن میکنند که با عنوان «دانش اجتماعی» (Social Knowledge) شناخته شده است.
شایان ذکر است که معیارهایی که برای ارزیابی خوب یا نامناسب بودن یک نقطه برای فرود مورد بررسی قرار میگیرند، شرایط بقایی هستند که در یک نقطه، برای بقا وجود خواهند داشت. از جمله این موارد، بیشینه بودن منابع غذایی و کمینه بودن خطر وجود شکارچیان است که پیشتر نیز به آنها اشاره شد. مسئله پیدا کردن بهترین نقطه برای فرود، یک مسئله بهینهسازی محسوب میشود. گروه، ازدحام یا گله باید بهترین نقطه فرود، برای مثال طول و عرض جغرافیایی را، به منظور بیشینه کردن شرایط بقای اعضای خود تعیین کند.
برای انجام این کار، هر پرندهای ضمن پرواز، به جستجوی نقطه مناسب فرود میپردازد و نقاط مختلف را از جهت معیارهای بقای گوناگون مورد ارزیابی قرار میدهد تا بهترین منطقه برای فرود را پیدا کند و این کار تا زمانی انجام میشود که بهترین منطقه برای فرود، توسط کل ازدحام مشخص شود.
کندی و اِبِرهارت، از رفتار جمعی پرندگان الهام گرفتند؛ رفتاری که مزایای بقای قابل توجهی را برای پرندگان در هنگام جستجو برای یک نقطه امن برای فرود تضمین میکرد. آنها بر همین اساس، الگوریتمی را ارائه کردند که الگوریتم ازدحام ذرات (Particle Swarm Optimization) نامیده میشود. الگوریتم PSO میتواند رفتاری به مثابه آنچه برای دسته پرندگان گفته شد را تقلید کند.