สวัสดีครับหลังจากบทความที่แล้ว https://cakeknowledgeblogs.blogspot.com/2020/03/genetic-algorithm.html ได้พูดถึงทฤษฎีของอัลกอริทึมหนึ่งที่ชื่อว่า Genetic Algorithm วันนี้เราเลยจะนำความรู้มาใช้กันครับซึ่งเราจะนำความรู้มาแก้ปัญหา TSP(Traveling
Salesman Problem) นั่นเอง
"แล้วปัญหา TSP(Traveling Salesman Problem) คืออะไร"
TSP(Traveling
Salesman Problem) เป็นปัญหาสำหรับหาเส้นทางในการเดินทางไปยัง N สถานที่แล้วให้ได้ประโยชน์มากสุดเช่น เวลาที่สั้น หรือ
ระยะทางที่สั้นที่สุดเป็นต้น
ตัวอย่างเช่น
เราต้องการไปทำบุญ 9 วัดซึ่งเรามีวัดในใจอยู่แล้ว แต่เราต้องการเดินทางไปทำบุญ 9 วัดโดยใช้ระยะทางทั้งหมดน้อยที่สุด
ดังนั้นเราจะนำ Genetic Algorithm นี้แหละมาทำการจัดลำดับการเดินทางแล้วหวังว่าการเดินทางนั้นจะใช้เวลาที่น้อยที่สุดครับ
"แล้วเราจะเอา genetic algorithm มาใช้เพื่อแก้ปัญหา TSP อย่างไร?"
หลังจากที่เราได้เรียนรู้แล้วว่า genetic algorithm นั้น จะมีขั้นตอนหลักๆ คือ
1.
Initial
population
2.
Fitness
Function
3.
Selection
4.
Crossover
5.
Mutation
เราก็จะเอาขั้นตอนพวกนี้แหละมาดัดแปลงเพื่อแก้ปัญหา TSP(Traveling Salesman Problem) กันดังนี้
1. Initial population
เราจะทำการสร้างคำตอบหลายคำตอบขึ้นมาก่อนซึ่งจะมีหน้าตาดังนี้
จากรูปจะเห็นว่าคำตอบของเราคือ
การซุ่มลำดับของวัดที่เราจะเดินทางขึ้นมา
และก็ทำการซุ่มอีกคำตอบเพื่อให้ได้หลายคำตอบ
จากคำตอบที่
1 จะเห็นว่าจะมีการเดินทางดังนี้
จากบ้านไป
วัดเอก, วัดจตุ, วัดสัตต , วัดโท ,
วัดตรี, วัดเบญจ, วัดนว ,วัดฉะ , วัดอัฎฐ, แล้วค่อยกลับมาบ้าน
(หมายเหตุชื่อวัดเป็นวัดที่คิดขึ้นมาเอง
ดังนั้นอาจจะไม่มีชื่อวัดจริงบนโลก)
2. Fitness Function
หลังจากนั้นเราก็มาทำการให้คะแนนคำตอบกันซึ่งการให้คะแนนนั้นจะให้คะแนนจากคนที่ใช้ระยะทางในการเดินทาง
โดยคำตอบใหนใช้ระยะทางเดินทางสั้นก็จะได้คะแนนเยอะ ส่วนคำตอบใหนที่ใช้ระยะทางเยอะก็จะได้คแนนน้อยดังรูป
จากรูปจะเห็นว่าค่า fitness สำหรับปัญหา TSP TSP(Traveling
Salesman Problem) เราจะใช้ 1/ระยะทางการเดินทางทั้งหมด เนื่องจากเราต้องการให้ระยะทางที่สั้นต้องได้คะแนนมากกว่าระยะทางที่ยาวนั่นเอง
3. Selection
หลังจากเราให้ได้คะแนนของทุกคำตอบแล้วเราก็มาทำการเลือกคำตอบที่ดีที่สุดมา
N จำนวนดังรูป โดยการเลือกคำตอบที่ดีที่สุดนั้นก็ดูจากค่า fitness ที่มากที่สุดมา N คำตอบนั่นเอง
4. Cross over
หลังจากเราเลือกมาแล้วเราก็ทำการ Crossover กัน
หรือก็คือการสร้างคำตอบขึ้นมาใหม่ที่เกิดจากการแลกคำตอบย่อยกันนั่นเองดังรูป
5. Mutation
หลังจากที่เราได้คำตอบที่เกิดจาก Cross over มาใหม่แล้วเราก็อาจจะทำการสุ่มคำตอบย่อยมา เพื่อเปลี่ยนค่า โดยในที่นี้คือการสุ่มคำตอบย่อยมา
2 ตัวเพื่อมาสลับลำดับการเดินทางใหม่นั่นเอง
โดยขั้นตอนการทำงานของโปรแกรมนั้นก็จะทำ
Initial
population -> Fitness Function -> Selection -> Crossover -> Mutaion
และก็เริ่มทำ Fitness Function ใหม่วนไปเรื่อยๆจนกระทั่งได้ระยะทางการเดินทางที่พอใจหรือระยะทางในแต่ละครั้งไม่ค่อยมีการเปลี่ยนแปลงนั่นเองครับ
ซึ่งหากใครสนใจอยากเขียนโปรแกรมการคำนวณ TSP(Traveling Salesman Problem) สามารถไปโหลดศึกษาดู code ได้ที https://github.com/CakeNuthep/GA_TSP โดยแอดได้เอาโคดต้นฉบับมากจาก https://github.com/7lb/TSP แล้วมาใส่คำอธิบายภาษาไทยไว้แล้วเพื่อให้สามารถเข้าใจได้เร็วขึ้น และสุดท้ายนี้หวังว่าโพสน์นี้จะมีประโยชน์นะครับ
ขอบคุณครับ
Refference
ไม่มีความคิดเห็น:
แสดงความคิดเห็น