การเปรียบเทียบการคัดเลือกและการกลายพันธุ์ในขั้นตอนวิธีเชิงพันธุกรรม สำหรับแก้ปัญหาการจัดตารางสอบ(Comparison of Selection and Mutation in Genetic Algorithms for Examination Schedule Problem)
Keywords:
Genetic Algorithms, Examination Scheduling Problem, Timetable ProblemAbstract
Abstract
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.
References
[2] M. Dipankar and M. Subhasis, “Cuckoo search algorithm for Constraint Satisfaction and Optimization”, Proceedings of the 2016 Second International Conference on Research in Computational Intelligence and Communication Networks (ICRCICN 2016), Kolkata, India, 2016, pp. 235-240.
[3] R. Ilyas and Z. Iqbal, “Study of Hybrid Approaches used for University Course Timetable Problem (UCTP)”, Proceedings of the 2015 IEEE 10th Conference on Industrial Electronics and Applications (ICIEA), Auckland, New Zealand, pp. 697-701.
[4] E. Ghasemi, P. Moradi and M. Fathi, “Integrating ABC With Genetic Grouping For University Course Timetabling Problem”, Proceedings of the 2015 5th International Conference on Computer and Knowledge Engineering (ICCKE), Mashhad, Iran, pp. 24-29.
[5] K. Sujanya and R. Wanida, “Solutions to the Timetable that many Students Learn Together by Applying Genetic Algorithms”, Engineering Journal Chiang Mai University, 2017, pp. 119-129.
[6] M. Hosny and M. Al-Olayan, “A Mutation-Based Genetic Algorithm for Room and Proctor Assignment in Examination Scheduling”, Proceedings of the 2014 Science and Information Conference, London, UK, pp. 260-268.
[7] A. Hideg, “Comparing genetic operators for the timetabling problem”, 2015 IEEE 13th International Symposium on Applied Machine Intelligence and Informatics (SAMI), 2015, pp. 53-57.
