 |
| By George Richmond - From Origins, Richard Leakey and Roger Lewin, Public Domain, Link |
การวิวัฒนาการ (evolution) [1] ของสิ่งมีชีวิตด้วยกระบวนการคัดเลือกโดยธรรมชาติ (natal selection) [2] ที่เสนอโดย Charles Darwin [3] พอสรุปแนวคิดหลักคร่าว ๆ ได้ดังนี้
1. สิ่งมีชีวิตมีความหลายหลาย เช่น มนุษย์มีสีผม สีผิว สีตา ความสูง ความแข็งแรง ว่องไว ฯล แตกต่างกัน
2. สภาพแวดล้อมมีผลต่อการอยู่รอด และขยายพันธุ์ สิ่งมีชีวิตที่อยู่ในสภาพแวดล้อมที่ปลอดภัย อุดมสมบูรณ์ย่อมมีทางรอดมากกว่า
3. มีการถ่ายทอดลักษณะไปยังรุ่นต่อไปผ่านระบบพันธุกรรม
4. ลักษณะสอดคล้องกับสภาพแวดล้อมย่อมมีโอกาสขยายพันธุ์ต่อไป
ความแตกต่างของลักษณะที่แสดงออกมาในสิ่งมีชีวิตถูกกำหนดไว้ในสิ่งที่เรียกว่า gene [4][7] อยู่เรียงตัวเป็นสายยาว แล้วม้วนตัวเข้าหากันคล้ายไหมพรม เรียกว่า chromosome [5] ซึ่งถูกเก็บไว้ใน nucleus ของเซลล์อีกทีหนึ่ง
 |
| รูปที่ 2 แสดงตำแหน่งของ gene และ chromosome ภายในเซลล์ของสิ่งมีชีวิต gene แต่ละตำแหน่งบน chromosome อาจมีความยาวแตกต่างกันไป |
การถ่ายทอดลักษณะของสิ่งมีชีวิตอาศัยกระบวนการที่เรียกว่าการจับคู่ (mating) [8] กันระหว่างสิ่งมีชีวิตชนิดเดียวกันในรุ่นหนึ่ง การจับคู่ทำให้เกิดการแลกเปลี่ยน gene (crossover) ระหว่าง individual แล้วสำเนาส่งต่อไปสู่รุ่นถัดไป (offspring) การแลกเปลี่ยน gene ส่งผลทำให้เกิดการหมุนเวียนของ gene ในประชากร นำไปสู่การเกิดขึ้นของลักษณะแสดงออกที่หลากหลาย ซึ่งอาจเป็นลักษณะที่เหมาะต่อการอยู่รอดของเผ่าพันธุ์ต่อไปได้ จากรูปที่ 3 เป็นการจับคู่กันระหว่างผีเสื้อพันธุ์เดียวกันแต่มีลักษณะที่แสดงออก (สี) ต่างกัน (มี gene บางส่วนต่างกัน) อาจส่งผลให้รุ่นลูกที่ออกมาอาจมีสีต่างไปจากรุ่นพ่อ-แม่ ได้
 |
| รูปที่ 3 Chalkhill blue butterflies (Lysandra coridon) mating By Charles J Sharp - Own work, from Sharp Photography, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=38295927 |
ยังมีอีกกระบวนการหนึ่งที่จะมีผลต่อการเปลี่ยนแปลงของลักษณะของสิ่งมีชีวิต นั่นคือ การกลายพันธุ์ (mutation)[9] การกลายพันธ์ุเกิดจากการเปลี่ยนแปลงลำดับภายในของ gene อาจส่งผลทำให้เกิดลักษณะที่แตกต่างออกไปจากปรกติจนกลายเป็นลักษณะใหม่ที่เหมาะสมกว่าหรือไม่เหมาะสมต่อการดำรงอยู่ต่อไปก็ได้ การกลายพันธุ์ในสิ่งมีชีวิตอาจเกิดจากความผิดพลาดระหว่างการสำเนา gene เพื่อส่งต่อไปยังรุ่นลูกหรืออาจเกิดจากสภาพแวดล้อม เช่น การรับรังสี สารพิษ ฯล ก็ได้
วงจรที่เกิดขึ้นในสิ่งมีชีวิตคือ ลักษณะถูกจัดเก็บไว้ใน gene ซึ่งขดรวมตัวกันเรียกว่า chromosome อยู่ใน nucleus ของ cell สิ่งมีชีวิตชนิดเดียวกันทำการจับคู่กัน จะเกิดการแลกเปลี่ยน gene ระหว่างกัน และถูกส่งต่อไปยังรุ่นถัดไป (offspring) ระหว่างนี้อาจเกิดการกลายพันธุ์ขึ้น การกลายพันธุ์อาจทำให้เกิดลักษณะที่ดีกว่าหรือแย่กว่า ลักษณะที่ดีกว่าเหมาะสมกว่าจะอยู่รอดและถูกส่งต่อไปยังรุ่นถัดไป เป็นแบบนี้เรื่อยๆ จนกว่าจะอะไรมาหยุดวงจรนี้
 |
| รูปที่ 4 ตัวอย่างวงจรการถ่ายทอดลักษณะของสิ่งมีชีวิต |
Genetic Algorithm เขียนอย่างย่อเป็น GA [6] เป็น search algorithm ที่อยู่ในกลุ่ม evolutionary algorithm [11] เกิดจากการนำแนวคิดการคัดเลือกโดยธรรมชาติของ Charles Darwin ดังที่กล่าวมาแล้ว นำมารวมเข้ากับเทคนิคที่เรียกว่า Generate and Test แนวทางใน GA คือ
- มี candidate solution หรือ individual (เทียบได้กับสิ่งมีชีวิตแต่ละ unit) รวมตัวเป็น population
- แต่ละ individual จะมีลักษณะหรือคุณสมบัติ (feature) ซึ่งจะถูกแทนที่อย่างเหมาะสมและจัดให้รูปในรูปแบบเดียวกับ gene บน chromosome ของสิ่งมีชีวิต
- ทุก individual จะถูกทดสอบว่ามีคุณสมบัติเหมาะสมต่อการแก้ปัญหามากน้อยเพียงใด ผ่าน function ที่เรียกว่า fitness function
- แต่ละ individual จะแข่งกันจับคู่กับ individual อื่นที่ใน population เดียวกัน เพื่อผสม gene แล้วส่งต่อไปยัง individual รุ่นถัดไป (offspring)
- ในขั้นตอนของการส่งต่อ gene อาจกำหนดให้มีการเพิ่ม gene เข้าไปใน chromosome ทำนองเดียวกันกับการเกิด mutation ของสิ่งมีชีวิตได้
เขียนในรูปแบบของ pseudo code
generate initial population , G(0)
evaluate G(0)
t := 1
repeat :
generate population G(t) using G(t-1)
evaluate G(t)
t = t + 1
until solution is found
 |
| รูปที่ 5 Flowchart ของ GA |
ยกตัวอย่างปัญหาการเดาคำ
สมมุติว่าต้องการให้ GA ทำการสร้างคำ "genetic" ขั้นตอนตาม flowchart ในรูปที่ 5 คือ
Initiate population
ใน population ประกอบด้วย individual แต่ละ individual ในปัญหานี้คือตัวแทนของคำที่มีความยาว 7 ตัวอักษร (ใช้อักษรภาษาอังกฤษ) สร้าง individual ขึ้นมาแบบสุ่ม สมมุติกำหนดให้มี individual ทั้งหมด 10 individual สำหรับ population รุ่นแรก (\(G_0\))
 |
| รูปที่ 6 ตัวอย่าง population ใน Generation ที่ t=0 (G0) |
Evaluation
ในธรรมชาติสิ่งมีชีวิตมีการเปลี่ยนแปลงโดยตอบสนองต่อสิ่งแวดล้อม ใน GA ใช้ fitness function เป็นตัวทำหน้าที่แทนสิ่งแวดล้อม ในตัวอย่างนี้ เป้าหมายคือการสร้างคำ 'genetic' ขึ้นมา ดังนั้น fitness function จึงเป็น function ที่ใช้บอกว่า chromosome ในแต่ละ individual ต่างจาก 'genetic' เท่าใด เราอาจใช้การวัดแบบง่ายคือการนับจำนวนตัวอักษรที่ตรงกันก็ได้ จากตัวอย่างนี้จะเห็นใน \( G_0 \) ไม่มี individual ใดที่มี chromosome ที่ตรงกับ "genetic" เลย ดังนั้น ทุก individual มี fitness เป็น 0
Mating
ทำการเลือก individual ใน \( G_0 \)มาครั้งละ 1 คู่แบบสุ่ม (การเลือกทำได้หลายวิธี จะกล่าวถึงต่อไป) เพื่อสร้าง generation ต่อไป \( G_1\)
 |
| รูปที่ 7 Generation ถัดมา มีการเปลี่ยนแปลง chromosome เนื่องจาการ crossover |
ลำพังการ crossover มักจะไม่ทำให้เกิดการเปลี่ยนแปลงมากนัก เพื่อให้การเพิ่ม gene เข้าไปใน population จึงต้องเพิ่มกระบวนการ mutation เข้าไป โดย gene ใหม่จะถูกนำมาจาก gene pool แบบสุ่ม ซึ่งจะโยงกับกรอบปัญหาที่กำลังสนใจ ในกรณีนี้ gene pool คือ อักษรตัวเล็กในภาษาอังกฤษ
 |
| รูปที่ 8 ตำแหน่งของ genet ที่เกิด mutant แทนที่ด้วยสีแดง |
Iteration
หลังจากได้ population ในรุ่นถัดไปแล้ว \(G_t \) ก็กลับไปสู่ขั้นตอน evaluation อีกครั้ง เรื่อยไปจนกว่าจะได้ population ที่มี individual ที่ตรงกับเงื่อนไขของการหยุดทำงาน
กล่าวโดยสรุป ในตอนนี้เป็นการเล่าถึงพื้นหลังของหลักคิดของ GA ที่ได้ล้อขั้นตอนของการคัดเลือกโดยธรรมชาติมาใช้ในการหาทางแก้ปัญหาทีกำหนด โดยหัวใจสำคัญอันหนึ่งของ GA คือ fitness test เป็นขั้นตอนสำคัญที่จะบอกว่า แนวทางแก้ปัญหาใดควรอยู่ต่อไแป แนวทางใดควรถูกกำจัดออกแล้วหาแนวทางใหม่มาทดแทน เช่นเดียวกับที่ธรรมชาติใช้เพื่อคัดเลือกสิ่งมีชีวิตที่เหมาะสมที่จะอยู่รอดในสภาพแวดล้อม แม้จะใช้เวลานานแต่ก็มีประสิทธิภาพ
ในตอนที่สองจะกล่าวถึงองค์ประกอบพื้นฐานและ basic flow ของ GA กันก่อนที่จะเข้าสู่ตัวอย่างการเขียน code ด้วยภาษา Python
เอกสารอ้างอิง
[1] https://en.wikipedia.org/wiki/Evolution
[2] https://en.wikipedia.org/wiki/Natural_selection
[3] https://en.wikipedia.org/wiki/Charles_Darwin
[4] https://en.wikipedia.org/wiki/Gene
[5] https://en.wikipedia.org/wiki/Chromosome
[6] https://th.wikipedia.org/wiki/%E0%B8%82%E0%B8%B1%E0%B9%89%E0%B8%99%E0%B8%95%E0%B8%AD%E0%B8%99%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%80%E0%B8%8A%E0%B8%B4%E0%B8%87%E0%B8%9E%E0%B8%B1%E0%B8%99%E0%B8%98%E0%B8%B8%E0%B8%81%E0%B8%A3%E0%B8%A3%E0%B8%A1
[7] https://en.wikipedia.org/wiki/Genetic_code
[8] https://en.wikipedia.org/wiki/Mating
[9] https://en.wikipedia.org/wiki/Mutation
[10] https://en.wikipedia.org/wiki/Least_squares
[11] https://en.wikipedia.org/wiki/Evolutionary_algorithm
ความคิดเห็น
แสดงความคิดเห็น