ตอนที่ 1 ว่ากันไปเรื่องทางชีวิทยาต้นทางแนวคิดของ GA ที่หยิบเอากระบวนการวิวัฒนาการของสิ่งมีชีวิตมาใช้ค้นหาทางเลือกที่ดีที่สุดใน searching space โดยสรุปขั้นตอนการทำงานของ GA ดังในรูปที่ 1
Initialization
เป็นขั้นตอนแรกที่ต้องทำ เพื่อสร้าง population ที่เวลา t = 0 โดยทั่วไปจะใช้การสุ่มลักษณะของ individual ขึ้นมาก่อน
Evaluation
เป็นขั้นตอนการคัดเลือก individual ที่มีลักษณะที่เหมาะสมไว้เพื่อส่งต่อ ความเหมาะสมนี้วัดด้วยสิ่งที่เรียกว่า fitness function ซึ่งต้องสร้างขึ้นมาโดยให้ผลที่สอดคล้องกับการแก้ปัญหา fitness function ถือเป็นหัวใจหลักของ GA ต้องพิจารณาให้ดี
Selection
มีหลายรูปแบบ จะขอกล่าวถึงแบบที่ใช้ง่ายและเห็นได้บ่อย
1. Roulette Selection
แนวคิดของการ roulette selection เอามาจากกติกาการเล่นวงล้า roulette โดยนำเอา individual มากำหนดค่า proportion ของแต่ละ individual มากน้อยโดยอิงกับค่าของ fitness ค่า proportion ในที่นี้ก็คือค่าความน่าจะเป็นในการถูกเลือกของ individual นั้นเอง
จากตารางตัวอย่างนี้ความน่าจะเป็นในการถูกเลือกจากมากไปน้อยคือ E,A,D,C,B ตามลำดับ
linear fitness scaling
ในบางครั้งการใช้ fitness อาจทำให้เกิดความแตกต่างกันมากจนอาจทำให้ individual บาง individual แทบไม่มีโอกาสถูกเลือกเลยก็ได้ การลด bias อาจใช้เทคนิคที่เรียกว่า scaling หรือการเปลี่ยนค่าให้ไปอยู่ในช่วงตัวเลขอื่นโดยอาศัยสมการเส้นตรง
\[ \text{new fitness} = a \times \text{old fitness} + b\]
โดยที่ a,b คือค่าคงที่
ขั้นตอน
1. กำหนดค่า maximum และ minimum ของ rank ใหม่ เช่น [1,5]
2. เอา fitness ของ 2 individual ที่มีค่ามากที่สุดและน้อยที่สุด ในกรณีนี้คือ B และ E โดยค่า new fitness ของ E,B จะเป็น 50 และ 1 ตามลำดับ แล้วแก้สมการ 2 ตัวแปร
\[ E : 5 = 9a + b \] \[ B : 1 = 3a + b \] \[ \therefore a = \frac{2}{3}, b = -1\]
3. นำค่า a,b มาสร้าง fitness ใหม่และหาค่า proportion
Crossover
บางครั้งจะเห็นในชื่อของ Mating สิ่งที่เกิดขึ้นในขั้นตอนนี้คือการแลกเปลี่ยน gene ระหว่าง 2 individual ที่ได้จากขั้นตอน selection โดยมีสมมุติฐานว่า การแลกเปลี่ยนนี้จะทำให้เกิด individual ในรุ่นถัดไปที่มี fitness ที่ดีขึ้นกว่ารุ่นก่อนหน้า
1. Single point crossover : chromosome ของแต่ละ individual ในรุ่น parent จะถูกแยกส่วนออก โดยตำแหน่งที่จะถูกแยกนั้นกำหนดขึ้นมาแบบสุ่ม 1 ตำแหน่ง
2. Two points crossover : เหมือนกับแบบแรก เพียงแต่ chromosome ของแต่ละ individual ในรุ่น parent จะถูกแยกส่วนออก โดยตำแหน่งที่จะถูกแยกนั้นกำหนดขึ้นมาแบบสุ่ม 2 ตำแหน่ง
3. Uniform crossover : geneที่ถูกเลือกแต่ละ gene จะถูกเลือกสลับไปมาระหว่าง parent ด้วยความน่าจะเป็นเท่ากัน แล้วนำมาประกอบกันในรุ่นลูก
Mutation
คือการเปลี่ยนแปลงในส่วนเล็กๆภายใน chromosome ของแต่ละ individual ในตอนนี้จะกล่าวถึงเฉพาะ Random mutation
ถ้า \( x \in [a,b] \) แล้วจะได้ \[ M_u (x) = U[a,b] \]
เมื่อ \( U[a,b] \) คือ Uniform distribution ของ [a,b]
การหยุด
 |
| รูปที่ 1 ขั้นตอนของ Genetic Algorithm |
Initialization
เป็นขั้นตอนแรกที่ต้องทำ เพื่อสร้าง population ที่เวลา t = 0 โดยทั่วไปจะใช้การสุ่มลักษณะของ individual ขึ้นมาก่อน
Evaluation
เป็นขั้นตอนการคัดเลือก individual ที่มีลักษณะที่เหมาะสมไว้เพื่อส่งต่อ ความเหมาะสมนี้วัดด้วยสิ่งที่เรียกว่า fitness function ซึ่งต้องสร้างขึ้นมาโดยให้ผลที่สอดคล้องกับการแก้ปัญหา fitness function ถือเป็นหัวใจหลักของ GA ต้องพิจารณาให้ดี
Selection
มีหลายรูปแบบ จะขอกล่าวถึงแบบที่ใช้ง่ายและเห็นได้บ่อย
1. Roulette Selection
 |
| รูปที่ 1 French roulette |
| Individual | Fitness | Proportion (Probablility) |
|---|---|---|
| A | 8 | \(\frac{8}{28} =0.28571429 \) |
| B | 3 | \(\frac{3}{28} =0.10714286\) |
| C | 4 | \(\frac{4}{28} =0.14285714\) |
| D | 4 | \(\frac{4}{28} =0.14285714\) |
| E | 9 | \(\frac{9}{28} =0.32142857\) |
| \(\sum_1^5{fitness} = 28 \) | \(\sum_1^5{proportion} = 1.00 \) |
จากตารางตัวอย่างนี้ความน่าจะเป็นในการถูกเลือกจากมากไปน้อยคือ E,A,D,C,B ตามลำดับ
linear fitness scaling
ในบางครั้งการใช้ fitness อาจทำให้เกิดความแตกต่างกันมากจนอาจทำให้ individual บาง individual แทบไม่มีโอกาสถูกเลือกเลยก็ได้ การลด bias อาจใช้เทคนิคที่เรียกว่า scaling หรือการเปลี่ยนค่าให้ไปอยู่ในช่วงตัวเลขอื่นโดยอาศัยสมการเส้นตรง
\[ \text{new fitness} = a \times \text{old fitness} + b\]
โดยที่ a,b คือค่าคงที่
ขั้นตอน
1. กำหนดค่า maximum และ minimum ของ rank ใหม่ เช่น [1,5]
2. เอา fitness ของ 2 individual ที่มีค่ามากที่สุดและน้อยที่สุด ในกรณีนี้คือ B และ E โดยค่า new fitness ของ E,B จะเป็น 50 และ 1 ตามลำดับ แล้วแก้สมการ 2 ตัวแปร
\[ E : 5 = 9a + b \] \[ B : 1 = 3a + b \] \[ \therefore a = \frac{2}{3}, b = -1\]
3. นำค่า a,b มาสร้าง fitness ใหม่และหาค่า proportion
| Individual | Old Fitness | New Fitness | Proportion (Probablility) |
|---|---|---|---|
| A | 8 | 4.33 | \(\frac{4.33}{13.67} = 0.31707317 \) |
| B | 3 | 1.00 | \(\frac{1.00}{13.67} = 0.07317073 \) |
| C | 4 | 1.67 | \(\frac{1.67}{13.67} = 0.12195122 \) |
| D | 4 | 1.67 | \(\frac{1.67}{13.67} = 0.12195122 \) |
| E | 9 | 5.00 | \(\frac{5.00}{13.67} = 0.36585366 \) |
| \(\sum_1^5{fitness} = 28 \) | \(\sum_1^5{fitness} = 13.67 \) |
Crossover
บางครั้งจะเห็นในชื่อของ Mating สิ่งที่เกิดขึ้นในขั้นตอนนี้คือการแลกเปลี่ยน gene ระหว่าง 2 individual ที่ได้จากขั้นตอน selection โดยมีสมมุติฐานว่า การแลกเปลี่ยนนี้จะทำให้เกิด individual ในรุ่นถัดไปที่มี fitness ที่ดีขึ้นกว่ารุ่นก่อนหน้า
1. Single point crossover : chromosome ของแต่ละ individual ในรุ่น parent จะถูกแยกส่วนออก โดยตำแหน่งที่จะถูกแยกนั้นกำหนดขึ้นมาแบบสุ่ม 1 ตำแหน่ง
2. Two points crossover : เหมือนกับแบบแรก เพียงแต่ chromosome ของแต่ละ individual ในรุ่น parent จะถูกแยกส่วนออก โดยตำแหน่งที่จะถูกแยกนั้นกำหนดขึ้นมาแบบสุ่ม 2 ตำแหน่ง
3. Uniform crossover : geneที่ถูกเลือกแต่ละ gene จะถูกเลือกสลับไปมาระหว่าง parent ด้วยความน่าจะเป็นเท่ากัน แล้วนำมาประกอบกันในรุ่นลูก
Mutation
คือการเปลี่ยนแปลงในส่วนเล็กๆภายใน chromosome ของแต่ละ individual ในตอนนี้จะกล่าวถึงเฉพาะ Random mutation
ถ้า \( x \in [a,b] \) แล้วจะได้ \[ M_u (x) = U[a,b] \]
เมื่อ \( U[a,b] \) คือ Uniform distribution ของ [a,b]
Elitism
ไม่มีแสดงในรูปที่ 1 แต่ขอกล่าวไว้สักหน่อย เมื่อเราสร้าง population ด้วยการทำ crossover และ mutation แล้วทำให้เรามีโอกาสพบกับลักษณะที่ดีใน individual ของ generation รุ่นถัดไป แต่ในขณะเดียวกันเราก็มีโอกาสที่จะสูญเสีย individual ที่มีลักษณะที่ดีไปด้วยเช่นกัน เพื่อเป็นการลดโอกาสการสูญเสีย จึงได้มีการเพิ่มเติมเรื่อง Elitism เข้ามา หลักการคือ individual กลุ่มหนึ่ง (จำนวนน้อย) ที่มีลักษณะที่ดี (ดูจากค่า fitness) จะถูกคัดเลือกไปสู่ generation ถัดไปโดยไม่ต้องผ่านขั้นตอน selection, crossover และ mutation เหมือน individual ที่มี fitness น้อยกว่า ข้อควรระวังในการใช้ elitism คือต้องไม่ใช้จำนวนมากเกินไป จนทำให้เกิดการเปลี่ยนแปลงในประชากรน้อยเกินไปการหยุด
มีเหตุผล 3 ประการในการที่จะหยุดขั้นตอนการทำงาน คือ
1. ค่าที่ได้จาก fitness function ถึงเป้าหมายที่ตั้งไว้
2. ค่าที่ได้จาก fitness function ไม่ถึงเป้าหมายแต่มีท่าทีว่าจะไม่มีการเปลี่ยนแปลง
3. ต้นทุนการทำงานสูงเกินกว่าจะรับได้
ในตอนที่ 3 จะกล่าวถึงตัวอย่างการเขียนโปรแกรมคอมพิวเตอร์โดยใช้ GA กัน
ในตอนที่ 3 จะกล่าวถึงตัวอย่างการเขียนโปรแกรมคอมพิวเตอร์โดยใช้ GA กัน
ความคิดเห็น
แสดงความคิดเห็น