วิธีเอนโทรปีไขว้

วิธีเอนโทรปีไขว้  เป็นขั้นตอนวิธีที่ใช้หลักการของ Monte Carlo เพื่อที่จะแก้ปัญหา ถูกนำเสนอโดย R.Y. Rubinstein ซึ่งประเภทของปัญหาที่สามารถใช้วิธีเอนโทรปีไขว้ได้นั้นจะมีอยู่สองลักษณะ คือ การประมาณค่า หรือ การหาค่าที่ดีที่สุด โดยวิธีการนี้ถูกประยุกต์ใช้ในปัญหาเชิงวิศวกรรม และวิทยาศาสตร์มากมาย
ภาพรวมของวิธีเอนโทรปีไขว้.
วิธีเอนโทรปีไขว้นั้นถูกพัฒนาขึ้นโดย Reuven Y. Rubinstein ซึ่งเป็นนักวิทยาศาสตร์ชาวอิสราเอลที่ให้ความสนใจทางด้านการพัฒนาขั้นตอนวิธีเชิงสถิติมากมาย เขียนหนังสือหกเล่มและตีพิมพ์ผลงานกว่าร้อยผลงาน ซึ่งแน่นอนว่าวิธีการเอนโทรปีไขว้เป็นหนึ่งในขั้นตอนวิธีเชิงสถิติเหล่านั้นเช่นกัน โดยเป็นขั้นตอนวิธีที่มีประสิทธิภาพตัวหนึ่งที่ใช้สำหรับปัญหาการประมาณค่าความน่าจะเป็นของเหตุการณ์ที่พบเจอได้ยาก (rare-event probability) ปัญหาการหาค่าที่เหมาะสมที่สุดเชิงการจัด (combinatorial optimization)
วิธีการเอนโทรปีไขว้นั้นได้ชื่อมาจาก "ระยะห่างเอนโทรปีไขว้" ซึ่งเป็นการหาระยะห่างระหว่าง "ข้อมูล" ที่ใช้กันแพร่หลายในทางวิทยาศาสตร์และวิศวกรรมกว่าศตวรรษ
วิธีการเอนโทรปีไขว้นั้นถูกนำไปใช้ในปัญหาการหาค่าที่เหมาะสมที่สุดเชิงการจัดมากมาย เช่น ปัญหาการตัดที่มากที่สุด (Maximum Cut Problem) ปัญหาการหาเส้นทางเดินของพนักงานขาย (Traveling Salesman Problem) ปัญหาการหากราฟย่อยบริบูรณ์ที่มีขนาดใหญ่ที่สุดในกราฟ (Clique Problem) และปัญหาต่างๆอีกมากมาย และจุดเด่นพิเศษอีกอย่างหนึ่งสำหรับวิธีการเอนโทรปีไขว้คือ สามารถหาค่าที่เหมาะสมที่สุดสำหรับปัญหาที่มีค่ารบกวน (noisy problem) ได้ เพราะลักษณะขั้นตอนวิธีแก้ปัญหาที่เป็นเชิงสถิตินั่นเอง
วิธีการเอนโทรปีไขว้นั้นสามารถแตกขั้นตอนที่สำคัญออกได้เป็นสองส่วน คือ
ประเด็นสำคัญสำหรับวิธีการเอนโทรปีไขว้ คือ จะนิยามขั้นตอนในเชิงคณิตศาสตร์อย่างไรให้สามารถปรับปรุงค่าพารามิเตอร์เพื่อให้เข้าใกล้ค่าที่เหมาะสมได้อย่างรวดเร็ว
ในด้านของการประมาณค่าความน่าจะเป็นของเหตุการณ์ที่พบเจอได้ยากนั้น วิธีการเอนโทรปีไขว้จะใช้ร่วมกับกลวิธีการสุ่มตัวอย่างสำคัญ (Importance Sampling Technique) วิธีการเอนโทรปีไขว้จะปรับค่าของพารามิเตอร์ซ้ำๆ หลายๆรอบเพื่อให้เข้าใกล้ค่าที่เหมาะสมที่สุด ปัญหาที่ประยุกต์วิธีนี้ตัวอย่างเช่นปัญหาการวัดประสิทธิภาพในระบบเครือข่ายทางคมนาคม หรือ ระบบที่ต้องการความน่าเชื่อถือ
การใช้วิธี เอนโทรปีไขว้ ในปัญหาการประมาณค่า.
แนวคิด.
ในกรณีที่เราพยายามที่จะใช้วิธีเอนโทรปีไขว้เพื่อประมาณค่านั้น สามารถแปลงปัญหาเป็นสมการคณิตศาสตร์ของการประมาณหาค่าคาดหวังง่ายๆได้ดังสมการที่ (1)
<math> \ell = \mathbb{E}_f[H(X)] = \int H(x)f(x)\,dx</math> (1)
เมื่อ H คือฟังก์ชันที่เราต้องการประมาณค่า เรียกได้อีกอย่างหนึ่งว่า ฟังก์ชันของประสิทธิภาพของตัวอย่างสุ่ม 
และ f คือฟังก์ชันของความหนาแน่นของความน่าจะเป็นของตัวแปรสุ่ม X 
ซึ่งสำหรับวิธีการประมาณค่า <math>l</math> ในสมการที่ 1 นั้น ในกรณีที่สามารถสุ่มตัวอย่างสุ่มด้วยความหนาแน่นของความน่าจะเป็น <math>f(x)</math> ได้ยาก จะทำการสร้างฟังก์ชัน <math>f(x)</math> เพื่อที่จะสามารถประมาณค่าได้ง่ายขึ้นตามสมการที่ 2
<math> \ell = \int H(x)\frac{f(x)}{g(x)}g(x)\,dx = \mathbb{E}_g[H(x)\frac{f(x)}{g(x)}]</math> (2)
โดยที่กำหนดให้ 
<math>g(x) = 0\,</math> เมื่อ <math>H(x)f(x) = 0\,</math>
เนื่องจาก g เป็นความหนาแน่นของความน่าจะเป็นที่เราเป็นคนสร้างขึ้น ทำให้การสุ่มตัวอย่างเป็นไปได้ง่ายกว่า f ดังนั้น เราจึงสามารถสุ่มตัวอย่างสุ่ม <math>X_1...,X_N</math> ตามความหนาแน่นของความน่าจะเป็นของ g(x) ได้ง่ายกว่า ทำให้ประมาณค่าของ l ด้วยตัวประมาณค่าที่ไม่ลำเอียงได้ง่ายขึ้นตามสมการที่ (3)
<math>\widehat{\ell}=\frac{1}{N}\sum_{k=1}^{N}H(X_k)\frac{f(X_k)}{g(X_k)}</math> (3)
จากปัญหาการประมาณค่า ก็จะเหลือแค่ปัญหาว่าจะสร้างความหนาแน่นของความน่าจะเป็น g ที่ดีที่สุดได้อย่างไรซึ่งค่า g ที่ดีที่สุดในอุดมคตินั้นนิยามด้วย 
<math>g^*(x) \alpha |H(x)|f(x)\,</math>
แต่สิ่งที่เกิดขึ้นก็คือ เราสามารถหาค่า g*(x) ได้ยาก สำหรับวิธีเอนโทรปีไขว้นี้แทนที่จะมุ่งไปที่การหาค่าของ g*(x) จะพยายามหาค่าของ g ที่ทำให้ความแตกต่างระหว่าง g และ g* น้อยที่สุด ซึ่งความแตกต่างนั้นเองที่เรียกว่าเอนโทรปีไขว้ตามที่เกริ่นไว้ในช่วงต้น ซึ่งเอนโทรปีไขว้ของความหนาแน่นของความน่าจะเป็นของสองฟังก์ชันนั้น นิยามได้ดังสมการที่ (4)
<math>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</math> (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 ที่ดีที่สุดจะทำให้ <math>\int H(x)f(x;u)ln(f(x;v))dx\,</math> มีค่ามากที่สุดนั่นเอง ซึ่งการแก้ปัญหานี้ก็สามารถหาได้ตามสมการที่ (5)
<math>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))\,</math> (5)
ซึ่งจากสมการที่ (5) R. Y. Rubinstein ได้นำเสนอวิธีสำหรับแก้ปัญหานี้ไว้แล้ว
ในปัญหาเฉพาะที่ชื่อว่าปัญหาการหาความน่าจะเป็นของเหตุการณ์ที่พบเจอได้ยาก(rare event probability) ซึ่งเป็นปัญหาที่ประยุกต์ด้วยวิธีเอนโทรปีไขว้กันอย่างแพร่หลาย โดยเป็นกรณีเฉพาะที่ฟังก์ชัน H เป็นฟังก์ชันตัวชี้ของฟังก์ชัน <math>S(x)</math> วัดที่ระดับ <math>\gamma</math> ตามสมการ <math>H(x)=I_{S(X) \ge \gamma}</math> ซึ่งในการประมาณค่าของ <math>\ell</math> ด้วยวิธีเดิมเพื่อหาความน่าจะเป็นที่ <math>S(x) \ge \gamma</math> นั้นจะยากโดยดูได้จากสมการที่ (5) คือค่าของ <math>H(X_k)</math> ส่วนมากจะมีค่าเป็น 0 ไปมากพอสมควรจะไม่สามารถประมาณหาค่าที่แม่นยำได้ วิธีการแก้ไขคือต้องทำวิธีการ เอนโทรปีไขว้หลายๆรอบ หลายๆชั้น โดยจะปรับค่าพารามิเตอร์ v และระดับปัจจุบันให้เข้าใกล้ v* และ <math>\gamma</math> ไปเรื่อยๆจนถึงเงื่อนไขยุติที่พอใจ สามารถเขียนขั้นตอนวิธีตามที่ได้อธิบายมาเป็นรหัสเทียมได้ดังนี้
รหัสเทียมสำหรับวิธีเอนโทรปีไขว้เพื่อประมาณความน่าจะเป็นสำหรับเหตุการณ์ที่พบเจอได้ยาก.
 1 <math>\widehat{v}_0 = u </math> และ 
 2 <math>N^e = \lceil \rho\,N \rceil </math>
 3 t = 0 /*ตัวนับจำนวนรอบ*/
 4
 5 ทำ
 6 t = t + 1
 7 สุ่มตัวอย่างสุ่ม <math>X_1...,X_N\,</math> ตามความหนาแน่นของความน่าจะเป็น <math>f(-:\widehat{v}_{t-1})\,</math>
 8 สำหรับทุก i ตั้งแต่ 1 ถึง N
 9 <math>S_{(i)} = S(X_i)\,</math>
 10 เรียงลำดับจากน้อยไปหามาก(S) 
 11 <math> \widehat{\gamma}_t = S_{(N - N^e + 1)}\,</math>
 12 <math>\widehat\gamma_t\,</math> = ค่าต่ำสุด(<math>\gamma\,</math>,<math>\widehat\gamma_t</math>)
 13 คำนวณ <math>\widehat{v}_t </math> จากสมการ (5) ด้วย <math>X_1...,X_N</math> และ <math>w = \widehat{v}_{t-1} </math>
 14 ระหว่างที่ <math> \widehat\gamma_t < \gamma</math> 
 15
 16 สุ่มตัวอย่างสุ่ม <math>X_1...,X_{N_{1}}\,</math> ตามความหนาแน่นของความน่าจะเป็น <math>f(-:\widehat{v}_{t})</math>
 17 คำนวณ <math>\ell</math> จากสมการ (3) ด้วย <math>X_1...,X_{N_{1}}\,</math>
 18 คืนค่า <math>\ell</math>
จะเห็นว่าหากต้องการใช้ขั้นตอนวิธีนี้ต้องทำการปรับค่า <math>\widehat{v}_0, N, \rho</math> ให้เหมาะสมกับความต้องการ ซึ่งโดยปกติ <math>\rho</math> จะมีค่าอยู่ระหว่าง 0.01 และ 0.1 และค่าของ <math>N</math> จะน้อยว่า <math>N_1</math> มากๆ เช่น <math>N = 10000</math> ในขณะที่ <math>N_1 = 100000</math> และขั้นตอนวิธีนี้จะรับประกันว่าสามารถทำงานจนจบได้แน่นอนหากค่าของ <math>\rho</math> มีค่าเล็กมากพอ
การใช้วิธี เอนโทรปีไขว้ ในปัญหาการหาค่าที่เหมาะสมที่สุด.
แนวคิด.
ให้ <math>\chi</math> เป็นเซตของสถานะ และ S เป็นฟังก์ชันจริงซึ่ง S(x) จะให้ค่าความเหมาะสมของ x โดยที่ x เป็นสมาชิกของ <math>\chi</math> โดยค่า x ที่เหมาะสมที่สุดคือ x* ซึ่งจะทำให้ค่าของ S(x*) มีค่าสูงที่สุด สามารถเขียนเป็นปัญหาในรูปของสมการทางคณิตศาสตร์ได้ดังสมการที่ (6)
<math>S(x^*) = \gamma^* = max_{x}S(x)\,</math> (6)
หาพิจารณาปัญหานี้เทียบกับปัญหาการประมาณค่าของ <math>H(x)=I_{S(X) \ge \gamma}</math> เมื่อ X เป็นตัวแปรสุ่มที่มีความหนาแน่นของความน่าจะเป็น <math>f(x;u)</math> และให้ <math>\gamma</math> เป็นค่าระดับชั้น จะสังเกตว่าถ้าค่า <math>\gamma</math> มีค่าใกล้เคียงกับ <math>\gamma^*</math> (ค่าสูงสุดของ S) แล้ว จะทำให้ค่าของ <math>H(x)=I_{S(X) \ge \gamma}</math> เป็นความน่าจะเป็นของเหตุการณ๊ที่พบเจอได้ยาก ซึ่งปัญหานี้เราจะต้องการสร้างตัวอย่างสุ่มจำนวนหนึ่งที่มีค่าใกล้เคียงกับ x* โดยเป็นเรื่องที่ดีที่วิธีเอนโทรปีไขว้ สามารถทำเรื่องนี้ได้
หากเปรียบเทียบความแตกต่างของปัญหาระหว่างการหาค่าที่เหมาะสมที่สุด กับ การประมาณค่า ความแตกต่างก็คือการหาค่าที่เหมาะสมที่สุด เราจะไม่รู้ค่าของระดับชั้น <math>\gamma = \gamma^*</math> ล่วงหน้าเหมือนในการประมาณค่า แต่อย่างไรก็ตามขั้นตอนวิธีในการแก้ปัญหาก็ไ่ม่ค่อยแตกต่างกันมากคือเราจะสร้างลำดับของ <math>\gamma_t</math> และ <math>\widehat{v}_t</math> ไปเรื่อยๆ โดยจะพยายามให้ทั้งสองค่าเข้าใกล้ <math>\gamma^*</math> และ <math>v^*</math> ตามลำดับ ซึ่งค่าของ <math>v^*</math> จะสอดคล้องกับค่าของ <math>x^*</math> ที่ต้องการหาเช่นกัน
รหัสเทียมสำหรับวิธีเอนโทรปีไขว้เพื่อใช้ในปัญหาการหาค่าที่เหมาะสมที่สุด.
 1 <math>\widehat{v}_0 = u </math> และ 
 2 <math>N^e = \lceil \rho\,N \rceil </math>
 3 t = 0 /*ตัวนับจำนวนรอบ*/
 4
 5 ทำ
 6 t = t + 1
 7 สุ่มตัวอย่างสุ่ม <math>X_1...,X_N\,</math> ตามความหนาแน่นของความน่าจะเป็น <math>f(-:\widehat{v}_{t-1})\,</math>
 8 สำหรับทุก i ตั้งแต่ 1 ถึง N
 9 <math>S_{(i)} = S(X_i)\,</math>
 10 เรียงลำดับจากน้อยไปหามาก(S) 
 11 <math> \widehat{\gamma}_t = S_{(N - N^e + 1)}\,</math>
 12 <math>\widehat\gamma_t\,</math> = ค่าต่ำสุด(<math>\gamma\,</math>,<math>\widehat\gamma_t</math>)
 13 คำนวณ <math>v = \widehat{v}_t\,</math> ที่ทำให้ <math>\frac{I_{S(X_k) \ge \widehat{\gamma}_t}ln(f(X_k;v))}{N}</math> สูงที่สุด
 14 ระหว่างที่ ยังไม่ถึงเงื่อนไขยุติ
 15
 16 คืนค่า <math>\widehat{v}_t\,</math>
จะเห็นว่าหากต้องการใช้ขั้นตอนวิธีนี้ต้องทำการปรับค่า <math>\widehat{v}_0, N, \rho</math> และเงื่อนไขยุติให้เหมาะสม
ปัญหาการเดินของพนักงานขายคือปัญหาที่มีผู้ที่ให้ความสนใจพอสมควรในวงการคอมพิวเตอร์ ปัญหาจะกำหนดด้วยกราฟเชื่อมโยงประกอบด้วยปม n ชื่อว่า 1,2...,n ปมซึ่งเชื่อมกันด้วยเส้นเชื่อมที่มีน้ำหนัก เส้นเชื่อมจากปม i ไปยังปม j จะมีน้ำหนัก <math>c_{ij} > 0\,</math>ให้ทำการหาเส้นทางซึ่งเป็นวงที่สั้นที่สุดซึ่งผ่านทุกปมและกลับมาที่จุดเดิม
โดยไม่เสียนัยสำคัญทั่วไป ให้กราฟเป็นกราฟบริบูรณ์ ซึ่งจะมีบางเส้นเชื่อมที่มีน้ำหนักเป็น +∞ ให้ <math>\chi\,</math> เป็นเซตของวงจรที่ผ่านทุกปม และให้ <math>S(x)\,</math> เป็นความยาวของวงจร <math>x \in \chi\,</math> ปมละหนึ่งครั้งตามเงื่อนไข เราสามารถแทนแต่ละวงจรใน Χ ได้ด้วยการเรียงสับเปลี่ยน(permutation) ของปม 1,2...,n ซึ่งจริงๆแล้วเราสามารถให้วงจร <math>x = x_1, x_2, x_3, ..., x_n\,</math> โดยที่ <math>x_1 = 1</math> ได้โดยไม่เสียนัยสำคัญทั่วไป เราสามารถแปลงปัญหาทางเดินของพนักงานขายได้เป็นสมการที่ (7)
<math>min_x(S(x)) = min_x(\sum_{i=1}^{n-1}c_{x_i,x_{i+1}} + c_{x_n,1})</math> (7)
ตัวอย่างปัญหาที่สามารถประยุกต์ใช้วิธีการเอนโทรปีไขว้ได้.
ปัญหาการหาเส้นทางเดินของพนักงานขาย (Traveling Salesman Problem).
แนวทางการแก้ปัญหา.
สังเกตว่าขนาดของสมาชิกใน <math>\chi\,</math> มีขนาดใหญ่มาก <math>|\chi| = (n-1)!\,</math>
จากสมการที่ (7) จะเห็นว่าปัญหาเป็นลักษณะของการหาค่าที่เหมาะสมที่สุดซึ่งสามารถแก้ไขได้ด้วยวิธีการเอนโทรปีไขว้ แต่แทนที่จะเป็นลักษณะของการหาค่าที่มากที่สุดจะต้องเปลี่ยนเป็นปัญหาการหาค่าที่น้อยที่สุด โดยหากจะแก้ปัญหาด้วยวิธีการเอนโทรปีไขว้นั้นเราจะต้องกำหนด
ก่อนที่จะหาวิธีการสร้างและปรับปรุงดังกล่าว จะขอนิยามเซตใหม่ขึ้นมาก่อน ให้
<math>\widehat{\chi} = {(x_1,x_2...,x_n) : x_1 = 1, x_i \in {1,2...,n}, i = 2,3...,n}</math>
จะเห็นว่าการหาเส้นทางเดินตามเงื่อนไขบนเซตของเส้นทางเดินใน <math>\widehat{\chi}\,</math> จะสมมูลกับปัญหาเส้นทางเดินของพนักงานขายเดิม และเพิ่มนิยาม <math>\widehat{S}(x) = S(x)</math> เมื่อ <math>x \in \widehat{\chi}</math> มิฉะนั้น <math>\widehat{S}(x) = \infty</math>
ก็จะสามารถเปลี่ยนปัญหาทางเดินของพนักงานขายได้เป็นหาค่าที่ต่ำที่สุดของ <math>{\widehat{S}(x)}\,</math> บน <math>x \in \widehat{\chi}\,</math>
วิธีง่ายๆวิธีหนึ่งที่จะสร้างทางเดินสุ่ม <math>X = (X_1,X_2...,X_n) \in \widehat{\chi}</math> คือการสร้างลูกโซ่มาร์คอฟ(Markov Chain) ของกราฟ G เริ่มต้นที่ปม 1 และหยุดหลังจากขั้นที่ n ให้ <math>P = (p_{ij})</math> คือเมตริกซ์ nxn เพื่อเปลี่ยนสถานะไปหนึ่งขั้นสำหรับลูกโซ่มาร์คอฟนี้ หรือจะพูดให้เข้าใจง่ายขึ้นเป็นภาษาทั่วไปก็คือเมตริกซ์ P จะเป็นส่วนที่ใช้เก็บเส้นทางเดินนั่นเอง กำหนดให้ในสมาชิกตามแนวเส้นทแยงมุมของ P เป็น 0 และสมาชิกอื่นๆใน P เป็นจำนวนจริงบวก ความหนาแน่นของความน่าจะเป็น <math>f(-;P)</math> ของ <math>X</math> ที่ถูกจำกัดด้วยพารามิเตอร์เป็นเมตริกส์ P นิยามโดย
<math>ln f(x;P) = \sum_{r=1}^{n}\sum_{i,j}I_{x \in \widehat{\chi}_{ij}(r)}ln(p_{ij})</math>(8) 
เมื่อ <math>\widehat{\chi}_{ij}(r)</math> เป็นเซตของเส้นทางทั้งหมดที่ "จำนวนครั้ง" ที่ต้องเดินระหว่างปม i ไปปม j เป็น r ครั้ง
หลังจากนี้จะเริ่มเป็นการคำนวณเชิงคณิตศาสตร์ที่ซับซ้อนหากผู้สนใจสามารถไปศึกษาเพิ่มเติมได้ตามแหล่งอ้างอิง
หากจะสรุปเฉพาะใจความสำคัญให้เข้าใจอย่างสั้นๆสามารถสรุปได้ว่าในขณะนี้เราจะแทนการเปลี่ยนสถานะจากปมปัจจุบันไปยังปมใดๆไ้ด้ด้วยเมตริกซ์ซึ่งก็คือ <math>P = (p_{ij})</math> นั่นเอง โดยเมตริกซ์นี้จะได้มาในแต่ละรอบที่ทำการสุ่มตัวอย่างและปรับปรุงพารามิเตอร์ ซึ่งทั้งสองขั้นตอนนี้สามารถทำได้โดย
<math>\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)}}</math> (9)
ซึ่งรายละเอียดการได้มาซึ่งสมการที่ 10 นั้นผู้สนใจสามารถไปค้นคว้าได้ตามแหล่งอ้่างอิงที่ได้ระบุไว้ข้างต้น
เมื่อเราสามารถนิยามว่าจะสุ่มตัวอย่างและปรับปรุงได้อย่างไรแล้วนั้น เราก็จะสามารถสร้างขั้นตอนวิธีเพื่อที่จะแก้ปัญหานี้ได้ดังรหัสเทียมด้านล่าง
รหัสเทียมสำหรับปัญหา.
 1 ตั้งค่า <math>P^{(1)} = P\,</math> และ <math>X_{1} = 1\,</math>
 2 t = 0 /*ตัวนับจำนวนรอบ*/
 3 ทำ
 4 t = t + 1
 5 ตั้งค่าในในหลักที่ <math>X_{t}\,</math> ของ <math>P^{(t)}</math> เป็น 0 
 6 ทำการทำค่าในแต่ละแถวของ <math>P^{(t)}\,</math> ให้เป็นมาตรฐาน(normalize) //เฉลี่ยค่าในแต่ละแถวให้รวมกันได้ 1 
 7 ใช้สมการที่ (8) สร้าง <math>X_{t+1}\,</math> ด้วยพารามิเตอร์ <math>P_t\,</math>
 8 ทำการปรับปรุงค่าให้ได้ <math>P^{(t+1)}\,</math> ในแต่ละแถว i และหลักที่ j ตามสมการที่ (9)
 9 ระหว่างที่ t < n-1 // ถ้ายังสร้างลำดับของทางเดินไม่ครบทุกจุด
 10 คืนค่า <math>P^{(t)}\,</math>
ดูเพิ่ม.
โปรแกรมภาษา C++ ของ Shark Machine Learning Library