क्रॉस-एन्ट्रॉपी विधि

क्रॉस-एंट्रॉपी (सीई) विधि महत्व नमूनाकरण और अनुकूलन (गणित) के लिए एक मोंटे कार्लो विधि विधि है। यह स्थिर या शोर वाले उद्देश्य के साथ संयोजन अनुकूलन और सतत अनुकूलन समस्याओं दोनों पर लागू होता है।

विधि दो चरणों को दोहराकर इष्टतम महत्व नमूना अनुमानक का अनुमान लगाती है:

1. संभाव्यता वितरण से एक नमूना बनाएं।
2. अगले पुनरावृत्ति में बेहतर नमूना तैयार करने के लिए इस वितरण और लक्ष्य वितरण के बीच क्रॉस-एन्ट्रॉपी|क्रॉस-एन्ट्रॉपी को कम करें।

रूवेन रुबिनस्टीन ने दुर्लभ घटना सिमुलेशन के संदर्भ में विधि विकसित की, जहां छोटी संभावनाओं का अनुमान लगाया जाना चाहिए, उदाहरण के लिए नेटवर्क विश्वसनीयता विश्लेषण, कतारबद्ध मॉडल, या दूरसंचार प्रणालियों के प्रदर्शन विश्लेषण में। यह विधि ट्रैवलिंग सेल्समैन की समस्या, द्विघात असाइनमेंट समस्या, अनुक्रम संरेखण, मैक्सकट|मैक्स-कट और बफर आवंटन समस्याओं पर भी लागू की गई है।

महत्व नमूने के माध्यम से अनुमान

मात्रा का अनुमान लगाने की सामान्य समस्या पर विचार करें

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

कहाँ $H$ कुछ प्रदर्शन समारोह है और $f(\mathbf {x} ;\mathbf {u} )$ वितरण के कुछ पैरामीट्रिक परिवार का सदस्य है। महत्व नमूने का उपयोग करके इस मात्रा का अनुमान लगाया जा सकता है

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

कहाँ $\mathbf {X} _{1},\dots ,\mathbf {X} _{N}$ से एक यादृच्छिक नमूना है $g\,$. सकारात्मक के लिए $H$, सैद्धांतिक रूप से इष्टतम महत्व नमूना संभाव्यता घनत्व फ़ंक्शन (पीडीएफ) द्वारा दिया गया है

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

हालाँकि, यह अज्ञात पर निर्भर करता है $\ell$. सीई विधि का लक्ष्य पैरामीट्रिक परिवार के उन सदस्यों का अनुकूलनपूर्वक चयन करके इष्टतम पीडीएफ का अनुमान लगाना है जो इष्टतम पीडीएफ के सबसे करीब हैं (कुलबैक-लीबलर विचलन | कुलबैक-लीबलर अर्थ में)। $g^{*}$.

जेनेरिक सीई एल्गोरिदम

1. प्रारंभिक पैरामीटर वेक्टर चुनें $\mathbf {v} ^{(0)}$; सेट टी = 1.
2. एक यादृच्छिक नमूना उत्पन्न करें $\mathbf {X} _{1},\dots ,\mathbf {X} _{N}$ से $f(\cdot ;\mathbf {v} ^{(t-1)})$
3. के लिए हल $\mathbf {v} ^{(t)}$, कहां
   $\mathbf {v} ^{(t)}=\mathop {\textrm {argmax}} _{\mathbf {v} }{\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})}}\log f(\mathbf {X} _{i};\mathbf {v} )$
4. अगर सहमति बन जाए तो रुक जाओ; अन्यथा, t को 1 से बढ़ाएँ और चरण 2 से दोहराएँ।

कई मामलों में, चरण 3 का समाधान विश्लेषणात्मक रूप से पाया जा सकता है। जिन स्थितियों में ऐसा होता है वे हैं

• कब $f\,$ घातीय परिवार से संबंधित है
• कब $f\,$ परिमित समर्थन के साथ पृथक स्थान है (गणित)
• कब $H(\mathbf {X} )=\mathrm {I} _{\{\mathbf {x} \in A\}}$ और $f(\mathbf {X} _{i};\mathbf {u} )=f(\mathbf {X} _{i};\mathbf {v} ^{(t-1)})$, तब $\mathbf {v} ^{(t)}$ उनके आधार पर अधिकतम संभावना से मेल खाती है $\mathbf {X} _{k}\in A$.

सतत अनुकूलन—उदाहरण

अनुमान के बजाय अनुकूलन के लिए समान सीई एल्गोरिदम का उपयोग किया जा सकता है। मान लीजिए कि समस्या किसी फ़ंक्शन को अधिकतम करने की है $S$, उदाहरण के लिए,

$S(x)={\textrm {e}}^{-(x-2)^{2}}+0.8\,{\textrm {e}}^{-(x+2)^{2}}$.

सीई को लागू करने के लिए, पहले अनुमान लगाने की संबंधित स्टोकेस्टिक समस्या पर विचार किया जाता है $\mathbb {P} _{\boldsymbol {\theta }}(S(X)\geq \gamma )$ किसी दिए गए स्तर के लिए $\gamma \,$, और पैरामीट्रिक परिवार $\left\{f(\cdot ;{\boldsymbol {\theta }})\right\}$, उदाहरण के लिए 1-आयामी गाऊसी वितरण, इसके माध्य द्वारा मानकीकृत $\mu _{t}\,$ और विचरण $\sigma _{t}^{2}$ (इसलिए ${\boldsymbol {\theta }}=(\mu ,\sigma ^{2})$ यहाँ)। इसलिए, किसी दिए गए के लिए $\gamma \,$, लक्ष्य खोजना है ${\boldsymbol {\theta }}$ ताकि $D_{\mathrm {KL} }({\textrm {I}}_{\{S(x)\geq \gamma \}}\|f_{\boldsymbol {\theta }})$ न्यूनतम किया गया है. यह केएल विचलन न्यूनीकरण समस्या के नमूना संस्करण (स्टोकेस्टिक समकक्ष) को हल करके किया जाता है, जैसा कि ऊपर चरण 3 में है। यह पता चला है कि पैरामीटर जो लक्ष्य वितरण की इस पसंद के लिए स्टोकेस्टिक समकक्ष को कम करते हैं और पैरामीट्रिक परिवार विशिष्ट नमूनों के अनुरूप नमूना माध्य और नमूना विचरण हैं, जो वे नमूने हैं जिनका उद्देश्य फ़ंक्शन मान है $\geq \gamma$. फिर विशिष्ट नमूनों में से सबसे खराब को अगले पुनरावृत्ति के लिए स्तर पैरामीटर के रूप में उपयोग किया जाता है। यह निम्नलिखित यादृच्छिक एल्गोरिदम उत्पन्न करता है जो वितरण एल्गोरिदम के तथाकथित अनुमान मल्टीवेरिएट नॉर्मल एल्गोरिदम (ईएमएनए) के साथ मेल खाता है।

छद्मकोड

//प्रारंभिक पैरामीटर
μ := −6
σ2 := 100
टी := 0
अधिकतम := 100
एन := 100
ने :=10
// जबकि अधिकतम सीमा पार नहीं हुई है और अभिसरण नहीं हुई है
'जबकि' t < अधिकतम 'और' σ2 > ε 'करें'
    // वर्तमान नमूना वितरण से एन नमूने प्राप्त करें
    एक्स := नमूनागौसियन(μ, σ2, एन)
    // नमूना बिंदुओं पर वस्तुनिष्ठ फ़ंक्शन का मूल्यांकन करें
    S := exp(-(X − 2) ^ 2) + 0.8 exp(-(X + 2) ^ 2)
    // वस्तुनिष्ठ फ़ंक्शन मानों के आधार पर X को अवरोही क्रम में क्रमबद्ध करें
    एक्स := सॉर्ट करें (एक्स, एस)
    // नमूना वितरण के अद्यतन पैरामीटर
    μ := माध्य(X(1:Ne))
    σ2 := var(X(1:Ne))
    टी := टी + 1
// समाधान के रूप में अंतिम नमूना वितरण का रिटर्न माध्य
'वापसी' μ

संबंधित विधियाँ

• तैयार किए हुयी धातु पे पानी चढाने की कला
• आनुवंशिक एल्गोरिदम
• सद्भाव खोज
• वितरण एल्गोरिदम का अनुमान
• तब्बू सर्च
• प्राकृतिक विकास रणनीति

यह भी देखें

• क्रॉस एन्ट्रापी
• कुल्बैक-लीब्लर विचलन
• यादृच्छिक एल्गोरिदम
• महत्व नमूनाकरण

जर्नल पेपर्स

• डी बोअर, पी-टी., क्रोसे, डी.पी., मैन्नोर, एस. और रुबिनस्टीन, आर.वाई. (2005)। क्रॉस-एन्ट्रॉपी विधि पर एक ट्यूटोरियल। एनल्स ऑफ ऑपरेशंस रिसर्च, '134' (1), 19-67।[1]
• रुबिनस्टीन, आर.वाई. (1997)। दुर्लभ घटनाओं के साथ कंप्यूटर सिमुलेशन मॉडल का अनुकूलन, यूरोपियन जर्नल ऑफ ऑपरेशनल रिसर्च, '99', 89-112।

सॉफ़्टवेयर कार्यान्वयन

• CEoptim R पैकेज
• नोवाक्टा.एनालिटिक्स .NET लाइब्रेरी