يهدف التحسين optimization في الخوارزميات إلى إيجاد مجموعة من المدخلات للدالة الهدف objective function، ما ينتج عنه قيمة قصوى أو دنيا لهذه الدالة. هذه المشكلة تلخص هدف عدد من خوارزميات الذكاء الاصطناعي، مثل الانحدار اللوجستي logistic regression وتدريب الشبكات العصبية الاصطناعية artificial neural networks. وعلى الأرجح، هناك المئات من الخوارزميات التحسينية المعروفة ومتغيراتها. وكذلك توجد عشرات الخوارزميات التي يمكنك الاختيار منها لحل مشكلتك، في مكتبات الكود البرمجي العلمية المعروفة scientific code libraries. إذاً فمن الصعب معرفة الخوارزمية الأفضل للاستعمال في حل مشكلتك التحسينية.

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

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

الخوارزميات التحسينية

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

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

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

القيم الدنيا والقصوى

بالإنجليزية maxima أي القيمة القصوى، بينما minima هي القيمة الدنيا. تمثل القيمة القصوى الشاملة global maxima أو القيمة الدنيا الشاملة global minima الحل الأمثل global optima الذي نهدف لإيجاده من خلال الخوارزميات التحسينية.
بينما تمثل القيم القصوى المحلية local maxima أو القيم الدنيا المحلية local minima الحلول المحلية المثلى local optima. والمقصود بالمحلية كونها مؤطرة في مجال محدد، أي في هذا النطاق هي الحل الأمثل، أي القيمة الدنيا أو القصوى، لكن خارجه لا تعتبر كذلك.

مفاهيم رياضية مهمة لفهم عملية التحسين

• المشتقة الأولى first-order derivative: الدالة القابلة للاشتقاق هي الدالة التي نستطيع حساب مشتقتها في أي نقطة من نقاط مجالها، أي الفضاء المدروس. فمشتقة الدالة في نقطة هي معدل أو مقدار التغير، تغير الدالة، في تلك النقطة، أو ما يسمى بالميل.
• التدرج gradient: يطلق على مشتقة دالة متعددة المتغيرات بالتدرج. أي دالة بأكثر من متغير واحد. وهذه المشتقة هي عبارة عن متجه. بحيث يمثل كل عنصر من عناصر هذه المتجه مشتقة جزئية للمتغير المكافئ لها.
• المشتقة الجزئية partial derivative: تمثل كذلك معدل أو مقدار التغير في نقطة بدلالة متغير باعتبار كل المتغيرات الأخرى ثابتة.
• المشتقة الثانية second-order derivative: وهي مشتقة المشتقة، بحيث تمثل تغير التغير. أي تغيرُ تغيرِ الدالة الهدف. وهي الأخرى يمكن أن تتواجد في نقطة من الفضاء أو لا، أي يمكن أن تكون المشتقة قابلة للاشتقاق أو غير قابلة.
• المصفوفة الهيسية hessian matrix: لكل دالة متعددة المتغيرات وقابلة للاشتقاق مرتين أو أكثر مصفوفة هيسية تعبر عن قيمة مشتقتها الثانية، والتي يمثل كل عنصر فيها المشتقة الجزئية من الدرجة الثانية لكل متغير.

الدالة الهدف القابلة للاشتقاق

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

خوارزميات التأطير

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

خوارزميات النزول المحلي

وتهدف إلى إيجاد الحل الأمثل فقط، وليس عدد من الحلول المحلية، عند تعدد المتغيرات. والمثال الأبرز لهذا النوع من الخوارزميات هو خوارزمية البحث الخطي line search algorithm والتي بدورها تتوفر على عدد من المتحورات.

خوارزميات الدرجة الأولى

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

يطلق عموما على هذه الخوارزميات، خوارزميات النزول التدرجي gradient descent algorithms. وتوفر خوارزمية النزول التدرجي الكلاسيكية الإطار العام لنظيرتها التصادفية، والمسمات بخوارزمية النزول التدرجي التصادفية stochastic gradient descent algorithm المستعملة في تدريب نماذج الشبكات العصبية الاصطناعية في التعلم العميق.

خوارزميات الدرجة الثانية

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

الدالة الهدف غير القابلة للاشتقاق

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

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

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

الخوارزميات المباشرة

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

• Cyclic Coordinate Search
• Powell’s Method
• Hooke-Jeeves Method
• Nelder-Mead Simplex Search

خوارزميات التحسين التصادفية

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

• التخمير المحاكى simulated annealing.
• الاستراتيجية التطورية evolution strategy.
• خوارزمية الإنتروبيا cross-entropy method.

خوارزميات الساكنة

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

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

• الخوارزميات الجينية genetic algorithms.
• خوارزمية التطور التفاضلي differential evolution.
• خوارزمية استمثال عناصر السرب particle swarm optimization.

المصادر

1. ScienceDirect
2. Machine Learning Mastery

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

أصل الخوارزميات الجينية

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

تطبيقات الخوارزمية الجينية

تم تطوير وتطبيق عدد كبير من تحورات الخوارزميات الجينية، على نطاق واسع، لحل مختلف المشاكل التحسينية. من مسألة تلوين المخطط graph coloring إلي التعرف على الأنماط pattern recognition. ومن الأنظمة غير المتصلة discrete systems مثل مشكلة البائع المتجول traveling salesman problem إلي المستمرة continuous systems مثل التصميم الفعال للأجنحة الحاملة في الهندسة الجوية airfoil efficient design. ومن الأسواق المالية إلي الأمثلة متعددة الأهداف multi-objective engineering.

مميزات الخوارزميات الجينية

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

عيوب الخوارزمية الجينية

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

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

آلية عمل الخوارزميات الجينية

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

1. يتنافس أفراد الساكنة على حقوق التزاوج أي حق الخضوع لعمليات التقاطع crossover والتطفر mutation.
2. الأفراد الأكثر ملائمة أي الأصلح fittest ينتجون الحصة الأكبر من الجيل التالي.
3. تنتقل جينات الأباء عبر الأجيال، ويبقى الأفضل، مما يصقل أفراد الساكنة جيلًا بعد جيل.
4. لا يعني الانتقال من جيل إلي جيل اندثار الآباء. فرغم أن متوسط الملائمة لكل جيل يكون أكبر من الذي سبقه، لكن يمكن أن يكون معامل ملائمة فرد أفضل من الأبناء.

معامل الملائمة

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

كل جيل جديد لديه في المتوسط ​​”جينات أفضل” أكثر من الأجيال السابقة، نظرًا لكون متوسط ​​اللياقة أعلى. وبالتالي فإن كل جيل جديد لديه “حلول جزئية” أفضل من الأجيال السابقة. وعند توقف معامل الملائمة عن الارتفاع لعدد من الأجيال المتتالية، يحدث إقرار التقارب. أي أن الساكنة الناتجة هي الأمثل والفرد الأكثر ملائمة هو الحل.

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

• عملية الانتقاء selection

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

• عملية الدمج أو التقاطع crossover

تكافئ هذه العملية مفهوم التزاوج بين أفراد الساكنة. تتمثل في اختيار فردين من الساكنة الحالية وتحديد عدد من الجينات عشوائيًا وتمريرها للخلف (الأبناء). بالطبع عدد جينات الأباء هو نفسه عدد جينات الأبناء ولكون الاختيار عشوائي لا يكون عدد الجينات من الأم أو الأب نفسه عدد الجينات من الأب أو الأم. أي التوزيع ليس 50 | 50.

• التطفر mutation

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

لم نستخدم الخوارزميات الجينية؟

1. هذه الخوارزميات قوية.
2. قادرة على توفير حلول في فضاءات إحتمال عملاقة.
3. على خلاف خوارزميات الذكاء الاصطناعي الأخرى، لا ينتهي التنفيد بفعل التشويش أو تغير المدخلات.

استخدامات الخوارزمية الجينية

• الذكاء الاصطناعي.
• كسر التشفير والاختراق.
• الشبكات العصبية الاصطناعية.
• فلترة الإشارات وتحليلها.
• مختلف المجالات العملية الأخرى.

مصادر

1. geeksforgeeks
2. ScienceDirect

أهمية وضع الساكنة البدئية

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

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

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

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

المشاكل الحقيقية

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

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

كيف نعالج المشاكل التي تواجهنا في وضع الساكنة البدئية؟

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

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

كيفية تحقيق العشوائية

أحد أصعب الأجزاء في توليد الأعداد العشوائية يرجع لكون الحواسب تكرر عدد من الخطوات المبرمجة لتنفيذها، وليس لتوليد خطوات. لذا فمن المستحيل توليد شيئ لا نستطيع التنبؤ به بواسطتها.

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

تجريبيًا، ما هي الطريقة المثلى لوضع الساكنة البدئية؟

هناك طريقتان أساسيتان معتمدتان لتوليد الساكنة البدئية المستعملة في الخوارزميات التحسينية و هما:

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

 ملاحظات تجريبية 

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

 نتيجة 

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

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

مصادر:

1- Medium
2-ScienceDirect

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

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

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

فما هي الخوارزميات المستوحاة من الطبيعة؟ و كيف ظهرت؟ وما أبرزها؟ ما هي استعمالاتها؟ وما الخصائص التي تتشارك فيها هذه الخوارزميات؟

ما هي الخوارزميات التحسينية المستوحاة من الطبيعة ؟

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

ظهور الخوارزميات التحسينية

ظهرت الخوارزميات التحسينية في بداية القرن التاسع عشر على يد عدد من علماء الرياضيات «ك ويستراس K.T.W Weierstrass»، و«شتاينر J. Steiner»، و«هاميلتون W.R.Hamilton»، و«جاكوبي C.G.J Jacobi».

ظهور الخوارزميات التحسينية المستوحاة من الطبيعة

على مر التاريخ وخصوصًا في الفترات الأولى، اعتمدت مقاربتنا نحن البشر في حل المشاكل التي نواجهها ولا تزال على التجربة والخطأ. أي أنها مقاربة تفاعل مع النظام المراد استكشافه خطوة بخطوة metaheuristic approach. فعدد كبير من الاكتشافات تم عن طريق التفكير خارج الصندوق أو بالصدفة، وهذا ما يعنيه الحدس heuristic. ورغم ذلك نجد أن أول استعمال مسجل لاستخدام هذه المقاربة كطريقة علمية رياضية meta-heuristic method لحل المشاكل problem-solving كان على الأرجح خلال فترة الحرب العالمية الثانية على يد عالم الرياضيات والحوسبة الغني عن التعريف «ألان تورنغ». استخدم تورنغ تلك التقنيات لفك تشفير إتصالات الألمان وكسر آلية تشفيرها Enigma. ورغم كون هذه الطريقة غير مضمونة الوصول للنتائج المرجوة إلا أن استعمالها في مشروعه كان نجاحًا باهرًا، ما أعطى دول الحلفاء ورقة رابحة لإنهاء الحرب لصالحهم.

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

في نفس الوقت، كان العالم والمهندس «جون هولاند John Holland» يعمل رفقة زملائه في جامعة ميشيغان على استكشاف وإنتاج أول الخوارزميات الجينية. وهو ما توج لاحقًا بنشر مجموع أبحاثه في كتابه «Adaptation in natural and artificial systems» سنة 1975. بعدها تم كتابة مئات الكتب وآلاف المقالات عن هذا الموضوع.

الأعوام التي تلت كانت جد حافلة بحيث شهدت تطوير مختلف أنواع الخوارزميات وفتح مجالات بحثية خاصة بكل منها.قاد ذلك الحراك عدد من الرواد مثل عالم الرياضيات «شين شي يانغ Xin-She Yang» مطور خوارزميات مثل «بحث الوقواق CS»، و«خوارزمية الخفاش BA»، و«خوارزمية اليراعة FA»، وغيرهم.

أمثلة على الخوارزميات المستوحاة من الطبيعة

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

• الخوارزميات الجينية أو Genetic Algorithms، إختصارًا GA.
• خوارزميات إستمثال عناصر السرب أو Particle Swarm Optimization، اختصارًا PSO Algorithms.
• خوارزمية التطور التافضلي Differential evolution، اختصار DE Algorithm.
• الخوارزمية مستعمرة النحل الاصطناعية Artificial Bee Colony، اختصارًا ABC Algorithm.
• خوارزمية التحسين مستعمرة النمل Ant Colony Optimization، اختصارًا ACO Algorithm.
• الخوارزمية بحث الوقواق Cuckoo Search، اختصارًا CS Algorithm.
• خوارزمية الخفاش Bat Algorithm، اختصارًا BA.
• خوارزمية اليراعة Firefly Algorithm، اختصارًا FA.
• الخوارزمية المنيعة Immune Algorithm، اختصارًا IA.
• خوارزمية التحسين الذئب الرمادي Grey Wolf Optimization، اختصارًا GWO Algorithm.
• الخوارزمية البحث التجاذبي Gravitational Search، اختصارًا GS Algorithm.
• خوارزمية البحث التناغمي Harmony Search، اختصارًا HS Algorithm.

ما الخصائص المشتركة بين الخوارزميات التحسينية المستوحاة من الطبيعة ؟

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

• وضع الساكنة البدئية. لتحقيق هذا، هناك العديد من المقاربات منها الاختيار العشوائي للساكنة 0، … .

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

• حساب معامل التوافق fitness value والتحقق من شروط إنهاء التنفيذ termination conditions. فإضافة إلى تحديد حجم الساكنة البدئية وكيفية بنائها، يجب أيضًا وضع المدخلات مثل المتغيرات التي تتدخل في كيفية التنفيذ وشروط وقف التنفيذ وإرجاع الحل. فأغلب الخوارزميات التحسينية تستعين بشروط للخروج من دورة التنفيذ المتمثلة في البدء، ثم المعالجة، ثم الفلترة. من بين هذه الشروط نجد:

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

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

•إرجاع المخرجات ووقف التنفيذ. فعند تحقق أحد شروط الخروج، يتم إرجاع الساكنة الحالية باعتبارها حلاً وإنهاء التنفيذ.

مفاهيم مهمة لفهم الخوارزميات المستوحاة من الطبيعة

• الطريقة «الحدسية – heuristic» هي مقاربة لحل المشاكل باستعمال طرق فعالة لكن غير مضمونة النتائج أو عقلانية في بعض الأحيان. لكن الحدسية فعالة وكافية لتحقيق المقاربة approximation وللوصول لنتائج سريعة وتحقيق أهداف متعددة على المدى القصير.

• «الأدلة العليا metaheuristic» وهي في علم الحاسوب والرياضيات إجراءات أو إرشادات عالية المستوى مصممة لإيجاد أو إبتكار أو اختيار طريقة بحث خوارزمية «حدسية» قادرة على توفير حل مقبول لمشكلة تحسينية. نلجأ إليها خاصة عند عدم توافر معلومات أو قوة حوسبية كافية تخولنا استخدام الطرق التقليدية.

أهم التحديات التي تواجه الخوارزميات المستوحاة من الطبيعة

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

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

• نقص البحث الكافي في النظريات البنيوية والأدوات التي تستخدمها هذه الخوارزميات مثل:

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

°وضع أساس صلب من النظريات الرياضية لدعم الخوارزميات التحسينية المستنبطة من الطبيعة، مثل تحليل التعقيد الزمني time complexity، واختبار التقارب convergence proof. ومن المهم تقديم نظرية رياضية شاملة للموازنة بين التناقض بين التقارب لحل محلي convergence to a local optima وبطء التقارب slow convergence.

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

• لا يوجد الكثير من الدراسات المشتركة inter-disciplinary researchs بينها وبين المجالات المستخدمة فيها والمجالات ذات الصلة، وذلك رغم كونها تحمل إمكانات كبيرة ذات فائدة مشتركة.

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

إمكانات خوارزميات الطبيعة

من هنا يتضح لنا أن التوجه البحثي المستقبلي في مجال الخوارزميات التحسينية يجب أن يتمحور حول معالجة هذه المشاكل؛ و ذلك بتقوية تحليل نظري متين لهذه الخوارزميات.

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

مجالات استخدام الخوارزميات التحسينية

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

• الطرق التحسينية الكلاسيكية في الحساب Optimization methods.
• الأنظمة المعلوماتية Information systems.
• هندسة التصنيع و الأنظمة الصناعية Industrial Engineering and Manufacturing systems.
• التصميم الهندسي Engineering design.
• سلسلة الإنتاج Supply chain management.
• الفلترة الرقمية Digital filter design.
• معالجة الصور Image processing.
• تعلم الآلة Machine learning.
• تصميم المفاضلات والمكاملات الرقمية Digital integrator and differentiator design.
• التعرف على الوجوه Face recognition.
• الشبكات العصبية الاصطناعية Artificial neural networks.

وغيرها.

المصادر:

1. ScienceDirect
2. Scholarly
3. Community Encyclopedia
4. Geeks for Geeks
5. Hindawy