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

จากวิกิพีเดีย สารานุกรมเสรี

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

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

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

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

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

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

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

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

แนวคิด[แก้]

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

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

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

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

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

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

g(x) = 0\, เมื่อ H(x)f(x) = 0\,

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

\widehat{\ell}=\frac{1}{N}\sum_{k=1}^{N}H(X_k)\frac{f(X_k)}{g(X_k)} (3)

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

g^*(x) \alpha |H(x)|f(x)\,

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

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 ที่ดีที่สุดจะทำให้ \int H(x)f(x;u)ln(f(x;v))dx\, มีค่ามากที่สุดนั่นเอง ซึ่งการแก้ปัญหานี้ก็สามารถหาได้ตามสมการที่ (5)
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 ได้นำเสนอวิธีสำหรับแก้ปัญหานี้ไว้แล้ว[4]
ในปัญหาเฉพาะที่ชื่อว่าปัญหาการหาความน่าจะเป็นของเหตุการณ์ที่พบเจอได้ยาก(rare event probability) ซึ่งเป็นปัญหาที่ประยุกต์ด้วยวิธีครอส-เอนโทรปีกันอย่างแพร่หลาย โดยเป็นกรณีเฉพาะที่ฟังก์ชัน H เป็นฟังก์ชันตัวชี้ของฟังก์ชัน S(x) วัดที่ระดับ \gamma ตามสมการ H(x)=I_{S(X) \ge \gamma} ซึ่งในการประมาณค่าของ \ell ด้วยวิธีเดิมเพื่อหาความน่าจะเป็นที่ S(x) \ge \gamma นั้นจะยากโดยดูได้จากสมการที่ (5) คือค่าของ H(X_k) ส่วนมากจะมีค่าเป็น 0 ไปมากพอสมควรจะไม่สามารถประมาณหาค่าที่แม่นยำได้ วิธีการแก้ไขคือต้องทำวิธีการ ครอส-เอนโทรปีหลายๆรอบ หลายๆชั้น โดยจะปรับค่าพารามิเตอร์ v และระดับปัจจุบันให้เข้าใกล้ v* และ \gamma ไปเรื่อยๆจนถึงเงื่อนไขยุติที่พอใจ สามารถเขียนขั้นตอนวิธีตามที่ได้อธิบายมาเป็นรหัสเทียมได้ดังนี้

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

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

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

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

แนวคิด[แก้]

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

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


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

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

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

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

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

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

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

นิยามปัญหา[แก้]

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

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

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

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

จากสมการที่ (7) จะเห็นว่าปัญหาเป็นลักษณะของการหาค่าที่เหมาะสมที่สุดซึ่งสามารถแก้ไขได้ด้วยวิธีการครอส-เอนโทรปี แต่แทนที่จะเป็นลักษณะของการหาค่าที่มากที่สุดจะต้องเปลี่ยนเป็นปัญหาการหาค่าที่น้อยที่สุด โดยหากจะแก้ปัญหาด้วยวิธีการครอส-เอนโทรปีนั้นเราจะต้องกำหนด
  1. จะสร้างเส้นทางแบบสุ่มอย่างไร?
  2. จะทำการปรับปรุงพารามิเตอร์ในแต่ละรอบการทำงานอย่างไร?
ก่อนที่จะหาวิธีการสร้างและปรับปรุงดังกล่าว จะขอนิยามเซตใหม่ขึ้นมาก่อน ให้
\widehat{\chi} = {(x_1,x_2,...,x_n) : x_1 = 1, x_i \in {1,2,...,n}, i = 2,3,...,n}

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

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

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

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

หากจะสรุปเฉพาะใจความสำคัญให้เข้าใจอย่างสั้นๆสามารถสรุปได้ว่าในขณะนี้เราจะแทนการเปลี่ยนสถานะจากปมปัจจุบันไปยังปมใดๆไ้ด้ด้วยเมตริกซ์ซึ่งก็คือ P = (p_{ij}) นั่นเอง โดยเมตริกซ์นี้จะได้มาในแต่ละรอบที่ทำการสุ่มตัวอย่างและปรับปรุงพารามิเตอร์ ซึ่งทั้งสองขั้นตอนนี้สามารถทำได้โดย
  1. ขั้นสุ่มตัวอย่าง สามารถสุ่มตัวอย่างให้ได้ x ต่างๆได้ตามสมการที่ 8
  2. ขั้นปรับปรุง ปรับปรุงพารามิเตอร์ p_{ij} ของสมการที่ 8 ได้ด้วยตัวประมาณค่าของ p_{ij} ตามสมการที่ (9)
\widehat{p}_{ij} = \frac{\sum_{k=1}^{N}I_{\widehat{S}(X_k) \le \gamma}\sum_{r=1}^{n}I_{X_k \in \widehat{\chi}_{ij}(r)}}{\sum_{k=1}^{N}I_{\widehat{S}(X_k) \le \gamma}\sum_{r=1}^{n}I_{X_k \in \widehat{\chi}_{i}(r)}} (9)

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

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

รหัสเทียมสำหรับปัญหา[แก้]

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