Skip to content
بازگشت به نتایج جست‌وجو

بهینه‌سازی ازدحام ذرات (PSO)

سال
1995
نوع
Population-based metaheuristic / swarm intelligence

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

بهینه‌سازی ازدحام ذرات (PSO) یک الگوریتم فراابتکاری مبتنی بر جمعیت است که در سال ۱۹۹۵ توسط کندی و ابرهارت معرفی شد و از حرکت جمعی دسته‌های پرندگان و دسته‌های ماهی الهام گرفته شده است. هر راه‌حل کاندید — که ذره نامیده می‌شود — با به‌روزرسانی سرعت و موقعیت خود بر اساس بهترین تجربه شخصی و بهترین تجربه کل ازدحام، در فضای جستجو حرکت می‌کند و همگرایی سریع را در مسائل بهینه‌سازی پیوسته امکان‌پذیر می‌سازد.

شهود پشت روش

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

تاریخ

PSO توسط جیمز کندی و راسل ابرهارت در کنفرانس بین‌المللی شبکه‌های عصبی IEEE در سال ۱۹۹۵ معرفی شد و مستقیماً از مدل‌های شبیه‌سازی رفتار اجتماعی در دسته‌های پرندگان و دسته‌های ماهی الهام گرفت. مقاله بنیادی سال ۱۹۹۵ معادلات به‌روزرسانی سرعت و موقعیت را که همچنان در مرکز الگوریتم قرار دارند، پایه‌گذاری کرد. در سال ۱۹۹۸، شی و ابرهارت پارامتر وزن اینرسی را به به‌روزرسانی سرعت معرفی کردند که کنترل همگرایی را به طور قابل توجهی بهبود بخشید و به اصلاح استاندارد پذیرفته شده توسط تحقیقات بعدی تبدیل شد. PSO به سرعت به عنوان یک جایگزین عملی برای الگوریتم‌های ژنتیک برای بهینه‌سازی پیوسته، به دلیل سادگی و سرعت همگرایی رقابتی، مورد توجه قرار گرفت و از آن زمان در مهندسی، تنظیم ابرپارامترهای یادگیری ماشین، پردازش سیگنال و مدل‌سازی علمی به کار رفته است.

چه زمانی استفاده شود

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

محدودیت‌ها و ملاحظات

  • برای فضاهای جستجوی پیوسته طراحی شده است؛ بدون اصلاح مستقیماً برای مسائل گسسته یا ترکیبی قابل استفاده نیست.
  • همگرایی زودهنگام یک خطر شناخته شده است: ازدحام ممکن است در اطراف یک بهینه محلی تجمع یابد اگر وزن اینرسی و ضرایب به نادرستی انتخاب شوند.
  • سرعت همگرایی و کیفیت راه‌حل به انتخاب وزن اینرسی و ضرایب شتاب حساس هستند.
  • هیچ تضمین نظری برای یافتن بهینه سراسری در تعداد محدودی از تکرارها وجود ندارد.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • همگرایی سریع در فضاهای جستجوی پیوسته در مقایسه با بسیاری از روش‌های مبتنی بر جمعیت.
  • پارامترهای بسیار کمی برای تنظیم — عمدتاً وزن اینرسی و دو ضریب شتاب.
  • نیازی به اطلاعات گرادیان یا مشتق ندارد و آن را برای توابع برازندگی غیرقابل مشتق‌گیری و جعبه سیاه قابل کاربرد می‌سازد.
  • به طور طبیعی به مسائل پیوسته با ابعاد بالا مقیاس می‌شود.
  • از نظر مفهومی ساده و پیاده‌سازی آن آسان است.

کاربردها

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

چگونه کار می‌کند

چگونه کار می‌کند

1

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

2

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

3

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

4

مراحل ارزیابی و به‌روزرسانی برای تعداد مشخصی از تکرارها تکرار می‌شوند. ازدحام به تدریج جستجوی خود را در اطراف امیدوارکننده‌ترین منطقه محدود می‌کند. اجرا زمانی به پایان می‌رسد که حد تکرار به دست آید، که در آن نقطه بهترین موقعیت جهانی به عنوان راه‌حل گزارش می‌شود. تعداد تکرار کافی — معمولاً حداقل چند صد تا هزار برای مسائل غیربدیهی — برای همگرا شدن ازدحام ضروری است؛ توقف زودهنگام خطر بازگرداندن یک نتیجه نامطلوب را دارد.

دام‌های رایج

  • اجرای تعداد تکرارهای کم — برای مسائل غیربدیهی، تکرارهای ناکافی مانع از همگرایی ازدحام می‌شود؛ در صورت محدودیت شدید بودجه محاسباتی، بهینه‌سازی بیزی ترجیح داده می‌شود.
  • انتخاب وزن اینرسی که بیش از حد بالا باشد باعث می‌شود ذرات به طور نامحدود کاوش کنند و همگرایی را به تأخیر بیندازد؛ بیش از حد پایین باعث تجمع زودهنگام در اطراف یک بهینه محلی می‌شود.
  • نادیده گرفتن حدود فضای جستجو — ذراتی که از حدود مورد نظر خارج می‌شوند، مناطق نامربوط را کاوش می‌کنند و بهترین موقعیت جهانی را تحریف می‌کنند.
  • در نظر گرفتن PSO به عنوان مناسب برای مسائل گسسته یا ترکیبی بدون تطبیق — معادلات استاندارد به‌روزرسانی سرعت و موقعیت فرض می‌کنند که فضا پیوسته است.
  • همگرایی زودهنگام در صورتی که پیشرفت برازندگی در طول تکرارها پایش نشود، شناسایی نمی‌شود؛ همیشه نمودار بهترین برازندگی جهانی در مقابل تعداد تکرار را ردیابی کنید.

پرسش‌های متداول

تفاوت PSO با الگوریتم ژنتیک چیست؟

هر دو فراابتکاری‌های مبتنی بر جمعیت برای بهینه‌سازی هستند، اما در مکانیسم متفاوتند. الگوریتم ژنتیک یک جمعیت را از طریق عملگرهای انتخاب، تقاطع و جهش الهام گرفته از تکامل زیستی تکامل می‌دهد. در عوض، PSO ذرات را با به‌روزرسانی سرعت‌ها بر اساس حافظه شخصی و اجتماعی در یک فضای پیوسته حرکت می‌دهد — هیچ تقاطع یا جهشی وجود ندارد. PSO معمولاً پارامترهای کمتری برای تنظیم دارد و اغلب در مسائل پیوسته سریع‌تر همگرا می‌شود، در حالی که الگوریتم‌های ژنتیک می‌توانند به طور طبیعی‌تر با فضاهای گسسته یا ترکیبی تطبیق داده شوند.

پارامترهای کلیدی چه هستند و چگونه باید تنظیم شوند؟

سه پارامتر اصلی عبارتند از وزن اینرسی (w)، که میزان سرعت قبلی حفظ شده را کنترل می‌کند؛ ضریب شناختی (c1)، که جاذبه به سمت بهترین موقعیت شخصی ذره را مقیاس می‌کند؛ و ضریب اجتماعی (c2)، که جاذبه به سمت بهترین موقعیت جهانی را مقیاس می‌کند. یک نقطه شروع رایج از ادبیات، w حدود ۰.۷ تا ۰.۹، و c1 و c2 حدود ۱.۵ تا ۲.۰ است. وزن اینرسی اغلب به طور خطی در طول تکرارها کاهش می‌یابد تا ازدحام را از کاوش اولیه به سمت بهره‌برداری بعدی هدایت کند.

آیا PSO می‌تواند مسائل گسسته یا ترکیبی را مدیریت کند؟

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

چگونه بفهمم که ازدحام زود همگرا شده است؟

مقدار بهترین برازندگی جهانی را در طول تکرارها ردیابی کنید. اگر منحنی قبل از اتمام بودجه تکرار مسطح شود و راه‌حل گزارش شده رضایت‌بخش نباشد، احتمالاً همگرایی زودهنگام رخ داده است. راه‌حل‌های رایج شامل افزایش وزن اینرسی، راه‌اندازی مجدد ازدحام از موقعیت‌های تصادفی جدید، یا افزایش اندازه ازدحام است. اگر بودجه محاسباتی اجازه تکرارهای بیشتر را ندهد، بهینه‌سازی بیزی ممکن است جایگزین کارآمدتری باشد.

روش‌های مرتبط

منابع

  1. Kennedy, J. & Eberhart, R. (1995). Particle Swarm Optimization. IEEE International Conference on Neural Networks (ICNN), 1942-1948.

    باز کردن مرجع DOI
    کپی شد.
  2. Shi, Y. & Eberhart, R. (1998). A Modified Particle Swarm Optimizer. IEEE Congress on Evolutionary Computation (CEC).

    باز کردن مرجع انتشار
    کپی شد.