การสุ่มแบบวงล้อรูเล็ต(roulette wheel selection) (ตอนที่2)

จาก บทความตอนที่ 1 ผมได้กล่าวถึงที่มาที่ไปของคำว่า roulette  ในบทความนี้ผมจะได้กล่าวถึง การสุ่มในคอมพิวเตอร์ ที่ใช้หลักการของ roulette wheel โดยใช้ภาษา java ในการอธิบายครับ

ก่อนอื่นผมขอยกตัวอย่างการสุ่มเลือกข้อมูลแบบธรรมดาก่อน จากตัวอย่างโค๊ดต่อไปนี้ครับ

 //NormalRandom.java

 int[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 int randomIndex ;
 for (int i = 0; i < 100; i++) {
    //สุ่มตำแหน่งข้อมูล
    randomIndex = (int) Math.floor( Math.random() * data.length);
    //พิมพ์ผลลัพธ์โดยกำหนดความกว้างขนาด 4 ตัวอักษรในแต่ละตัว
    System.out.printf("%4d", data[randomIndex]);
    if ((i + 1) % 10 == 0)
      System.out.println();

 }

บรรทัดที่ห้า เป็นการสุ่มโดยใช้เมธอด random( )  จากคลาส java.lang.Math  จะได้ค่าเป็นจำนวนจริงอยู่ระหว่าง 0 – 1  จากนั้นนำไปคูณกับขนาดของ array (data.length)  ได้ผลลัพธ์ เป็นจำนวนจริง อยู่ระหว่าง 0-10    แล้วส่งต่อให้เมธอด Math.floor ที่รีเทิร์นค่าเป็นจำนวนเต็ม ที่ต่ำที่สุด(ตัดเศษทศนิยมออก)ครับ ในที่นี้ผมแปลงผลลัพธ์ที่ได้เป็น integer เพื่อนำไปใช้เป็น index ในการเลือกครับ ผลลัพธ์สุดท้ายที่ตัวแปร randomIndex เก็บค่าจะเป็นจำนวนเต็มมีค่า ตั้งแต่ 0-9 ซึ่งก็คือตำแหน่งของข้อมูลในอาเรย์นั่นเอง

 

Read more

Advertisements

การสุ่มแบบวงล้อรูเล็ต(roulette wheel selection) (ตอนที่1)

การสุ่มแบบวงล้อรูเล็ต เป็นกระบวนการสุ่มจากกลุ่มคำตอบที่มี โดยใช้การถ่วงน้ำหนัก(weight) มาเป็นนัยยะ  โดยคำตอบที่มีค่าน้ำหนักสูงสุด(เป็นคำตอบเริ่มต้นที่ดีที่สุด) มีโอกาสที่จะถูกเลือกมากที่สุด (มีความน่าจะเป็นสูงสุดที่จะถูกสุ่มเจอ) และคำตอบที่มีค่าน้ำหนักต่ำสุด มีโอกาสถูกเลือกน้อยสุด(ความน่าจะเป็นต่ำสุดที่จะถูกสุ่มเจอ)

แนวคิดนี้เป็นการจำลองการพนันชนิดหนึ่งในคาสิโน รูเล็ต หรือ วงล้อรูเล็ต ซึ่งเกมจะมีลักษณะเป็นจานวงกลมหมุน ผู้เล่นจะทำการลงเดิมพันในจานกลม โดยเลือกเลขเฉพาะ(1,2,3,4..)  สี (ดำ,แดง)   หรืออื่นๆ แล้วแต่คาสิโนเป็นผู้กำหนด  การสุ่มจะทำโดยการเหวี่ยงลูกบอลทรงกลมให้หมุนไปในรางเมื่อลูกบอลตกจากรางลงไปในจานช่องใด การสุ่มจะสิ้นสุด ถ้าตกลงที่ช่องที่ผู้เล่นเลือก ก็ถือว่าผู้เล่นชนะ และได้เงินจากการเดิมพัน ถ้าตกที่อื่นถือว่าเจ้ามือชนะและริบเงินจากผู้เล่น

 

ขอบคุณภาพ roulette wheel จาก wikipedia

Read more

การประมาณค่า PI โดยใช้ Monte Carlo Method ตอนที่ 2(จบ)

บทความนี้ เป็นตอนจบ  ของการประมาณค่า PI ด้วย Monte Carlo Method  ครับ ใครยังไม่ได้อ่านตอนแรก สามารถตามไปอ่านได้ที่นี่ครับ

การประมาณค่า PI โดยใช้ Monte Carlo Method ตอนที่ 1

พิจารณาพื้นที่ใน quadrant ที่ 1 ของวงกลม จะได้ว่า พื้นที่สี่เหลี่ยมจัตุรัสที่มีความยาวของแต่ละด้านเป็น r มีค่าเท่ากับ r^2 ดังรูป

ถ้ากำหนดให้ r = 1  จะได้พื้นที่ของ สี่เหลี่ยมจัตุรัสมีค่าเท่ากับ 1  ด้วย(1^2=1)

ดังนั้นขนาดของพื้นที่ สี่เหลี่ยมทั้งหมดที่ครอบคลุมพื้นที่ของ วงกลมที่มีรัศมี 1 หน่วย จึงมีค่าเป็น 1*4 = 4 หน่วย จากข้อมูลดังกล่าว เราสามารถประมาณค่า Pi ด้วยสายตาได้ว่า ค่าของ Pi นั้นจะมีค่าน้อยกว่า 4

แนวคิดของ Monte Carlo Method ที่นำมาใช้ในการหาพื้นที่ของ Pi คือการใช้คอมพิวเตอร์ในการสุ่มจำนวนจุดทั้งหมดใน quadrant ที่ 1 แล้วนับอัตราส่วนของจำนวนจุดที่อยู่ในรัศมีต่อจำนวนจุดทั้งหมด เราก็จะได้พื้นที่ 1 ใน 4 ของ Pi นั่นเอง

ตัวอย่างเช่น ถ้าเราสุ่มจำนวนจุดขึ้นมา 10 จุด ปรากฏว่า มี 9 จุดอยู่ภายในรัศมีของวงกลม และอีก 1 จุดอยู่นอกรัศมีของวงกลม ดังนั้นเราจะได้ว่า ค่าของ Pi ที่หาได้ด้วยวิธีการนี้มีค่าเป็น   4*9/10  = 3.6

ข้อสังเกตของวิธีการนี้คือ หากเราสุ่มค่าออกมาแล้ว ตกอยู่ในพื้นที่ของวงกลมทั้งหมด ค่าของ Pi ที่หาได้จะมีค่าเป็น 4*1  หรือหากค่าที่สุ่มตกอยู่นอกพื้นที่ของวงกลมทั้งหมดเราจะได้ค่าของ Pi เท่ากับ 4*0 ซึ่งก็คือขอบเขตของคำตอบที่เราต้องการหานั่นเอง

ถ้าเราเพิ่มจำนวนครั้งในการสุ่ม หรือในที่นี้คือการเพิ่มจำนวนจุด ให้มากขึ้นค่าของ Pi ที่หาได้จะยิ่งมีความคลาดเคลื่อนน้อย หรือเข้าใกล้สู่ค่าที่ใกล้เคียง(โดยประมาณ) ค่า Pi(22/7) มากขึ้นเท่านั้น

หลักคิดของ Monte Carlo Method ก็มีเพียงเท่านี้ครับ ในส่วนต่อไปผมจะได้อธิบายถึงวิธีขั้นตอน(Algorithm) ในการหาค่า Pi ด้วยวิธีทางคอมพิวเตอร์ครับ ก่อนอื่นพิจารณาค่าของจุดที่เกิดจากการสุ่ม 1 จุดใน quadrant ที่ 1

[ ภาพประกอบ ]

ถ้าให้ระยะห่างจากแนวแกน x เป็น x1 และ ระยะห่างจากแนวแกน y เป็น y1 จากทฤษฎีของปิทากอรัส จะได้ว่า พิกัดของจุด  x1,y1  นั้นห่างจากจุดศูนย์กลางเท่ากับ รากที่สองของ x1^2+y1^2 ในที่นี้แทนที่ด้วยค่า d ดังสมการ

เนื่องจากรัศมีของวงกลมมีค่าเป็น 1 ดังนั้น ระยะห่างของจุดที่มีพิกัด  x,y ใดๆ จะอยู่ในพื้นที่วงกลมก็ต่อเมื่อ d มีค่าน้อยกว่าหรือเท่ากับ 1 นั่นเอง

เมื่อเราได้ระยะห่างจากจุดศูนย์กลางของแต่ละจุดออกมาแล้ว ขั้นตอนต่อไปก็คือการนับจำนวนจุดทั้งหมดแล้ว นำมาเปรียบเทียบอัตราส่วนเพื่อคำนวณหาค่า Pi ต่อไป ผมขอสรุปเป็นลำดับขั้นตอนดังนี้ครับ

  1. สุ่มค่า x และ y โดยให้ x และ y เป็นทศนิยมมีค่าอยู่ระหว่าง 0 ถึง 1
  2. หาค่า d ออกมาตามสมการข้างบน
  3. ถ้า ค่า d น้อยกว่าหรือเท่ากับ 1 ให้นับจำนวนไว้ (ในที่นี้ขอแทนที่ด้วย n )
  4. วนรอบทำข้อ 1-3 ซ้ำ โดยจำนวนรอบเท่ากับจำนวนจุดทั้งหมดที่ต้องการสุ่ม (ในที่นี้ขอแทนที่ด้วย N )
  5. Pi มีค่าเท่ากับ  4* n/N

จบแล้วครับสำหรับบทความ การหาค่า Pi โดยใช้  Monte Carlo Method  จากการทดสอบของผมเมื่อนำไปเขียนเป็นโปรแกรม พบว่าค่าที่หาได้มีค่าใกล้เคียงกับค่า Pi จริงๆ ยิ่งเราเพิ่มจำนวนรอบในการสุ่ม ค่าที่ได้ยิ่งใกล้เคียงกับค่าจริงมากเท่านั้น อย่างไรก็ตามวิธีการนี้เป็นแค่การประมาณค่าเท่านั้น ไม่สามารถเทียบเท่ากับการหาด้วยอัตราส่วน 22/7 ได้  ใครไม่เชื่อก็ลองทดสอบด้วยตัวเองดูนะครับ