التطور التفاضلي

التطور التفاضلي ( DE ) هو خوارزمية تطورية لتحسين حل مشكلة ما من خلال محاولة تحسين حل مرشح بشكل متكرر وفقًا لمقياس جودة محدد. تُعرف هذه الأساليب عادةً باسم الخوارزميات فوق الحدسية ، لأنها لا تفترض إلا القليل من الافتراضات أو لا تفترض أي افتراضات على الإطلاق حول المشكلة المُحسَّنة، ويمكنها البحث في مساحات واسعة جدًا من الحلول المرشحة. مع ذلك، لا تضمن الخوارزميات فوق الحدسية، مثل التطور التفاضلي، إيجاد حل أمثل على الإطلاق.

تُستخدم خوارزمية التطور التفاضلي (DE) للدوال الحقيقية متعددة الأبعاد ، لكنها لا تستخدم تدرج المسألة المراد تحسينها، مما يعني أنها لا تتطلب أن تكون مسألة التحسين قابلة للتفاضل ، كما هو الحال في طرق التحسين التقليدية مثل انحدار التدرج وطرق شبه نيوتن . لذا، يمكن استخدام خوارزمية التطور التفاضلي أيضًا في مسائل التحسين غير المتصلة ، أو التي تتسم بالتشويش، أو التي تتغير بمرور الوقت، وما إلى ذلك. ^{[ 1 ]}

تعمل خوارزمية التطور التفاضلي (DE) على تحسين المسألة من خلال الاحتفاظ بمجموعة من الحلول المرشحة، وإنشاء حلول مرشحة جديدة بدمج الحلول الموجودة وفقًا لصيغها البسيطة، ثم الاحتفاظ بالحل المرشح الذي يحقق أفضل نتيجة أو أعلى مستوى ملاءمة في مسألة التحسين المطروحة. وبهذه الطريقة، تُعامل مسألة التحسين كصندوق أسود يوفر فقط مقياسًا للجودة بناءً على الحل المرشح، وبالتالي لا حاجة إلى حساب التدرج.

قدّم ستورن وبرايس خوارزمية التطور التفاضلي عام ١٩٩٥. ^{[ ٢ ] [ ٣ ] [ ٤ ]} نُشرت كتبٌ تتناول الجوانب النظرية والعملية لاستخدام هذه الخوارزمية في الحوسبة المتوازية ، والتحسين متعدد الأهداف ، والتحسين المقيد ، كما تتضمن هذه الكتب دراساتٍ استقصائيةً لمجالات التطبيق. ^{[ ٥ ] [ ٦ ] [ ٧ ] [ ٨ ]} ويمكن الاطلاع على دراساتٍ استقصائيةٍ حول الجوانب البحثية المتعددة الأوجه لخوارزمية التطور التفاضلي في مقالاتٍ منشورةٍ في المجلات العلمية. ^{[ ٩ ] [ ١٠ ]}

تعتمد إحدى الصيغ الأساسية لخوارزمية التطور التفاضلي على مجموعة من الحلول المرشحة (تُسمى العوامل). تُنقل هذه العوامل في فضاء البحث باستخدام معادلات رياضية بسيطة لدمج مواقع العوامل الموجودة في المجموعة. إذا كان الموقع الجديد لعامل ما يُحسّن الحل الحالي، يُقبل ويُضاف إلى المجموعة، وإلا يُستبعد. تُكرر هذه العملية، ويُؤمل، وإن لم يكن مضمونًا، التوصل في النهاية إلى حل مُرضٍ.

بصورة رسمية، دع${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$لتكن دالة اللياقة التي يجب تصغيرها (لاحظ أنه يمكن إجراء التعظيم من خلال النظر في الدالة${\displaystyle h:=-f}$بدلاً من ذلك). تأخذ الدالة حلاً مرشحاً كوسيط على شكل متجه من الأعداد الحقيقية . وتُنتج عدداً حقيقياً كناتج يُشير إلى مدى ملاءمة الحل المرشح المُعطى . تدرج${\displaystyle f}$غير معروف. الهدف هو إيجاد حل${\displaystyle \mathbf {m} }$والتي${\displaystyle f(\mathbf {m} )\leq f(\mathbf {p} )}$للجميع${\displaystyle \mathbf {p} }$في مساحة البحث، مما يعني أن${\displaystyle \mathbf {m} }$هو الحد الأدنى العالمي.

يترك${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$يتم تحديد حل مرشح (عامل) ضمن المجموعة. ويمكن وصف خوارزمية التطور التفاضلي الأساسية على النحو التالي:

• اختر المعلمات${\displaystyle {\text{NP}}\geq 4}$،${\displaystyle {\text{CR}}\in [0,1]}$، و${\displaystyle F\in [0,2]}$.
  • NP  :${\displaystyle {\text{NP}}}$حجم السكان، أي عدد العملاء المرشحين أو "الآباء".
  • CR  : المعامل${\displaystyle {\text{CR}}\in [0,1]}$يُطلق عليه اسم احتمال التقاطع .
  • F  : المعامل${\displaystyle F\in [0,2]}$يُطلق عليه الوزن التفاضلي .
  • الإعدادات النموذجية هي${\displaystyle NP=10n}$،${\displaystyle CR=0.9}$و${\displaystyle F=0.8}$.
  • قد تتأثر كفاءة التحسين بشكل كبير بهذه الخيارات؛ انظر أدناه.
• تهيئة جميع الوكلاء${\displaystyle \mathbf {x} }$بمواقع عشوائية في مساحة البحث.
• إلى حين استيفاء معيار الإنهاء (مثل عدد التكرارات التي تم إجراؤها، أو الوصول إلى مستوى لياقة كافٍ)، كرر ما يلي:
  • لكل وكيل${\displaystyle \mathbf {x} }$في السكان يفعلون:
    • اختر ثلاثة عملاء${\displaystyle \mathbf {a} ,\mathbf {b} }$، و${\displaystyle \mathbf {c} }$من بين السكان بشكل عشوائي، يجب أن يكونوا متميزين عن بعضهم البعض وكذلك عن العامل${\displaystyle \mathbf {x} }$. (${\displaystyle \mathbf {a} }$يُطلق عليه اسم متجه "الأساس".
    • اختر فهرسًا عشوائيًا${\displaystyle R\in \{1,\ldots ,n\}}$أين${\displaystyle n}$هو بُعد المشكلة التي يتم تحسينها.
    • احسب الوضع الجديد المحتمل للوكيل${\displaystyle \mathbf {y} =[y_{1},\ldots ,y_{n}]}$على النحو التالي:
      • لكل${\displaystyle i\in \{1,\ldots ,n\}}$اختر رقمًا عشوائيًا موزعًا بشكل منتظم${\displaystyle r_{i}\sim U(0,1)}$
      • لو${\displaystyle r_{i}<CR}$أو${\displaystyle i=R}$ثم اضبط${\displaystyle y_{i}=a_{i}+F\times (b_{i}-c_{i})}$وإلا يتم تعيينه${\displaystyle y_{i}=x_{i}}$(موضع الفهرس)${\displaystyle R}$يتم استبدالها بالتأكيد.)
    • لو${\displaystyle f(\mathbf {y} )\leq f(\mathbf {x} )}$ثم استبدل الوكيل${\displaystyle \mathbf {x} }$في المجموعة السكانية التي لديها الحل المرشح المحسن أو المكافئ${\displaystyle \mathbf {y} }$.
• اختر العامل من بين المجموعة الذي يتمتع بأفضل لياقة وأعده كأفضل حل مرشح تم العثور عليه.

اختيار معلمات DE${\displaystyle {\text{NP}}}$،${\displaystyle {\text{CR}}}$و${\displaystyle F}$يمكن أن يكون لاختيار معلمات الخوارزمية التفاضلية التي تُحقق أداءً جيدًا تأثير كبير على أداء التحسين. ولذلك، كان اختيار هذه المعلمات موضوعًا للعديد من الأبحاث. وقد وضع ستورن وآخرون ^{[ 4 ] [ 5 ]} وليو ولامبينين ^{[ 11 ]} قواعد عامة لاختيار المعلمات. كما أجرى زاهاري ^{[ 12 ] تحليلًا رياضيًا للتقارب فيما يتعلق باختيار المعلمات.}

يمكن استخدام التطور التفاضلي لتحسين القيود أيضًا. تتضمن إحدى الطرق الشائعة تعديل دالة الهدف لتشمل عقوبة على أي انتهاك للقيود، ويتم التعبير عنها على النحو التالي:${\displaystyle f{\tilde {(}}x)=f(x)+\rho \times \mathrm {CV} (x)}$. هنا،${\displaystyle \mathrm {CV} (x)}$يمثل إما انتهاكًا للقيد (عقوبة L1) أو مربع انتهاك القيد (عقوبة L2).

إلا أن هذه الطريقة تنطوي على بعض العيوب. يتمثل أحد التحديات الرئيسية في الاختيار المناسب لمعامل الجزاء.${\displaystyle \rho }$. لو${\displaystyle \rho }$إذا تم ضبط قيمة منخفضة جدًا، فقد لا يتم تطبيق القيود بفعالية. وعلى العكس، إذا تم ضبطها على قيمة عالية جدًا، فقد يؤدي ذلك إلى إبطاء عملية التقارب بشكل كبير أو حتى إيقافها تمامًا. على الرغم من هذه التحديات، لا يزال هذا النهج شائع الاستخدام نظرًا لبساطته ولأنه لا يتطلب تعديل خوارزمية التطور التفاضلي نفسها.

توجد استراتيجيات بديلة، مثل الإسقاط على مجموعة ممكنة أو تقليل الأبعاد، والتي يمكن استخدامها في حالات القيود الصندوقية أو القيود الخطية. مع ذلك، في سياق القيود غير الخطية العامة، تتضمن الطرق الأكثر موثوقية عادةً دوال الجزاء.

يجري تطوير نسخ مختلفة من خوارزمية التطور التفاضلي باستمرار في محاولة لتحسين أداء التحسين. ^{[ 13 ]} ويمكن تلخيص اتجاهات التطوير التالية:

• مخططات جديدة لإجراء التزاوج والتحول بين العوامل ^{[ 4 ]}
• استراتيجيات متنوعة للتعامل مع القيود
• استراتيجيات تكيفية تعمل على تعديل حجم السكان ومعاملات F و CR بشكل ديناميكي
• خوارزميات متخصصة لتحسين العمليات على نطاق واسع
• الخوارزميات متعددة الأهداف والخوارزميات ذات الأهداف المتعددة
• تقنيات التعامل مع المتغيرات الثنائية/الصحيحة

• خوارزمية مستعمرة النحل الاصطناعية
• CMA-ES
• استراتيجية التطور
• الخوارزمية الجينية