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

تکامل تفاضلی — بهینه‌ساز تصادفی سراسری

معرفی‌شده توسط
Rainer Storn & Kenneth Price
سال
1997
نوع
Population-based stochastic metaheuristic

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

تکامل تفاضلی توسط راینر استورن و کنت پرایس در مقاله برجسته آنها در سال ۱۹۹۷ در مجله Global Optimization معرفی شد. این الگوریتم از کارهای قبلی پرایس در مورد بازپخت ژنتیکی و آزمایشات استورن با تقاطع ممیز شناور نشأت گرفت. نوع اصلی، که اکنون DE/best/1/bin نامیده می‌شود، در معیارهای استاندارد با استراتژی‌های تکاملی و الگوریتم‌های ژنتیک معاصر رقابتی — و اغلب برتر — بود. یک بررسی جامع توسط داس، مولیک و سوگانثان (۲۰۱۶) بیش از دو دهه از انواع، طرح‌های تطبیقی و کاربردها را فهرست کرد و DE را به عنوان یکی از روش‌های بنیادی در ادبیات فراابتکاری تثبیت کرد.

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

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

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

  • اگر تعداد تکرارها کافی نباشد، همگرایی می‌تواند کند باشد؛ کمتر از ۱۰۰۰ نسل اغلب منجر به نتیجه‌ای زیربهینه می‌شود.
  • عملکرد به انتخاب F و CR حساس است — پارامترهای بد تنظیم شده می‌توانند منجر به همگرایی زودهنگام یا پیشرفت بیش از حد کند شوند.
  • برای فضاهای جستجوی کاملاً گسسته یا ترکیبی طراحی نشده است؛ نسخه‌های گسسته وجود دارند اما کمتر استاندارد هستند.
  • هر تکرار نیاز به ارزیابی تابع هدف NP بار دارد، که زمانی که هر ارزیابی از نظر محاسباتی پرهزینه باشد، می‌تواند گران باشد.

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

نقاط قوت

  • به اطلاعات گرادیان نیازی ندارد — با هر تابع هدف جعبه سیاه، از جمله توابع غیرقابل‌اشتقاق و نویزدار، کار می‌کند.
  • پارامترهای کنترلی بسیار کمی (F، CR، NP) نسبت به قدرت جستجوی آن دارد، که پیکربندی آن را نسبتاً آسان می‌کند.
  • به طور طبیعی با چشم‌اندازهای چندوجهی که بهینه‌سازهای مبتنی بر گرادیان به بهینه‌های محلی همگرا می‌شوند، کنار می‌آید.
  • ارزیابی‌های جمعیت مستقل هستند و می‌توانند به سادگی موازی‌سازی شوند، که زمان ساعت دیواری را در سیستم‌های چند هسته‌ای کاهش می‌دهد.
  • در بسیاری از معیارهای استاندارد با الگوریتم‌های ژنتیک و بهینه‌سازی ازدحام ذرات رقابتی است، در حالی که از یک قانون به‌روزرسانی ساده‌تر استفاده می‌کند.

کاربردها

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

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

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

1

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

2

برای هر بردار هدف در جمعیت، سه بردار متمایز به طور تصادفی انتخاب می‌شوند. یک بردار جهش‌یافته با افزودن تفاوت مقیاس‌بندی شده دو بردار به سومی تشکیل می‌شود: v = x_r1 + F*(x_r2 - x_r3)، که در آن F عامل مقیاس است (معمولاً ۰.۴ تا ۱.۰). این گام مبتنی بر تفاوت چیزی است که DE را از سایر الگوریتم‌های تکاملی متمایز می‌کند و اطلاعات جهت‌دار خودسازگار را بدون نیاز به محاسبه گرادیان فراهم می‌کند.

3

یک بردار آزمایشی با ترکیب بردار جهش‌یافته و بردار هدف اصلی عنصر به عنصر ساخته می‌شود. هر عنصر با احتمال CR (نرخ تقاطع، معمولاً ۰.۵ تا ۱.۰) از جهش‌یافته و در غیر این صورت از هدف گرفته می‌شود؛ حداقل یک عنصر همیشه از جهش‌یافته گرفته می‌شود. این گام تعادل بین اکتشاف و بهره‌برداری را کنترل می‌کند: CR بالا به نفع جهش‌یافته است، CR پایین‌تر بخش بیشتری از راه‌حل فعلی را حفظ می‌کند.

4

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

5

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

دام‌های رایج

  • اجرای DE با تکرارهای بسیار کم (زیر ~۱۰۰۰) رایج‌ترین اشتباه است — الگوریتم نسل‌های کافی برای همگرایی نداشته است و نتیجه باید مقدماتی تلقی شود؛ اگر بودجه ارزیابی محدود است، به بهینه‌سازی بیزی روی آورید.
  • تنظیم عامل مقیاس F بسیار پایین، تنوع را زودتر از موعد از بین می‌برد؛ تنظیم آن بسیار بالا از همگرایی جلوگیری می‌کند. با F در [۰.۴، ۱.۰] شروع کنید و به صورت تجربی تنظیم کنید.
  • حذف یا اشتباه مشخص کردن حدود جستجو یک خطای حیاتی است — DE از حدود برای مقداردهی اولیه جمعیت استفاده می‌کند و اگر حدود بسیار محدود یا غایب باشند، نتایج بی‌معنی تولید خواهد کرد.
  • برخورد با DE به عنوان یک اجرای یک‌باره در چشم‌اندازهای چندوجهی خطرناک است — چندین آزمایش مستقل را با بذرهای تصادفی مختلف اجرا کنید و بهترین راه‌حل یافت شده در طول اجراها را گزارش دهید.

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

چگونه عامل مقیاس F و نرخ تقاطع CR را انتخاب کنم؟

رایج‌ترین مقادیر پیش‌فرض F = 0.8 و CR = 0.9 برای استراتژی DE/best/1/bin هستند. در عمل، F اندازه گام را کنترل می‌کند — مقادیر حدود ۰.۴ تا ۱.۰ معمول هستند — و CR میزان جایگزینی هدف توسط جهش‌یافته را کنترل می‌کند. اگر جمعیت خیلی سریع همگرا می‌شود، F را افزایش دهید یا CR را کاهش دهید. انواع تطبیقی DE (jDE, JADE) این پارامترها را به طور خودکار در طول اجرا تنظیم می‌کنند، که انتخاب معقولی است زمانی که تنظیم دستی غیرعملی است.

چند نسل لازم است؟

به عنوان یک قاعده کلی، حداقل ۱۰۰۰ نسل توصیه می‌شود. برای مسائل با ابعاد بالا (پارامترهای زیاد) یا چشم‌اندازهای پیچیده، تکرارهای بیشتری ممکن است لازم باشد. مقدار هدف بهترین راه‌حل را در طول نسل‌ها مشاهده کنید: اگر برای صدها تکرار تغییر نکرده است، DE احتمالاً همگرا شده است — یا راکد شده است، که در این صورت اجرای مجدد با یک بذر تصادفی تازه توصیه می‌شود.

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

هر سه فراابتکاری مبتنی بر جمعیت برای بهینه‌سازی پیوسته هستند. DE معمولاً پارامترهای کنترلی کمتری نسبت به GAها دارد و یک قانون به‌روزرسانی ساده‌تر و قطعی‌تر در مقایسه با PSO دارد. در بسیاری از معیارهای استاندارد، DE با هر دو رقابتی است یا از آنها بهتر عمل می‌کند، اما عملکرد وابسته به مسئله است. انتخاب اغلب به آشنایی و پیاده‌سازی‌های موجود بستگی دارد تا یک رتبه‌بندی جهانی.

آیا DE می‌تواند پارامترهای صحیح یا طبقه‌ای را مدیریت کند؟

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

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

منابع

  1. Storn, R. & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341–359.

    باز کردن مرجع DOI
    کپی شد.
  2. Das, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution – An updated survey. Swarm and Evolutionary Computation, 27, 1–30.

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