خوارزمية التطور التفاضلي، الخوارزمية المستوحاة من نظرية التطور!

خوارزمية التطور التفاضلي أو Differential Evolution، هي مقاربة حدسية heuristic approach للتحسين الأمثل global optimization. هدفها هو إيجاد الحل الأمثل للدالة الهدف، أي القيمة الدنيا لدالة التكلفة، غير الخطية و غير القابلة للاشتقاق في فضاء البحث المعرفة فيه.

تنتمي خوارزمية التطور التفاضلي لعائلة كبيرة من خوارزميات الحوسبة التطورية evolutionary computing algorithms. فمثل عدد من طرق البحث المباشرة المعروفة، مثل الخوارزميات الجينية والاستراتيجيات التطورية، تُسْتهل خوارزمية التطور التفاضلي هي الأخرى بساكنة بدئية، من عدد من الحلول المحتملة. وبالتكرار، يتم تحسين هذه الحلول المحتملة. فتحدث طفرات وانتقاء الأصلح بين الناتج، أي الأفراد الذين يحققون أدنى قيم دالة التكلفة في محاكاة واضحة لآليات التطور البيولوجي.

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

أصل ومقارنة

طوّر خوارزمية التطور التفاضلي كلا من رينر ستورن R. Storn و كينيث برايس K. Price بين سنتي 1996 و1997. حيث قاما بنشر مجموعة من الأوراق البحثية عنها خلال هاتين السنتين، وهو ما توجاه بعدها بكتابهما “Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces”، ومعناه “التطور التفاضلي: حدسية بسيطة وفعالة للتحسين الأمثل في الفضاءات المستمرة.”

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

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

ألية عمل خوارزمية التطور التفاضلي

معايير الفاعلية

لاعتبار خوارزمية تقليصية ما عملية يتوجب تحقيقها لعدد من الشروط، وهي:

• القدرة على التعامل مع المشاكل ذات الدوال الهدف غير القابلة للاشتقاق. والمشاكل متعددة الأطوار، أي متعددة الحلول المحلية.
• التمكن من التعامل مع الدوال الهدف المكلفة حوسبيًا computation intensive.
• سهولة الاستعمال، أي قلة وسهولة وضع معلمات الضبط.
• توافرها على خصائص تقارب جيدة، أي تماسك قدرتها على التقارب للحل الأمثل في تجارب مستقلة متوالية.

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

الساكنة البدئية

لمعالجة مشكل تحسيني متعدد الأبعاد، عدد أبعاده d، تقوم الخوارزمية أولا بتوليد n حل محتمل. هذه الحلول متوزعة بشكل عشوائي على فضاء البحث المدروس، و نعبر عنها بمتجهات.

كما الخوارزميات الجينية يمكن اعتبار كل فرد من أفراد ساكنة أي جيل مجموعة من الكروموسومات أو الجينات.

العمليات الأساسية في التطور التفاضلي

نجد أن خوارزمية التطور التفاضلي تتكون من ثلاث عمليات أساسية: التطفر mutation، والتقاطع crossover، والانتقاء selection.

التطفر

يتم تنفيذ هذه العملية اعتمادًا على ما يسمى بمخطط التطفر mutation scheme. بحيث لكل متجهة Xi في أي وقت أو جيل، ونقوم باختيار ثلاث متجهات عشوائية أخرى Xp، و Xq، و Xr من نفس الجيل ونقوم بواسطتها بتوليد متجهة مانحة donor vector، كما توضح الصيغة التالية:

نجد أنه من الضروري توفير على الأقل على أربع أفراد ساكنة من أجل توليد المتجهة المانحة donor vector. مبدئيا نجد أن F محصورة بين 0 و 2، لكن عمليا يجب حصرها بين 0 و 1 من أجل فاعلية أعلى.

التقاطع

يُتحكم في التقاطع بواسطة المعامل Cr والذي يسمى بمعامل التقاطع. وهذا الأخير محصور بين 0 و 1. وبالتالي يتحكم في احتمالات التقاطع.
وتوجد طريقتين مختلفتين لتحقيق التقاطع. الطريقة الزوجية والطريقة الأسية.

تقوم الطريقة الزوجية على تحقيق التقاطع ببن كل أفراد ساكنة الجيل الحالي وذلك بتوليد عدد عشوائي ri محصور بين 0 و 1. هذا العدد يتحكم فيما إن كانت المتجهة الناتجة ستأخد مكون من مكونات المتجهة المانحة Vi أو المتجهة Xi، كما توضح المعادلة التالية:

في المخطط الأسي نقوم باختيار مقطع من المتجهة يتكون من عدد من المكونات المتتالية يبدأ عشوائيًا من المكون k ويستمر إلي المكون k+L بحيث L تمثل طول هذه القطعة.

الانتقاء

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