ผิวๆ เรื่อง Genetic Algorithms

กำลังศึกษา Genetic Algorithms อยู่ .. ถือเป็นจุดเริ่มต้น จึงอยากสรุปไว้ตรงนี้นิดนึง .. บทความของใครไม่รู้ แต่ผมเห็นอยู่ใน file .doc และ http://www.numvarn.com/blog/node/133

ขอนำมาเรียบเรียงใหม่ดังนี้ ครับ

Concept Genetic Algorithm

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

1. Chromosome Encoding

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

2. Initial Population

การสุ่มเลือกเพื่อสร้างประชากรต้นแบบขึ้นมา เพื่อใช้เป็นจุดเริ่มต้นของขั้นตอนการวิวัฒนาการ ขั้นตอนนี้จะเป็นขึ้นตอนแรกที่เกิดขึ้น ก่อนที่จะเร่ิมเข้ากระบวนการของ Genetic Algorithm โดยประชากรกลุ่มแรก หรือประชาการต้นกำเนิด จะเกิดจากการสุ่มเลือกขึ้นมาจาก กลุ่มของประชากรทั้งหมดที่มีอยู่ โดยในการสุ่มเลือกจะทำการสุ่มตามจำนวนของประชากรที่ได้กำหนดไว้เป็น Parameter ของ Algorithm

3. Fitness Function

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

4. Genetic Operator -> Selection, Crossover, Mutation

การคำเนินการต่างๆ ตามขั้นตอนของ Genetic Algorithm เพื่อให้การเกิดวิวัฒนาการไปสู่คำตอบที่ดีขึ้น ซึ่งได้แก่ Selection, Crossover และ Mutation

5. Parameters

ปัจจัยที่ส่งผลต่อการทำงานของ Genetic Algorithm เช่น ขนาดของประชาการ, ความน่าจะเป็นของการ Crossover หรือ ความน่าจะเป็นของการ Mutation

Crossover Probability คือ ความน่าจะเป็นของการเกิด Crossover ซึ่งมีค่าอยู่ในช่วง 0 – 100 โดยทั่วไปค่าความเหมาะสมของความน่าจะเป็นในการเกิด Crossover จะอยู่ที่ 60% – 95% และในกรณีที่ไม่เกิดการ Crossover เกิดขึ้นจะเป็นการทำสำเนา (Copy) รูปแบบของพันธุกรรมจาก Parent ไปสู่ Offspring เลย ยกตัวอย่าง การทำ Crossover เช่น เรากำหนดให้ Crossover Probability มีค่าเป็น 85% ถ้าเราทำการสุ่มเลือกตัวเลขขึ้นมาเพื่อเปรียบเทียบกับค่า Crossover Probability ได้เท่ากับ 20 นั่นคืออยู่ในช่วงที่ <= 85 ในกรณีจะยอมให้เกิดการ Crossover เกิดขึ้น

Mutation Probability คือ ความน่าจะเป็นของการเกิด Mutation จะมีค่าอยู่ในช่วง 0 – 100 ส่วนใหญ่ค่าความน่าจะเป็นของการเกิด Mutation จะถูกกำหนดไว้ให้อยู่ในช่วง 0% – 1% ต่อตำเหน่งของ Chromosome ในกรณีที่ไม่มีการ Mutation นั่นหมายความว่ามีเพียงการ Crossover เกิดขึ้นเพียงอย่างเดียว แต่ถ้าหากว่า เกิดการ Mutation 100% จะทำให้ทุกตำเหน่งใน Chromosome มีการเปลี่ยนแปลงทั้งหมด ซึ่งสำหรับใน Genetic Algorithm นั้นอาจเกิดกรณีนี้ขึ้นได้ แต่ไม่บ่อยนัก ไม่เช่นนั้นการค้นหาจะเปลี่ยนจาก Genetic Algorithm การเป็น Random Search

Population Size หรือ จำนวนของประชากรในแต่ละรุ่น ถ้ามีจำนวนมากเกิดไปจะทำให้ต้องเสียเวลาในการประมวลผลมากและทำงานได้ช้าลง หรือ หากน้อยเกินไปก็จะทำให้การค้นหานั้นสามารถที่จะลู่เข้าสู่คำตอบที่เป็น Global Minimum ได้ช้าเกินไป

Operational Step

สำหรับเงื่อนไขในการหยุดการทำงาน หรือ Stop Condition นั้น สามารถกำหนดได้หลากหลายรูปแบบ เช่น

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

..

.

Del.icio.us : ,

Advertisements

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s