خوارزمية التطور التفاضلي أو 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. وهو الشيء الذي يجعلها مشابهة لخوارزميات مثل الخوارزميات الجينية و خوارزميات البحث عن الأنماط.
ولا يقتصر هذا على تشابه فقط، إذ يمكننا اعتبار خوارزمية التطور التفاضلي بديلاً محسنًا للخوارزميات الجينية. بحيث تستعمل هذه الأخيرة معادلات محددة لتحديث الساكنة، ما يمكننا من دراسة هذه الخوارزميات دراسة نظرية.
لاعتبار خوارزمية تقليصية ما عملية يتوجب تحقيقها لعدد من الشروط، وهي:
وتستمد خوارزمية التطور التفاضلي قوتها من حقيقة أنها صممت لتلبية هذه الشروط بالضبط. ما يجعلها أحد أقوى خوارزميات التحسين التطورية وأكثرها تنوعًا ضد المشاكل المستمرة.
لمعالجة مشكل تحسيني متعدد الأبعاد، عدد أبعاده 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 تمثل طول هذه القطعة.
تتم هذه العملية بنفس طريقة نظيرتها في الخوارزميات الجينية. بحيث يتم ببساطة اختيار الأصلح بين الفرد و خلفه، أي الفرد الذي يحقق القيمة الأدنى لدالة التكلفة بينهما، مثل ما هو موضح في الصيغة التالية:
ارتكزت أغلب الدراسات على اختيار المعلمات F، و Cr، و n، وكذلك معادلة التطفر. ففي الحقيقة يمكننا توليد متجهات التطفر بطرق عديدة ومختلفة، ما يأخدنا لوضع مخططات تطفر مختلفة باصطلاح التسمية DE/x/y/z. فتمثل DE اختصارًا لاسم الخوارزمية بالإنجليزية Differential Evolution. كما تمثل x كيفية اختيارنا للمتجهة التي نحورها، ويكون هذا الاختيار إما عشوائيًا rand أو اختيار الأفضل best. وتعبر y عن عدد متجهات الفرق. و z عن خطة التقاطع إما زوجية bin أو أسية exp.
ما يعني أن */DE/Rand/1 هي الخطة الأساسية والتي تتكون من اختيار عشوائي للمتجهة التي سنحورها Rand، و متجهة فرق واحدة 1، مع مخطط زوجي أو أسي *.
بحيث تمثل DE/Rand/1/Bin معادلة التطفر:
عند استبدال Xp ب Xbest نجد أن معادلة التطفر أصبحت على شكل:
كما أنه لايوجد سبب يمنعنا من استعمال أكثر من متجهة فرق واحدة. فباستعمال متجهتين والحل الأفضل في الجيل الحالي نجد:
وباختيار حل عشوائي ومتجهتين نجد:
يمكننا بالطبع أخد F1 = F2 إن أردنا تبسيط المعادلة. فباتباع نفس النهج يمكن تعميم هذه المتحورات باستعمال معادلة واحدة:
يعتبر اختيار معلمات الضبط أمر جد مهم. بحيث أثبتت كل من الملاحظات التجريبية والدراسات البارامترية أن هذا الضبط يجب أن يتم بشكل مدروس من أجل تحقيق نتائج جيدة. ونجد أن عامل القياس F هو الأكثر حساسية، فرغم كون النظرية تتيح اختياره بين 0 و 2 نجد أن التجربة تحتم اختياره بين 0 و 1 وذلك من أجل الحصول على استقرار مناسب وكفاءة في التنفيذ. بالتجربة والخطأ تم التوصل إلي أن القيم الأفضل هي بين 0.4 و 0.95، و القيمة البدئية الملائمة هي بين 0.7 و 0.9.
يمكن اختيار معامل التقاطع Cr بين 0.1 و 0.8 مع 0.5 قيمة بدئية مناسبة. كما من الأفضل اختيار حجم الساكنة بالاعتماد على عدد أبعاد الفضاء المدروس. ففي فضاء ذو d بعد اختيار حجم ساكنة بدئي بين 5d و 10d مناسب جدا. قد يعد هذا مشكلا بالنسبة للمسائل ذات فضاءات البحث ذات أبعاد كثيرة ما يعني أنه لا مشكل في استخدام حجم ساكنة مستقل أولا من أجل اختبار الأداء.
لا تزال أفكار نيتشه الفلسفية يتردد صداها في المجتمع المعاصر، وتتحدى فهمنا للأخلاق ومكانتها في…
تخيل فريقًا من العلماء الرواد يعملون بلا كلل لكشف أسرار الدماغ البشري. إنهم في سعيهم…
في عالم وسائل التواصل الاجتماعي، تظهر الصيحات وتختفي، لكن بعضها يجعلك تتساءل: ما السبب وراء…
الصداع تجربة إنسانية عالمية، وعلى الرغم من انتشاره إلا أن الأسباب الكامنة وراءه لا تزال…
إن فهم كيف بدأت الحياة وتطورت على الأرض هو السؤال الذي أذهل البشر على مر…
يصادف في شهر أغسطس الذكرى السنوية الثالثة لانسحاب الولايات المتحدة من أفغانستان وعودة طالبان إلى…