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

بهینه‌سازی ازدحام ذرات تصادفی — جستجوی سراسری مبتنی بر ازدحام تصادفی

معرفی‌شده توسط
Kennedy, J. and Eberhart, R. (base PSO); stochastic extensions by Clerc, Kennedy and community
سال
1995–2002
نوع
Metaheuristic optimization — stochastic swarm intelligence
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

بهینه‌سازی ازدحام ذرات توسط کندی و ابرهارت در سال 1995 معرفی شد، که از رفتار اجتماعی پرواز پرندگان و دسته‌بندی ماهی‌ها الهام گرفته شده بود. کلرک و کندی (2002) نوع ضریب انقباض را فرموله کرده و پایداری را تحلیل کردند و زمینه را برای کارهای نظری فراهم نمودند. گسترش‌های تصادفی — وزن‌های اینرسی تصادفی، سرعت‌های تقویت شده با نویز، بازنشانی‌های احتمالی — در اواخر دهه 1990 و دهه 2000 ظهور کردند زیرا محققان همگرایی زودهنگام را به عنوان ضعف اصلی عملی الگوریتم اصلی شناسایی کردند.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

یک ازدحام متشکل از N ذره با موقعیت‌های x_i و سرعت‌های v_i را که به طور یکنواخت در فضای جستجوی ممکن نمونه‌گیری شده‌اند، مقداردهی اولیه کنید. تابع هدف f(x_i) را برای هر ذره ارزیابی کرده و بهترین شخصی p_i = x_i و بهترین سراسری g = argmin f(x_i) را تعیین کنید.

2

سرعت هر ذره را با استفاده از قانون تصادفی به‌روزرسانی کنید: v_i(t+1) = omega * v_i(t) + c1*r1*(p_i - x_i) + c2*r2*(g - x_i)، که در آن r1, r2 ~ Uniform(0,1) در هر تکرار نمونه‌های تصادفی جدید هستند. در Stochastic PSO، خود omega ممکن است از یک توزیع (مثلاً Uniform(0.4, 0.9)) نمونه‌برداری شود یا یک جمله نویز گاوسی epsilon ~ N(0, sigma^2) برای حفظ تنوع اضافه شود.

فرمول
v_i(t+1) = \omega v_i(t) + c_1 r_1 (p_i - x_i(t)) + c_2 r_2 (g - x_i(t))
3

هر ذره را به موقعیت کاندید جدید خود منتقل کنید: x_i(t+1) = x_i(t) + v_i(t+1). برای نگه داشتن ذرات در دامنه ممکن، مدیریت مرز (بازتاب، برش، یا پیچش توروس) را اعمال کنید.

فرمول
x_i(t+1) = x_i(t) + v_i(t+1)
4

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

5

f(x_i(t+1)) را برای همه ذرات ارزیابی کنید؛ بهترین‌های شخصی و بهترین سراسری را به‌روزرسانی کنید. به‌روزرسانی سرعت را تا بررسی همگرایی برای T تکرار یا تا زمانی که یک معیار توقف برآورده شود (مثلاً بهبود برازش < epsilon در K تکرار متوالی) تکرار کنید. بهترین سراسری g را به عنوان راه‌حل برگردانید.

دام‌های رایج

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

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

Stochastic PSO چگونه با PSO استاندارد تفاوت دارد؟

PSO استاندارد از ضرایب تصادفی r1 و r2 که در هر تکرار به طور یکنواخت نمونه‌برداری می‌شوند، استفاده می‌کند. Stochastic PSO به طور عمدی این تصادفی بودن را ساختاردهی یا تقویت می‌کند — برای مثال با نمونه‌برداری وزن اینرسی omega از یک توزیع احتمال در هر تکرار، افزودن نویز گاوسی به موقعیت ذرات، یا بازنشانی احتمالی ذرات ایستا — برای ارائه حفظ تنوع قوی‌تر.

چند ذره باید استفاده کنم؟

یک نقطه شروع رایج 20–50 ذره برای مسائل تا حدود 30 بعد است. ازدحام‌های بزرگتر (50–200) پوشش را در فضاهای با ابعاد بالا یا چندوجهی بالا با هزینه ارزیابی‌های تابع بیشتر در هر تکرار بهبود می‌بخشند.

چگونه واریانس نویز را برای اغتشاشات تصادفی انتخاب کنم؟

روی یک نمونه نماینده از کلاس مسئله خود کالیبره کنید. یک قاعده سرانگشتی عملی این است که انحراف معیار نویز افزوده را تقریباً 1–5٪ عرض فضای جستجو در هر بعد تنظیم کنید، سپس بر اساس تشخیص‌های همگرایی تنظیم کنید — معیار تنوع نباید قبل از اتمام بودجه به نزدیک صفر فرو بریزد.

چه زمانی باید Stochastic PSO را به Differential Evolution یا الگوریتم‌های ژنتیک ترجیح دهم؟

Stochastic PSO تمایل دارد در مسائل پیوسته با ابعاد کم تا متوسط سریع‌تر همگرا شود و پیاده‌سازی آن بسیار ساده است. Differential Evolution و الگوریتم‌های ژنتیک معمولاً ساختارهای ترکیبی یا گسسته را بهتر مدیریت می‌کنند. اگر مسئله شما کاملاً پیوسته و چندوجهی است، Stochastic PSO یک انتخاب اول قوی است.

آیا Stochastic PSO برای مسائل چندهدفه مناسب است؟

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

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

منابع

  1. Kennedy, J., Eberhart, R. (1995). Particle swarm optimization. Proceedings of ICNN'95 - International Conference on Neural Networks, Vol. 4, pp. 1942-1948. IEEE.

    باز کردن مرجع DOI
    کپی شد.
  2. Clerc, M., Kennedy, J. (2002). The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), 58-73.

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