การเปรียบเทียบการคัดเลือกและการกลายพันธุ์ในขั้นตอนวิธีเชิงพันธุกรรม สำหรับแก้ปัญหาการจัดตารางสอบ Comparison of Selection and Mutation in Genetic Algorithms for Examination Schedule Problem

Abstract

บทคัดย่อ

งานวิจัยนี้มีวัตถุประสงค์เพื่อเปรียบเทียบการคัดเลือกและการกลายพันธุ์ในขั้นตอนวิธีเชิงพันธุกรรม เพื่อหาชุดพารามิเตอร์ที่เหมาะสมที่สุด สำหรับปัญหาที่สนใจในงานวิจัยนี้ประกอบไปด้วย 1) กลุ่มผู้เรียนที่เรียนในรายวิชาเดียวกันต้องสอบพร้อมกัน 2) ผู้เรียนจะต้องสอบ 1 วิชาในช่วงเวลาเดียวกัน 3) ห้องสอบต้องมีขนาดเพียงพอกับผู้เรียน 4) ถ้าเป็นไปได้ไม่ควรจัดตารางคุมสอบให้อยู่นอกคาบเวลาปกติ 5) ถ้าเป็นไปได้ไม่ควรจัดตารางสอบให้ผู้เรียน สอบมากเกินไปในแต่ละวัน การคัดเลือกที่นำมาเปรียบเทียบประกอบไปด้วยการคัดเลือก 3 รูปแบบ คือ การคัดเลือกแบบวงล้อรูเล็ต (Roulette Wheel Selection) การคัดเลือกแบบจัดอันดับ (Ranking Selection) และการคัดเลือกแบบจัดการแข่งขัน (Tournament Selection) การกลายพันธุ์ที่นำมาเปรียบเทียบประกอบไปด้วยการกลายพันธุ์ 3 รูปแบบ คือ การกลายพันธุ์แบบสลับที่ (Swap Mutation) การกลายพันธุ์แบบแทรก (Insertion Mutation) และการกลายพันธุ์แบบผกผัน (Inversion Mutation) รวมไปถึงการหาค่าความเหมาะสมของความน่าจะเป็นในการกลายพันธุ์ จำนวนประชากร และจำนวนรุ่นที่เหมาะสมที่สุด ซึ่งจากผลการวิจัยพบว่า ชุดพารามิเตอร์ที่ให้ค่าความเหมาะสมเฉลี่ยสูงสุดคือ การคัดเลือกแบบจัดการแข่งขัน การกลายพันธุ์แบบสลับที่ ความน่าจะเป็นในการกลายพันธุ์เท่ากับ 75 % โดยมีจำนวนประชากรเท่ากับ 20 ซึ่งให้ค่าความเหมาะสมเฉลี่ยอยู่ที่ 6,168 จาก 7,350 และจำนวนรุ่นที่ให้ค่าความเหมาะสมเฉลี่ยสูงที่สุดอยู่ที่ 365 รุ่น

Absteract

The purpose of this study is to present the comparison of selection and mutation in genetic algorithms to identify the most accurate parameter of examination schedule problem. Which includes 1) The group of students studying in the same course must take the same exam. 2) A student will have to take 1 examination at same time. 3) The number of students for each examination must not exceed the class capacity. 4) A proctor cannot supervise more than two sessions in the same day. 5) No student should have examinations on consecutive sessions. This study examined the selection based on three methods: Roulette Wheel Selection, Ranking Selection, and Tournament Selection. Similarly, three different methods were employed for mutation namely Swap Mutation, Insertion Mutation, and Inversion Mutation. In addition, the study investigated the most accurate parameter to determine the result by adjusting the probability of mutation, size of population, and the number of generations in the experiment. The result demonstrated that the most accurate parameter was from Tournament Selection and Swap Mutation where the probability of mutation is 75 %. The results showed that the Fitness Function average was 6,168 from 7,350.  The experiment also revealed that the number of generations that provided the highest average Fitness Function was 365 generations.