สวัสดีครับหลังจากห่างหายไปนาน เนื่องจากได้ไปศึกษา AI ตัวนึงที่มีอัลกอริทึมที่ชื่อว่า Genetic Algorithm ซึ่งเป็นแนวคิดที่ดี ซึ่งสามารถนำ Gentic Algorithm ไปประยุกต์ในการแก้ปัญหาหลายๆอย่างดังลิงค์นี้ครับ
https://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications ซึ่งจะเห็นว่ามีหลายแอพพลิเคชันเลยที่นำไปใช้
"แล้ว Genetic Algorithm คืออะไร?"
Genetic Algorithm ก็คือขั้นตอนการแก้ปัญหาบางอย่างโดยเลียนแบบกระบวนการถ่ายทอดทางพันธุกรรม
"แล้วทำไม่ต้องเลียนแบบการถ่ายถอดทางพันธุกรรม?"
เนื่องจากเราสังเกตุว่าสิ่งมีชีวิตที่อยู่รอดปัจจุบันนั้นเกิดจากการวิวัฒนาการให้เข้ากับสภาพแวดล้อมให้เหมาะสม โดยการวิวัฒนาการของสิ่งมีชีวิตนั้นก็คือ การสืบพันธ์เพื่อให้รุ่นลูกมีสภาพที่ทนต่อสภาพแวดล้อม หรืออาจเกิดจากการกลายพันธ์ รุ่น สู่ รุ่น ไปเรื่อยๆ จนทำให้สิ่งมีชีวิตใหม่ที่ปรับตัวได้เหมาะสมก็จะเป็นผู้อยู่รอดนั่นเอง จึงได้เกิดแนวคิดในการเขียนโปรแกรมเพื่อหาคำตอบของปัญหาโดยให้เปรียบเทียบคำตอบนั้นเหมือนกับสิ่งมีชีวิตแล้วคำตอบนั้นสามารถปรับแก้ไขได้โดยการสืบทอด หรือ การกลายพันธ์จนได้คำตอบที่เหมาะสมกับปัญหามากที่สุดนั่นเอง
"แล้ววิวัฒนาการกับการเขียนโคดมันจะเขียนยังไง?"
ในการที่จะเขียนโคดเพื่อเลียนแบบการวิวัฒนาการของสิ่งมีชีวิตนั้นเราจะมองลึกลงไปอีก ของการวิวัฒนาการนั่นก็คือ Chromosome เพราะสิ่งมีชีวิตที่เกิดการกลายพัน หรือลูกที่เกิดจากการสืบพันธ์นั้นเกิดจาก การทำให้ Chromosome มีการเปลี่ยนแปลงกันทั้งสิ้นดังนั้นในการเขียน Code เราจำเป็นที่จะให้คำตอบในการแก้ปัญหานั้นเปรียบเทียบคล้ายกับ Chromosome นั่นเอง ซึ่งก่อนที่จะเริ่มเขียนโคดกันเรามาทำความเข้าใจของการวิวัฒนาการเมื่อมองในมุมมองของ Chromosome ซึ่งในการวิวัฒนาการนั้นจะมีขั้นตอนดังนี้
1. การคัดสรร คือการเลือก Chromosome ที่เหมาะสมกับธรรมชาติมากที่สุด ส่วน Chromosome ใหนที่ไม่เหมาะสมก็จะตายไป
ดังรูปจะเห็นว่า สิ่งมีชีวิตที่มี Chromosome1, Chromosome2, Chromosome4 จะถูกเลือกให้อยู่รอด ส่วนสิ่งมีชีวิตที่มี Chromosome3 จะตายไป เนื่องจาก Chromosome1, Chromosome2, Chromosome4 มีค่าความเร็วและความแข็งแรงมากกว่า Chromosome3
2. การสืบพันธ์ คือการสืบพันธ์เพื่อให้ได้ Chromosome ตัวใหม่และหวังว่า Chromosome ตัวใหม่นั้นจะดีกว่าเดิม
ดังรูปจะเห็นว่า สิ่งมีชีวิตที่มี Chromosome1, Chromosom2 ได้ทำการสืบพันธ์กัน และได้ลูกมา 2 ตัวหรือก็คือ Chromosome5, Chromosome6 ซึ่งจะเห็นว่า Chromosome5, กับ Chromsome6 เกิดจากการแลกเปลี่ยนบางพันธุกรรมใน Chromosome1 กับ Chromosome2 จนทำให้เกิด Chromome5, กับ Chromome6 นั่นเอง
3. การกลายพันธ์ คือ การทำให้ Chromosome มีการเปลี่ยนเปลงข้อมูลบางจุด
ดังรูปจะเห็นว่า chromosome5 เกิดการกลายพันธ์จนทำให้ค่าความเร็วมีค่ามากขึ้นกว่าของแม่และของพ่อ(นั่นก็คือ Chromosome1 กับ Chromosome2) นั่นเอง
"แล้วตกลงจะมาเขียนโคดยังไง?"
ในการเขียนโคดก็เอาขั้นตอนวิวัฒนาการดังกล่าวนี่แหละมาเขียนโคดซึ่งจะมีขั้นตอนดังนี้
1. Initial population
2. Fitness Function
3. Selection
4. Crossover
5. Mutation
1. Initial population
ในตอนเริ่มต้นจำเป็นจะต้องสร้าง Chromosome หลาย Chromosome ขึ้นมาซึ่ง สิ่งที่เรียกหลายๆ Chromsome ทั้งหมดนี้เราจะเรียกว่า ประชากรดังรูป
โดยข้างใน Chromosome ก็จะมีคำตอบอยู่แล้ว ซึ่งคำตอบเหล่านั้นเป็นคำตอบที่เกิดจากการมั่วทั้งหมดซึ่งอาจทำให้มีทั้งคำตอบที่ผิดมาก มีทั้งที่ผิดน้อย หรือใกล้เคียงกับความถูกต้องมากที่สุด เป็นต้น
2.Fitness Function
เมื่อเรามี Chromosome หลายๆตัวและแต่ละ Chromosome ก็จะมีคำตอบที่แตกต่างกัน ดังนั้นเราจำเป็นที่จะต้องมีการตรวจคำตอบว่า Chromosome แต่ละตัวให้คำตอบที่ใกล้เคียงกับความถูกต้องมากสุดเท่าไหร่ หรือก็คือเราจะทำการให้คะแนนของคำตอบแต่ละ Chromosome นั่นเองว่า คำตอบดีหรือไม่ ถ้าคำตอบดีหรือถูกต้องก็ได้คะแนนเยอะ ถ้าคำตอบไม่ดีหรือไม่ถูกต้องก็ใด้คะแนนน้อยเป็นต้น
3. Selection
คือการเลียนแบบการคัดสรรธรรมชาติโดยเลือกเอากลุ่ม Chromosome ที่ดีที่สุดมา N ลำดับซึ่งเราจะรู้ได้อย่างไรว่า Chromosome ใหนดีไม่ดีสามารถดูได้จากการใข้ Fitness Function จากข้อ 2 นั่นเอง
4. Crossover
ถ้าให้เปรียบเทียบจะคล้ายๆกับการสืบพันธ์ โดยทำการแลกเปลี่ยนข้อมูลระหว่าง 2 Chromosome(Chromosome ของพ่อแม่) จนเกิด Chromosome ใหม่ 2 Chromosome (Chromosome ของลูก)
จากรูปจะเห็นว่า Chromosome3 กับ Chromosome4 มาทำการ Crossover กัน จนเกิด Chromosome ใหม่ขึ้นมา 2 ตัวที่ชื่อว่า Chromosome5 กับ Chromosome6 ที่เกิดจากการสลับข้อมูลระหว่างคำตอบย่อยที่1 กับคำตอบย่อยที่2 หรือถ้าให้เปรียบเทียบก็เหมือนกับเราลอกคำตอบกับเพื่อนสองคนสลับข้อกันและหวังว่าจะทำให้เราถูกมากขึ้นนั่นเอง
5. Mutation
คือการกลายพันธ์ของ Chromosome โดยเกิดจากการสุ่มเปลี่ยนค่าบางค่าในข้อมูลของ Chromosome
ดังรูปจะเห็นว่าหลังจากที่เราทำการ Crossover จากข้อ 4 แล้วเราก็ทำการกลายพันธ์โดยการเลือก คำตอบย่อยที่2 มาเปลียนค่านั้นเอง
ถ้าให้เปรียบเทียบก็เหมือนกับเราเอาคำตอบย่อยมาบางข้อแล้วมามั่วคำตอบใหม่และหวังว่าหลังจากมั่วคำตอบแล้วจะทำให้คะแนนเพิ่มขึ้นนั่นเอง
6. Termination
คือการหาคำตอบที่เหมาะสมกับปัญหา โดยอาจจะดูค่า Fitness แล้วผลที่ได้จาก Fitness ตรงตามที่เราต้องการ หรืออาจจะเป็นค่า Fitness ในรุ่นลูกถัดไปเรื่อยๆไม่ค่อยมีการเปลี่ยนแปลง
โดยลำดับในการทำงานของ Genetic Algorithm นั้นจะเป็นดังนี้ครับ
จะเห็นว่าตอนแรกสุดจะทำการ
Initial population ขึ้นมาจำนวนนึงเสร็จแล้วก็จะทำการคัดสรร(
selector) เพื่อนำไป
Crossover หลังจาก
Crossover แล้วอาจจะมีการ
Mutation ของข้อมูลเกิดขึ้น แล้วเราก็ทำการคัดสรรอีก(
selector) วนไปเรื่อยๆจนกว่าเราได้
Chromosome หรือคำตอบที่เราพอใจ ก็จะทำการ
Termination นั่นเองครับ
ถ้าให้เปรียบเทียบก็เหมือนกับเรานำคำตอบที่เกิดจากการมั่วขึ้นมา N คำตอบ (
Initial population) เสร็จแล้วเราก็มาตรวจคำตอบที่เกิดจากการมั่วนี่แหละว่าใครได้มากใครได้น้อย เสร็จแล้วเราก็เอาคำตอบของพวกที่ได้คะแนนมาก(
selector)มาสลับคำตอบข้อย่อยกัน(
Crossover) เพื่อหวังว่าคำตอบใหม่ที่เกิดจากการสลับไปนั้นจะทำให้ได้คะแนนที่เพิ่มขึ้น และบางครั้งอาจจะลองเลือกข้อย่อยมามั่วเอง(
Mutation) เพื่อหวังว่าข้อที่มั่วจะเป็นตัวที่ได้คะแนนมากกว่าคนอื่น หลังจากนั้นเราก็มาตรวจคำตอบว่าใครได้มากใครได้น้อย เสร็จแล้วเราก็เอาคำตอบของพวกที่ได้คะแนนมาก(
selector) มาสลับคำตอบข้อย่อยกัน(
Crossover) เพื่อหวังว่าคำตอบใหม่ที่เกิดจากการสลับไปนั้นจะทำให้ได้คะแนนที่เพิ่มขึ้น และบางครั้งอาจจะลองเลือกข้อย่อยมามั่วเอง(
Mutation)เพื่อหวังว่าข้อที่มั่วจะเป็นตัวที่ได้คะแนนมากกว่าคนอื่น ทำแบบนี้วนไปเรื่อยๆจนกระทั้งได้คะแนนที่พอใจนั่นเอง(
Termination)
สุดท้ายนี้หวังว่าบทความนี้จะช่วยเพิ่มความเข้าใจในการทำ Genetic Algorithm มากขึ้นและบทต่อไปเราจะนำความรู้เรื่อง Genetic Algorithm มาแก้ปัญหาในการจัดสถานที่เดินทางโดยใช้ระยะทางเดินทางที่น้อยที่สุดกันครับ ตัวอย่างเช่น เราต้องการไปทำบุญ 9 วัดซึ่งเรามีวัดในใจอยู่แล้ว ซึ่งเราต้องการเดินทางไปทำบุญ 9 วัดโดยใช้ระยะทางทั้งหมดน้อยที่สุด ดังนั้นเราจะนำ Genetic Algorithm นี้แหละมาทำการจัดลำดับการเดินทางแล้วหวังว่าการเดินทางนั้นจะใช้เวลาที่น้อยที่สุดครับ
แล้วพบกันใหม่ในบทความถัดไปครับ
Genetic Algorithm2😊
Refference
-
https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3
-
https://lukkiddd.com/genetic-algorithm-พันธุกรรมมหัศจรรย์-6314fc9afca5
