الگوریتم ازدحام ذرات PSO : از صفر تا صد!

الگوریتم ازدحام ذرات PSO : از صفر تا صد!

پیدایش و اساس الگوریتم ازدحام ذرات PSO

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

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

یک مثال دقیقتر از منبع الهام الگوریتم ازدحام ذرات PSO

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

الگوریتم ازدحام ذرات الهام گرفته از حرکت پرندگان

الگوریتم ازدحام ذرات جستجو را از میان یک سری عوامل انجام می دهد. این عوامل که به ذرات معروفند ، مسیر هایی را به صورت آماری یا دقیق تعیین شده اند طی میکنند. هر ذره متاثر از بهترین موقعیت خود و بهترین موقعیت کل گروه است. اما باید به صورت تصادفی حرکت کند. هر ذره i ، بوسیله ی بردار موقعیت خود (xi) و بردار سرعت خود (vi) تعریف می شود. در هر بار تکرار این الگوریتم ، هر ذره موقعیت مکانی جدیدی را بر راسال بردار سرعت جدید خود بدست می آورد.

حتما بخوانید:  روش های بهینه سازی در متلب

فرمول های الگوریتم ازدحام ذرات

در این رابطه متغیر های xBest و gBest به ترتیب نشانگر بهترین موقعیت ذره و بهترین موقعیت گروه می باشند. سایر متغیر ها در زیر توضیح داده شده اند:

\( \Large \omega \) : برابر است با اینرسی وزن

\( \Large c_1 , c_2 \) : دو مقدار ثابت با علامت مثبت

\( \Large r_1 , r_2 \) : دو پارامتر مثبت با مقدار بین صفر تا یک

در ابتدای توسعه ی الگوریتم ازدحام ذرات متغیر \( \Large \omega \) بعنوان مقداری ثابت انتخاب میگردید. اما در ادامه و با توسعه بیشتر این الگوریتم بهینه سازی ، مقدار مناسب آن \( \Large \omega = [0.5 , 0.9] \) در نظر گرفته شد. به طور معمول مقدار حداکثر و حداقل سرعت نیز تعریف میگردد. همچنین در ابتدا ذرات به صورت تصادفی در کل محیط پخش می شوند تا مشوقی باشند برای جستجو در تمام موقعیت های ممکن.

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

  1. سیستم با یک جمعیت تصادفی از جواب های محتمل شروع به کار میکند. هر عضو محتمل راه حل یک سرعت تصادفی دارد و به آن ذره میگوییم. این ذره در فضای پاسخ دارای یک موقعیت نیز میباشد. این ذرات در فضای پاسخ شروع به حرکت میکنند.
  2. ارزیابی تناسب (fitness) هر ذره در بین گروه.
  3. در هر بار تکرار این الگوریتم ، تناسب ذره در آن تکرار با بهترین تناسب قبلی آن \( P_{best} \) مقایسه میگردد. اگر مقدار فعلی بهتر از \( P_{best} \) باشد، بنابراین \( P_{best} \) را برابر با مقدار فعلی قرار میدهیم. و موقعیت \( P_{best} \) را نیز به همین ترتیب.
  4. مقایسه \( P_{best} \) ذرات با یکدیگر و بروزرسانی بهترین موقعیت کل گروه با بزرگترین تناسب \( g_{best} \) .
  5. سرعت هر ذره متناسب با \( P_{best} \) و \( g_{best} \) اش تغییر میکند (شتاب میگیرد). این شتاب با مقدار تصادفی وزن میگیرد. یک موقعیت جدید در فضای پاسخ برای هر ذره محاسبه میگردد. این کار بوسیله ی اضافه کردن سرعت جدید به هر جزء از بردار موقعیت ذره انجام میذیرد.
  6. تکرار مراحل 2 تا 5 تا زمانی که همگرایی مورد نظر بر اساس یک یا چند ضابطه ی مطلوب حاصل گردد.”
حتما بخوانید:  الگوریتم کلونی مورچگان ACO : هرآنچه باید بدانید!

مراحل الگوریتم ازدحام ذرات

برتری الگوریتم ازدحام ذرات PSO نسبت به سایر الگوریتم ها

یکی از نکات مثبت این الگوریتم نسب به دیگر روشها ، کاهش تعداد پارامترهای مورد نیاز برای تنظیم و رعایت محدودیت هاست.

نمایش حرکت یک ذره

شکل زیر نمایشگر دو بعدی ذره ی \( \Large i \) است.

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

حرکت ذره ی i در فضای پاسخ. در تکرار k و k+1 . تکامل حرکت ذره متاثر از بهترین موقعیت ذره \( P_{best} \) و بهترین موقعیت کل گروه \( G_{best} \)

این شکل به خوبی نشان می دهد که چگونه بهترین موقعیت ذره \( P_{best} \) و بهترین موقعیت گروه \( G_{best} \) بر روی سرعت ذره در تکرار بعدی تاثیر گذار هستند. با این حال ، خواص آماری الگوریتم این امکان را فراهم می سازد که کل فضای پاسخ جستجو گردد.

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

برای الگوریتم های بهینه سازی به خصوص الگوریتم ازدحام ذرات میتوان کاربرد های گوناگونی را ذکر کرد. یکی از این کاربردها استفاده از این الگوریتمها در بهینه سازی پارامتر های مربوط به شبکه های عصبی در حوزه هوش مصنوعی است. شبکه های عصبی یکی از شاخه های اصلی در یادگیری ماشین هستند.

الگوریتم ازئحام ذرات در خودروهای هیبرید

گائو (Gao) و همکارانش یک مقاله تاریخی را ارائه دادند. آنها تحلیلی جامع برای الگوریتم های عاری از مشتقات به منظور بهینه سازی خودروهای الکتریکی هیبرید در یک محیط شبیه سازی انجام دادند. آنها الگوریتمهای متعددی مانند الگوریتم ژنتیک ، الگوریتم تبرید ، الگوریتم مستقیم (DIRECT) و الگوریتم ازدحام ذرات PSO را به کار گرفتند. این الگوریتمهای بهینه سازی به منظور کاهش مصرف سوخت ، طراحی و عملکرد بهینه تر استفاده شدند. مطالعه نشان داد که الگوریتم تبرید و الگوریتم ازدحام ذرات بهترین خروجی های بهینه سازی را داشتند. که البته بین این دو، الگوریتم ازدحام ذرات کمی بهتر بود.

حتما بخوانید:  الگوریتم ژنتیک در متلب

الگوریتم ازدحام ذرات در بهینه سازی مصرف سوخت برای خودروی هوشمند الکتریکی

همچنین چن (Chen) و همکارانش به دفعات طراحی و مصرف انرژی را در یک خودروی هیبرید الکتریکی بهینه کردند. آنها این کار را به منظور کاهش مصرف سوخت و تولید آلاینده ها انجام دادند. نویسندگان آن مقاله مدعی شدند که کاهش قابل توجهی در سوخت و تولید آلاینده ها با ترکیب طراحی و کنترل بوسیله الگوریتم ازدحام ذرات حاصل گردید.

الگوریتم ازدحام ذرات در مهندسی عمران

بعنوان یک الگوریتم بهینه سازی ، الگوریتم ازدحام ذرات موفقیت های گسترده ای در حوزه مهندسی عمران داشته است.

استفاده از الگوریتم ازدحام ذرات در صنعت حمل و نقل

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

  • بهینه سازی در طراحی سازه در مورد شکل و اندازه
  • ارزیابی شرایط سازه و پایش سلامت آن
  • شاخصه های مواد سازه ای و مدلسازی آنها
  • طراحی شبکه های حمل و نقل
  • پیش بینی جریان ترافیک
  • کنترل ترافیک
  • پیش بینی حوادث ترافیکی
  • پیش بینی سطح رودخانه ها
  • طراحی شبکه های پخش آب و پسآب
  • حل مشکلات عملیات ذخیره سازی
  • تخمین و کالیبره کردن مدلهای هیدرولوژیکی
  • برنامه ریزی ساخت
  • زمان بندی و مدیریت
  • تخمین و پیش بینی هزینه ساخت
  • روش معکوس شناسایی پارامتر و کالیبره کردن مدلهای ژئوتکنیکی
  • تحلیل پایداری شیب
  • مهندسی خاکبرداری
  • و غیره

در نوشتارهای آینده از این دوره آموزشی، به آموزش الگوریتم ازدحام ذرات در نرم افزار متلب خواهیم پرداخت.

منبع : مقاله مروری بر الگوریتم ازدحام ذرات از ScienceDirect

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.