تکامل تفاضلی

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

 

استورن و پرایس DE را در دهه 1990 معرفی کردند.[2][3] کتاب‌هایی در مورد جنبه‌های نظری و عملی استفاده از DE در محاسبات موازی، بهینه‌سازی چندهدفه، بهینه‌سازی محدود منتشر شده‌اند، و کتاب‌ها همچنین شامل بررسی‌هایی از حوزه‌های کاربردی هستند.[4][5][6][7] نظرسنجی در مورد جنبه‌های تحقیقاتی چند وجهی DE را می‌توان در مقالات مجلات یافت.[8][9]

الگوریتم

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

به طور رسمی، اجازه دهید f : ℝⁿ → ℝ  تابع برازش است که باید حداقل شود (توجه داشته باشید که حداکثر کردن را می‌توان با در نظر گرفتن تابع h := -f به جای آن انجام داد). تابع یک راه‌حل کاندید را به عنوان آرگومان در قالب بردار اعداد حقیقی می‌گیرد. یک عدد واقعی را به عنوان خروجی تولید می‌کند که برازش راه‌حل نامزد داده شده را نشان می‌دهد. گرادیان از f شناخته نشده است. هدف یافتن راه‌حل m است که f(m) ≤  f(p)  برای همه p در فضای جستجو، که m به این معنی حداقل سراسری است.

اجازه دهید x ∈ ℝⁿ یک راه‌حل (عامل) نامزد را در جمعیت تعیین کنید. سپس الگوریتم پایه DE را می توان به صورت زیر توصیف کرد:

·         پارامترها را انتخاب کنید NP ≥ 4, CR ∈ [0, 1] و F ∈ [0,2].

§         NP اندازه جمعیت است، یعنی تعداد نمایندگان نامزد یا "والدین"؛ یک تنظیم معمولی 10n است

§         پارامتر CR ∈ [0, 1] احتمال متقاطع نامیده می‌شود و پارامتر F ∈ [0,2] وزن تفاضل نامیده می‌شود. تنظیمات معمولی CR = 0.9 و F = 0.8 هستند.

§         عملکرد بهینه‌سازی ممکن است تا حد زیادی تحت تاثیر این انتخاب‌ها باشد. زیر را ببینید.

·         همه عوامل x با موقعیت‌های تصادفی در فضای جستجو مقدار دهی اولیه کنید.

·         تا زمانی که یک معیار خاتمه برآورده شود (مثلاً تعداد تکرارهای انجام شده یا رسیدن به تناسب کافی)، موارد زیر را تکرار کنید:

§         برای هر عامل x در جمعیت انجام دهید:

o       سه عاملa، b و c را از جمعیت به طور تصادفی انتخاب کنید، آنها باید از یکدیگر و همچنین x از عامل متمایز باشند. (a بردار "پایه" نامیده می‌شود.)

o       یک شاخص تصادفی R ∈ {1, …, n} انتخاب کنید که در آن n ابعاد مسئله در حال بهینه‌سازی است.

o       موقعیت بالقوه جدید عامل را محاسبه کنید y = [y₁, …, y_n] به شرح زیر:

§         برای هر i ∈ {1, …, n}، یک عدد تصادفی توزیع شده یکنواخت را انتخاب کنید

§         اگر r_i < CR یا i = R سپس تنظیم کنید و در غیر این صورت y_i = x_i تنظیم می شود (موقعیت شاخصR به طور قطع جایگزین می‌شود.)

o       اگر f(y) ≤ f(x) سپس عامل x را جایگزین کنید در جمعیت با راه‌حل کاندید بهبودیافته یا برابر را جایگزین کنید.

§         عاملی را از بین جمعیتی که بهترین برازش را دارد انتخاب کنید و آن را به عنوان بهترین راه‌حل کاندید پیدا شده برگردانید.

انتخاب پارامتر

انتخاب پارامترهای DE NP، CR و F می تواند تأثیر زیادی بر عملکرد بهینه‌سازی داشته باشد. بنابراین انتخاب پارامترهای DE که عملکرد خوبی دارند موضوع تحقیقات زیادی بوده است. قوانین سرانگشتی برای انتخاب پارامتر توسط استورن و همکاران ابداع شد.[3][4] و لیو و لامپینن.[10] تجزیه و تحلیل همگرایی ریاضی در مورد انتخاب پارامتر توسط زهاری انجام شد.[11]

مدیریت محدودیت

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

f^~(x) = f(x) + ρ × CV(x)

 اینجا CV(x)، یا نقض محدودیت (جریمه L1) یا مربع نقض محدودیت (جریمه L2) را نشان می‌دهد.

اما این روش دارای معایب خاصی است. یکی از چالش های مهم انتخاب مناسب ρ ضریب جریمه است اگر ρ خیلی پایین تنظیم شده است، ممکن است به طور موثر محدودیت‌ها را اعمال نکند. برعکس، اگر خیلی زیاد باشد، می‌تواند روند همگرایی را تا حد زیادی کند کرده یا حتی متوقف کند. علیرغم این چالش‌ها، این رویکرد به دلیل سادگی و عدم نیاز به تغییر خود الگوریتم تکامل تفاضلی، همچنان به طور گسترده مورد استفاده قرار می‌گیرد. استراتژی‌های جایگزینی وجود دارد، مانند طرح‌ریزی بر روی یک مجموعه امکان‌پذیر یا کاهش ابعاد، که می‌تواند برای موارد محدود شده با جعبه یا محدودیت خطی استفاده شود. با این حال، در زمینه محدودیت‌های غیرخطی عمومی، مطمئن‌ترین روش‌ها معمولاً شامل توابع جریمه هستند. انواع الگوریتم DE به طور مداوم در تلاش برای بهبود عملکرد بهینه‌سازی در حال توسعه هستند. بسیاری از طرح‌های مختلف برای انجام متقاطع و جهش عوامل در الگوریتم اصلی ارائه شده در بالا امکان‌پذیر است [3].

منابع

Rocca, P.; Oliveri, G.; Massa, A. (2011). "Differential Evolution as Applied to Electromagnetics". IEEE Antennas and Propagation Magazine. 53 (1): 38–49. doi:10.1109/MAP.2011.5773566. S2CID 27555808.

 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:10.1023/A:1008202821328. S2CID 5297867.

 Storn, R. (1996). "On the usage of differential evolution for function optimization". Biennial Conference of the North American Fuzzy Information Processing Society (NAFIPS). pp. 519–523. doi:10.1109/NAFIPS.1996.534789. S2CID 16576915.

 Price, K.; Storn, R.M.; Lampinen, J.A. (2005). Differential Evolution: A Practical Approach to Global Optimization. Springer. ISBN 978-3-540-20950-8.

 Feoktistov, V. (2006). Differential Evolution: In Search of Solutions. Springer. ISBN 978-0-387-36895-5.

 G. C. Onwubolu and B V Babu, "New Optimization Techniques in Engineering". Retrieved 17 September 2016.

 Chakraborty, U.K., ed. (2008), Advances in Differential Evolution, Springer, ISBN 978-3-540-68827-3

 S. Das and P. N. Suganthan, "Differential Evolution: A Survey of the State-of-the-art", IEEE Trans. on Evolutionary Computation, Vol. 15, No. 1, pp. 4-31, Feb. 2011, DOI: 10.1109/TEVC.2010.2059031.

 S. Das, S. S. Mullick, P. N. Suganthan, "Recent Advances in Differential Evolution - An Updated Survey," Swarm and Evolutionary Computation, doi:10.1016/j.swevo.2016.01.004, 2016.

 Liu, J.; Lampinen, J. (2002). "On setting the control parameter of the differential evolution method". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 11–18.

 Zaharie, D. (2002). "Critical values for the control parameters of differential evolution algorithms". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 62–67.