Sezgisel Algoritmalar Yardımıyla Ders Programı Optimizasyonu

Abstract

Günümüzde çoğu eğitim kurumunda hazırlanan ders programı her dönem için yeniden yapılmaktadır. Bu işlemin her dönem tekrardan yapılması ve çoğu kurumda elle hazırlanıyor olması bu olayı zahmetli ve zaman alıcı bir iş haline getirmektedir. Bu çalışma için bir fakültenin gerçek verileri kullanılmış ve fakültenin bölümleri için uygun bir haftalık ders programı çizelgesi oluşturulmaya çalışılmıştır. Çalışmada problemin çözümü noktasında evrimsel hesaplama teknikleri olarak kabul edilen Genetik Algoritma, Parçacık Sürü Optimizasyonu ve Yapay Arı Kolonisi yöntemleri kullanılmış ve üç yöntem için de aynı veriler kullanılarak, mevcut yöntemlerin problemin çözümü üzerindeki performansları analiz edilmiştir. Çalışmada öğretim elemanı, öğrenci ve fakülte personelini memnun edecek şekilde bütün kısıtlar dikkate alınmıştır. Geliştirilen sistemde kullanılan yöntemlerin parametreleri üzerinde değişiklikler yapılarak algoritmalar optimize edilmiştir. Yapılan deneyler sonucunda elde edilen ders programları kontrol edilerek fakülte için uygun ders programları elde edildiği görülmüştür. Ayrıca kullanılan algoritmalar, çalışma zamanı ve çözüme yakınsama açısından değerlendirilerek performansları karşılaştırılmıştır. 

Keywords

• Genetik Algoritma
• Parçacık Sürü Optimizasyonu
• Yapay Arı Kolonisi
• Ders Çizelgeleme Problemi

Course Scheduling Optimization with the Help of Heuristic Algorithms

Abstract

Nowadays, the curriculum prepared in most educational institutions is carried out for each term. The fact that this process is repeated every semester and that it is prepared manually in most institutions makes this event a laborious and time consuming task. The actual data of a faculty were used for this study and an appropriate weekly course schedule was prepared for the departments of the faculty. In the study, the methods of Genetic Algorithm, Particle Swarm Optimization and Artificial Bee Colony, which are accepted as evolutionary calculation techniques at the point of solution of the problem, were used and the performance of the existing methods on the solution of the problem was analyzed by using the same data for all three methods. In the study, all constraints were taken into consideration in a way that would satisfy the teaching staff, students and faculty staff. The algorithms are optimized by making changes on the parameters of the methods used in the developed system. It was observed that the curriculum obtained as a result of the experiments were controlled and appropriate curriculum for the faculty was obtained. In addition, the algorithms used were evaluated in terms of runtime and convergence, and their performance was compared.

Keywords

• Genetic Algorithm
• Particle Swarm Optimization
• Artificial Bee Colony

References

1. Abdullah, S. ve H. Turabieh, (2008). Generating University Course Timetable Using Genetic Algorithms and Local Search. In Convergence and Hybrid, Information Technology ICCIT'08 Third, 1, 254-2
2. Abidin, D. (2013). “Curriculum Plan Optimization with Rule Based Genetic Algorithms”, Doktora Tezi, DEÜ, Fen Bilimleri Enstitüsü.
3. Akay, B. ve Karaboga, D. (2012). Artificial Bee Colony Algorithm for Large-Scale Problems and Engineering Design Optimization, Journal of Intelligent Manufacturing, 23(4), 1001-1014.
4. Akkan, C. ve Gülcü, A. (2018). A Bi-Criteria Hybrid Genetic Algorithm with Robustness Objective for the Course Timetabling Problem, Computers & Operations Research, 90, 22-32.
5. Alzaqebah, M. ve Abdullah, (2011). S. Artificial Bee Colony Search Algorithm for Examination Timetabling Problems”, International Journal of Physical Sciences, 6(17), 4264-4272.
6. Alzaqebah, M. ve Abdullah, S. (2011). Comparison on The Selection Strategies in the Artificial Bee Colony Algorithm for Examination Timetabling Problems, Int J Soft Comput Eng, 1(5), 158-163.
7. Bolaji, A. L. A., Khader, A. T., Al-Betar, M. A. ve Awadallah, M. A. (2011). An Improved Artificial Bee Colony for Course Timetabling, in Bio-Inspired Computing: Theories and Applications (BIC-TA), 2011 Sixth International Conference, 9-14. Chen, R. M. ve Shih, H. F. (2013). Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search, Algorithms, 6(2), 227-244.
8. Çolak, R. (2015). Sezgisel Algoritmalarla Ders Programı Çizelgeleme Problemi Çözümü, Yüksek Lisans Tezi, Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Bilgisayar Mühendisliği Anabilim Dalı.

9. Daban, F. ve Özdemir, E. (2004). Eğitimde Verimliliği Artıran Ders Programlarının Hazırlanması için Genetik Algoritma Kullanımı, Journal of Educational Sciences & Practices, 3(6), 245-257.
10. Dener, M. ve Calp, M. H. (2019). Solving the Exam Scheduling Problems in Central Exams with Genetic Algorithms, Journal of Science and Technology, 4(1), 102-115.
11. Eberhart, R. C. ve Shı, Y. (1998). Comparison Between Genetic Algorithms and Particle Swarm Optimization, In Evolutionary Programming VII, Porto, 611–616.
12. Eberhart, R. C., Shı Y. ve Kennedy, J. (2001). Swarm Intelligence, Morgan Kaufmann, San Mateo, CA.
13. Eberhart, R., Sımpson, P. ve Dobbıns, R. (1996). Computational Intelligent PC Tools, Academic Press Professional, US. Fang, H. L. (1994). Genetic Algorithms in Timetabling and Scheduling, Diss. University of Edinburgh.
14. Ghaemı, S., Vakılı, M. T. ve Aghagolzadeh, A. (2007). Using A Genetic Algorithm Optimizer Tool to Solve University Timetable Scheduling Problem, In Signal Processing and Its Applications, ISSPA 9th International Symposium, 1-4.
15. Goldberg, D. E. (1989). Genetic Algoritm in Search, Optimization & Machine Learning, Addison-Wesley Longman Publishing, Boston, MA, USA.
16. Grefenstette, J. J. (1986). “Optimization of Control Parameters for Genetic Algorithms”, IEEE Transactions on Systems Man and Cybernetics, 16(1), 122-128.
17. Haupt, R. L. ve Haupt, S. (2004). Ellen Practical Genetic Algorithms, John Wiley & Sons.
18. Karaboga, D. (2005). An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical Report-Tr06, Erciyes University, Engineering Faculty, Computer Engineering Department, 200.
19. Karaboğa, D. (2017). Yapay Zeka Optimizasyon Algoritmaları, Ankara: Nobel Yayıncılık.
20. Kennedy, J. ve Eberhart, R. C. (1995). Particle Swarm Optimization, Conference on Neural Networks, 4, 1942-1948.
21. Küçüksille, E. U. ve Tokmak, M. (2011). Yapay Arı Kolonisi Algoritması Kullanarak Otomatik Ders Çizelgeleme, Yüksek Lisans Tezi, Süleyman Demirel Üniversitesi, Fen Bilimleri Enstitüsü Dergisi.
22. Mathew, T. V. (2012). Genetic Algorithm, Report Submitted at IIT Bombay.
23. Mitchell, M. (1998). An Introduction to Genetic Algorithms, MIT Press.
24. Özcan, M. (2016). Atölye Tipi Çizelgeleme Problemlerinde Evrimsel Algoritmalar ile Yapay Arı Kolonisi Algoritmasının Bütünleşik Bir Yaklaşımı, Doktora Tezi, Sakarya Üniversitesi, Fen Bilimleri Enstitüsü. Rechenberg, I. et al., (1994). Evolution Strategy, in Computational İntelligence: İmitating Life. Computational İntelligence İmitating Life, IEEE Press, Piscataway.
25. Ryder, J. (2006). A Genetic Algorithm for Scheduling.
26. Schwefel, H. P. ve Rudolph, G. (1995). Contemporary Evolution Strategies, In: European Conference on Artificial Life, Berlin, Heidelberg, 891-907.
27. Shiau, D. F. (2011). A Hybrid Particle Swarm Optimization for a University Course Scheduling Problem with Flexible Preferences, Expert Systems with Applications, 38, 235–248.
28. Sigl, B., Golub M. ve Mornar, V. (2003). Solving Timetable Scheduling Problem Using Genetic Algorithms, In Information Technology Interfaces, ITI 2003. Proceedings of the 25th International Conference, 519-524.
29. Şahin, Y. (2009). “Depo Operasyonlarının Planlanması için Genetik Algoritma Esaslı Bir Model”. Yüksek Lisans Tezi, Pamukkale Üniversitesi, Fen Bilimleri Enstitüsü.
30. Taç, K. C. (2006). Genetik Algoritma Kullanılarak Haftalık Ders Programı Zaman Çizelgeleme Yazılımının Geliştirilmesi, Yüksek Lisans Tezi, Marmara Üniversitesi, Fen Bilimleri Enstitüsü Elektronik-Bilgisayar Eğitimi Anabilim Dalı.
31. Uysal, Ö. (2006). Comparıson of Genetıc Algorıthm and Particle Swarm Optımızatıon Algorıthm for Bicriteria Permutation Flowshop Scheduling Problem, Doktora Tezi, Marmara Üniversitesi, Endüstri Mühendisliği Programı.
32. Yu, E. ve Sung, K. (2002). A Genetic Algorithm for a University Weekly Courses Timetabling Problem, International Transactions in Operational Research, 9(6), 703-717.
33. Zhang, R. ve Wu, C. (2011). An Artificial Bee Colony Algorithm for the Job Shop Scheduling Problem with Random Processing Times, Entropy, 13(9), 1708-1729.