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

بهینه‌ساز گرگ خاکستری — GWO

معرفی‌شده توسط
Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis
سال
2014
نوع
Swarm-intelligence metaheuristic

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

اندازه قلم

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

بهینه‌ساز گرگ خاکستری (GWO) یک فراابتکاری مبتنی بر هوش ازدحامی است که در سال ۲۰۱۴ توسط میرجلیلی، میرجلیلی و لوئیس معرفی شد و سلسله‌مراتب اجتماعی و رفتار شکار مشارکتی گرگ‌های خاکستری را مدل‌سازی می‌کند. جمعیتی از راه‌حل‌های کاندید به چهار رتبه رهبری — آلفا، بتا، دلتا و امگا — تقسیم می‌شوند و سه راه‌حل برتر در هر تکرار، کل ازدحام را به سمت نواحی بهتر و بهتر فضای جستجو هدایت می‌کنند.

شهود پشت روش

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

تاریخ

GWO توسط سیدعلی میرجلیلی، سیدمحمد میرجلیلی و اندرو لوئیس در سال ۲۰۱۴ در مجله Advances in Engineering Software پیشنهاد شد. این الگوریتم از مشاهدات زیست‌محیطی ساختار گله گرگ خاکستری الهام گرفته است: یک سلسله‌مراتب اجتماعی سختگیرانه (آلفا، بتا، دلتا، امگا) و استراتژی شکار سه مرحله‌ای شامل محاصره، آزار و حمله به طعمه. میرجلیلی و همکاران GWO را در برابر بهینه‌سازی ازدحام ذرات، الگوریتم جستجوی گرانشی و تکامل تفاضلی بر روی ۲۹ تابع آزمایشی و چندین مسئله طراحی مهندسی محک زدند و نتایج رقابتی یا برتر را گزارش کردند. از سال ۲۰۱۴، این الگوریتم ادبیات پیگیری قابل توجهی تولید کرده است: Faris و همکاران (۲۰۱۸) بیش از یک دهه از انواع آن — افزونه‌های باینری، چندهدفه، آشوبناک و ترکیبی — را بررسی کردند و کاربردهایی در انتخاب ویژگی، سیستم‌های قدرت، تقسیم‌بندی تصویر و زمان‌بندی را مستند کردند.

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

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

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

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

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

نقاط قوت

  • بدون گرادیان: روی هر تابع هدفی که یک مقدار اسکالر برمی‌گرداند، از جمله شبیه‌سازی‌ها و مدل‌های جعبه سیاه، کار می‌کند.
  • پارامتردهی حداقلی: فقط اندازه جمعیت و تعداد تکرارها باید تنظیم شوند؛ a به طور خودکار کاهش می‌یابد.
  • تعادل بین کاوش و بهره‌برداری از طریق یک پارامتر واحد با کاهش خطی، مکانیسم تعادل را شفاف می‌سازد.
  • عملکرد رقابتی در معیارهای طراحی مهندسی با پیچیدگی پیاده‌سازی کم (سطح دشواری ۲ از ۵).

کاربردها

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

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

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

1

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

2

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

3

کاندیداها بر اساس برازندگی مرتب می‌شوند. بهترین راه‌حل آلفا (α)، دومین بهترین بتا (β) و سومین بهترین دلتا (δ) نامیده می‌شود. تمام کاندیداهای باقی‌مانده گرگ‌های امگا (ω) هستند. این نقش‌ها هر تکرار مجدداً تخصیص داده می‌شوند تا برچسب‌ها همیشه سه موقعیت برتر فعلی را دنبال کنند.

4

هر گرگ امگا با محاسبه سه بردار فاصله — یکی به سمت هر یک از α، β و δ — موقعیت خود را به‌روزرسانی می‌کند و به مرکز سه موقعیت هدف حاصل منتقل می‌شود. پارامتر کنترلی a به صورت خطی از ۲ به ۰ در طول اجرا کاهش می‌یابد: مقادیر بزرگ a باعث کاوش می‌شوند (کاندیداها می‌توانند از حد بگذرند و دور از رهبران جستجو کنند)، مقادیر کوچک باعث بهره‌برداری می‌شوند (کاندیداها به شدت در اطراف رهبران همگرا می‌شوند).

5

مرحله شکار تکرار می‌شود تا زمانی که حداکثر تعداد تکرارها به پایان برسد یا یک معیار توقف برآورده شود. موقعیت گرگ آلفا در پایان به عنوان بهترین راه‌حل یافت شده برگردانده می‌شود.

دام‌های رایج

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

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

چگونه اندازه جمعیت و تعداد تکرارها را انتخاب کنم؟

یک نقطه شروع رایج ۳۰ عامل و ۲۰۰ تا ۵۰۰ تکرار برای مسائل با ابعاد متوسط (تا حدود ۳۰ متغیر) است. با افزایش ابعاد مسئله، اندازه جمعیت و تکرارها را افزایش دهید. از آنجایی که GWO تصادفی است، آن را حداقل ۲۰ تا ۳۰ بار با بذرهای تصادفی مختلف اجرا کنید و میانگین و انحراف معیار بهترین برازندگی را گزارش دهید.

آیا GWO می‌تواند متغیرهای گسسته یا باینری را مدیریت کند؟

ذاتاً نه. معادلات استاندارد به‌روزرسانی موقعیت برای فضاهای پیوسته با مقادیر حقیقی تعریف شده‌اند. انواع باینری یا گسسته در ادبیات وجود دارند — معمولاً با استفاده از یک تابع انتقال برای نگاشت موقعیت‌های پیوسته به تصمیمات باینری — اما اینها افزونه‌هایی هستند نه الگوریتم اصلی.

GWO چگونه با بهینه‌سازی ازدحام ذرات مقایسه می‌شود؟

هر دو روش هوش ازدحامی با هزینه محاسباتی مشابه هستند. GWO از سه رهبر (آلفا، بتا، دلتا) به جای یک بهترین سراسری و بهترین موقعیت شخصی هر ذره استفاده می‌کند، که تمایل دارد تنوع را طولانی‌تر حفظ کند. میرجلیلی و همکاران (۲۰۱۴) GWO را در مجموعه معیار خود رقابتی یا برتر از PSO یافتند، اما عملکرد به مسئله بستگی دارد؛ هیچ روشی به طور جهانی غالب نیست.

پارامتر a چه چیزی را کنترل می‌کند و آیا باید آن را تنظیم کنم؟

پارامتر a به صورت خطی از ۲ به ۰ در طول اجرا کاهش می‌یابد و کنترل می‌کند که آیا گرگ‌ها کاوش می‌کنند (a بالا) یا بهره‌برداری می‌کنند (a پایین). این برنامه توسط الگوریتم ثابت شده است — شما مستقیماً a را تنظیم نمی‌کنید. تنها اهرم‌هایی که شما کنترل می‌کنید اندازه جمعیت و تعداد کل تکرارها هستند که با هم تعیین می‌کنند a با چه سرعتی کاهش می‌یابد.

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

منابع

  1. Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey Wolf Optimizer. Advances in Engineering Software, 69, 46-61.

    باز کردن مرجع DOI
    کپی شد.
  2. Faris, H., Aljarah, I., Al-Betar, M. A., & Mirjalili, S. (2018). Grey Wolf Optimizer: A Review of Recent Variants and Applications. Neural Computing and Applications, 30(2), 413-435.

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