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

بهینه‌سازی کلونی ذرات چندهدفه (MOPSO)

معرفی‌شده توسط
Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S.
سال
2004
نوع
Population-based swarm metaheuristic
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

بهینه‌سازی کلونی ذرات در سال ۱۹۹۵ توسط کندی و ابرهارت معرفی شد که از رفتار اجتماعی پرسه زدن پرندگان الهام گرفته شده بود. اولین توسعه چندهدفه که به طور گسترده پذیرفته شد، MOPSO، در سال ۲۰۰۴ توسط کوئلو کوئلو، پولیدو و لچوگا پیشنهاد شد که بایگانی خارجی پارتو و انتخاب رهبر مبتنی بر ابرمکعب را معرفی کرد. انواع بعدی — از جمله OMOPSO، dMOPSO و SMPSO — مدیریت بایگانی، پارامترهای تطبیقی و مدیریت محدودیت‌ها را اصلاح کردند و MOPSO را در کنار NSGA-II به عنوان یک الگوریتم اصلی تقریب جبهه پارتو تثبیت کردند.

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

هنگامی که با یک مسئله بهینه‌سازی پیوسته با دو یا چند هدف متعارض روبرو هستید و نیاز به تقریب جبهه پارتوی کامل به جای یک راه‌حل واحد دارید، از MOPSO استفاده کنید. این الگوریتم در طراحی مهندسی، زنجیره تأمین، سیستم‌های انرژی و تنظیم ابرپارامترها که در آن ارزیابی اهداف نسبتاً پرهزینه است و فضای تصمیم‌گیری پیوسته است، عالی عمل می‌کند. الگوریتم‌های NSGA-II یا NSGA-III را برای مسائل ترکیبی یا مختلط صحیح ترجیح دهید و در صورتی که اهداف هموار و مشتق‌پذیر باشند، روش‌های چندهدفه مبتنی بر گرادیان را ترجیح دهید. زمانی که تعداد اهداف از پنج تا هفت بیشتر می‌شود از MOPSO استفاده نکنید — مسائل چندهدفه بهینه‌سازهای تخصصی چندهدفه (مانند NSGA-III، MOEA/D) نیاز دارند. همچنین زمانی که هر ارزیابی تابع فوق‌العاده پرهزینه است (کمتر از ۱۰۰ ارزیابی در دسترس است) از آن اجتناب کنید — روش‌های با کمک جانشین در آن رژیم ترجیح داده می‌شوند.

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

  • عملکرد به وزن اینرسی (w) و ضرایب شتاب (c1، c2) حساس است؛ پارامترهای نامناسب باعث همگرایی زودرس یا انحراف بیش از حد می‌شوند.
  • مدیریت بایگانی و انتخاب رهبر، ابرپارامترهای اضافی (اندازه بایگانی، معیار ازدحام) را معرفی می‌کنند که وابسته به مسئله هستند.
  • تضمین‌های همگرایی و تنوع، تقریبی هستند، نه ریاضی — جبهه پارتوی تقریبی ممکن است نواحی از جبهه حقیقی را از دست بدهد.
  • با بیش از پنج تا هفت هدف به دلیل نفرین ابعاد در انتخاب مبتنی بر تسلط، دست و پنجه نرم می‌کند.
  • بدون رمزگذاری و تطبیق‌های محدودکننده سرعت خاص مسئله، مستقیماً برای فضاهای جستجوی گسسته یا ترکیبی قابل استفاده نیست.

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

نقاط قوت

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

کاربردها

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

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

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

1

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

2

تمام مقادیر تابع هدف را برای هر ذره در کلونی فعلی محاسبه کنید. مقایسه‌های تسلط را اعمال کنید: یک راه‌حل x بر y تسلط دارد اگر x در تمام اهداف بدتر نباشد و حداقل در یک هدف به طور قابل توجهی بهتر باشد. اگر موقعیت جدید بر بهترین موقعیت شخصی ذخیره‌شده تسلط دارد یا نسبت به آن غیرمسلط است، pbest هر ذره را به‌روزرسانی کنید.

3

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

4

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

5

سرعت و موقعیت هر ذره را با استفاده از قاعده به‌روزرسانی PSO به‌روز کنید: v = w*v + c1*r1*(pbest - x) + c2*r2*(gbest - x)، که در آن w وزن اینرسی است که تعادل کاوش/بهره‌برداری را کنترل می‌کند، c1 و c2 ضرایب شتاب شناختی و اجتماعی هستند، و r1 و r2 اعداد تصادفی یکنواخت هستند. برای نگه داشتن ذرات در فضای تصمیم‌گیری ممکن، مدیریت مرز را اعمال کنید.

فرمول
v_{id}^{t+1} = w v_{id}^t + c_1 r_1 (pbest_{id} - x_{id}^t) + c_2 r_2 (gbest_d - x_{id}^t)
6

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

دام‌های رایج

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

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

MOPSO چگونه با NSGA-II تفاوت دارد؟

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

از چه اندازه بایگانی باید استفاده کنم؟

یک اندازه پیش‌فرض رایج برای مسائل دو یا سه هدفه، ۱۰۰ تا ۲۰۰ راه‌حل است. بایگانی‌های بزرگتر پوشش جبهه پارتو را بهبود می‌بخشند اما انتخاب رهبر را کند می‌کنند. برای مسائل با چهار یا چند هدف، اندازه بایگانی باید با پیچیدگی مورد انتظار جبهه پارتو مقیاس شود؛ طرح‌های مدیریت بایگانی تطبیقی می‌توانند کمک کنند.

آیا MOPSO می‌تواند محدودیت‌ها را مدیریت کند؟

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

MOPSO به طور مؤثر با چند تابع هدف می‌تواند کار کند؟

MOPSO برای دو تا چهار هدف به خوبی کار می‌کند. فراتر از پنج تا هفت هدف، فشار تسلط به شدت تضعیف می‌شود — تقریباً تمام راه‌حل‌ها به طور متقابل غیرمسلط می‌شوند — و بهینه‌سازهای تخصصی چندهدفه (NSGA-III، MOEA/D، یا روش‌های مبتنی بر تجزیه) از MOPSO استاندارد بهتر عمل می‌کنند.

از چه معیارهایی برای ارزیابی نتایج MOPSO باید استفاده کنم؟

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

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

منابع

  1. Coello Coello, C. A., Pulido, G. T., & Lechuga, M. S. (2004). Handling multiple objectives with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8(3), 256–279.

    باز کردن مرجع DOI
    کپی شد.
  2. Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks (ICNN), Perth, Australia, 4, 1942–1948.

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