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

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

यह विधि द्विचरणीय तकनीक का उपयोग करके उत्तम आवश्यक प्रतिदर्श प्राक्कलन कर्त्ता का अनुमान लगाता है:

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)}$ चुनें; t को 1 से सेट करें।.
2. $f(\cdot ;\mathbf {v} ^{(t-1)})$ से एक यादृच्छिक प्रतिदर्श $\mathbf {X} _{1},\dots ,\mathbf {X} _{N}$ उत्पन्न करें।
3. $\mathbf {v} ^{(t)}$ के लिए समस्या का हल करें, जहां
4. $\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} )$
5. यदि संघटन तक पहुंचा जाता है, तो रुकें; अन्यथा, 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))
    σ2X:= var(X(1:Ne))
    टी1:= टी + 1
// समाधान के रूप में अंतिम प्रतिदर्श     वितरण का रिटर्न माध्य
'वापसी' μ

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

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

यह भी देखें

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

जर्नल पेपर्स

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

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

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