طريقة الإنتروبيا المتقاطعة

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

تقوم هذه الطريقة بتقريب مقدر أخذ العينات الأمثل للأهمية عن طريق تكرار مرحلتين: ^{[ 1 ]}

1. اسحب عينة من توزيع احتمالي .
2. قلل من الانتروبيا المتقاطعة بين هذا التوزيع والتوزيع المستهدف لإنتاج عينة أفضل في التكرار التالي.

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

لننظر في المشكلة العامة المتمثلة في تقدير الكمية

${\displaystyle \ell =\mathbb {E} _{\mathbf {u} }[H(\mathbf {X} )]=\int H(\mathbf {x} )\,f(\mathbf {x}$ ;\mathbf {u} )\,{\textrm {d}}\mathbf {x} } ,

أين${\displaystyle H}$هي وظيفة أداء معينة و${\displaystyle f(\mathbf {x}$ يمثل ;\mathbf {u} )} أحد أفرادالتوزيعات البارامترية . وباستخدام أسلوب أخذ العينات المهمة، يمكن تقدير هذه الكمية على النحو التالي:

${\displaystyle {\hat {\ell }}={\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{g(\mathbf {X} _{i})}}}$،

أين${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$هي عينة عشوائية من${\displaystyle g\,}$. من أجل الإيجابية${\displaystyle H}$، تُعطى كثافة أخذ العينات المهمة المثلى نظريًا (PDF) بواسطة

${\displaystyle g^{*}(\mathbf {x} )=H(\mathbf {x})f(\mathbf {x}$ ;\mathbf {u} )/\ell } .

لكن هذا يعتمد على المجهول${\displaystyle \ell }$تهدف طريقة CE إلى تقريب دالة كثافة الاحتمال المثلى عن طريق اختيار أعضاء العائلة البارامترية الأقرب ( بمعنى كولباك-لايبير ) إلى دالة كثافة الاحتمال المثلى بشكل تكيفي${\displaystyle g^{*}}$.

1. اختر متجه المعلمات الأولية${\displaystyle \mathbf {v} ^{(0)}}$; اجعل t = 1.
2. قم بتوليد عينة عشوائية${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$من${\displaystyle f(\cdot$ ;\mathbf {v} ^{(t-1)})}
3. أوجد قيمة${\displaystyle \mathbf {v} ^{(t)}}$، أين$// )}{f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}}\log f(\mathbf {X} _{i};\mathbf {v} )}$
4. إذا تم الوصول إلى التقارب، فتوقف ؛ وإلا، فقم بزيادة t بمقدار 1 وكرر العملية من الخطوة 2.

في العديد من الحالات، يمكن إيجاد حل الخطوة 3 تحليليًا . ومن بين الحالات التي يحدث فيها ذلك:

• متى${\displaystyle f\,}$ينتمي إلى عائلة الدوال الأسية الطبيعية
• متى${\displaystyle f\,}$منفصلة ذات دعم محدود
• متى${\displaystyle H(\mathbf {X} )=\mathrm {I} _{\{\mathbf {x} \in A\}}}$و${\displaystyle f(\mathbf {X} _{i};\mathbf {u} )=f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}$، ثم${\displaystyle \mathbf {v} ^{(t)}}$يتوافق ذلك مع مقدر الاحتمال الأقصى بناءً على تلك${\displaystyle \mathbf {X} _{k}\in A}$.

يمكن استخدام خوارزمية CE نفسها للتحسين، بدلاً من التقدير. لنفترض أن المشكلة هي تعظيم دالة ما.${\displaystyle S}$، على سبيل المثال، ${\displaystyle S(x)={\textrm {e}}^{-(x-2)^{2}}+0.8\,{\textrm {e}}^{-(x+2)^{2}}}$لتطبيق طريقة التقدير المتقاطع، ينبغي أولاً النظر في المشكلة العشوائية المرتبطة بها والمتمثلة في تقدير ${\displaystyle \mathbb {P} _{\boldsymbol {\theta }}(S(X)\geq \gamma )}$لمستوى معين${\displaystyle \gamma \,}$، والعائلة البارامترية${\displaystyle \left\{f(\cdot$ ;{\boldsymbol {\theta }})\right\}} ، على سبيل المثال التوزيع الغاوسي أحادي البعد ، الذي يتم تحديده بواسطة متوسطه${\displaystyle \mu _{t}\,}$والتباين${\displaystyle \sigma _{t}^{2}}$(لذا${\displaystyle {\boldsymbol {\theta }}=(\mu ,\sigma ^{2})}$هنا). وبالتالي، بالنسبة لقيمة معينة${\displaystyle \gamma \,}$الهدف هو إيجاد${\displaystyle {\boldsymbol {\theta }}}$لهذا السبب. ${\displaystyle D_{\mathrm {KL}}({\textrm {I}}_{\{S(x)\geq \gamma \}}\|f_{\boldsymbol {\theta }})}$ يتم تقليلها. ويتم ذلك عن طريق حل نسخة العينة (النظير العشوائي) لمسألة تقليل تباعد كولباك-لايبير، كما في الخطوة 3 أعلاه. ويتضح أن المعلمات التي تقلل النظير العشوائي لهذا الاختيار لتوزيع الهدف والعائلة المعلمية هي متوسط ​​العينة وتباين العينة المقابلين للعينات النخبة ، وهي تلك العينات التي لها قيمة دالة الهدف${\displaystyle \geq \gamma }$ثم تُستخدم أسوأ عينة من العينات النخبوية كمعيار للمستوى في التكرار التالي. ينتج عن ذلك الخوارزمية العشوائية التالية التي تتطابق مع ما يُسمى بخوارزمية تقدير التوزيع الطبيعي متعدد المتغيرات (EMNA)، وهي خوارزمية لتقدير التوزيع .

// تهيئة المعلمات μ := −6 ​​σ 2 := 100 t := 0 الحد الأقصى := 100 ن := 100 Ne := 10 // طالما لم يتم تجاوز الحد الأقصى ولم يتم التقارب، طالما أن t < الحد الأقصى و σ² > ε ، // احصل على N عينة من توزيع المعاينة الحالي X := SampleGaussian( μ , σ² , N) // قيّم دالة الهدف عند نقاط المعاينة S := exp(−(X − 2) ^ 2) + 0.8 exp(−(X + 2) ^ 2) // فرز X حسب قيم دالة الهدف بترتيب تنازلي X := sort(X, S) // تحديث معلمات توزيع المعاينة عبر عينات النخبة μ := mean(X(1:Ne)) σ 2 := var(X(1:Ne)) t := t + 1 // إرجاع متوسط ​​توزيع المعاينة النهائي كحل return μ

• التلدين المحاكي
• الخوارزميات الجينية
• بحث عن الانسجام
• خوارزمية تقدير التوزيع
• بحث تابو
• استراتيجية التطور الطبيعي
• خوارزميات تحسين مستعمرات النمل

• الانتروبيا المتقاطعة
• تباعد كولباك-لايبير
• خوارزمية عشوائية
• أخذ العينات المهمة

• دي بوير، بي.-تي.، كروس، دي بي، مانور، إس. وروبنشتاين، آر واي (2005). دليل تعليمي حول طريقة الإنتروبيا المتقاطعة. حوليات بحوث العمليات ، 134 (1)، 19-67.
• روبنشتاين، آر واي (1997). تحسين نماذج المحاكاة الحاسوبية مع الأحداث النادرة، المجلة الأوروبية لبحوث العمليات ، 99 ، 89-112.

• حزمة CEopt Matlab
• حزمة CEoptim R
• مكتبة Novacta.Analytics .NET