الانتقال إلى المحتوى
العودة إلى نتائج البحث

استراتيجية التطور (CMA-ES) — تكييف مصفوفة التغاير

قدّمه
Nikolaus Hansen & Andreas Ostermeier
السنة
2001
النوع
Derivative-free continuous black-box optimizer

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

CMA-ES، اختصار لـ Covariance Matrix Adaptation Evolution Strategy، هي مُحسِّن حديث خالٍ من المشتقات للدوال الصندوق الأسود المستمرة، قدمه هانسن وأوسترمير في عام 2001. يحافظ على مجموعة من الحلول المرشحة المستمدة من توزيع طبيعي متعدد المتغيرات ويحدّث بشكل متكرر متوسط التوزيع وحجم الخطوة ومصفوفة التغاير الكاملة لتوجيه البحث نحو مناطق أفضل في فضاء المعلمات. لقد أصبح المعيار الفعلي لتحسين الصندوق الأسود المستمر ويستخدم على نطاق واسع في البحث عن البنى العصبية وتحسين سياسات التعلم المعزز.

الفكرة الحدسية وراء الطريقة

تخيل أنك تبحث عن أدنى نقطة في منظر طبيعي جبلي ولكن لا يمكنك رؤية التضاريس — يمكنك فقط استكشاف مواقع فردية ومعرفة ارتفاعاتها. تعمل CMA-ES مثل سرب موجه: فهي تسقط سحابة من المجسات حول أفضل تخمين حالي، وتقيس مدى جودة كل مسبار، ثم تعيد تشكيل السحابة للجولة التالية. السحابة ليست كرة بسيطة — إنها تتعلم الشكل الممدود والمائل للوادي الذي تنحدر فيه من خلال تذكر الاتجاهات التي أدت إلى التحسن. على مدى الأجيال المتتالية، تضيق السحابة وتميل لتتماشى مع انحناء سطح الخسارة، مما يسمح للخوارزمية بالتنقل في الوديان الطويلة الضيقة التي قد تحبس الطرق الأبسط.

التاريخ

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

متى تُستخدم

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

الحدود والاعتبارات

  • تحد الذاكرة التربيعية والتكلفة الحسابية لكل جيل في عدد الأبعاد من قابلية التطبيق بما يتجاوز حوالي 1000 معلمة دون متغيرات تقليل الأبعاد.
  • تتقارب إلى حل أمثل محلي في غياب عمليات إعادة التشغيل؛ بالنسبة للمناظر الطبيعية متعددة الأنماط للغاية، يلزم إعادة تشغيل متعددة (IPOP-CMA-ES أو BIPOP-CMA-ES).
  • غير مناسبة لمساحات البحث المنفصلة أو التوافقية — الطريقة معرفة بطبيعتها على المتجهات المستمرة ذات القيم الحقيقية.

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

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

التطبيقات

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

كيف يعمل

كيف يعمل

1

تُلقم الخوارزمية بمتجه حل أولي وحجم خطوة أولي (سيجما). تبدأ مصفوفة التغاير كمصفوفة الوحدة — سحابة بحث كروية تمامًا. يتم تحديد حجم السكان، وعادة ما يكون حوالي 4 + floor(3 * ln(dimension)).

2

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

3

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

4

يتم تحريك المتوسط نحو الحلول الأفضل ترتيبًا. يتم تحديث مصفوفة التغاير وحجم الخطوة باستخدام مسارين تكييفيين متكاملين — تحديثات الرتبة الأولى والرتبة mu — بحيث تصبح الاتجاهات التي أنتجت تحسينات جيدة أكثر احتمالًا في الجيل التالي. هذه هي الآلية الأساسية التي تتعلم بها CMA-ES الهندسة المحلية للمشهد.

5

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

الأخطاء الشائعة

  • يؤدي تعيين حجم الخطوة الأولي صغيرًا جدًا إلى حبس البحث في منطقة ضيقة ويمنع الاستكشاف؛ كبير جدًا وتضيع الأجيال المبكرة التقييمات بعيدًا عن الحل الأمثل. القاعدة العامة الشائعة هي تعيين سيجما بحيث يقع الحل الأمثل ضمن ثلاثة سيجما من نقطة البداية.
  • عادة ما يكون تطبيق CMA-ES على المشاكل ذات الأبعاد المنخفضة جدًا (أقل من خمس معلمات) مضيعة — يكفي البحث الشبكي الأبسط أو Nelder-Mead، ولا تجلب النفقات العامة للسكان في CMA-ES أي فائدة.
  • تشغيل مثيل CMA-ES واحد فقط على مشهد متعدد الأنماط يخاطر بفقدان الحل الأمثل العالمي؛ استخدم استراتيجيات إعادة التشغيل المتعددة أو القائمة على السكان (IPOP/BIPOP) عندما يُعرف أن المشهد متعدد الأنماط للغاية.
  • يعد التعامل مع أفضل حل تم إرجاعه على أنه الحل الأمثل العالمي الحقيقي دون التحقق من إعادة التشغيل خطأً شائعًا — تأكد دائمًا من ذلك من خلال عمليات تشغيل مستقلة متعددة عندما يكون الهدف غير محدب للغاية.

الأسئلة الشائعة

كيف تختلف CMA-ES عن خوارزمية جينية بسيطة؟

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

هل تضمن CMA-ES العثور على الحل الأمثل العالمي؟

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

ما هي أهم معلمة فائقة يجب تعيينها؟

حجم الخطوة الأولي سيجما هو المعلمة الفائقة الأكثر تأثيرًا. القاعدة الإرشادية الجيدة هي تعيينها بحيث يقع الحل الأمثل المتوقع ضمن حوالي ثلاثة سيجما من نقطة البداية. حجم السكان والحد الأقصى لعدد التقييمات هما ضابطان ثانويان؛ تعمل صيغة حجم السكان الافتراضية (4 + floor(3 * ln(dimension))) بشكل جيد في الممارسة.

هل يمكن لـ CMA-ES التعامل مع دوال الهدف الصاخبة؟

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

طرق ذات صلة

المصادر

  1. Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.

    افتح مرجع DOI
    تم النسخ.
  2. Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

    افتح مرجع المنشور
    تم النسخ.