Genetic Algorithm ขั้นตอนวิธีเชิงพันธุกรรม

สวัสดีคร้าบ ผู้อ่านทุกท่าน วันนี้เราจะมาพูดถึง Genetic Algorithm กันนะครับ มันคืออะไร ใช้ทำอะไร ก่อนจะไปทำความรู้จักกับมัน ดูคลิปนี้ก่อนเลยครับ ว่ามันล้ำขนาดไหน!!!??

คลิปนี้เป็นการนำ Genetic Algorithm มาใช้ให้ไอเจ้าก้อน ๆ นี่มันกระโดดข้ามบอลได้

เจ้า Genetic Algo. มันคือวิธีการค้นหาคำตอบ(วิธีการ)ที่เหมาะสมที่สุด โดยมีรูปแบบการทำงานเหมือนกับการคัดเลือกหรือการวิวัฒนาการทางธรรมชาติ

เช่น สมมติว่า เราทำระบบการจัดตารางเวลา ซึ่งตอนแรกเราก็อาจจะจัดเวลาได้ไม่ดี ลองจัดไปเรื่อย ๆ ลองย้ายนู่นย้ายนี่ สลับนิด ขยับหน่อย (mutation, crossover) สุดท้ายก็จะได้ตารางเวลาที่จัดแล้วดีที่สุด

Genetic Algo ต้องทำยังไงบ้าง งง!

• Chromosome Encoding
• Initial population
• Fitness function
• Genetic Operator (Selection, Crossover, Mutation)
• Termination

Chromosome Encoding

มันคือการเอา Feature ต่าง ๆ ของคำตอบที่เป็นไปได้มาทำให้อยู่ในรูปแบบ Chromosome เช่น ปัญหาของการทำระบบการจัดตารางเวลา เราอาจจะใช้ Binary encoding เข้ามาช่วยครับ สมมติว่า 1 วัน มี 8 ชั่วโมง แล้วให้เลข ‘1’ แทน ‘ว่าง’ และ ‘0’ แทน ‘ไม่ว่าง’ ก็จะได้เป็น Chromosome ดังนี้

1111 0000 -> ว่างตอน 4 ชั่วโมงแรก ไม่ว่าง 4 ชั่วโมงหลัง

แปลว่ารูปแบบการ Encode ของเราคือ แต่ละ bit แทน แต่ละชั่วโมงตามลำดับ

Initial population

อันดับต่อมา เราก็จะทำการ กำหนดจำนวนประชากร (คำตอบ) ที่เราจะสร้างขึ้นมาตอนแรก (อาจจะด้วยการสุ่ม) แล้วก็ทำการสุ่ม Chromosome ขึ้นมาตามจำนวนนั้น

เช่นเราบอกว่าจะเริ่มจาก 5 Chromosome ก็จะได้

1100 0101
1001 0111
0000 1111
0101 1010
1110 1111

Fitness function

อันนี้สำคัญเลย มันคือ function ที่จะใช้ประเมินว่า Chromosome ไหนจะได้ไปต่อในรอบต่อไป ใครจะเป็นผู้ที่ได้รับการคัดเลือก เจ้านี่แหละเป็นเกณฑ์ในการตัดสิน ซึ่งก็จะแตกต่างไปตามแต่ละปัญหา

สมมติถ้าปัญหาอันนี้ผมบอกว่า อยากให้ ตอนเช้าว่าง ‘มากกว่า’ ตอนบ่าย และ ไม่ว่างติดกันห้ามเกิน 2 ชั่วโมง

เราก็จะเอาเกณฑ์ตรงนี้มาคิด อาจจะให้คะแนนเป็น 1,0 ธรรมดาว่าเข้าเงื่อนไขไหม หรืออาจจะมีวิธีการให้คะแนนในรูปแบบอื่น เช่น การให้ค่าความสำคัญ (weight) ของแต่ละเงื่อนไข มาช่วยจัดคะแนนก็ได้ครับ

Genetic Operator

เจ้านี่คือวิธีการในการปรับเปลี่ยนรูปแบบโครงสร้างของเจ้า Chromosome สำหรับรุ่นถัดไปครับ ซึ่งก็มีวิธีการอยู่หลายแบบ แบ่งเป็น 3 อันหลัก ๆ ครับ

1. Selection

มันคือการเลือก Chromosome รุ่นถัดไปด้วยรูปแบบการเลือกสักอย่างนึง เช่น Ranking, Roulette Wheel, Elitist

ยกตัวอย่างเช่น เราอาจจะเลือกตัวที่คะแนน Fitness เยอะสุด 5 ตัวแรก ไปรอบถัดไป

2. Crossover

มันคือการนำ Chromosome 2 เส้น มาผสมกันให้เป็นค่าใหม่ ซึ่งก็อาจจะสุ่ม Chromosome บางคู่เข้ามาทำครับ เช่น

Crossover

จะเห็นว่ามันก็จะเกิดเป็น Chromosome เส้นใหม่ขึ้นมาแบบนี้ สำหรับใช้ในรอบคัดเลือกรอบถัดไป

3. Mutation

มันคือการนำ Chromosome มา ‘ผ่าเหล่า’ หรือเปลี่ยนยีนส์ในนั้นสักอันนึงเพื่อให้เกิดความแตกต่างของ Chromosome รอบถัดไป ซึ่งก็อาจจะสุ่ม Chromosome บางเส้นเข้ามาทำครับ

Mutation

แล้วมันก็จะทำวนอยู่แบบนี้แหละครับ

Genetic Algorithm chart (http://learnabouttravelmaps.info/pics/g/genetic-algorithm.html)

Initial population -> Evaluate (เอาเข้า Fitness) -> Selection -> Crossover -> Mutation -> วนกลับไปใหม่ ถ้ายังไม่ถึงจุดที่พอใจหรือ Termination Criteria

Termination

มันคือจุดที่เราพอใจแล้ว เช่น คะแนน Fitness เกินที่กำหนดแล้ว หรือคะแนน Fitness มันไม่มากไปกว่านี้แล้วเป็นจำนวน 10 รุ่น(Generation)

ตัวอย่าง Code

Evolutionary algorithm - Rosetta Code

ตัวอย่างการนำไปใช้

คลิปนี้เค้านำ Genetic Algorithm มาสร้างตัวเอเลี่ยน ว่าแบบเอเลี่ยนที่มี ขนาด, สี, ความเร็ว, รูปแบบการเคลื่อนไหว แบบไหนที่เราไม่ฆ่ามัน หรือมันอยู่รอด

สุดยอดไหมล่ะครัช แบบนี้แล้วจะอดใจไว้ ไม่ค้นหาต่อได้ยังไง!! ไปค้นหาความมหัศจรรย์ของ Algorithm เหล่านี้กันเถอะครับ!

Credit: http://learnabouttravelmaps.info/pics/g/genetic-algorithm.html