معرفی الگوریتم تکامل دیفرانسیل (Differential Evolution)

این الگوریتم یکی از روش‌های محاسبه توابع حقیقی (Real value) با استفاده از استراتژی‌های تکاملی است.
روند تکامل در این الگوریتم مبتنی بر ایجاد بهبود تدریجی و مستمر در حدس اولیه (پاسخ کاندید) بوده و طبق اصول تمامی الگوریتم‌های رده تکاملی، به یک تابع برازندگی (Fitness function) جهت مقایسه پاسخها نیاز داریم.

نقطه قوت الگوریتم
DE در مقایسه با روشهای حل معادلات حقیقی دیگر (مانند روشهای نیوتن)، عدم نیاز آن به گرادیان یا شیب تابع است. در نتیجه با استفاده از این الگوریتم، بدون وجود هر گونه اطلاعاتی در مورد نوع تابع میتوان به محاسبه یک پاسخ نسبتا بهینه برای انواع توابع چند بعدی پیوسته/غیر پیوسته، متغیر زمانی و نامنظم امیدوار بود.
مراحل الگوریتم Differential Evolution به صورت زیر است: 

  1. تولید جمعیت اولیه از پاسخهای کاندید. هر پاسخ کاندید، یک بردار از اعداد حقیقی به تعداد ابعاد مسئله (پارامترهای مجهول) می‌باشد.
  1. به ازای هر پاسخ کاندید X، سه پاسخ متمایز a, b, c را از جمعیت انتخاب می‌نماییم.
  1. تعیین پارامتر تصادفی R، در محدوده  1 و ابعاد مسئله.
  1. محاسبه پاسخ بهبود یافته Y به این صورت که به ازای هر بعد X(i) از X، در صورت برابر بودن R با i و یا برآورده شدن احتمال ترکیب p(i)، از فرمول برآورد Y(i) = a(i) + F*(b(i) – c(i)) برای محاسبه بعد y(i) استفاده می‌نماییم. در غیر اینصورت خود X(i) به Y(i) انتصاب داده می‌شود.
  1. پذیرش پاسخ جدید Y، در صورتی که برازندگی آن از X بیشتر باشد.
  1. تکرار مراحل 2 تا 5 تا زمان تحقق شرط خاتمه.

لازم به ذکر است که پارامتر
CR همان احتمال ترکیب است (مانند ژنتیک) و p(i) نیز شانس تحقق ترکیب برای هر بعد از پاسخ می‌باشد. مقدار F نیز یک مقدار صحیح و ثابت می‌باشد که با توجه به نوع مسئله انتخاب می‌گردد. (البته شیوه انتخاب مقداری مناسب برای F خود ماجرایی دارد)

همانطور که می‌بینید این الگوریتم شباهت زیادی به
Simulated Annealing دارد، با این تفاوت که صرفا برای محاسبه توابع حقیقی طراحی شده است.

About محمد شمس

برنامه‌نویس، طراح انیمیشن و علاقمند به هوش مصنوعی

4 Comments

  1. اگر کد این الگوریتم رو دارید ممنون میشم برام بفرستید
    mereka7702@yahoo.com

  2. الگوریتم آن در لینک ویکیپدیا موجود است

  3. salam, khaste nabashid age emkanesh hast daliel bartari DE nesbat be sayer ravesh haro tozih midahaid

پاسخ دادن به Mohammad Shams لغو پاسخ

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *


× 1 = 1