วิธีครอสเอนโทรปี ( 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} }$,

โดยที่เป็นฟังก์ชันประสิทธิภาพ บางอย่าง และเป็นสมาชิกของตระกูลการแจกแจงแบบพาราเมตริกบางอย่าง โดยใช้การสุ่มตัวอย่างแบบสำคัญ (importance sampling)สามารถประมาณค่าปริมาณนี้ได้ดังนี้ ${\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})}}}$,

โดยที่เป็นตัวอย่างสุ่มจากสำหรับค่าบวกความหนาแน่นของการสุ่มตัวอย่างแบบสำคัญ (PDF) ที่เหมาะสมที่สุดในเชิงทฤษฎีจะกำหนดโดย ${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$${\displaystyle g\,}$${\displaystyle H}$

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

อย่างไรก็ตาม สิ่งนี้ขึ้นอยู่กับสิ่งที่ไม่ทราบแน่ชัดวิธีการ CE มีเป้าหมายเพื่อประมาณค่า PDF ที่เหมาะสมที่สุดโดยการเลือกสมาชิกของตระกูลพารามิเตอร์ที่ใกล้เคียงที่สุด (ในแง่ของKullback–Leibler ) กับ PDF ที่เหมาะสมที่สุด อย่างปรับเปลี่ยน ได้ ${\displaystyle \ell }$${\displaystyle g^{*}}$

1. เลือกเวกเตอร์พารามิเตอร์เริ่มต้นตั้งค่า t = 1${\displaystyle \mathbf {v} ^{(0)}}$
2. สร้างตัวอย่างแบบสุ่มจาก${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$${\displaystyle f(\cdot ;\mathbf {v} ^{(t-1)})}$
3. แก้สมการหาค่าโดยที่${\displaystyle \mathbf {v} ^{(t)}}$${\displaystyle \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 ได้โดยใช้วิธีการวิเคราะห์สถานการณ์ที่เกิดกรณีเช่นนี้ได้แก่

• เมื่อจัดอยู่ในกลุ่มเลขชี้กำลังธรรมชาติ${\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 เดียวกันนี้สามารถใช้สำหรับการปรับให้เหมาะสมที่สุด แทนที่จะเป็นการประมาณค่า สมมติว่าปัญหาคือการหาค่าสูงสุดของฟังก์ชันบางอย่างเช่น เพื่อใช้ CE ก่อนอื่นต้องพิจารณาปัญหาเชิงสุ่มที่เกี่ยวข้องกับการประมาณค่า สำหรับระดับ ที่กำหนด และตระกูลพารามิเตอร์เช่น การแจกแจงแบบเกาส์ เซียน 1 มิติ ซึ่งมีพารามิเตอร์เป็นค่าเฉลี่ยและความแปรปรวน(ดังนั้นในที่นี้คือ ) ดังนั้น สำหรับค่า ที่กำหนดเป้าหมายคือการหาค่าเพื่อ ให้ มีค่าน้อยที่สุด ซึ่งทำได้โดยการแก้ปัญหาการลดค่าความแตกต่าง KL ในเวอร์ชันตัวอย่าง (เวอร์ชันเชิงสุ่ม) ดังขั้นตอนที่ 3 ข้างต้น ปรากฏว่าพารามิเตอร์ที่ลดค่าเวอร์ชันเชิงสุ่มสำหรับตัวเลือกการแจกแจงเป้าหมายและตระกูลพารามิเตอร์นี้ คือค่าเฉลี่ยตัวอย่างและความแปรปรวนตัวอย่างที่สอดคล้องกับตัวอย่างชั้นยอดซึ่งเป็นตัวอย่างที่มีค่าฟังก์ชันเป้าหมายเท่ากับ จากนั้นจะใช้ตัวอย่างชั้นยอดที่แย่ที่สุดเป็นพารามิเตอร์ระดับสำหรับการวนซ้ำครั้งต่อไป ผลลัพธ์ที่ได้คืออัลกอริทึมแบบสุ่มต่อไปนี้ ซึ่งบังเอิญตรงกับสิ่งที่เรียกว่า อัลกอริทึมการประมาณค่าการกระจายแบบปกติหลายตัวแปร (EMNA) ซึ่งเป็นอั ลกอริทึมการประมาณค่าการกระจาย${\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 {\boldสัญลักษณ์ {\theta }}}$${\displaystyle D_{\mathrm {KL} }({\textrm {I}__{\{S(x)\geq \gamma \}}\|f_{\boldสัญลักษณ์ {\theta }})}$${\displaystyle \geq \gamma }$

// กำหนดค่าเริ่มต้นให้กับพารามิเตอร์ μ := −6 σ2 := 100 t := 0 maxits := 100 N := 100 Ne := 10 // ในขณะที่ค่า maxits ยังไม่เกินและยังไม่บรรจบกันในขณะที่ t < maxits และ σ2 > ε ให้ทำ// สุ่มตัวอย่าง N ตัวอย่างจากการกระจายการสุ่มตัวอย่างปัจจุบัน X := ตัวอย่างเกาส์เซียน(μ, σ2, N) // ประเมินฟังก์ชันเป้าหมาย ณ จุดที่สุ่มมา S := exp(−(X − 2) ^ 2) + 0.8 exp(−(X + 2) ^ 2) // เรียงลำดับ X ตามค่าฟังก์ชันเป้าหมายจากมากไปน้อย X := เรียงลำดับ (X, S) // อัปเดตพารามิเตอร์ของการกระจายตัวอย่างผ่านตัวอย่างชั้นยอด μ := mean(X(1:Ne)) σ2 := var(X(1:Ne)) t := t + 1 // ส่งคืนค่าเฉลี่ยของการกระจายตัวอย่างสุดท้ายเป็นผลลัพธ์ μ 

• การอบอ่อนจำลอง
• อัลกอริทึมทางพันธุกรรม
• การค้นหาฮาร์โมนี
• อัลกอริทึมการประมาณค่าการกระจาย
• การค้นหาต้องห้าม
• กลยุทธ์วิวัฒนาการตามธรรมชาติ
• อัลกอริทึมการเพิ่มประสิทธิภาพอาณานิคมมด

• เอนโทรปีไขว้
• ความแตกต่าง Kullback–Leibler
• อัลกอริทึมแบบสุ่ม
• การสุ่มตัวอย่างแบบสำคัญ

• De Boer, P.-T., Kroese, DP, Mannor, S. และ Rubinstein, RY (2005). บทช่วยสอนเกี่ยวกับวิธี Cross-Entropy. Annals of Operations Research , 134 (1), 19–67. [1]
• Rubinstein, RY (1997). การเพิ่มประสิทธิภาพของแบบจำลองการจำลองด้วยคอมพิวเตอร์ที่มีเหตุการณ์หายาก, European Journal of Operational Research , 99 , 89–112.

• แพ็คเกจCEopt Matlab
• แพ็คเกจ CEoptim R
• ไลบรารีNovacta.Analytics .NET