CMA-ES

الموسوعة الحرة

استراتيجية التطور التكيفي لمصفوفة التغاير (CMA-ES) هي نوع خاص من استراتيجيات التحسين العددي . استراتيجيات التطور (ES) هي طرق عشوائية لا تعتمد على المشتقات ، وتُستخدم للتحسين العددي لمسائل التحسين المستمر غير الخطية أو غير المحدبة . وهي تنتمي إلى فئة الخوارزميات التطورية والحوسبة التطورية . تعتمد الخوارزمية التطورية بشكل عام على مبدأ التطور البيولوجي ، أي التفاعل المتكرر بين التباين (عن طريق إعادة التركيب والطفرة ) والاختيار: ففي كل جيل (تكرار)، تظهر أفراد جديدة (حلول مرشحة، يُشار إليها بـx{\displaystyle x}يتم توليدها عن طريق تغيير الأفراد الأبويين الحاليين، عادةً بطريقة عشوائية. ثم يتم اختيار بعض الأفراد ليصبحوا آباءً في الجيل التالي بناءً على لياقتهم أو قيمة دالة الهدف.و(x){\displaystyle f(x)}وهكذا، يصبح الأفراد أفضل وأفضلو{\displaystyle f}يتم توليد القيم خلال تسلسل الأجيال.

في استراتيجية التطور ، يتم عادةً اختيار الحلول المرشحة الجديدة وفقًا لتوزيع طبيعي متعدد المتغيرات فيRن{\displaystyle \mathbb {R} ^{n}}إعادة التركيب تعني اختيار قيمة متوسطة جديدة للتوزيع. أما الطفرة فتعني إضافة متجه عشوائي، وهو اضطراب بمتوسط ​​صفري. تُمثَّل العلاقات الثنائية بين المتغيرات في التوزيع بمصفوفة تباين . يُعدّ تكييف مصفوفة التباين (CMA) طريقةً لتحديث مصفوفة التباين لهذا التوزيع. وهذا مفيدٌ بشكلٍ خاص إذا كانت الدالةو{\displaystyle f}هو في حالة سيئة .

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

مبادئ

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

يتم استغلال مبدأين رئيسيين لتكييف معلمات توزيع البحث في خوارزمية CMA-ES.

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

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

الخوارزمية

فيما يلي شرحٌ موجزٌ لخوارزمية ( μ / μw , λ )-CMA-ES الأكثر شيوعًا، حيث تُستخدم في كل خطوة تكرارية توليفةٌ مُرجّحةٌ لأفضل μ حلًا من بين λ حلولٍ مرشحةٍ جديدةٍ لتحديث معلمات التوزيع. تتكون الحلقة الرئيسية من ثلاثة أجزاء رئيسية: 1) أخذ عيناتٍ من الحلول الجديدة، 2) إعادة ترتيب الحلول المأخوذة بناءً على مدى ملاءمتها، 3) تحديث متغيرات الحالة الداخلية بناءً على العينات المُعاد ترتيبها. فيما يلي رمزٌ زائفٌ للخوارزمية. 

تعيينλ{\displaystyle \lambda } // عدد العينات لكل تكرار، اثنان على الأقل، وعادةً ما يكون أكبر من 4، قم بالتهيئةم{\displaystyle m}،σ{\displaystyle \sigma }،ج=أنا{\displaystyle C=I}،صσ=0{\displaystyle p_{\sigma }=0}،صج=0{\displaystyle p_{c}=0} // تهيئة متغيرات الحالة طالما لم يتم الإنهاء // التكرار من أجلأنا{\displaystyle i}في{1...λ}{\displaystyle \{1\ldots \lambda \}}قم // عينةλ{\displaystyle \lambda }حلول جديدة وتقييمها xأنا={\displaystyle x_{i}={}}sample_multivariate_normal(المتوسط=م{\displaystyle {}=m}، مصفوفة التغاير=σ2ج{\displaystyle {}=\sigma ^{2}C}) وأنا=لياقة بدنية⁡(xأنا){\displaystyle f_{i}=\operatorname {fitness} (x_{i})}x1...λ{\displaystyle x_{1\ldots \lambda }}←xs(1)...s(λ){\displaystyle x_{s(1)\ldots s(\lambda )}}معs(أنا)=فرز⁡(و1...λ،أنا){\displaystyle s(i)=\operatorname {argsort} (f_{1\ldots \lambda },i)}// فرز الحلول م′=م{\displaystyle m'=m} // نحتاجها لاحقاًم-م′{\displaystyle mm'}وxأنا-م′{\displaystyle x_{i}-m'}م{\displaystyle m}← تحديث_م(x1،...،xλ){\displaystyle (x_{1},\ldots ,x_{\lambda })} // نقل المتوسط ​​إلى حلول أفضل صσ{\displaystyle p_{\sigma }}← تحديث_ps(صσ،σ-1ج-1/2(م-م′)){\displaystyle (p_{\sigma },\sigma ^{-1}C^{-1/2}(mm'))} // تحديث مسار التطور المتساوي الخواص صج{\displaystyle p_{c}}← تحديث_الحاسوب(صج،σ-1(م-م′)،‖صσ‖){\displaystyle (p_{c},\sigma ^{-1}(mm'),\|p_{\sigma }\|)} // تحديث مسار التطور غير المتناحي ج{\displaystyle C}← تحديث_ج(ج،صج،(x1-م′)/σ،...،(xλ-م′)/σ){\displaystyle (C,p_{c},(x_{1}-m')/\sigma ,\ldots ,(x_{\lambda }-m')/\sigma )} // تحديث مصفوفة التغاير σ{\displaystyle \sigma }← تحديث سيجما(σ،‖صσ‖){\displaystyle (\sigma ,\|p_{\sigma }\|)} // تحديث حجم الخطوة باستخدام طول المسار المتساوي الخواصم{\displaystyle m}أوx1{\displaystyle x_{1}}

ترتيب مهام التحديث الخمسة مهم:م{\displaystyle m}يجب تحديثها أولاً،صσ{\displaystyle p_{\sigma }}وصج{\displaystyle p_{c}}يجب تحديثها قبلج{\displaystyle C}، وσ{\displaystyle \sigma }يجب تحديثها أخيرًا. معادلات التحديث لمتغيرات الحالة الخمسة موضحة أدناه.

أبعاد مساحة البحث معروضةن{\displaystyle n}وخطوة التكرارك{\displaystyle k}المتغيرات الخمسة للحالة هي

  • مك∈Rن{\displaystyle m_{k}\in \mathbb {R} ^{n}}، متوسط ​​التوزيع والحل المفضل الحالي لمسألة التحسين،
  • σك>0{\displaystyle \sigma _{k}>0}، حجم الخطوة،
  • جك{\displaystyle C_{k}}، متناظر وموجب التحديدن×ن{\displaystyle n\times n}مصفوفة التغاير معج0=أنا{\displaystyle C_{0}=I}و
  • صσ∈Rن،صج∈Rن{\displaystyle p_{\sigma }\in \mathbb {R} ^{n},p_{c}\in \mathbb {R} ^{n}}، مساران للتطور، تم ضبطهما مبدئيًا على متجه الصفر.

تبدأ عملية التكرار بأخذ العيناتλ>1{\displaystyle \lambda >1}حلول مرشحةxأنا∈Rن{\displaystyle x_{i}\in \mathbb {R} ^{n}}من توزيع طبيعي متعدد المتغيراتشمال(مك،σك2جك){\displaystyle \textstyle {\mathcal {N}}(m_{k},\sigma _{k}^{2}C_{k})}أي لـأنا=1،...،λ{\displaystyle i=1,\ldots ,\lambda }

xأنا ∼ شمال(مك،σك2جك)∼ مك+σك×شمال(0،جك){\displaystyle {\begin{aligned}x_{i}\ &\sim \ {\mathcal {N}}(m_{k},\sigma _{k}^{2}C_{k})\\&\sim \ m_{k}+\sigma _{k}\times {\mathcal {N}}(0,C_{k})\end{aligned}}}

يشير السطر الثاني إلى تفسير ذلك على أنه اضطراب (طفرة) غير متحيز لمتجه الحل المفضل الحاليمك{\displaystyle m_{k}}(متجه متوسط ​​التوزيع). الحلول المرشحةxأنا{\displaystyle x_{i}}يتم تقييمها بناءً على دالة الهدفو:Rن→R{\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }يجب تقليلها إلى الحد الأدنى. للدلالة علىو{\displaystyle f}- تم فرز الحلول المرشحة كـ

{xأنا:λ|أنا=1...λ}={xأنا|أنا=1...λ} و و(x1:λ)≤⋯≤و(xμ:λ)≤و(xμ+1:λ)≤⋯،{\displaystyle \{x_{i:\lambda }\mid i=1\dots \lambda \}=\{x_{i}\mid i=1\dots \lambda \}{\text{ and }}f(x_{1:\lambda })\leq \dots \leq f(x_{\mu })\leq f(x_{\mu +1:\lambda })\leq \cdots ,}

يتم حساب القيمة المتوسطة الجديدة على النحو التالي:

مك+1=∑أنا=1μwأناxأنا:λ=مك+∑أنا=1μwأنا(xأنا:λ-مك){\displaystyle {\begin{aligned}m_{k+1}&=\sum _{i=1}^{\mu }w_{i}\,x_{i:\lambda }\\&=m_{k}+\sum _{i=1}^{\mu }w_{i}\,(x_{i:\lambda }-m_{k})\end{aligned}}}

حيث الأوزان الموجبة (إعادة التركيب)w1≥w2≥⋯≥wμ>0{\displaystyle w_{1}\geq w_{2}\geq \dots \geq w_{\mu }>0}المجموع يساوي واحدًا. عادةً،μ≤λ/2{\displaystyle \mu \leq \lambda /2}ويتم اختيار الأوزان بحيثμw:=1/∑أنا=1μwأنا2≈λ/4{\displaystyle \textstyle \mu _{w}:=1/\sum _{i=1}^{\mu }w_{i}^{2}\approx \lambda /4}إنّ التغذية الراجعة الوحيدة المستخدمة من دالة الهدف هنا وفيما يلي هي ترتيب الحلول المرشحة التي تم أخذ عينات منها بناءً على المؤشرات.أنا:λ{\displaystyle i:\lambda }.

حجم الخطوةσك{\displaystyle \sigma _{k}}يتم تحديثها باستخدام التكيف التراكمي لحجم الخطوة (CSA)، والذي يُشار إليه أحيانًا باسم التحكم في طول المسار . مسار التطور (أو مسار البحث)صσ{\displaystyle p_{\sigma }}يتم تحديثها أولاً.

صσ←(1-جσ)⏟عامل الخصمصσ+1-(1-جσ)2⏞مكملات للتباين المخفضμwجك-1/2مك+1-مك⏞إزاحة مσك⏟موزعة على النحو التالي شمال(0،أنا) في ظل الاختيار المحايد{\displaystyle p_{\sigma }\gets \underbrace {(1-c_{\sigma })} _{\!\!\!\!\!{\text{discount factor}}\!\!\!\!\!}\,p_{\sigma }+\overbrace {\sqrt {1-(1-c_{\sigma })^{2}}} ^{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{complements for discounted variance}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\underbrace {{\sqrt {\mu _{w}}}\,C_{k}^{\;-1/2}\,{\frac {\overbrace {m_{k+1}-m_{k}} ^{\!\!\!{\text{displacement of }}m\!\!\!}}{\sigma _{k}}}} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{distributed as }}{\mathcal {N}}(0,I){\text{ under neutral selection}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}}σك+1=σك×خبرة⁡(جσدσ(‖صσ‖هـ⁡‖شمال(0،أنا)‖-1)⏟غير متحيز بشأن الصفر في ظل الاختيار المحايد){\displaystyle \sigma _{k+1}=\sigma _{k}\times \exp {\bigg (}{\frac {c_{\sigma }}{d_{\sigma }}}\underbrace {\left({\frac {\|p_{\sigma }\|}{\operatorname {E} \|{\mathcal {N}}(0,I)\|}}-1\right)} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{unbiased about 0 under neutral selection}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}{\bigg )}}

أين

  • جσ-1≈ن/3{\displaystyle c_{\sigma }^{-1}\approx n/3}يمثل الأفق الزمني العكسي لمسار التطورصσ{\displaystyle p_{\sigma }}وأكبر من واحد (جσ≪1{\displaystyle c_{\sigma }\ll 1}يشبه ذلك ثابت الاضمحلال الأسي كما(1-جσ)ك≈خبرة⁡(-جσك){\displaystyle (1-c_{\sigma })^{k}\approx \exp(-c_{\sigma }k)}أينجσ-1{\displaystyle c_{\sigma }^{-1}}العمر المرتبط وجσ-1ln⁡(2)≈0.7جσ-1{\displaystyle c_{\sigma }^{-1}\ln(2)\approx 0.7c_{\sigma }^{-1}}نصف العمر)،
  • μw=(∑أنا=1μwأنا2)-1{\displaystyle \mu _{w}=\left(\sum _{i=1}^{\mu }w_{i}^{2}\right)^{-1}}هل التباين هو كتلة الاختيار الفعالة و1≤μw≤μ{\displaystyle 1\leq \mu _{w}\leq \mu }بحسب تعريفwأنا{\displaystyle w_{i}}،
  • جك-1/2=جك-1=جك-1{\displaystyle C_{k}^{\;-1/2}={\sqrt {C_{k}}}^{\;-1}={\sqrt {C_{k}^{\;-1}}}}هو الجذر التربيعي المتناظر الوحيد لمعكوسجك{\displaystyle C_{k}}، و
  • دσ{\displaystyle d_{\sigma }}معامل التخميد عادةً ما يكون قريبًا من الواحد. بالنسبة لـدσ=∞{\displaystyle d_{\sigma }=\infty }أوجσ=0{\displaystyle c_{\sigma }=0}يبقى حجم الخطوة دون تغيير.

حجم الخطوةσك{\displaystyle \sigma _{k}}تزداد إذا وفقط إذا‖صσ‖{\displaystyle \|p_{\sigma }\|}أكبر من القيمة المتوقعة

هـ⁡‖شمال(0،أنا)‖=2Γ((ن+1)/2)Γ(ن/2)≈ن(1-14ن+121ن2){\displaystyle {\begin{aligned}\operatorname {E} \|{\mathcal {N}}(0,I)\|&={\sqrt {2}}\;{\frac {\Gamma ((n+1)/2)}{\Gamma (n/2)}}\\[1ex]&\approx {\sqrt {n}}\,\left(1-{\frac {1}{4n}}+{\frac {1}{21\,n^{2}}}\right)\end{aligned}}}

ويتناقص حجم الخطوة إذا كان أصغر. ولهذا السبب، يميل تحديث حجم الخطوة إلى اتخاذ خطوات متتالية.جك-1{\displaystyle C_{k}^{-1}}-conjugate ، بمعنى أنه بعد نجاح عملية التكيف(مك+2-مك+1σك+1)تيجك-1مك+1-مكσك≈0{\displaystyle \textstyle \left({\frac {m_{k+2}-m_{k+1}}{\sigma _{k+1}}}\right)^{T}\!C_{k}^{-1}{\frac {m_{k+1}-m_{k}}{\sigma _{k}}}\approx 0}[ 1 ]​

وأخيرًا، يتم تحديث مصفوفة التغاير ، حيث يتم تحديث مسار التطور المعني أولاً.

صج←(1-جج)⏟عامل الخصمصج+1[0،αن](‖صσ‖)⏟وظيفة المؤشر1-(1-جج)2⏞مكملات للتباين المخفضμwمك+1-مكσك⏟موزعة على النحو التاليشمال(0،جك)في ظل الاختيار المحايد{\displaystyle p_{c}\gets \underbrace {(1-c_{c})} _{\!\!\!\!\!{\text{discount factor}}\!\!\!\!\!}\,p_{c}+\underbrace {\mathbf {1} _{[0,\alpha {\sqrt {n}}]}(\|p_{\sigma }\|)} _{\text{indicator function}}\overbrace {\sqrt {1-(1-c_{c})^{2}}} ^{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{complements for discounted variance}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\underbrace {{\sqrt {\mu _{w}}}\,{\frac {m_{k+1}-m_{k}}{\sigma _{k}}}} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{distributed as}}\;{\mathcal {N}}(0,C_{k})\;{\text{under neutral selection}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}}

جك+1=(1-ج1-جμ+جs)⏟عامل الخصمجك+ج1صجصجتي⏟مصفوفة من الرتبة الأولى+جμ∑أنا=1μwأناxأنا:λ-مكσك(xأنا:λ-مكσك)تي⏟رتبة⁡مين(μ،ن) مصفوفة{\displaystyle C_{k+1}=\underbrace {(1-c_{1}-c_{\mu }+c_{s})} _{\!\!\!\!\!{\text{discount factor}}\!\!\!\!\!}\,C_{k}+c_{1}\underbrace {p_{c}p_{c}^{T}} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{rank one matrix}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}+\,c_{\mu }\underbrace {\sum _{i=1}^{\mu }w_{i}{\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\left({\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\right)^{T}} _{\operatorname {rank} \min(\mu ,n){\text{ matrix}}}}

أينتي{\displaystyle T}يشير إلى عملية النقل و

  • جج-1≈ن/4{\displaystyle c_{c}^{-1}\approx n/4}يمثل الأفق الزمني العكسي لمسار التطورصج{\displaystyle p_{c}}وأكبر من واحد،
  • α≈1.5{\displaystyle \alpha \approx 1.5}ووظيفة المؤشر1[0،αن](‖صσ‖){\displaystyle \mathbf {1} _{[0,\alpha {\sqrt {n}}]}(\|p_{\sigma }\|)}تكون النتيجة واحدًا إذا وفقط إذا‖صσ‖∈[0،αن]{\displaystyle \|p_{\sigma }\|\in [0,\alpha {\sqrt {n}}]}أو بعبارة أخرى،‖صσ‖≤αن{\displaystyle \|p_{\sigma }\|\leq \alpha {\sqrt {n}}}وهو ما يحدث عادةً،
  • جs=(1-1[0،αن](‖صσ‖)2)ج1جج(2-جج){\displaystyle c_{s}=(1-\mathbf {1} _{[0,\alpha {\sqrt {n}}]}(\|p_{\sigma }\|)^{2})\,c_{1}c_{c}(2-c_{c})}يعوض جزئياً عن خسارة التباين الطفيفة في حالة كون المؤشر صفراً،
  • ج1≈2/ن2{\displaystyle c_{1}\approx 2/n^{2}}يمثل معدل التعلم لتحديث مصفوفة التغاير من الرتبة الأولى و
  • جμ≈μw/ن2{\displaystyle c_{\mu }\approx \mu _{w}/n^{2}}معدل التعلم للرتبة-μ{\displaystyle \mu }تحديث مصفوفة التغاير ويجب ألا يتجاوز1-ج1{\displaystyle 1-c_{1}}.

يؤدي تحديث مصفوفة التغاير إلى زيادة احتماليةصج{\displaystyle p_{c}}ولـ(xأنا:λ-مك)/σك{\displaystyle (x_{i:\lambda }-m_{k})/\sigma _{k}}يتم أخذ عينات منهاشمال(0،جك+1){\displaystyle {\mathcal {N}}(0,C_{k+1})}وبهذا تكتمل خطوة التكرار.

عدد العينات المرشحة لكل تكرار،λ{\displaystyle \lambda }لا يتم تحديدها مسبقًا ويمكن أن تتفاوت ضمن نطاق واسع. القيم الأصغر، على سبيل المثالλ=10{\displaystyle \lambda =10}تؤدي القيم الأكبر، على سبيل المثال، إلى سلوك بحث محلي أكثر.λ=10ن{\displaystyle \lambda =10n}مع القيمة الافتراضيةμw≈λ/4{\displaystyle \mu _{w}\approx \lambda /4}مما يجعل البحث أكثر شمولية. في بعض الأحيان، تتم إعادة تشغيل الخوارزمية بشكل متكرر مع زيادةλ{\displaystyle \lambda }بمقدار الضعف لكل عملية إعادة تشغيل. [ 2 ] بالإضافة إلى الضبطλ{\displaystyle \lambda }(أو ربماμ{\displaystyle \mu }بدلاً من ذلك، على سبيل المثالλ{\displaystyle \lambda }يتم تحديدها مسبقًا من خلال عدد المعالجات المتاحة)، فإن المعلمات المذكورة أعلاه ليست خاصة بدالة الهدف المعطاة، وبالتالي لا يُقصد تعديلها من قبل المستخدم.

مثال على الكود في MATLAB/Octave

دالة xmin = purecmaes % ( mu/mu_w, lambda ) - CMA - ES % -------------------- التهيئة -------------------------------- % معلمات الإدخال المُعرَّفة من قِبل المستخدم (تحتاج إلى تعديل) strfitnessfct = 'frosenbrock' ; % اسم دالة الهدف/اللياقة N = 20 ; % عدد متغيرات الهدف/بعد المشكلة xmean = rand ( N , 1 ); % النقطة الأولية لمتغيرات الهدف sigma = 0.3 ; % الانحراف المعياري لكل إحداثية (حجم الخطوة) stopfitness = 1e-10 ; % التوقف إذا كانت اللياقة < stopfitness (التقليل) stopeval = 1e3 * N ^ 2 ; % التوقف بعد stopeval عدد تقييمات الدالة % إعداد معلمات الاستراتيجية: الاختيار lambda = 4 + floor ( 3 * log ( N )); % حجم المجموعة، عدد النسل mu = lambda / 2 ; عدد الآباء/النقاط لأوزان إعادة التركيب = log ( mu + 1 / 2 ) - log ( 1 : mu ) ' ; % مصفوفة muXone لإعادة التركيب الموزون mu = floor ( mu ); weights = weights / sum ( weights ); % تطبيع مصفوفة أوزان إعادة التركيب mueff = sum ( weights ) ^ 2 / sum ( weights .^ 2 ); % فعالية التباين للمجموع w_i x_i% ضبط معلمات الاستراتيجية: التكيف cc = ( 4 + mueff / N ) / ( N + 4 + 2 * mueff / N )؛ % ثابت الزمن للتراكم لـ C cs = ( mueff + 2 ) / ( N + mueff + 5 )؛ % ثابت الزمن للتراكم للتحكم في سيجما c1 = 2 / (( N + 1.3 ) ^ 2 + mueff )؛ % معدل التعلم لتحديث الرتبة الأولى لـ C cmu = min ( 1 - c1 , 2 * ( mueff - 2 + 1 / mueff ) / (( N + 2 ) ^ 2 + mueff ))؛ % ولتحديث الرتبة μ damps = 1 + 2 * max ( 0 , sqrt (( mueff - 1 ) / ( N + 1 )) - 1 ) + cs ؛ نسبة التخميد لـ sigma % عادةً ما تكون قريبة من 1 % تهيئة معلمات وثوابت الاستراتيجية الديناميكية (الداخلية) pc = zeros ( N , 1 ); ps = zeros ( N , 1 ); % مسارات التطور لـ C و sigma B = eye ( N , N ); % B تحدد نظام الإحداثيات D = ones ( N , 1 ); % القطر D يحدد المقياس C = B * diag ( D .^ 2 ) * B ' ; % مصفوفة التغاير C invsqrtC = B * diag ( D .^- 1 ) * B '; % C^-1/2 eigeneval = 0 ; % تتبع تحديث B و D chiN = N ^ 0.5 * ( 1 - 1 / ( 4 * N ) + 1 / ( 21 * N ^ 2 )); % توقع % ||N(0,I)|| == norm(randn(N,1)) % -------------------- حلقة التوليد -------------------------------- counteval = 0 ; % تحتوي الأسطر الأربعون التالية على 20 سطرًا من التعليمات البرمجية المهمة while counteval < stopeval % توليد وتقييم ذرية lambda for k = 1 : lambda arx (:, k ) = xmean + sigma * B * ( D .* randn ( N , 1 )); % m + sig * Normal(0,C) arfitness ( k ) = feval ( strfitnessfct , arx (:, k )); % استدعاء دالة الهدف counteval = counteval + 1 ; نهاية % فرز حسب اللياقة وحساب المتوسط ​​المرجح في xmean [ arfitness , arindex ] = sort ( arfitness ); % التقليل xold = xmean ; xmean = arx (:, arindex ( 1 : mu )) * weights ; % إعادة التركيب، قيمة المتوسط ​​الجديدة % التراكم: تحديث مسارات التطور ps = ( 1 - cs ) * ps ... + sqrt ( cs * ( 2 - cs ) * mueff ) * invsqrtC * ( xmean - xold ) / sigma ; hsig = norm ( ps ) / sqrt (1 - ( 1 - cs ) ^ ( 2 * counteval / lambda )) / chiN < 1.4 + 2 / ( N + 1 )؛ pc = ( 1 - cc ) * pc ... + hsig * sqrt ( cc * ( 2 - cc ) * mueff ) * ( xmean - xold ) / sigma ؛% تعديل مصفوفة التغاير C artmp = ( 1 / sigma ) * ( arx (:, arindex ( 1 : mu )) - repmat ( xold , 1 , mu )); C = ( 1 - c1 - cmu ) * C ...  % تعديل المصفوفة القديمة + c1 * ( pc * pc ' ...  % إضافة تحديث الرتبة الأولى + ( 1 - hsig ) * cc * ( 2 - cc ) * C ) ... % تصحيح طفيف إذا كانت hsig تساوي صفرًا + cmu * artmp * diag ( weights ) * artmp ' ; % إضافة تحديث الرتبة mu% ضبط حجم الخطوة sigma sigma = sigma * exp (( cs / damps ) * ( norm ( ps ) / chiN - 1 )); % تحليل C إلى B*diag(D.^2)*B' (القطرية) إذا كان counteval - eigeneval > lambda / ( c1 + cmu ) / N / 10 % لتحقيق O(N^2) eigeneval = counteval ; C = triu ( C ) + triu ( C , 1 ) ' ; % فرض التناظر [ B , D ] = eig ( C ); % تحليل القيم الذاتية، B == المتجهات الذاتية المعيارية D = sqrt ( diag ( D )); % D هو متجه الانحرافات المعيارية الآن invsqrtC = B * diag ( D .^- 1 ) * B ' ; نهاية % توقف، إذا كانت اللياقة جيدة بما يكفي أو تجاوزت الحالة 1e14، يُنصح باستخدام طرق إنهاء أفضل إذا كانت arfitness ( 1 ) <= stopfitness || max ( D ) > 1e7 * min ( D ) توقف ؛ نهايةنهاية حلقة التكرار % while، نهاية حلقة التوليدxmin = arx (:, arindex ( 1 )); % إرجاع أفضل نقطة من التكرار الأخير. % لاحظ أنه من المتوقع أن يكون xmean أفضل. % نهاية % --------------------------------------------------------------- دالة f = frosenbrock ( x ) إذا كان حجم ( x , 1 ) < 2 خطأ ( 'يجب أن يكون البعد أكبر من واحد' ); نهاية f = 100 * مجموع (( x ( 1 : نهاية - 1 ) .^ 2 - x ( 2 : نهاية )) .^ 2 ) + مجموع (( x ( 1 : نهاية - 1 ) - 1 ) .^ 2 ); نهاية

الأسس النظرية

بالنظر إلى معلمات التوزيع - المتوسط ​​والتباينات والتباينات المشتركة - فإن توزيع الاحتمال الطبيعي لأخذ عينات من الحلول المرشحة الجديدة هو توزيع الاحتمال ذو الإنتروبيا القصوى علىRن{\displaystyle \mathbb {R} ^{n}}أي توزيع العينة الذي يتضمن الحد الأدنى من المعلومات المسبقة. وسيتم تناول المزيد من الاعتبارات المتعلقة بمعادلات التحديث لخوارزمية CMA-ES فيما يلي.

مقياس متغير

تُطبّق خوارزمية CMA-ES طريقة المقياس المتغير العشوائي . في حالة خاصة جدًا لدالة هدف محدبة تربيعية

و(x)=12(x-x*)تيح(x-x*){\displaystyle f(x)={\textstyle {\frac {1}{2}}}(x-x^{*})^{T}H(x-x^{*})}

مصفوفة التغايرجك{\displaystyle C_{k}}يتكيف مع معكوس مصفوفة هيسيانح{\displaystyle H}، حتى عامل قياسي وتقلبات عشوائية صغيرة. وبشكل أكثر عمومية، ينطبق ذلك أيضًا على الدالةز∘و{\displaystyle g\circ f}، أينز{\displaystyle g}مصفوفة التغاير متزايدة تمامًا وبالتالي تحافظ على الترتيبجك{\displaystyle C_{k}}يتكيف معح-1{\displaystyle H^{-1}}، حتى عامل قياسي وتقلبات عشوائية صغيرة. لنسبة الاختيارλ/μ→∞{\displaystyle \lambda /\mu \to \infty }(وبالتالي حجم السكان)λ→∞{\displaystyle \lambda \to \infty })، الμ{\displaystyle \mu }تُنتج الحلول المختارة مصفوفة تباين تجريبية تعكس مصفوفة هيسيان المعكوسة حتى في استراتيجيات التطور التي لا تتطلب تعديل مصفوفة التباين. وقد تم إثبات هذه النتيجة لـμ=1{\displaystyle \mu =1}[ 3 ] على نموذج ثابت، بالاعتماد على التقريب التربيعي.

تحديثات الاحتمالية القصوى

تهدف معادلات التحديث لمصفوفة المتوسط ​​ومصفوفة التباين إلى تعظيم دالة الاحتمال مع تشابهها مع خوارزمية التوقع والتعظيم . تحديث متجه المتوسطم{\displaystyle m}تعظيم دالة الاحتمال اللوغاريتمي، بحيث

مك+1=arg⁡الأعلىم∑أنا=1μwأناسجل⁡صشمال(xأنا:λ|م){\displaystyle m_{k+1}=\arg \max _{m}\sum _{i=1}^{\mu }w_{i}\log p_{\mathcal {N}}(x_{i:\lambda }\mid m)}

أين

سجل⁡صشمال(x)=-12سجل⁡المحقق(2πج)-12(x-م)تيج-1(x-م){\displaystyle \log p_{\mathcal {N}}(x)=-{\tfrac {1}{2}}\log \det(2\pi C)-{\tfrac {1}{2}}(x-m)^{T}C^{-1}(x-m)}

يرمز إلى احتمالية اللوغاريتم لـx{\displaystyle x}من توزيع طبيعي متعدد المتغيرات بمتوسطم{\displaystyle m}وأي مصفوفة تباين موجبة محددةج{\displaystyle C}. لرؤية ذلكمك+1{\displaystyle m_{k+1}}مستقل عنج{\displaystyle C}لاحظ أولاً أن هذا ينطبق على أي مصفوفة قطريةج{\displaystyle C}لأن المُعظِّم على مستوى الإحداثيات مستقل عن عامل القياس. بعد ذلك، يتم تدوير نقاط البيانات أو اختيارج{\displaystyle C}العناصر غير القطرية متكافئة.

الرتبة-μ{\displaystyle \mu }تحديث مصفوفة التغاير، أي الحد الأيمن في معادلة التحديث الخاصة بـجك{\displaystyle C_{k}}، يزيد من احتمالية اللوغاريتم في ذلك

∑أنا=1μwأناxأنا:λ-مكσك(xأنا:λ-مكσك)تي=arg⁡الأعلىج∑أنا=1μwأناسجل⁡صشمال(xأنا:λ-مكσك|ج){\displaystyle \sum _{i=1}^{\mu }w_{i}{\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\left({\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\right)^{T}=\arg \max _{C}\sum _{i=1}^{\mu }w_{i}\log p_{\mathcal {N}}\left(\left.{\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\right|C\right)}

لμ≥ن{\displaystyle \mu \geq n}(خلاف ذلكج{\displaystyle C}هي مفردة، ولكن النتيجة نفسها تنطبق إلى حد كبير علىμ<ن{\displaystyle \mu <n}). هنا،صشمال(x|ج){\displaystyle p_{\mathcal {N}}(x|C)}يشير إلى احتماليةx{\displaystyle x}من توزيع طبيعي متعدد المتغيرات بمتوسط ​​صفري ومصفوفة تباينج{\displaystyle C}لذلك، من أجلج1=0{\displaystyle c_{1}=0}وجμ=1{\displaystyle c_{\mu }=1}،جك+1{\displaystyle C_{k+1}}هذا هو مُقدِّر الاحتمال الأقصى المذكور أعلاه . انظر تقدير مصفوفات التغاير لمزيد من التفاصيل حول الاشتقاق.

الانحدار التدرجي الطبيعي في فضاء توزيعات العينات

اكتشف كل من أكيموتو وآخرون [ 4 ] وجلاسماشرز وآخرون [ 5 ] بشكل مستقل أن تحديث معلمات التوزيع يشبه الانحدار في اتجاه التدرج الطبيعي المأخوذ عينات منه لقيمة دالة الهدف المتوقعةهـو(x){\displaystyle Ef(x)}(لتقليلها إلى الحد الأدنى)، حيث يتم حساب القيمة المتوقعة وفقًا لتوزيع العينة. مع ضبط المعلمة لـجσ=0{\displaystyle c_{\sigma }=0}وج1=0{\displaystyle c_{1}=0}أي بدون التحكم في حجم الخطوة وتحديث الرتبة الأولى ، يمكن اعتبار CMA-ES تجسيدًا لاستراتيجيات التطور الطبيعي (NES). [ 4 ] [ 5 ] التدرج الطبيعي مستقل عن معلمات التوزيع. عند أخذه بالنسبة للمعلمات θ لتوزيع العينة p ، فإن تدرجهـو(x){\displaystyle Ef(x)}يمكن التعبير عنها على النحو التالي

∇θهـ(و(x)|θ)=∇θ∫Rنو(x)ص(x)دx=∫Rنو(x)∇θص(x)دx=∫Rنو(x)ص(x)∇θln⁡ص(x)دx=هـ⁡(و(x)∇θln⁡ص(x|θ)){\displaystyle {\begin{aligned}{\nabla }_{\!\theta }E(f(x)\mid \theta )&=\nabla _{\!\theta }\int _{\mathbb {R} ^{n}}f(x)p(x)\,\mathrm {d} x\\&=\int _{\mathbb {R} ^{n}}f(x)\nabla _{\!\theta }p(x)\,\mathrm {d} x\\&=\int _{\mathbb {R} ^{n}}f(x)p(x)\nabla _{\!\theta }\ln p(x)\,\mathrm {d} x\\&=\operatorname {E} (f(x)\nabla _{\!\theta }\ln p(x\mid \theta ))\end{aligned}}}

أينص(x)=ص(x|θ){\displaystyle p(x)=p(x\mid \theta )}يعتمد على متجه المعلماتθ{\displaystyle \theta }ما يسمى بدالة التقييم ،∇θln⁡ص(x|θ)=∇θص(x)ص(x){\displaystyle \nabla _{\!\theta }\ln p(x\mid \theta )={\frac {\nabla _{\!\theta }p(x)}{p(x)}}}يشير إلى الحساسية النسبية لـ p بالنسبة إلى θ ، ويتم حساب القيمة المتوقعة بالنسبة إلى التوزيع p . التدرج الطبيعي لـهـو(x){\displaystyle Ef(x)}، بما يتوافق مع مقياس معلومات فيشر (وهو مقياس للمسافة المعلوماتية بين التوزيعات الاحتمالية وانحناء الإنتروبيا النسبية )، أصبح الآن كالتالي:

∇~هـ⁡(و(x)|θ)=Fθ-1∇θهـ⁡(و(x)|θ){\displaystyle {\begin{aligned}{\tilde {\nabla }}\operatorname {E} (f(x)\mid \theta )&=F_{\theta }^{-1}\nabla _{\!\theta }\operatorname {E} (f(x)\mid \theta )\end{aligned}}}

حيث مصفوفة معلومات فيشرFθ{\displaystyle F_{\theta }}يمثل هذا القيمة المتوقعة لمصفوفة هيسيان لـ −ln p، ويجعل التعبير مستقلاً عن المعاملات المختارة. بدمج المعادلات السابقة نحصل على

∇~هـ⁡(و(x)|θ)=Fθ-1هـ⁡(و(x)∇θln⁡ص(x|θ))=هـ⁡(و(x)Fθ-1∇θln⁡ص(x|θ)){\displaystyle {\begin{aligned}{\tilde {\nabla }}\operatorname {E} (f(x)\mid \theta )&=F_{\theta }^{-1}\operatorname {E} (f(x)\nabla _{\!\theta }\ln p(x\mid \theta ))\\&=\operatorname {E} (f(x)F_{\theta }^{-1}\nabla _{\!\theta }\ln p(x\mid \theta ))\end{aligned}}}

يأخذ تقريب مونت كارلو للتوقع الأخير المتوسط ​​على λ عينة من p

∇~هـ^θ(و):=-∑أنا=1λwأنا⏞الوزن المفضلFθ-1∇θln⁡ص(xأنا:λ|θ)⏟توجيهات المرشح من xأنا:λمع wأنا=-و(xأنا:λ)/λ{\displaystyle {\tilde {\nabla }}{\widehat {E}}_{\theta }(f):=-\sum _{i=1}^{\lambda }\overbrace {w_{i}} ^{\!\!\!\!{\text{preference weight}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\underbrace {F_{\theta }^{-1}\nabla _{\!\theta }\ln p(x_{i:\lambda }\mid \theta )} _{\!\!\!\!\!{\text{candidate direction from }}x_{i:\lambda }\!\!\!\!\!}\quad {\text{with }}w_{i}=-f(x_{i:\lambda })/\lambda }

حيث الترميزأنا:λ{\displaystyle i:\lambda }يتم استخدام ما سبق، وبالتاليwأنا{\displaystyle w_{i}}تتناقص بشكل رتيب فيأنا{\displaystyle i}.

توصل أوليفييه وآخرون [ 6 ] في النهاية إلى اشتقاق دقيق للأوزان،wأنا{\displaystyle w_{i}}كما هو مُعرَّف في CMA-ES. تُعتبر الأوزان مُقدِّرًا متسقًا تقاربيًا لدالة التوزيع التراكمي لـو(X){\displaystyle f(X)}عند نقاطأنا{\displaystyle i}إحصائية الترتيب رقم 1و(xأنا:λ){\displaystyle f(x_{i:\lambda })}كما هو موضح أعلاه، حيثX∼ص(.|θ){\displaystyle X\sim p(.|\theta )}، مؤلفة من تحويل ثابت متناقص بشكل رتيبw{\displaystyle w}، إنه،

wأنا=w(رأنك(و(xأنا:λ))-1/2λ).{\displaystyle w_{i}=w\left({\frac {{\mathsf {rank}}(f(x_{i:\lambda }))-1/2}{\lambda }}\right).}

هذه الأوزان تجعل الخوارزمية غير حساسة للخصائص المحددةو{\displaystyle f}-القيم. وبشكل أكثر إيجازًا، باستخدام مُقدِّر دالة التوزيع التراكمي لـو{\displaystyle f}بدلاً منو{\displaystyle f}دع الخوارزمية تعتمد فقط على ترتيبو{\displaystyle f}القيم - ولكن ليس على توزيعها الأساسي. وهذا يجعل الخوارزمية ثابتة بالنسبة للقيم المتزايدة تمامًاو{\displaystyle f}التحويلات. الآن نُعرّف

θ=[مكتيمتجه⁡(جك)تيσك]تي∈Rن+ن2+1{\displaystyle \theta =[m_{k}^{T}\operatorname {vec} (C_{k})^{T}\sigma _{k}]^{T}\in \mathbb {R} ^{n+n^{2}+1}}

بحيثص(⋅|θ){\displaystyle p(\cdot \mid \theta )}هي كثافة التوزيع الطبيعي متعدد المتغيراتشمال(مك،σك2جك){\displaystyle {\mathcal {N}}(m_{k},\sigma _{k}^{2}C_{k})}ثم، لدينا تعبير صريح لمعكوس مصفوفة معلومات فيشر حيثσك{\displaystyle \sigma _{k}}ثابت

Fθ|σك-1=[σك2جك002جك⊗جك]{\displaystyle F_{\theta \mid \sigma _{k}}^{-1}=\left[{\begin{array}{cc}\sigma _{k}^{2}C_{k}&0\\0&2C_{k}\otimes C_{k}\end{array}}\right]}

ولـ

ln⁡ص(x|θ)=ln⁡ص(x|مك،σك2جك)=-12(x-مك)تيσك-2جك-1(x-مك)-12ln⁡المحقق(2πσك2جك){\displaystyle {\begin{aligned}\ln p(x\mid \theta )&=\ln p(x\mid m_{k},\sigma _{k}^{2}C_{k})\\[1ex]&=-{\tfrac {1}{2}}(x-m_{k})^{T}\sigma _{k}^{-2}C_{k}^{-1}(x-m_{k})-{\tfrac {1}{2}}\ln \det(2\pi \sigma _{k}^{2}C_{k})\end{aligned}}}

وبعد إجراء بعض الحسابات، تبين أن التحديثات في CMA-ES هي [ 4 ]

مك+1=مك-[∇~هـ^θ(و)]1،...،ن⏟التدرج الطبيعي للمتوسط=مك+∑أنا=1λwأنا(xأنا:λ-مك){\displaystyle {\begin{aligned}m_{k+1}&=m_{k}-\underbrace {[{\tilde {\nabla }}{\widehat {E}}_{\theta }(f)]_{1,\dots ,n}} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{natural gradient for mean}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\\&=m_{k}+\sum _{i=1}^{\lambda }w_{i}(x_{i:\lambda }-m_{k})\end{aligned}}}

و

جك+1=جك+ج1(صجصجتي-جك)-جμحصيرة⁡([∇~هـ^θ(و)]ن+1،...،ن+ن2⏞التدرج الطبيعي لمصفوفة التغاير)=جك+ج1(صجصجتي-جك)+جμ∑أنا=1λwأنا(xأنا:λ-مكσك(xأنا:λ-مكσك)تي-جك){\displaystyle {\begin{aligned}C_{k+1}&=C_{k}+c_{1}(p_{c}p_{c}^{T}-C_{k})-c_{\mu }\operatorname {mat} (\overbrace {[{\tilde {\nabla }}{\widehat {E}}_{\theta }(f)]_{n+1,\dots ,n+n^{2}}} ^{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{natural gradient for covariance matrix}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!})\\&=C_{k}+c_{1}(p_{c}p_{c}^{T}-C_{k})+c_{\mu }\sum _{i=1}^{\lambda }w_{i}\left({\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\left({\frac {x_{i:\lambda }-m_{k}}{\sigma _{k}}}\right)^{T}-C_{k}\right)\end{aligned}}}

حيث تُشكّل mat المصفوفة المناسبة من متجه التدرج الطبيعي الفرعي الخاص بها. وهذا يعني، وضعج1=جσ=0{\displaystyle c_{1}=c_{\sigma }=0}، تتناقص تحديثات CMA-ES في اتجاه التقريب∇~هـ^θ(و){\displaystyle {\tilde {\nabla }}{\widehat {E}}_{\theta }(f)}من التدرج الطبيعي أثناء استخدام أحجام خطوات مختلفة (معدلات التعلم 1 وجμ{\displaystyle c_{\mu }}) للمعاملات المتعامدةم{\displaystyle m}وج{\displaystyle C}على التوالي. تسمح الإصدارات الأحدث بمعدل تعلم مختلف للمتوسط.م{\displaystyle m}كذلك. [ 7 ] يستخدم أحدث إصدار من CMA-ES وظيفة مختلفة أيضًا.w{\displaystyle w}لم{\displaystyle m}وج{\displaystyle C}مع قيم سالبة فقط للأخير (ما يسمى بـ CMA النشط).

الثبات أو عدم التحيز

من السهل نسبيًا ملاحظة أن معادلات التحديث لخوارزمية CMA-ES تحقق بعض شروط الاستقرار، حيث إنها غير متحيزة بشكل أساسي. في ظل الاختيار المحايد، حيثxأنا:λ∼شمال(مك،σك2جك){\displaystyle x_{i:\lambda }\sim {\mathcal {N}}(m_{k},\sigma _{k}^{2}C_{k})}، نجد أن

هـ⁡(مك+1|مك)=مك{\displaystyle \operatorname {E} (m_{k+1}\mid m_{k})=m_{k}}

وبافتراض بعض الافتراضات الإضافية البسيطة بشأن الشروط الأولية

هـ⁡(سجل⁡σك+1|σك)=سجل⁡σك{\displaystyle \operatorname {E} (\log \sigma _{k+1}\mid \sigma _{k})=\log \sigma _{k}}

وبإجراء تصحيح طفيف إضافي في تحديث مصفوفة التغاير في حالة تقييم دالة المؤشر إلى الصفر، نجد

هـ⁡(جك+1|جك)=جك{\displaystyle \operatorname {E} (C_{k+1}\mid C_{k})=C_{k}}

الثبات

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

  • ثبات قيمة دالة الهدف تحت التحويلات التي تحافظ على الترتيبو{\displaystyle f}، بمعنى أنه لأيح:Rن→R{\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }السلوك متطابق فيو:x↦ز(ح(x)){\displaystyle f:x\mapsto g(h(x))}لجميع الزيادات الصارمةز:R→R{\displaystyle g:\mathbb {R} \to \mathbb {R} }يسهل التحقق من هذا الثبات، لأنه فقطو{\displaystyle f}يُستخدم الترتيب في الخوارزمية، وهو ثابت بغض النظر عن اختيارز{\displaystyle g}.
  • عدم تأثر المقياس ، بمعنى أنه لأيح:Rن→R{\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }السلوك مستقل عنα>0{\displaystyle \alpha >0}بالنسبة لدالة الهدفو:x↦ح(αx){\displaystyle f:x\mapsto h(\alpha x)}منحσ0∝1/α{\displaystyle \sigma _{0}\propto 1/\alpha }وم0∝1/α{\displaystyle m_{0}\propto 1/\alpha }.
  • الثبات تحت دوران فضاء البحث، وذلك لأيح:Rن→R{\displaystyle h:\mathbb {R} ^{n}\to \mathbb {R} }وأيz∈Rن{\displaystyle z\in \mathbb {R} ^{n}}السلوك علىو:x↦ح(Rx){\displaystyle f:x\mapsto h(Rx)} مستقل عن المصفوفة المتعامدةR{\displaystyle R}، منحم0=R-1z{\displaystyle m_{0}=R^{-1}z}وبشكل أعم، فإن الخوارزمية ثابتة أيضًا تحت التحويلات الخطية العامة.R{\displaystyle R}بالإضافة إلى ذلك، يتم اختيار مصفوفة التغاير الأولية على النحو التالي:R-1R-1تي{\displaystyle R^{-1}{R^{-1}}^{T}}.

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

التقارب

تشير اعتبارات مفاهيمية مثل خاصية عدم تغير المقياس للخوارزمية، وتحليل استراتيجيات التطور الأبسط ، والأدلة التجريبية الدامغة، إلى أن الخوارزمية تتقارب بسرعة على فئة كبيرة من الدوال نحو الحل الأمثل العالمي، والذي يُشار إليه بـx*{\displaystyle x^{*}}في بعض الدوال، يحدث التقارب بشكل مستقل عن الشروط الابتدائية باحتمالية تساوي واحدًا. أما في دوال أخرى، فتكون الاحتمالية أقل من واحد وتعتمد عادةً على الشروط الابتدائية.م0{\displaystyle m_{0}}وσ0{\displaystyle \sigma _{0}}. تجريبياً، أسرع معدل تقارب ممكن فيك{\displaystyle k}يمكن ملاحظة تقارب خطي أو لوغاريتمي خطي أو أسي في كثير من الأحيان في طرق البحث المباشر القائمة على الترتيب (حسب السياق ). ويمكننا كتابة ذلك بشكل غير رسمي.

‖مك-x*‖≈‖م0-x*‖×هـ-جك{\displaystyle \|m_{k}-x^{*}\|\;\approx \;\|m_{0}-x^{*}\|\times e^{-ck}}

بالنسبة للبعضج>0{\displaystyle c>0}وبشكل أكثر صرامة

1ك∑أنا=1كسجل⁡‖مأنا-x*‖‖مأنا-1-x*‖=1كسجل⁡‖مك-x*‖‖م0-x*‖→-ج<0ل ك→∞،{\displaystyle {\frac {1}{k}}\sum _{i=1}^{k}\log {\frac {\|m_{i}-x^{*}\|}{\|m_{i-1}-x^{*}\|}}\;=\;{\frac {1}{k}}\log {\frac {\|m_{k}-x^{*}\|}{\|m_{0}-x^{*}\|}}\;\to \;-c<0\quad {\text{for }}k\to \infty \;,}

أو على نحو مماثل،

هـ⁡سجل⁡‖مك-x*‖‖مك-1-x*‖→-ج<0ل ك→∞.{\displaystyle \operatorname {E} \log {\frac {\|m_{k}-x^{*}\|}{\|m_{k-1}-x^{*}\|}}\;\to \;-c<0\quad {\text{for }}k\to \infty \;.}

هذا يعني أن المسافة إلى الحل الأمثل تتناقص في المتوسط ​​في كل تكرار بمعامل "ثابت"، أي بـخبرة⁡(-ج){\displaystyle \exp(-c)}معدل التقاربج{\displaystyle c}تقريبًا0.1λ/ن{\displaystyle 0.1\lambda /n}، منحλ{\displaystyle \lambda }ليس أكبر بكثير من البعدن{\displaystyle n}حتى مع الوضع الأمثلσ{\displaystyle \sigma }وج{\displaystyle C}معدل التقاربج{\displaystyle c}لا يمكن أن يتجاوز إلى حد كبير0.25λ/ن{\displaystyle 0.25\lambda /n}بالنظر إلى أوزان إعادة التركيب المذكورة أعلاهwأنا{\displaystyle w_{i}}جميعها غير سالبة. التبعيات الخطية الفعلية فيλ{\displaystyle \lambda }ون{\displaystyle n}إنها نتائج رائعة، وهي في كلتا الحالتين أفضل ما يمكن توقعه في هذا النوع من الخوارزميات. وقد تم إثبات التقارب الخطي لخوارزمية CMA-ES باحتمالية واحد للدوال التربيعية المحدبة. [ 8 ]

التفسير كتحويل لنظام الإحداثيات

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

xأنا∼ مك+σك×شمال(0،جك)∼ مك+σك×جك1/2شمال(0،أنا){\displaystyle {\begin{aligned}x_{i}&\sim \ m_{k}+\sigma _{k}\times {\mathcal {N}}(0,C_{k})\\&\sim \ m_{k}+\sigma _{k}\times C_{k}^{1/2}{\mathcal {N}}(0,I)\end{aligned}}}

ويمكن التعبير عنها بشكل مكافئ في "مساحة مشفرة" على النحو التالي: جك-1/2xأنا⏟ممثلة في مساحة التشفير∼ جك-1/2مك⏟+σك×شمال(0،أنا){\displaystyle \underbrace {C_{k}^{-1/2}x_{i}} _{{\text{represented in the encode space}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\sim \ \underbrace {C_{k}^{-1/2}m_{k}} {}+\sigma _{k}\times {\mathcal {N}}(0,I)}

تُعرّف مصفوفة التغاير تحويلاً تقابلياً (ترميزاً) لجميع متجهات الحلول في فضاءٍ يتم فيه أخذ العينات باستخدام مصفوفة تغاير الوحدة. ولأن معادلات التحديث في خوارزمية CMA-ES ثابتة تحت تحويلات نظام الإحداثيات الخطي، يُمكن إعادة كتابة هذه الخوارزمية كإجراء ترميز تكيفي يُطبق على استراتيجية تطور بسيطة ذات مصفوفة تغاير الوحدة. [ 9 ] لا يقتصر إجراء الترميز التكيفي هذا على الخوارزميات التي تأخذ عينات من توزيع طبيعي متعدد المتغيرات (مثل استراتيجيات التطور)، بل يُمكن من حيث المبدأ تطبيقه على أي طريقة بحث تكرارية.

الأداء في الممارسة

على عكس معظم الخوارزميات التطورية الأخرى ، فإن خوارزمية CMA-ES، من وجهة نظر المستخدم، شبه خالية من المعاملات. إذ يتعين على المستخدم اختيار نقطة حل أولية.م0∈Rن{\displaystyle m_{0}\in \mathbb {R} ^{n}}، وحجم الخطوة الأولية،σ0>0{\displaystyle \sigma _{0}>0}. اختيارياً، يمكن للمستخدم تعديل عدد العينات المرشحة λ (حجم السكان) لتغيير سلوك البحث المميز (انظر أعلاه) ويمكن أو ينبغي تعديل شروط الإنهاء لتناسب المشكلة المطروحة.

أثبتت خوارزمية CMA-ES نجاحها التجريبي في تطبيقات متنوعة، وتُعتبر مفيدة بشكل خاص مع دوال الهدف غير المحدبة، وغير القابلة للفصل، وسيئة التكييف، ومتعددة الأنماط، أو المشوشة. [ 10 ] وقد وجدت إحدى الدراسات الاستقصائية لخوارزميات التحسين ذات الصندوق الأسود أنها تفوقت على 31 خوارزمية تحسين أخرى، حيث حققت أداءً قويًا بشكل خاص على "الدوال الصعبة" أو مساحات البحث ذات الأبعاد الأكبر. [ 11 ]

يتراوح بُعد فضاء البحث عادةً بين اثنين وبضع مئات. بافتراض سيناريو تحسين الصندوق الأسود، حيث لا تتوفر التدرجات (أو لا تكون مفيدة) وتُعتبر تقييمات الدوال هي التكلفة الوحيدة المُعتبرة للبحث، فمن المرجح أن تتفوق الطرق الأخرى على طريقة CMA-ES في الظروف التالية:

  • على الدوال منخفضة الأبعاد، على سبيل المثالن<5{\displaystyle n<5}، على سبيل المثال عن طريق طريقة سيمبلكس المنحدرة أو الطرق القائمة على البدائل (مثل كريجينج مع التحسين المتوقع)؛
  • على الدوال القابلة للفصل بدون أو مع تبعيات ضئيلة فقط بين متغيرات التصميم، لا سيما في حالة تعدد الأنماط أو الأبعاد الكبيرة، على سبيل المثال عن طريق التطور التفاضلي ؛
  • على الدوال التربيعية المحدبة (تقريبًا) ذات رقم شرط منخفض أو متوسط ​​لمصفوفة هيسيان ، حيث تكون BFGS أو NEWUOA أو SLSQP أسرع عادةً بعشر مرات على الأقل؛
  • بالنسبة للدوال التي يمكن حلها بالفعل بعدد قليل نسبيًا من عمليات تقييم الدالة، على سبيل المثال لا الحصر10ن{\displaystyle 10n}، حيث يكون CMA-ES أبطأ في كثير من الأحيان من، على سبيل المثال، NEWUOA أو البحث الإحداثي متعدد المستويات (MCS).

في الدوال القابلة للفصل، من المرجح أن يكون عيب الأداء أكثر وضوحًا، حيث قد لا يتمكن CMA-ES من إيجاد حلول قابلة للمقارنة على الإطلاق. من ناحية أخرى، في الدوال غير القابلة للفصل التي تكون سيئة التكييف أو صعبة الحل أو لا يمكن حلها إلا بأكثر من100ن{\displaystyle 100n}في تقييمات الوظائف، يُظهر CMA-ES في أغلب الأحيان أداءً متفوقًا.

التباينات والتوسعات

تُنتج خوارزمية (1+1)-CMA-ES [ 12 ] حلاً جديداً واحداً فقط في كل خطوة تكرارية، والذي يصبح متوسط ​​التوزيع الجديد إذا كان أفضل من المتوسط ​​الحالي.جج=1{\displaystyle c_{c}=1}تُعدّ خوارزمية (1+1)-CMA-ES صيغةً قريبةً من التكيف الغاوسي . بعض استراتيجيات التطور الطبيعي هي صيغ قريبة من خوارزمية CMA-ES مع إعدادات معلمات محددة. لا تستخدم استراتيجيات التطور الطبيعي مسارات التطور (أي في إعدادات خوارزمية CMA-ES).جج=جσ=1{\displaystyle c_{c}=c_{\sigma }=1}(ويقومون بإضفاء الطابع الرسمي على تحديث التباينات والتباينات المشتركة بناءً على عامل تشوليسكي بدلاً من مصفوفة التباين المشترك. كما تم توسيع خوارزمية CMA-ES لتشمل التحسين متعدد الأهداف تحت مسمى MO-CMA-ES. [ 13 ] ومن الإضافات البارزة الأخرى إضافة تحديث سلبي لمصفوفة التباين المشترك باستخدام ما يُعرف بخوارزمية CMA النشطة. [ 14 ] ويُعتبر استخدام تحديث CMA النشط الإضافي هو الخيار الافتراضي حاليًا. [ 7 ]

انظر أيضاً

مراجع

  1. ↑ هانسن، ن. (2006)، "استراتيجية تطور CMA: مراجعة مقارنة"، نحو حساب تطوري جديد. تطورات في تقدير خوارزميات التوزيع ، سبرينغر، ص 1769-1776 ، CiteSeerX 10.1.1.139.7369  
  2. ↑ أوجيه، أ.؛ ن. هانسن (2005). "استراتيجية تطور CMA لإعادة التشغيل مع زيادة حجم السكان" (ملف PDF) . وقائع مؤتمر IEEE للحوسبة التطورية لعام 2005. IEEE. الصفحات 1769-1776 . مؤرشف من الأصل (ملف PDF) بتاريخ 4 مارس 2016. تم الاطلاع عليه بتاريخ 13 يوليو 2012 . 
  3. ↑ شير، أوم؛ أ. يهودايوف (2020). "حول علاقة التغاير-هيسيان في استراتيجيات التطور" . علوم الحاسوب النظرية . 801. إلسيفير: 157-174 . arXiv : 1806.03674 . doi : 10.1016/j.tcs.2019.09.002 .
  4. 1 2 3 أكيموتو، ي.؛ ناغاتا، ي.؛ أونو، إ.؛ كوباياشي، س. (2010). "العلاقة ثنائية الاتجاه بين استراتيجيات تطور CMA واستراتيجيات التطور الطبيعي" . حل المشكلات المتوازية من الطبيعة، PPSN XI . سبرينغر. ص 154-163 . 
  5. 1 2 غلاسماتشرز، ت.؛ ت. شاول؛ ي. صن؛ د. ويرسترا؛ ج. شميدهوبر (2010). "استراتيجيات التطور الطبيعي الأسي" (ملف PDF) . مؤتمر الحوسبة الجينية والتطورية GECCO . بورتلاند، أوريغون.
  6. ↑ أوليفييه، ي.؛ أرنولد، ل.؛ أوجيه، أ.؛ هانسن، ن. (2017). "خوارزميات التحسين الهندسي للمعلومات: صورة موحدة عبر مبادئ الثبات" (ملف PDF) . مجلة أبحاث تعلم الآلة . 18 (18): 1-65.
  7. 1 2 هانسن، ن. (2016). "استراتيجية تطور CMA: دليل تعليمي". arXiv : 1604.00772 [ cs.LG ].
  8. ↑ جيسلر، أرماند (2024). التقارب الخطي لاستراتيجيات التطور مع تكييف مصفوفة التغاير (أطروحة دكتوراه). معهد البوليتكنيك في باريس.
  9. 1 2 هانسن، ن. (2008). "الترميز التكيفي: كيفية جعل نظام إحداثيات البحث ثابتًا" . حل المشكلات المتوازية من الطبيعة، PPSN X. سبرينغر. ص 205-214 . 
  10. ↑ "مراجع لتطبيقات CMA-ES" (ملف PDF) .
  11. ↑ هانسن، نيكولاس (2010). "مقارنة نتائج 31 خوارزمية من معيار تحسين الصندوق الأسود BBOB-2009" (PDF) .
  12. ↑ إيجل، سي.؛ تي. سوتورب؛ إن. هانسن (2006). "تحديث فعال حسابيًا لمصفوفة التغاير و(1+1)-CMA لاستراتيجيات التطور" (ملف PDF) . وقائع مؤتمر الحوسبة الجينية والتطورية (GECCO) . مطبعة ACM. الصفحات 453-460 . 
  13. ↑ إيجل، سي.؛ ن. هانسن؛ س. روث (2007). " تكييف مصفوفة التغاير لتحسين الأهداف المتعددة". الحوسبة التطورية . 15 (1): 1-28 . doi : 10.1162/evco.2007.15.1.1 . PMID 17388777. S2CID 7479494 .  
  14. ↑ جاستربسكي، جي إيه؛ دي في أرنولد (2006). "تحسين استراتيجيات التطور من خلال التكيف النشط لمصفوفة التغاير". وقائع المؤتمر العالمي لعام 2006 لمعهد مهندسي الكهرباء والإلكترونيات حول الذكاء الحسابي . معهد مهندسي الكهرباء والإلكترونيات. الصفحات 9719-9726 . doi : 10.1109/CEC.2006.1688662 . 

فهرس

  • هانسن ن، أوسترماير أ (2001). التكيف الذاتي غير العشوائي تمامًا في استراتيجيات التطور. الحوسبة التطورية ، 9 (2) ص  159-195.
  • هانسن ن، مولر إس دي، كوموتساكوس ب (2003). تقليل التعقيد الزمني لاستراتيجية التطور غير العشوائية باستخدام تكييف مصفوفة التغاير (CMA-ES). الحوسبة التطورية ، 11 (1) ص  1-18.
  • هانسن ن، كيرن س (2004). تقييم استراتيجية تطور CMA على دوال الاختبار متعددة الأنماط. في شين ياو وآخرون، المحررون، حل المشكلات المتوازية من الطبيعة - PPSN VIII ، الصفحات  282-291، سبرينغر.
  • إيجل سي، هانسن إن، روث إس (2007). تكييف مصفوفة التغاير لتحسين الأهداف المتعددة. الحوسبة التطورية ، 15 (1) ص  1-28.