Otomatik ders çizelgeleme problemi için yapay arı koloni algoritmasının özelleştirilmesi
Customization of artificial bee colony algorithm for automatic course scheduling problem
Yazar: MUSTAFA ŞAMDAN
Danışman: PROF. DR. ZEKİ YETGİN
Mersin Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2019
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Bir çizelge, olası görevlerin veya eylemlerin gerçekleşeceği zamanların kronolojik bir listesi olarak düşünülebilir. Çizelge oluşturma işlemi karmaşık bir problem olarak gösterilmektedir ve üstel olarak büyüdüğünden polinom zamanda çözülememektedir. Son yıllarda gelişen teknolojiye rağmen birçok kurumda çizelgeler halen elle oluşturulmaktadır. Bu durum yüksek kalitede çizelge oluşturulamamasına, kaynakların verimli kullanılamamasına ve yüksek iş gücü maliyetine sebep olmaktadır. Ders çizelgeleme de çizelge çeşitlerinden biridir. Kurumdan kuruma farklılık gösterebilen, öğretim elemanları, idari personeller, öğrenciler ve yöneticilerin talepleri başta olmak üzere, fiziki kaynakların verimli kullanılması gibi çok çeşitli ihtiyaçlar ders çizelgeleme problemini karmaşık hale getirmektedir. Bu çalışmada, yapay arı kolonisi(YAK) algoritması, otomatik ders çizelgeleme problemi için özelleştirilmiş ve Mersin Üniversitesi Mühendislik Fakültesi(MÜMF) ders çizelgesini oluşturmak üzere uygulanmıştır. 2016-2017 eğitim öğretim yılında, 9 bölümde kayıtlı 2395 öğrenciden ve 289 dersten oluşan MÜMF ders kayıt bilgileri anonim olarak temin edilmiş ve veri seti olarak kullanılmıştır. Problemin karmaşıklığını azaltmak için MÜMF bölümlerinden her birinin ders çizelgesi yerel birer çözüm olarak kabul edilmiş, fakülte çizelgesi ise bu yerel çözümlerden oluşan bir genel çözüm olarak düşünülmüştür. Böylece problem çok amaçlı maliyet fonksiyonu optimizasyonuna dönüştürülmüştür. Yerel çözümlerin kullandığı bir yerel amaç fonksiyonu ve yerel uygunluk fonksiyonu tanımlanmıştır. Başarılı bir genel çözüme gidiş yolunun tüm yerel çözümlerin hep birlikte başarılı olduğu durumlardan geçtiği düşünülmüştür. Bu amaçla genel çözümün uygunluk fonksiyonu, yerel uygunluk değerlerinin ortalama kare hatası azaldıkça iyileşen bir fonksiyon olarak modellenmiştir. Bu dengeli iyileştirme sürecini yakalamak amacıyla YAK algoritmasının seçim stratejisine ve yerel arama stratejisine müdahale edilmiştir. Önerilen yeni yaklaşıma göre dengeli çözümler başarılı olan çözümlerdir ve arılar tarafından sık ziyaret edilmelidir. Ancak seçilen çözüm üzerinde yerel arama yapılırken, çözümün kendi içindeki dengesini artırmak için başarısız olan yerel çözümler daha sık ziyaret edilmeli ve iyileştirilmelidir.
Önerilen YAK algoritması ve sıradan YAK algoritması MÜMF çizelgeleme problemine uygulanmış ve kıyaslanmıştır. Durdurma kriteri olarak iterasyon sayısı seçilmiş ve 1000 değeri verilmiştir. Algoritmalar eşit şartlarda 50'şer kez çalıştırılmış ve elde edilen deneysel veriler yorumlanmıştır. Deneysel sonuçlara göre, önerilen YAK algoritmasının, yüksek kaliteli çözümlere ulaşmada sıradan YAK algoritmasına göre yaklaşık %25 daha başarılı olduğu gözlemlenmiştir.

Abstract:
A schedule can be treated as a chronological list of occurrence of possible tasks or events. Scheduling is shown as a complex problem and cannot be solved in polynomial time because it grows exponentially. Despite of technological developments in recent years, schedules are still created by hand in many institutions. This results in low quality schedules as well as inefficient use of resources and high labor costs. Course scheduling is also a special type of scheduling problem. A wide range of needs, particularly the demands of lecturers, administrative staff, students and administrators, which may vary from institution to institution and also efficient use of physical resources complicate the problem of course scheduling. In this study, the artificial bee colony(ABC) algorithm was customized for the automated course scheduling problem and applied to generate course schedule of Faculty of Engineering(MUFE) in Mersin University. In 2016-2017 academic year, an anonymous MUFE course registration dataset consisting of 2395 students enrolled in 9 departments and 289 courses was used in this study for scheduling. In order to reduce the complexity of the problem, the course schedule of each of the MUFE departments was considered as a local solution, while the faculty schedule was considered as a general solution consisting of these local solutions. In this way the problem has been transformed into multi-purpose cost function optimization. A local objective function and a local fitness function are defined to be used in local solutions. It has been thought that the way to a successful general solution goes through situations where all local solutions succeed all together. For this purpose, fitness function of the global solution is modelled as a function that improves as the mean squared error of the local fitness function decreases. In order to achieve this balanced improvement process, the ABC algorithm's election strategy and local search strategy have been interfered. According to the proposed new approach, balanced solutions are the better ones and must be visited frequently by bees. However, during local search process on the chosen solution, worse solutions should be visited more frequently and improved in order to increase the balance of the solution in itself.
Suggested modified ABC and standard ABC algorithms are applied on the same MUFE course scheduling problem and the results were compared. The number of iterations is used as the stop criterion and a value of 1000 is given. Algorithms were run 50 times in equal conditions and experimental data were interpreted. According to experimental results, the proposed ABC algorithm was observed to be about 25% more successful in achieving high quality solutions than the standard ABC algorithm.