การจัดวางกล่องโดยใช้ Genetic Algorithm

ชื่อผู้จัดทำโครงงานวิทยาศาสตร์
  • ธนวัฒน์ เป้งไชยโม

อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์
  • ชิดชนก เหลือสินทรัพย์

สถาบันการศึกษาที่กำกับดูแลโครงงานวิทยาศาสตร์

นิสิตระดับปริญญาตรีปีที่ 1 มหาวิทยาลัยเกษตรศาสตร์

ระดับการศึกษา

โครงงานในระดับการศึกษาปริญญาโทขึ้นไป

หมวดวิชา

โครงงานในสาขาวิชาคอมพิวเตอร์

วันที่จัดทำโครงงานวิทยาศาสตร์

01 มกราคม 2541

บทคัดย่อโครงงานวิทยาศาสตร์

Genetic Algorithm คือขั้นตอนในการแก้ปัญหา โดยใช้ลักษณะของปัญหาเป็นการหาค่าประมาณที่สูงสุด โดยเลียนแบบกระบวนการการถ่ายทอดพันธุกรรมของยีน โดยธรรมชาติ สิ่งมีชีวิตที่ปรับตัวได้ดีหรือมีลักษณะทางพันธุกรรมที่เหมาะสมจะดำรงอยู่ได้ดีกว่าสิ่งมีชีวิตที่ไม่เหมาะสมกับสิ่งแวดล้อมนั้น ๆ ซึ่งก็คือการคัดเลือกโดยธรรมชาติ สิ่งใดที่ด้อยกว่าก็จะหมดไปเหลือไว้แต่กลุ่มที่มีคุณภาพ จากข้อเท็จจริงที่กล่าวมา เราสามารถนำไปประยุกต์ใช้กับการแก้ปัญหาที่สูญเสียในการค้นหาคำตอบนานมาก เช่น ปัญหาใน Class NP Complete โดยที่เราจะใช้ Genetic Algorithm เข้ามาช่วยในการแก้ปัญหา หลักการของ Genetic Algorithm 1. สร้างคำตอบ (Generate solution) โดยวิธีสุ่มคำตอบที่เป็นไปได้ออกมามาก ๆ แต่ไม่จำเป็นต้องทั้งหมดของทุกรูปแบบคำตอบ 2. สร้าง function สำหรับวัดค่าความดี (Cost function) เพื่อคัดเลือกกลุ่มคำตอบที่ดี ๆ เก็บไว้จำนวนหนึ่ง 3. นำคำตอบที่ได้คัดเลือกมาแล้วมาเป็นต้นแบบ (Parent) ในการ generate คำตอบรุ่นลูกต่อไป โดยการผสมคำตอบซึ่งเลียนแบบกระบวนการทางพันธุกรรมของยีน 4. นำคำตอบในรุ่นลูกมาคัดเลือกและผสมไปเรื่อย ๆ จนกว่าจะได้คำตอบที่น่าพอใจ (อาจไม่ใช่คำตอบที่ดีที่สุดแต่เป็นคำตอบที่ใกล้เคียง และใช้เวลาในการค้นหาคำตอบไม่นานจนเกินไป)