Basic Genetic Algorithm
สำหรับองค์ประกอบหลักๆ ของ Genetic Algorithm มีดังนี้
1. Chromosome Encoding
2. Initial Population
3. Fitness Function
4. Genetic Operator -> Selection, Crossover, Mutation
5. Parameters
สามารถแจงรายระเอียดได้ดังนี้
- Chromosome Encoding
คือ ขั้นตอนสำหรับแปลงทางเลือกสำหรับการแก้ปัญหาที่เป็นไปได้ให้อยู่ในรูปแบบของ Chromosome
ในการแปลงวิธีการสำหรับแก้ปัญหาที่เป็นไปได้ ให้อยู่ในรูปแบบของ Chromosome นั้นสามารถที่จะทำได้ในหลายรูปแบบซึ่งแล้วแต่ความเหมาะสมของแต่ละปัญหา
- Initial Population
คือ การสุ่มเลือกเพื่อสร้างประชากรต้นแบบขึ้นมาเพื่อใช้เป็นจุดเริ่มต้นของขั้นตอนการวิวัฒนาการ
ขั้นตอนนี้จะเป็นขึ้นตอนแรกที่เกิดขึ้นก่อนที่จะเร่ิมเข้ากระบวนการของ Genetic Algorithm โดยประชากรกลุ่มแรก หรือประชาการต้นกำเนิด จะเกิดจากการสุ่มเลือกขึ้นมาจาก กลุ่มของประชากรทั้งหมดที่มีอยู่ โดยในการสุ่มเลือกจะทำการสุ่มตามจำนวนของประชากรที่ได้กำหนดไว้เป็น Parameter ของ Algorithm
- Fitness Function
คือ ฟังชันสำหรับประเมินค่าความเหมาะสม เพื่อให้คะแนนสำหรับคำตอบต่างๆ ที่เป็นไปได้ของปัญหา
โครโมโซมทุกตัวจะมีค่าความเหมาะสมของตัวเองเพื่อใช้สำหรับพิจารณาว่า โครโมโซมตัวนั้น เหมาะหรือไม่ที่จะนำมาใช้สืบทอดพันธุกรรมสำหรับสร้างโครโมโซมรุ่มใหม่ โดยวิธีการสำหรับคิดค่าความเหมาะสมนั้นจะใช้สมการที่สอดคล้องกับแต่ละปัญหา
- Genetic Operator
คือ การคำเนินการต่างๆ ตามขั้นตอนของ Genetic Algorithm เพื่อให้การเกิดวิวัฒนาการไปสู่คำตอบที่ดีขึ้น ซึ่งได้แก่ Selection, Crossover และ Mutation
- Parameter
คือ ปัจจัยที่ส่งผลต่อการทำงานของ Genetic Algorithm เช่น ขนาดของประชาการ, ความน่าจะเป็นของการ Crossover หรือ ความน่าจะเป็นของการ Mutation
1. Crossover Probability คือ ความน่าจะเป็นของการเกิด Crossover ซึ่งมีค่าอยู่ในช่วง 0 - 100 โดยทั่วไปค่าความเหมาะสมของความน่าจะเป็นในการเกิด Crossover จะอยู่ที่ 60% - 95% และในกรณีที่ไม่เกิดการ Crossover เกิดขึ้นจะเป็นการทำสำเนา (Copy) รูปแบบของพันธุกรรมจาก Parent ไปสู่ Offspring เลย ยกตัวอย่าง การทำ Crossover เช่น เรากำหนดให้ Crossover Probability มีค่าเป็น 85% ถ้าเราทำการสุ่มเลือกตัวเลขขึ้นมาเพื่อเปรียบเทียบกับค่า Crossover Probability ได้เท่ากับ 20 นั่นคืออยู่ในช่วงที่ <= 85 ในกรณีจะยอมให้เกิดการ Crossover เกิดขึ้น
2. Mutation Probability คือ ความน่าจะเป็นของการเกิด Mutation จะมีค่าอยู่ในช่วง 0 - 100 ส่วนใหญ่ค่าความน่าจะเป็นของการเกิด Mutation จะถูกกำหนดไว้ให้อยู่ในช่วง 0% - 1% ต่อตำเหน่งของ Chromosome ในกรณีที่ไม่มีการ Mutation นั่นหมายความว่ามีเพียงการ Crossover เกิดขึ้นเพียงอย่างเดียว แต่ถ้าหากว่า เกิดการ Mutation 100% จะทำให้ทุกตำเหน่งใน Chromosome มีการเปลี่ยนแปลงทั้งหมด ซึ่งสำหรับใน Genetic Algorithm นั้นอาจเกิดกรณีนี้ขึ้นได้ แต่ไม่บ่อยนัก ไม่เช่นนั้นการค้นหาจะเปลี่ยนจาก Genetic Algorithm การเป็น Random Search
3. Population Size หรือ จำนวนของประชากรในแต่ละรุ่น ถ้ามีจำนวนมากเกิดไปจะทำให้ต้องเสียเวลาในการประมวลผลมากและทำงานได้ช้าลง หรือ หากน้อยเกินไปก็จะทำให้การค้นหานั้นสามารถที่จะลู่เข้าสู่คำตอบที่เป็น Global Minimum ได้ช้าเกินไป
แผนผังลำดับของขั้นตอนการทำงาน
สำหรับเงื่อนไขในการหยุดการทำงาน หรือ Stop Condition นั้น สามารถกำหนดได้หลากหลายรูปแบบเช่น
- ครบรอบการทำงานที่ได้กำหนดไว้
- พบเป้าหมายหรือคำตอบที่ต้องการ
- พบว่าคำตอบที่ได้เร่ิมลู่เข้าสู่คำตอบที่เป็นคำตอบที่ดีที่สุด เช่น คำตอบที่ได้จากประชากรแต่ละรุ่นไม่มีการเปลี่ยนแปลงหรือคงที่เป็นจำนวนที่ติดต่อกัน
ข้อมูลศึกษาเพ่ิมเติมจาก :
http://cs.felk.cvut.cz/~xobitko/ga/
