วิธีการครอส-เอนโทรปี

วิธีครอส-เอนโทรปี (อังกฤษ: Cross-Entropy Method) เป็นขั้นตอนวิธีที่ใช้หลักการของ Monte Carlo เพื่อที่จะแก้ปัญหา ถูกนำเสนอโดย R.Y. Rubinstein ซึ่งประเภทของปัญหาที่สามารถใช้วิธีครอส-เอนโทรปีได้นั้นจะมีอยู่สองลักษณะ คือ การประมาณค่า หรือ การหาค่าที่ดีที่สุด โดยวิธีการนี้ถูกประยุกต์ใช้ในปัญหาเชิงวิศวกรรม และวิทยาศาสตร์มากมาย

ภาพรวมของวิธีครอส-เอนโทรปี

วิธีการครอส-เอนโทรปีนั้นถูกพัฒนาขึ้นโดย Reuven Y. Rubinstein ซึ่งเป็นนักวิทยาศาสตร์ชาวอิสราเอลที่ให้ความสนใจทางด้านการพัฒนาขั้นตอนวิธีเชิงสถิติมากมาย เขียนหนังสือหกเล่มและตีพิมพ์ผลงานกว่าร้อยผลงาน ซึ่งแน่นอนว่าวิธีการครอส-เอนโทรปีเป็นหนึ่งในขั้นตอนวิธีเชิงสถิติเหล่านั้นเช่นกัน โดยเป็นขั้นตอนวิธีที่มีประสิทธิภาพตัวหนึ่งที่ใช้สำหรับปัญหาการประมาณค่าความน่าจะเป็นของเหตุการณ์ที่พบเจอได้ยาก (rare-event probability) ปัญหาการหาค่าที่เหมาะสมที่สุดเชิงการจัด (combinatorial optimization)

วิธีการครอสเอนโทรปีนั้นได้ชื่อมาจาก "ระยะห่างครอส-เอนโทรปี" ซึ่งเป็นการหาระยะห่างระหว่าง "ข้อมูล" ที่ใช้กันแพร่หลายในทางวิทยาศาสตร์และวิศวกรรมกว่าศตวรรษ

วิธีการครอส-เอนโทรปีนั้นถูกนำไปใช้ในปัญหาการหาค่าที่เหมาะสมที่สุดเชิงการจัดมากมาย เช่น ปัญหาการตัดที่มากที่สุด (Maximum Cut Problem) ปัญหาการหาเส้นทางเดินของพนักงานขาย (Traveling Salesman Problem) ปัญหาการหากราฟย่อยบริบูรณ์ที่มีขนาดใหญ่ที่สุดในกราฟ (Clique Problem) และปัญหาต่างๆอีกมากมาย และจุดเด่นพิเศษอีกอย่างหนึ่งสำหรับวิธีการครอส-เอนโทรปีคือ สามารถหาค่าที่เหมาะสมที่สุดสำหรับปัญหาที่มีค่ารบกวน (noisy problem) ได้ เพราะลักษณะขั้นตอนวิธีแก้ปัญหาที่เป็นเชิงสถิตินั่นเอง

วิธีการครอสเอนโทรปีนั้นสามารถแตกขั้นตอนที่สำคัญออกได้เป็นสองส่วน คือ

1. ขั้นสุ่มตัวอย่าง (Generate) จะสร้างตัวอย่างจากความหนาแน่นของความน่าจะเป็นที่ได้มาจากการคำนวณในขั้นตอนวิธี
2. ขั้นปรับปรุง (Update) ปรับพารามิเตอร์บางอย่าง เพื่อให้การสุ่มครั้งต่อไป ได้ตัวอย่างที่ดีขึ้นไปอีก
   

ประเด็นสำคัญสำหรับวิธีการครอส-เอนโทรปี คือ จะนิยามขั้นตอนในเชิงคณิตศาสตร์อย่างไรให้สามารถปรับปรุงค่าพารามิเตอร์เพื่อให้เข้าใกล้ค่าที่เหมาะสมได้อย่างรวดเร็ว

ในด้านของการประมาณค่าความน่าจะเป็นของเหตุการณ์ที่พบเจอได้ยากนั้น วิธีการครอส-เอนโทรปีจะใช้ร่วมกับกลวิธีการสุ่มตัวอย่างสำคัญ (Importance Sampling Technique) วิธีการครอส-เอนโทรปีจะปรับค่าของพารามิเตอร์ซ้ำๆ หลายๆรอบเพื่อให้เข้าใกล้ค่าที่เหมาะสมที่สุด ปัญหาที่ประยุกต์วิธีนี้ตัวอย่างเช่นปัญหาการวัดประสิทธิภาพในระบบเครือข่ายทางคมนาคม หรือ ระบบที่ต้องการความน่าเชื่อถือ

การใช้วิธี ครอส-เอนโทรปี ในปัญหาการประมาณค่า

แนวคิด

ในกรณีที่เราพยายามที่จะใช้วิธีครอส-เอนโทรปีเพื่อประมาณค่านั้น สามารถแปลงปัญหาเป็นสมการคณิตศาสตร์ของการประมาณหาค่าคาดหวังง่ายๆได้ดังสมการที่ (1)

${\displaystyle \ell =\mathbb {E} _{f}[H(X)]=\int H(x)f(x)\,dx}$  (1)

เมื่อ H คือฟังก์ชันที่เราต้องการประมาณค่า เรียกได้อีกอย่างหนึ่งว่า ฟังก์ชันของประสิทธิภาพของตัวอย่างสุ่ม
และ f คือฟังก์ชันของความหนาแน่นของความน่าจะเป็นของตัวแปรสุ่ม X

ซึ่งสำหรับวิธีการประมาณค่า ${\displaystyle l}$  ในสมการที่ 1 นั้น ในกรณีที่สามารถสุ่มตัวอย่างสุ่มด้วยความหนาแน่นของความน่าจะเป็น ${\displaystyle f(x)}$  ได้ยาก จะทำการสร้างฟังก์ชัน ${\displaystyle f(x)}$  เพื่อที่จะสามารถประมาณค่าได้ง่ายขึ้นตามสมการที่ 2

${\displaystyle \ell =\int H(x){\frac {f(x)}{g(x)}}g(x)\,dx=\mathbb {E} _{g}[H(x){\frac {f(x)}{g(x)}}]}$  (2)

โดยที่กำหนดให้

${\displaystyle g(x)=0\,}$  เมื่อ ${\displaystyle H(x)f(x)=0\,}$ 

เนื่องจาก g เป็นความหนาแน่นของความน่าจะเป็นที่เราเป็นคนสร้างขึ้น ทำให้การสุ่มตัวอย่างเป็นไปได้ง่ายกว่า f ดังนั้น เราจึงสามารถสุ่มตัวอย่างสุ่ม ${\displaystyle X_{1},...,X_{N}}$  ตามความหนาแน่นของความน่าจะเป็นของ g(x) ได้ง่ายกว่า ทำให้ประมาณค่าของ l ด้วยตัวประมาณค่าที่ไม่ลำเอียงได้ง่ายขึ้นตามสมการที่ (3)

${\displaystyle {\widehat {\ell }}={\frac {1}{N}}\sum _{k=1}^{N}H(X_{k}){\frac {f(X_{k})}{g(X_{k})}}}$  (3)

จากปัญหาการประมาณค่า ก็จะเหลือแค่ปัญหาว่าจะสร้างความหนาแน่นของความน่าจะเป็น g ที่ดีที่สุดได้อย่างไรซึ่งค่า g ที่ดีที่สุดในอุดมคตินั้นนิยามด้วย

${\displaystyle g^{*}(x)\alpha |H(x)|f(x)\,}$ 

แต่สิ่งที่เกิดขึ้นก็คือ เราสามารถหาค่า g*(x) ได้ยาก สำหรับวิธีครอส-เอนโทรปีนี้แทนที่จะมุ่งไปที่การหาค่าของ g*(x) จะพยายามหาค่าของ g ที่ทำให้ความแตกต่างระหว่าง g และ g* น้อยที่สุด ซึ่งความแตกต่างนั้นเองที่เรียกว่าครอส-เอนโทรปีตามที่เกริ่นไว้ในช่วงต้น ซึ่งครอส-เอนโทรปีของความหนาแน่นของความน่าจะเป็นของสองฟังก์ชันนั้น นิยามได้ดังสมการที่ (4)

${\displaystyle D(f,g)=\mathbb {E} _{f}[ln{\frac {f(X)}{g(X)}}]=\int f(x)ln(f(x))dx-\int f(x)ln(g(x))dx}$  (4)

หลังจากที่ได้รู้หลักการคร่าวๆของวิธีการครอส-เอนโทรปีเพื่อการประมาณค่าในทางทฤษฎีไปแล้วว่าเป็นไปในลักษณะอย่างไร หากพิจารณาในทางปฏิบัติแล้วนั้นฟังก์ชัน f นอกจากจะแปรไปตามตัวแปรต้น x แล้ว ยังถูกควบคุมโดยพารามิเตอร์ u บางอย่าง ซึ่งสามารถเขียนฟังก์ชัน f ได้เป็น f(x; u) ซึ่งคงเดาได้ไม่ยากว่าบางกรณีนั้น พารามิเตอร์ u นี้หาได้ยากมาก เราจึงพยายามหาค่าของ g ที่ทำให้มี v ที่ทำให้ g(x) = f(x; v) และ v ทำให้ความแตกต่างของ f(x; v) และ f(x; u) น้อยๆ ซึ่งความแตกต่างนี้วัดโดยครอส-เอนโทรปีตามสมการที่ 4 นั่นเอง ก็จะทำให้ปัญหาเล็กลงอีกขั้นหนึ่งคือเป็นปัญหาที่จะพยายามหาค่าของ v ที่ดีที่สุดเท่านั้น ซึ่งนิยาม v ในอุดมคติว่า v* ลองไปแทนค่าของ f(x; v) และ f(x; u) ลงในสมการที่ (4) แล้วจัดรูปสักเล็กน้อยก็จะรู้ว่า v ที่ดีที่สุดจะทำให้ ${\displaystyle \int H(x)f(x;u)ln(f(x;v))dx\,}$  มีค่ามากที่สุดนั่นเอง ซึ่งการแก้ปัญหานี้ก็สามารถหาได้ตามสมการที่ (5)

${\displaystyle max_{v}({\frac {1}{N}}\sum _{k=1}^{N}H(X_{k}){\frac {f(X_{k};u)}{f(X_{k};w)}}ln(f(X_{k};v))\,}$  (5)

ซึ่งจากสมการที่ (5) R. Y. Rubinstein ได้นำเสนอวิธีสำหรับแก้ปัญหานี้ไว้แล้ว
ในปัญหาเฉพาะที่ชื่อว่าปัญหาการหาความน่าจะเป็นของเหตุการณ์ที่พบเจอได้ยาก(rare event probability) ซึ่งเป็นปัญหาที่ประยุกต์ด้วยวิธีครอส-เอนโทรปีกันอย่างแพร่หลาย โดยเป็นกรณีเฉพาะที่ฟังก์ชัน H เป็นฟังก์ชันตัวชี้ของฟังก์ชัน ${\displaystyle S(x)}$  วัดที่ระดับ ${\displaystyle \gamma }$  ตามสมการ ${\displaystyle H(x)=I_{S(X)\geq \gamma }}$  ซึ่งในการประมาณค่าของ ${\displaystyle \ell }$  ด้วยวิธีเดิมเพื่อหาความน่าจะเป็นที่ ${\displaystyle S(x)\geq \gamma }$  นั้นจะยากโดยดูได้จากสมการที่ (5) คือค่าของ ${\displaystyle H(X_{k})}$  ส่วนมากจะมีค่าเป็น 0 ไปมากพอสมควรจะไม่สามารถประมาณหาค่าที่แม่นยำได้ วิธีการแก้ไขคือต้องทำวิธีการ ครอส-เอนโทรปีหลายๆรอบ หลายๆชั้น โดยจะปรับค่าพารามิเตอร์ v และระดับปัจจุบันให้เข้าใกล้ v* และ ${\displaystyle \gamma }$  ไปเรื่อยๆจนถึงเงื่อนไขยุติที่พอใจ สามารถเขียนขั้นตอนวิธีตามที่ได้อธิบายมาเป็นรหัสเทียมได้ดังนี้

รหัสเทียมสำหรับวิธีครอส-เอนโทรปีเพื่อประมาณความน่าจะเป็นสำหรับเหตุการณ์ที่พบเจอได้ยาก

 1 ${\displaystyle {\widehat {v}}_{0}=u}$  และ 2 ${\displaystyle N^{e}=\lceil \rho \,N\rceil }$  3 t = 0 /*ตัวนับจำนวนรอบ*/ 4 5 ทำ 6 t = t + 1 7 สุ่มตัวอย่างสุ่ม ${\displaystyle X_{1},...,X_{N}\,}$  ตามความหนาแน่นของความน่าจะเป็น ${\displaystyle f(-:{\widehat {v}}_{t-1})\,}$  8 สำหรับทุก i ตั้งแต่ 1 ถึง N 9 ${\displaystyle S_{(i)}=S(X_{i})\,}$  10 เรียงลำดับจากน้อยไปหามาก(S) 11 ${\displaystyle {\widehat {\gamma }}_{t}=S_{(N-N^{e}+1)}\,}$  12 ${\displaystyle {\widehat {\gamma }}_{t}\,}$  = ค่าต่ำสุด(${\displaystyle \gamma \,}$ ,${\displaystyle {\widehat {\gamma }}_{t}}$ ) 13 คำนวณ ${\displaystyle {\widehat {v}}_{t}}$  จากสมการ (5) ด้วย ${\displaystyle X_{1},...,X_{N}}$  และ ${\displaystyle w={\widehat {v}}_{t-1}}$  14 ระหว่างที่ ${\displaystyle {\widehat {\gamma }}_{t}<\gamma }$  15 16 สุ่มตัวอย่างสุ่ม ${\displaystyle X_{1},...,X_{N_{1}}\,}$  ตามความหนาแน่นของความน่าจะเป็น ${\displaystyle f(-:{\widehat {v}}_{t})}$  17 คำนวณ ${\displaystyle \ell }$  จากสมการ (3) ด้วย ${\displaystyle X_{1},...,X_{N_{1}}\,}$  18 คืนค่า ${\displaystyle \ell }$  

จะเห็นว่าหากต้องการใช้ขั้นตอนวิธีนี้ต้องทำการปรับค่า ${\displaystyle {\widehat {v}}_{0},N,\rho }$  ให้เหมาะสมกับความต้องการ ซึ่งโดยปกติ ${\displaystyle \rho }$  จะมีค่าอยู่ระหว่าง 0.01 และ 0.1 และค่าของ ${\displaystyle N}$  จะน้อยว่า ${\displaystyle N_{1}}$  มากๆ เช่น ${\displaystyle N=10000}$  ในขณะที่ ${\displaystyle N_{1}=100000}$  และขั้นตอนวิธีนี้จะรับประกันว่าสามารถทำงานจนจบได้แน่นอนหากค่าของ ${\displaystyle \rho }$  มีค่าเล็กมากพอ

การใช้วิธี ครอส-เอนโทรปี ในปัญหาการหาค่าที่เหมาะสมที่สุด

แนวคิด

ให้ ${\displaystyle \chi }$  เป็นเซตของสถานะ และ S เป็นฟังก์ชันจริงซึ่ง S(x) จะให้ค่าความเหมาะสมของ x โดยที่ x เป็นสมาชิกของ ${\displaystyle \chi }$  โดยค่า x ที่เหมาะสมที่สุดคือ x* ซึ่งจะทำให้ค่าของ S(x*) มีค่าสูงที่สุด สามารถเขียนเป็นปัญหาในรูปของสมการทางคณิตศาสตร์ได้ดังสมการที่ (6)

${\displaystyle S(x^{*})=\gamma ^{*}=max_{x}S(x)\,}$  (6)

หาพิจารณาปัญหานี้เทียบกับปัญหาการประมาณค่าของ ${\displaystyle H(x)=I_{S(X)\geq \gamma }}$  เมื่อ X เป็นตัวแปรสุ่มที่มีความหนาแน่นของความน่าจะเป็น ${\displaystyle f(x;u)}$  และให้ ${\displaystyle \gamma }$  เป็นค่าระดับชั้น จะสังเกตว่าถ้าค่า ${\displaystyle \gamma }$  มีค่าใกล้เคียงกับ ${\displaystyle \gamma ^{*}}$  (ค่าสูงสุดของ S) แล้ว จะทำให้ค่าของ ${\displaystyle H(x)=I_{S(X)\geq \gamma }}$  เป็นความน่าจะเป็นของเหตุการณ๊ที่พบเจอได้ยาก ซึ่งปัญหานี้เราจะต้องการสร้างตัวอย่างสุ่มจำนวนหนึ่งที่มีค่าใกล้เคียงกับ x* โดยเป็นเรื่องที่ดีที่วิธีครอส-เอนโทรปี สามารถทำเรื่องนี้ได้

หากเปรียบเทียบความแตกต่างของปัญหาระหว่างการหาค่าที่เหมาะสมที่สุด กับ การประมาณค่า ความแตกต่างก็คือการหาค่าที่เหมาะสมที่สุด เราจะไม่รู้ค่าของระดับชั้น ${\displaystyle \gamma =\gamma ^{*}}$  ล่วงหน้าเหมือนในการประมาณค่า แต่อย่างไรก็ตามขั้นตอนวิธีในการแก้ปัญหาก็ไ่ม่ค่อยแตกต่างกันมากคือเราจะสร้างลำดับของ ${\displaystyle \gamma _{t}}$  และ ${\displaystyle {\widehat {v}}_{t}}$  ไปเรื่อยๆ โดยจะพยายามให้ทั้งสองค่าเข้าใกล้ ${\displaystyle \gamma ^{*}}$  และ ${\displaystyle v^{*}}$  ตามลำดับ ซึ่งค่าของ ${\displaystyle v^{*}}$  จะสอดคล้องกับค่าของ ${\displaystyle x^{*}}$  ที่ต้องการหาเช่นกัน

รหัสเทียมสำหรับวิธีครอส-เอนโทรปีเพื่อใช้ในปัญหาการหาค่าที่เหมาะสมที่สุด

 1 ${\displaystyle {\widehat {v}}_{0}=u}$  และ 2 ${\displaystyle N^{e}=\lceil \rho \,N\rceil }$  3 t = 0 /*ตัวนับจำนวนรอบ*/ 4 5 ทำ 6 t = t + 1 7 สุ่มตัวอย่างสุ่ม ${\displaystyle X_{1},...,X_{N}\,}$  ตามความหนาแน่นของความน่าจะเป็น ${\displaystyle f(-:{\widehat {v}}_{t-1})\,}$  8 สำหรับทุก i ตั้งแต่ 1 ถึง N 9 ${\displaystyle S_{(i)}=S(X_{i})\,}$  10 เรียงลำดับจากน้อยไปหามาก(S) 11 ${\displaystyle {\widehat {\gamma }}_{t}=S_{(N-N^{e}+1)}\,}$  12 ${\displaystyle {\widehat {\gamma }}_{t}\,}$  = ค่าต่ำสุด(${\displaystyle \gamma \,}$ ,${\displaystyle {\widehat {\gamma }}_{t}}$ ) 13 คำนวณ ${\displaystyle v={\widehat {v}}_{t}\,}$  ที่ทำให้ ${\displaystyle {\frac {I_{S(X_{k})\geq {\widehat {\gamma }}_{t}}ln(f(X_{k};v))}{N}}}$  สูงที่สุด 14 ระหว่างที่ ยังไม่ถึงเงื่อนไขยุติ 15 16 คืนค่า ${\displaystyle {\widehat {v}}_{t}\,}$  

จะเห็นว่าหากต้องการใช้ขั้นตอนวิธีนี้ต้องทำการปรับค่า ${\displaystyle {\widehat {v}}_{0},N,\rho }$  และเงื่อนไขยุติให้เหมาะสม

ตัวอย่างปัญหาที่สามารถประยุกต์ใช้วิธีการครอสเอนโทรปีได้

ปัญหาการหาเส้นทางเดินของพนักงานขาย (Traveling Salesman Problem)

นิยามปัญหา

ปัญหาการเดินของพนักงานขายคือปัญหาที่มีผู้ที่ให้ความสนใจพอสมควรในวงการคอมพิวเตอร์ ปัญหาจะกำหนดด้วยกราฟเชื่อมโยงประกอบด้วยปม n ชื่อว่า 1,2,...,n ปมซึ่งเชื่อมกันด้วยเส้นเชื่อมที่มีน้ำหนัก เส้นเชื่อมจากปม i ไปยังปม j จะมีน้ำหนัก ${\displaystyle c_{ij}>0\,}$ ให้ทำการหาเส้นทางซึ่งเป็นวงที่สั้นที่สุดซึ่งผ่านทุกปมและกลับมาที่จุดเดิม

แนวทางการแก้ปัญหา

โดยไม่เสียนัยสำคัญทั่วไป ให้กราฟเป็นกราฟบริบูรณ์ ซึ่งจะมีบางเส้นเชื่อมที่มีน้ำหนักเป็น +∞ ให้ ${\displaystyle \chi \,}$  เป็นเซตของวงจรที่ผ่านทุกปม และให้ ${\displaystyle S(x)\,}$  เป็นความยาวของวงจร ${\displaystyle x\in \chi \,}$  ปมละหนึ่งครั้งตามเงื่อนไข เราสามารถแทนแต่ละวงจรใน Χ ได้ด้วยการเรียงสับเปลี่ยน(permutation) ของปม 1,2,...,n ซึ่งจริงๆแล้วเราสามารถให้วงจร ${\displaystyle x=x_{1},x_{2},x_{3},...,x_{n}\,}$  โดยที่ ${\displaystyle x_{1}=1}$  ได้โดยไม่เสียนัยสำคัญทั่วไป เราสามารถแปลงปัญหาทางเดินของพนักงานขายได้เป็นสมการที่ (7)

${\displaystyle min_{x}(S(x))=min_{x}(\sum _{i=1}^{n-1}c_{x_{i},x_{i+1}}+c_{x_{n},1})}$  (7)

สังเกตว่าขนาดของสมาชิกใน ${\displaystyle \chi \,}$  มีขนาดใหญ่มาก ${\displaystyle |\chi |=(n-1)!\,}$ 

จากสมการที่ (7) จะเห็นว่าปัญหาเป็นลักษณะของการหาค่าที่เหมาะสมที่สุดซึ่งสามารถแก้ไขได้ด้วยวิธีการครอส-เอนโทรปี แต่แทนที่จะเป็นลักษณะของการหาค่าที่มากที่สุดจะต้องเปลี่ยนเป็นปัญหาการหาค่าที่น้อยที่สุด โดยหากจะแก้ปัญหาด้วยวิธีการครอส-เอนโทรปีนั้นเราจะต้องกำหนด

1. จะสร้างเส้นทางแบบสุ่มอย่างไร?
2. จะทำการปรับปรุงพารามิเตอร์ในแต่ละรอบการทำงานอย่างไร?
   

ก่อนที่จะหาวิธีการสร้างและปรับปรุงดังกล่าว จะขอนิยามเซตใหม่ขึ้นมาก่อน ให้

${\displaystyle {\widehat {\chi }}={(x_{1},x_{2},...,x_{n}):x_{1}=1,x_{i}\in {1,2,...,n},i=2,3,...,n}}$ 

จะเห็นว่าการหาเส้นทางเดินตามเงื่อนไขบนเซตของเส้นทางเดินใน ${\displaystyle {\widehat {\chi }}\,}$  จะสมมูลกับปัญหาเส้นทางเดินของพนักงานขายเดิม และเพิ่มนิยาม ${\displaystyle {\widehat {S}}(x)=S(x)}$  เมื่อ ${\displaystyle x\in {\widehat {\chi }}}$  มิฉะนั้น ${\displaystyle {\widehat {S}}(x)=\infty }$ 
ก็จะสามารถเปลี่ยนปัญหาทางเดินของพนักงานขายได้เป็นหาค่าที่ต่ำที่สุดของ ${\displaystyle {{\widehat {S}}(x)}\,}$  บน ${\displaystyle x\in {\widehat {\chi }}\,}$ 

วิธีง่ายๆวิธีหนึ่งที่จะสร้างทางเดินสุ่ม ${\displaystyle X=(X_{1},X_{2},...,X_{n})\in {\widehat {\chi }}}$  คือการสร้างลูกโซ่มาร์คอฟ(Markov Chain) ของกราฟ G เริ่มต้นที่ปม 1 และหยุดหลังจากขั้นที่ n ให้ ${\displaystyle P=(p_{ij})}$  คือเมตริกซ์ nxn เพื่อเปลี่ยนสถานะไปหนึ่งขั้นสำหรับลูกโซ่มาร์คอฟนี้ หรือจะพูดให้เข้าใจง่ายขึ้นเป็นภาษาทั่วไปก็คือเมตริกซ์ P จะเป็นส่วนที่ใช้เก็บเส้นทางเดินนั่นเอง กำหนดให้ในสมาชิกตามแนวเส้นทแยงมุมของ P เป็น 0 และสมาชิกอื่นๆใน P เป็นจำนวนจริงบวก ความหนาแน่นของความน่าจะเป็น ${\displaystyle f(-;P)}$  ของ ${\displaystyle X}$  ที่ถูกจำกัดด้วยพารามิเตอร์เป็นเมตริกส์ P นิยามโดย

${\displaystyle lnf(x;P)=\sum _{r=1}^{n}\sum _{i,j}I_{x\in {\widehat {\chi }}_{ij}(r)}ln(p_{ij})}$ (8)
เมื่อ ${\displaystyle {\widehat {\chi }}_{ij}(r)}$  เป็นเซตของเส้นทางทั้งหมดที่ "จำนวนครั้ง" ที่ต้องเดินระหว่างปม i ไปปม j เป็น r ครั้ง

หลังจากนี้จะเริ่มเป็นการคำนวณเชิงคณิตศาสตร์ที่ซับซ้อนหากผู้สนใจสามารถไปศึกษาเพิ่มเติมได้ตามแหล่งอ้างอิง

หากจะสรุปเฉพาะใจความสำคัญให้เข้าใจอย่างสั้นๆสามารถสรุปได้ว่าในขณะนี้เราจะแทนการเปลี่ยนสถานะจากปมปัจจุบันไปยังปมใดๆไ้ด้ด้วยเมตริกซ์ซึ่งก็คือ ${\displaystyle P=(p_{ij})}$  นั่นเอง โดยเมตริกซ์นี้จะได้มาในแต่ละรอบที่ทำการสุ่มตัวอย่างและปรับปรุงพารามิเตอร์ ซึ่งทั้งสองขั้นตอนนี้สามารถทำได้โดย

1. ขั้นสุ่มตัวอย่าง สามารถสุ่มตัวอย่างให้ได้ x ต่างๆได้ตามสมการที่ 8
2. ขั้นปรับปรุง ปรับปรุงพารามิเตอร์ ${\displaystyle p_{ij}}$  ของสมการที่ 8 ได้ด้วยตัวประมาณค่าของ ${\displaystyle p_{ij}}$  ตามสมการที่ (9)

${\displaystyle {\widehat {p}}_{ij}={\frac {\sum _{k=1}^{N}I_{{\widehat {S}}(X_{k})\leq \gamma }\sum _{r=1}^{n}I_{X_{k}\in {\widehat {\chi }}_{ij}(r)}}{\sum _{k=1}^{N}I_{{\widehat {S}}(X_{k})\leq \gamma }\sum _{r=1}^{n}I_{X_{k}\in {\widehat {\chi }}_{i}(r)}}}}$  (9)

ซึ่งรายละเอียดการได้มาซึ่งสมการที่ 10 นั้นผู้สนใจสามารถไปค้นคว้าได้ตามแหล่งอ้่างอิงที่ได้ระบุไว้ข้างต้น

เมื่อเราสามารถนิยามว่าจะสุ่มตัวอย่างและปรับปรุงได้อย่างไรแล้วนั้น เราก็จะสามารถสร้างขั้นตอนวิธีเพื่อที่จะแก้ปัญหานี้ได้ดังรหัสเทียมด้านล่าง

รหัสเทียมสำหรับปัญหา

 1 ตั้งค่า ${\displaystyle P^{(1)}=P\,}$  และ ${\displaystyle X_{1}=1\,}$  2 t = 0 /*ตัวนับจำนวนรอบ*/ 3 ทำ 4 t = t + 1 5 ตั้งค่าในในหลักที่ ${\displaystyle X_{t}\,}$  ของ ${\displaystyle P^{(t)}}$  เป็น 0 6 ทำการทำค่าในแต่ละแถวของ ${\displaystyle P^{(t)}\,}$  ให้เป็นมาตรฐาน(normalize) //เฉลี่ยค่าในแต่ละแถวให้รวมกันได้ 1 7 ใช้สมการที่ (8) สร้าง ${\displaystyle X_{t+1}\,}$  ด้วยพารามิเตอร์ ${\displaystyle P_{t}\,}$  8 ทำการปรับปรุงค่าให้ได้ ${\displaystyle P^{(t+1)}\,}$  ในแต่ละแถว i และหลักที่ j ตามสมการที่ (9) 9 ระหว่างที่ t < n-1 // ถ้ายังสร้างลำดับของทางเดินไม่ครบทุกจุด 10 คืนค่า ${\displaystyle P^{(t)}\,}$  

ดูเพิ่ม

โปรแกรมภาษา C++ ของ Shark Machine Learning Library

อ้างอิง

1. R. Y. Rubinstein. The cross-entropy method for combinatorial and continuous optimization. Methodology and Computing in Applied Probability, 2:127–190, 1999.
2. R. Y. Rubinstein. Combinatorial optimization, cross-entropy, ants and rare events. In S. Uryasev and P. M. Pardalos, editors, Stochastic Optimization: Algorithms and Applications, pages 304–358, Dordrecht, 2001. Kluwer.
3. "Conference on the Occasion of R.Y. Rubinstein's 70th Birthday".
4. R. Y. Rubinstein and D. P. Kroese. Simulation and the Monte Carlo Method. John Wiley & Sons, New York, second edition, 2007.
5. Pieter-Tjerk de Boer. A Tutorial on the Cross-Entropy Method, P.25 - 27.