มารู้จัก Genetic Algorithm พื้นฐานกัน มันกว่าที่คิด

Genetic Algorithm 

           ขั้นตอนวิธีเชิงพันธุกรรม (Genetic Algorithm – GA) เป็นเทคนิคทางปัญญาประดิษฐ์ (AI : artificial intelligence) อย่างหนึ่งที่ใช้ในการค้นหา การเพิ่มประสิทธิภาพ และการเรียนรู้ (Search, Optimization, and Learning) ด้วยการเลียนแบบทฤษฎีการวิวัฒนาการทางธรรมชาติ โดยขั้นตอนวิธีเชิงพันธุกรรมมีจุดเด่นในด้านความทนทานต่อความผิดพลาดในการค้นหาคำตอบจากแหล่งข้อมูลที่มีความซับซ้อนและยากที่จะสร้างแบบจำลองด้วยสมการคณิตศาสตร์ เนื่องจากเป็นกระบวนการค้นหาที่ไม่มีความเฉพาะเจาะจงกับแบบจำลองหรือลักษณะเฉพาะของข้อมูลแบบใดแบบหนึ่ง ด้วยเหตุนี้ขั้นตอนวิธีเชิงพันธุกรรมจึงถูกนำมาประยุกต์ใช้ในการแก้ปัญหาได้หลากหลายรูปแบบ
     - ตั้งแต่การจัดตารางเวลา (Timetable Scheduling)
     - การออกแบบระบบควบคุมอัตโนมัติ (Control System Design)
     - การออกแบบเพื่อเพิ่มประสิทธิภาพของระบบท่อส่งก๊าซ (Gas Pipeline Optimization)
     - การพัฒนาระบบปัญญาประดิษฐ์ (AI : artificial intelligence) ที่สามารถเรียนรู้จากสภาพแวดล้อมได้ (Genetic Based Machine Learning)
     เป็นต้น
    โดยหลักการของขั้นตอนวิธีเชิงพันธุกรรม เป็นการเลียนแบบกระบวนการวิวัฒนาการตามธรรมชาติ เพื่อพัฒนาหรือทำการ

“วิวัฒนาการ” 

คำตอบที่ดีที่สุดในการแก้ปัญหา

ที่มา : https://kapitaennem0.wordpress.com/2013/07/17/genetic-algorithm/

(ผู้เขียนบล๊อกนี้อธิบายได้ดี ผมจึงนำมานำเสนอต่อ)

Genetic Algorithm มีอะไรบ้าง

สำหรับองค์ประกอบหลักๆ ของ Genetic Algorithm มีดังนี้

1. Chromosome Encoding
2. Initial Population
3. Fitness Function
4. Genetic Operator -> Selection, Crossover, Mutation
5. Replacement

1. Chromosome Encoding

เป็นขั้นตอนในการแปลงปัญหาให้เป็น Chromosome หรือพูดง่ายๆคือ รูปแบบหรือรูปร่างของข้อมูลของปัญหานั้นๆ
เช่น ปัญหา Binary Encoding จะมีลักษณะของ Chromosome เป็นดังนี้

1001 1011

นิยามให้มันมี 0 หรือ 1 และมียีนในแต่ละ  Chromosome ทั้งหมด 8 ตัว

2. Initial Population

คือการ สร้างประชากรขึ้นมาโดยการสุ่มสร้างหรือสุ่มเลือกขึ้นมา และการสร้างจำนวนประชากร(จำนวน Chromosome) จะเป็น Parameter ของ Algorithm
เช่น เราจะสร้างประชากรขึ้นมา 4 Chromosome โดยการสุ่มเลข 0 , 1 เข้าไปใน Chromosome

A: 0110 0100
B: 0010 1011
C: 1110 1101
D: 1101 1001

3. Fitness Function

คือสิ่งที่จะใช้ในการการประเมินค่าความเหมาะสม หรือ คะแนนของประชากรนั้นๆ เพื่อใช้ในการพิจารณาว่า โครโมโซมตัวนั้น เหมาะหรือไม่ที่จะนำมาใช้สืบทอดพันธุกรรมสำหรับสร้างโครโมโซมรุ่มใหม่หรือไม่ โดยสมการหรือวิธีการในการคิดค่า Fitness นั้นขึ้นอยู่กับปัญหานั้นๆ
เช่น ในปัญหา Binary Encoding เราจะให้ Chromosome ที่มีเลข 1 จะนับเป็น 1 คะแนน

A: 0110 0100 = 3
B: 0010 1011 = 4
C: 1110 1101 = 6
D: 1101 1001 = 5

4. Genetic Operator

จะให้พูดง่ายๆในขั้นตอนนี้คือ เป็นวิธีปรับเปลี่ยนองค์ประกอบของ Chromosome ซึ้งจะแบ่งออกเป็น 3 ส่วนได้แก่
       1 Selection
          เพื่อให้เกิดการอยู่รอดของสิ่งมีชีวิต จึงต้องทำการคัดเลือกประชากรบางส่วนเพื่อใช้ในการสืบทอดในรุ่นถัดไป ซึ้งในที่นี้คือการคัดเลือก Chromosome ที่จะใช้ในการทำขั้นตอน Genetic ในขั้นตอนถัดไป โดยวิธีการคัดเลือกนั้นก็มีมากมายหลายอย่าง เช่น
   - Roulette Wheel
   - Ranking
   - Tournament
   - Elitist
   - Steady State
   เป็นต้น
โดยปัญหา Binary Encoding นั้นเราจะใช้วิธีการคัดเลือกทั้งหมด (ง่ายดี) และสำหรับการ Crossover จะใช้ค่า Fitness ที่ดีที่สุดผสมกัน

        2 Crossover
           เป็นกระบวนการในการนำ 2 Chromosome มาผสมกันกันเพื่อให้ได้ Chromosome ใหม่ๆเกิดขึ้น
และสำหรับ ปัญหา Binary Encoding เราจะใช้วิธีที่ง่ายที่สุดคือ แบ่งครึ่ง Chromosome ระหว่าง 2 Chromosome และนำมาผสมกัน

C: 1110 1101 = 6
D: 1101 1001 = 5
B: 0010 1011 = 4
A: 0110 0100 = 3

ดังนั้น  C กับ D , A กับ B จะ Crossover กัน

C' : 1110 / 1001
D' : 1101 / 1101
B' : 0010 / 0100
A' : 0110 / 1011

       3 Mutation
          คือการทำการเปลี่ยนแปลงคุณลักษณะภายใน Chromosome ในบางตำแหน่งของรุ่นลูกเพื่อให้เกิดลักษณะใหม่ๆเกิดขึ้น เช่น จากตัวอย่าง ในตำแหน่งยีนที่ 7 สิ่งใดมีค่าเป็น 0 ให้เปลี่ยนเป็น 1 ทั้งหมด

C' : 1110 / 1011
D' : 1101 / 1111
B' : 0010 / 0110
A' : 0110 / 1011

5. Replacement
หรือการแทนที่ประชากรรุ่นเก่า ซึ้งวิธีการแทนที่ก็มีหลายหลายรูปแบบมากมาย ไม่ว่าจะเป็นการแทนที่ประชากรรุ่นเก่าทั้งหมด หรือการแทนที่ประชากรเฉพาะบางประชากรเท่านั้นโดยมีวิธีเลือกจากค่า Fitness หรือ ประชากรที่ถูกคัดเลือกจาก Selection แล้ว copy ประชากรที่ไม่ได้ถูกเลือก Selection มาเป็นรุ่นถัดไป บลาๆๆๆๆๆๆๆๆ มากมาย

จากนั้นถ้ายังได้ประชากรรุ่งนที่เรายังไม่ถูกใจ ก็ไปเริ่มกระบวนการใหม่ในขั้นตอนที่ 2 ไปเรื่อยๆ จะกว่าจะถึงจุดที่เราพอใจ แล้วแต่ว่าจุดที่เราพอใจคืออะไร หรือวัดจากอะไรแล้วแต่ความเหมาะสมของปัญหานั้นเอง

ทั้งหมดนี้คือ Genetic Algorithm ขั้นพื้นฐานเท่านั้น ซึ้งเป็น Algorithm ที่ใช้ศิลปะในการทำอีกมากมาย ซึ้งมันทำให้ผมรู้สึกสนุกนั้นเอง ... ผิดพลาดประการก็ขออภัยมา ณ ที่นี้ด้วยครับ หรือมีอะไรเพิ่มเติมก็ comment มาด้านล่างได้เลยครับ