يهدف التحسين 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.
