الگوریتم DE

امروزه با پیشرفت تکنولوژی در همه ی علوم از جمله علوم مهندسی و در نتیجه بزرگتر و پیچیده تر شدن مسائل سبب شده است روشهای بینه سازی کلاسیک با توجه به اهمیت زمان و دقت دیگر قادر به حل مسائلی با ابعاد بزرگ نباشند.در علوم مهندسی اکثر مسائل دارای تابع هدف غیر خطی همراه با معادلات دیفرانسیل غیر خطی و به صورت گسسته یا پیوسته هستند و در نتیجه هر چه ابعاد مسائل بزرگتر باشد روشهای مستقیم برنامه ریزی غیر خطی و جستجوی همه جانبه نیازمند زمان و هزینه ی بیشتری است و ممکن است حتی به جواب نرسند یا به بهینه محلی همگرا شود. به همین دلیل استفاده از الگوریتم های تکاملی روز به روز بیشتر می شود. این الگوریتم ها می توانند هم در زمان صرفه جویی کنند و هم با استفاده از تدابیری خاص از بهینه های محلی بگریزند و به بهینه ی سراسری همگرا شوند.

با بزرگ شدن مسائل و اهمیت یافتن سرعت رسیدن به پاسخ و عدم پاسخگویی روشهای کلاسیک ،امروزه از الگوریتمهای جستجوی رندوم به جای جستجوی همه جانبه[1] فضای مسئله ، استقبال بیشتری می شود. در این بین در سالهای اخیر استفاده از الگوریتمهای جستجوی هیوریستیک (شهودی) همچون الگوریتم وراثتی(GA)[2] ، الگوریتم کلونی مورچه ها(ACO)[3] ، الگوریتم پرندگان(PSO) [4] و ... رشد چشمگیری داشته است. الگوریتم جستجوی DE[5] یکی از جدیدترین روشهای جستجو است

فرضیه سیر الگوریتم تکاملی تفاضلی برخواسته از تلاشهای Kenneth V.Price در زمینه حل مسأله تطبیق چند جمله ای chebychev است که توسط Rainer Storn مطرح شد و الگوریتم تکاملی تفاضلی در سال 1996 ارائه گردید. الگوریتم جستجوی DE یکی از جدیدترین تکنیک بهینه سازی مبتنی بر قوانین احتمال است . اساس کار DE بر مبنای عملیات ( جمع ، تفریق ، ضرب و ... ) بدون استفاده از مشتق بر روی بردار هاست که این بردارها فاصله ی بین نقطه ای از فضای جستجو و مبدأ خاصی است. این الگوریتم ماهیت پیوسته دارد و در کارهای متعدد کارآیی خود را ثابت کرده است. امروزه این الگوریتم در بسیاری از کاربردها استفاده می شود]3[. الگوریتم DE ذاتاً یک الگوریتم پیوسته است. برای حل مسائل گسسته نسخه باینری آن نیز ارائه شده است. DE جمعیتی متشکل از یک سری ذرات تشکیل می دهد که هر ذره معرف یک جواب مسئله در فضای جستجو است وDE با به روز[6] کردن موقعیت[7] ذرات با توجه به میزان شایستگی جمعیت[8] را به سمت جواب بهینه[9] هدایت می کند.



مروری بر الگوریتم DE



اکثر تکنیکهای تکاملی روند زیر را دنبال می کنند:

1- شروع بکار با یک جمعیت تصادفی اولیه

2- محاسبه مقدار شایستگی برای هر جزء

3- تولید جمعیت جدید براساس شایستگی

4-اگر نیاز برآورده نشده باشد همین روند را از مرحله 2 تکرار می شود.



مراحل عملکرد الگوریتمDE بصورت ذیل می باشد:



الف- ایجاد جمعیت اولیه ) Population (: الگوریتم DE با ایجاد جمعیت اولیه شروع می شود که دارایNP سطر و D ستون می باشد.

ب- جهش ( Mutation ): در این مرحله یک بردار نوزاد برای هر والد تولید می گردد.

ج- انطباق) Mapping یا Boundary check (: در این مرحله در صورت لزوم بردار نوزاد بایستی در بازه (umin, umax) منطبق گردد.

د- همبری (Crossover) : در این مرحله بردار جهش یافته و بردار جمعیت اولیه ، بردارهای آزمایشی را تولید می کنند.

ه- انتخاب(Selection): در این مرحله نوزاد تولید شده با والد مورد مقایسه قرار می گیرد و جمعیت نسل بعد بوجود می آید . بعد از مرحله انتخاب سیکل محاسبات در DE تا زمان همگرایی کل بردارها یا وقوع شرط توقف ادامه می یابد .




--------------------------------------------------------------------------------

[1] Exhaustive search

[2] Genetic Algorithm(GA)

[3] Ant Colony Optimization(ACO)

[4] Particle Swarm Optimization(PSO)

[5] Differential evolution

[6] Up to date

[7] Position

[8] population

[9] Optimum Solution

. "Differential Evolution - A Practical Approach to Global Optimization" by Ken Price, Rainer Storn, and Jouni Lampinen (Springer, ISBN: 3-540-20950-6)