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

الگوریتم تکاملی تفاضلی یا الگوریتم DE یک الگوریتم بهینه سازی است که اولین بار در سال 1995 توسط Rainer Storn و Kenneth Price معرفی شد. این محققان در مقاله ای تحت عنوان Differential Evolution a Practical Approach to Global Optimization نشان دادند که این الگوریتم توانایی خوبی در بهینه سازی توابع غیرخطی مشتق ناپذیر دارد که به عنوان روشی قدرتمند و سریع برای مسائل بهینه سازی در فضاهای پیوسته معرفی شده است.

 

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

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

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

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

الگوریتم تکاملی تفاضلی - Differential Eevolution Algorithm

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

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

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

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

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

الگوریتم DE

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

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

 

محصولات مرتبط

مطالب زیر را حتما بخوانید

پاسخی بگذارید

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

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.