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

استراتژی تکاملی (CMA-ES) — تطبیق ماتریس کوواریانس

معرفی‌شده توسط
Nikolaus Hansen & Andreas Ostermeier
سال
2001
نوع
Derivative-free continuous black-box optimizer

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

اندازه قلم

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

CMA-ES، مخفف عبارت Covariance Matrix Adaptation Evolution Strategy، یک بهینه‌ساز مدرن بدون مشتق برای توابع جعبه سیاه پیوسته است که در سال ۲۰۰۱ توسط هانسن و اوسترِمِیر معرفی شد. این الگوریتم جمعیتی از راه‌حل‌های کاندید را که از یک توزیع نرمال چندمتغیره نمونه‌برداری شده‌اند، حفظ می‌کند و به طور تکراری میانگین، اندازه گام و ماتریس کوواریانس کامل توزیع را به‌روزرسانی می‌کند تا جستجو را به سمت نواحی بهتر فضای پارامتر هدایت کند. این الگوریتم به استاندارد عملی برای بهینه‌سازی جعبه سیاه پیوسته تبدیل شده و به طور گسترده در جستجوی معماری عصبی و بهینه‌سازی خط‌مشی یادگیری تقویتی استفاده می‌شود.

شهود پشت روش

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

تاریخ

استراتژی‌های تکاملی در دهه‌های ۱۹۶۰ و ۱۹۷۰ به عنوان خانواده‌ای از بهینه‌سازهای مبتنی بر جمعیت که از تکامل بیولوژیکی الهام گرفته‌اند، معرفی شدند. مکانیزم تطبیق ماتریس کوواریانس توسط هانسن و اوسترِمِیر توسعه یافت و به طور کامل در مقاله آن‌ها در سال ۲۰۰۱ در Evolutionary Computation شرح داده شد، که نشان داد خود-تطبیق کاملاً غیرتصادفی — یادگیری هندسه مرتبه دوم کامل منظره جستجو از تاریخچه گام‌های موفق — به طور چشمگیری از استراتژی‌های تکاملی قبلی در مسائل بدحالت و غیرقابل تفکیک بهتر عمل کرد. مقاله آموزشی هانسن در سال ۲۰۱۶ الگوریتم و خواص نظری آن را تثبیت کرد و CMA-ES را به روش مرجع استاندارد برای سنجش عملکرد بهینه‌سازی جعبه سیاه پیوسته تبدیل کرد.

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

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

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

  • هزینه حافظه درجه دوم و هزینه محاسباتی در هر نسل نسبت به تعداد ابعاد، کاربرد را فراتر از حدود ۱۰۰۰ پارامتر بدون واریانت‌های کاهش ابعاد محدود می‌کند.
  • در غیاب راه‌اندازی مجدد، به یک بهینه محلی همگرا می‌شود؛ برای مناظر بسیار چندوجهی، راه‌اندازی مجدد متعدد (IPOP-CMA-ES یا BIPOP-CMA-ES) لازم است.
  • برای فضاهای جستجوی گسسته یا ترکیبی مناسب نیست — روش ذاتاً بر روی بردارهای پیوسته با مقادیر حقیقی تعریف شده است.

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

نقاط قوت

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

کاربردها

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

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

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

1

الگوریتم با یک بردار راه‌حل اولیه و یک اندازه گام اولیه (سیگما) آغاز می‌شود. ماتریس کوواریانس به صورت ماتریس همانی شروع می‌شود — یک ابر جستجوی کاملاً کروی. اندازه جمعیت تنظیم می‌شود، معمولاً حدود ۴ + floor(۳ * ln(بعد)).

2

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

3

هر راه‌حل کاندید به تابع هدف ارسال شده و یک امتیاز برازندگی دریافت می‌کند. هیچ اطلاعات گرادیانی مورد نیاز نیست — فقط مقدار هدف اسکالر در هر نقطه نمونه‌برداری شده لازم است. این امر CMA-ES را برای اهداف نویزی، غیرقابل تفکیک و مبتنی بر شبیه‌سازی مناسب می‌سازد.

4

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

5

الگوریتم چرخه نمونه‌برداری–ارزیابی–به‌روزرسانی را تکرار می‌کند تا زمانی که یک معیار توقف برآورده شود: حداکثر تعداد ارزیابی‌های تابع، تحمل در تغییر میانگین یا اندازه گام، یا انحطاط تشخیص داده شده ماتریس کوواریانس. بهترین راه‌حل یافت شده در تمام نسل‌ها بازگردانده می‌شود.

دام‌های رایج

  • تنظیم اندازه گام اولیه خیلی کوچک، جستجو را در یک همسایگی باریک به دام می‌اندازد و از کاوش جلوگیری می‌کند؛ خیلی بزرگ و نسل‌های اولیه ارزیابی‌ها را دور از بهینه تلف می‌کنند. یک قانون سرانگشتی رایج این است که سیگما را طوری تنظیم کنید که بهینه در حدود سه سیگما از نقطه شروع قرار گیرد.
  • اعمال CMA-ES بر روی مسائل با ابعاد بسیار کم (کمتر از پنج پارامتر) معمولاً اتلاف وقت است — جستجوی شبکه‌ای ساده‌تر یا Nelder-Mead کافی است و سربار جمعیت CMA-ES هیچ منفعتی ندارد.
  • اجرای تنها یک نمونه CMA-ES بر روی یک منظره چندوجهی، خطر از دست دادن بهینه سراسری را دارد؛ هنگام شناخته شدن منظره به عنوان بسیار چندوجهی، از راه‌اندازی مجدد چندگانه یا استراتژی‌های راه‌اندازی مجدد مبتنی بر جمعیت (IPOP/BIPOP) استفاده کنید.
  • رفتار کردن بهترین راه‌حل بازگردانده شده به عنوان بهینه سراسری واقعی بدون تأیید راه‌اندازی مجدد، یک اشتباه رایج است — هنگام غیرمحدب بودن شدید تابع هدف، همیشه با چندین اجرای مستقل تأیید کنید.

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

CMA-ES چگونه با یک الگوریتم ژنتیک ساده تفاوت دارد؟

یک الگوریتم ژنتیک کلاسیک جمعیتی را حفظ کرده و از عملگرهای تقاطع و جهش با عملگرهای ثابت استفاده می‌کند. در عوض، CMA-ES جمعیت را به عنوان نمونه‌هایی از یک توزیع نرمال چندمتغیره مدل می‌کند و آن توزیع — میانگین، اندازه گام و ماتریس کوواریانس کامل آن — را به طور مداوم بر اساس اینکه کدام راه‌حل‌ها موفق بوده‌اند، تطبیق می‌دهد. این امر به CMA-ES اجازه می‌دهد تا شکل منظره زیان را یاد بگیرد و فضاهای همبسته و بدحالت را بسیار کارآمدتر از یک الگوریتم ژنتیک با عملگرهای ثابت پیمایش کند.

آیا CMA-ES تضمین می‌کند که بهینه سراسری را پیدا کند؟

خیر. CMA-ES به این معنا یک روش جستجوی محلی است که یک اجرای منفرد می‌تواند به یک بهینه محلی همگرا شود. برای مناظر چندوجهی، راه‌اندازی مجدد مستقل متعدد — احتمالاً با افزایش اندازه جمعیت (IPOP-CMA-ES) — برای بهبود پوشش فضای جستجو توصیه می‌شود.

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

اندازه گام اولیه سیگما، تأثیرگذارترین ابرپارامتر است. یک راهنمای خوب این است که آن را طوری تنظیم کنید که بهینه مورد انتظار در حدود سه سیگما از نقطه شروع قرار گیرد. اندازه جمعیت و حداکثر تعداد ارزیابی‌ها کنترل‌های ثانویه هستند؛ فرمول پیش‌فرض اندازه جمعیت (۴ + floor(۳ * ln(بعد))) در عمل به خوبی کار می‌کند.

آیا CMA-ES می‌تواند توابع هدف نویزی را مدیریت کند؟

بله. از آنجایی که CMA-ES فقط از اطلاعات رتبه-ترتیب جمعیت استفاده می‌کند — نه مقادیر مطلق تابع — نسبتاً در برابر نویز مقاوم است. برای ارزیابی‌های بسیار نویزی، افزایش اندازه جمعیت یا میانگین‌گیری چندین ارزیابی برای هر کاندید می‌تواند مقاومت را بیشتر کند.

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

منابع

  1. Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.

    باز کردن مرجع DOI
    کپی شد.
  2. Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

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