الگوریتم تکاملی تفاضلی – Differential Evolution Algorithm

معرفی الگوریتم تکاملی تفاضلی

الگوریتم DE جهت غلبه بر عیب اصلی الگوریتم ژنتیک، یعنی نبود جستجوی محلی در این الگوریتم ارائه شده است، تفاوت اصلی بین الگوریتم‌های ژنتیک و الگوریتم DE در عملگر انتخاب Selection Operators است. در عملگر انتخاب الگوریتم GA ،شانس انتخاب یک جواب به عنوان یکی از والدین وابسته به مقدار شایستگی آن می‌باشد، اما در الگوریتم DE همه جواب‌ها دارای شانس مساوی جهت انتخاب شدن می‌باشند. یعنی شانس انتخاب شدن، وابسته به مقدار شایستگی آنها نمی‌باشد، پس از این که یک جواب جدید با استفاده از یک عملگر جهش mutation و عملگر crossover تولید شد، جواب جدید با مقدار قبلی مقایسه می‌شود و در صورت بهتر بودن جایگزین می‌گردد.

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

تولید جمعیت اولیه

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

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

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

شبه کد الگوریتم DE

فلوچارت الگوریتم DE

سخن آخر در مورد الگوریتم تکاملی تفاضلی

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