Introduction
to Evolutionary Algorithms
Introduction to Evolutionary Algorithms คือการนำต้นแบบของรุ่นปัจจจุบันเพื่อนำมาสร้างรุ่นต่อไป เช่น การผลิตรถ จะมีการพัฒนารูปทรง สมรรถนะเครื่องยนต์์ อย่างต่อเนื่องแต่ยังคงไว้ซึ่งเอกลักษณ์ของรุ่นเดิม การพัฒนานี้เป็น genneration จากรุ่นต่อรุ่น และ อัลกอลิทึมที่ถูกนำมาใช้มากที่สุดคือ ขั้นตอนวิธีเชิงพันธุกรรม (genetic algorithm )
genetic algorithm
initialize population
ตัวอย่าง one max problem หาบิตสตริงที่ทุกๆ บิต เป็น 1 หมด
one max 10 บิต คำตอบที่ดีที่สุดคือ 1 111 111 111
ขั้นตอน
1. สร้างประชากรเริ่มต้น (สมติว่ามีประชากร 6 ตัว )
- 100 110 100 1 มีหนึ่งทั้งหมด 5 fitness value = 5
- 001 010 011 0 มีหนึ่งทั้งหมด 4 fitness value = 4
- 110 011 010 0 มีหนึ่งทั้งหมด 5 fitness value = 5
- 001 011 101 1 มีหนึ่งทั้งหมด 6 fitness value = 6
- 110 010 111 0 มีหนึ่งทั้งหมด 6 fitness value = 6
- 011 110 101 1 มีหนึ่งทั้งหมด 7 fitness value = 7
การนำจำนวนเลขหนึ่ง ว่าแต่ละตัวอย่างมีหนึ่งทั้งหมดกี่ตัว เรียกค่านั้นว่า fitness value
2. fitness funtion ประเมินค่าความเหมาะสม
3. คัดเลือกประชากรตัวที่ดีๆ มาสร้างประชากรใหม่
เลือกหมายเลข 2,4 มาสร้างประชากรใหม่
ขั้นตอนการสร้างประชากรใหม่
1. cross over
001 0100 110 -->พ่อ,แม่ 1
001 0111 011 -->พ่อ,แม่ 2
0010100 011 -->ลูก 1
0010111 110 -->ลูก 2
เกิดการแลกเปลี่ยนบิต 3 ตัวท้าย ทำให้เกิดรุ่นลูกใหม่ 2 ตัว
2.mutation เป็นการวิเคราะห์สุ่มหาตำแหน่งที่อาจจะเกิดการกลายพันธ์ุ
0010100 011 -->ลูก 1
0010111 110 -->ลูก 2 --> 0110111 110 กลายพันธ์ุตำแหน่งที่ 2 นับจากทางซ้าย
ทำให้ได้ประชากรรุ่นใหม่ดังนี้
- 0010100 011
- 0110111 110
- ----------- -----
- ----------- -----
- ----------- -----
- ----------- -----
สุ่มนำตัวอย่างที่เป็นค่าเริ่มต้นมาเข้ากระบวนการเพื่อหารุ่นลูกลำดับที่ 3 4 5 6 (ในที่นี้ขอเว้นไว้เพราะหลักการเดียวกัน)
ถ้าในรุ่นนี้ไม่มีคำตอบ ให้นำรุ่นลูกมาคิดต่อจนกว่าจะได้คำตอบที่ดีที่สุดคือ 1111111111
