Genetik algoritma kullanılarak ders çizelgeleme yazılımının geliştirilmesi

Abstract

Bu çalışmada kaynak kısıtlı ders çizelgelemeye yönelik olarak genetik algoritma temelli bir çizelgeleme yazılımı geliştirmek amaçlanmaktadır. Üniversitelerde otomatik ders çizelgesi hazırlamak, bir öğrencinin, öğretim elemanın veya şubenin derslerinin çakışmaması, herhangi bir derslikte aynı saate birden fazla dersin konmaması gibi bir çok kısıt altında çözülmesi gereken zor bir optimizasyon problemidir. Çözümü zor olan bu tür problemlerde, kesin çözüm veren bir algoritmanın hazırlanması oldukça güçtür. Bunun için bu tip problemlerde yalın optimal çözümü veren sezgisel algoritmalara ihtiyaç bulunmaktadır. Genetik bilimi ve doğal seçme mantığına dayalı olan genetik algoritmalar, bu tipten algoritmalar olup, çözülmesi zor problemler için kullanılan ve iyi sonuçlar elde edilen bir algoritmadır.Bu çalışmada kısıtların kolayca girilebildiği, çözümlerin üretilebildiği, değiştirilebildiği ve bilgilerin saklanabildiği, otomatik ders programı hazırlayan bir yazılım genetik algoritma kullanılarak geliştirilmiştir. Yazılım MS Visual Studio 2010 programı kullanılarak C# programlama dilinde geliştirilmiştir. En uygun yaklaşımı en kısa sürede bulmak için, tam genetik algoritma ve yarı genetik algoritma birlikte test edilmiştir. Testler için gerçek ve rastgele oluşturulmuş veriler kullanılmıştır. Problemin çözümünde kullanılan tam genetik algoritma, rastgele oluşturulan başlangıç popülasyonundan itibaren kullanılmaya başladığında uygun çözümün bulunması oldukça zaman almaktadır. Kullanılan yarı genetik algoritma ile uygun çözüme çok daha hızlı bir şekilde ulaşılmıştır.

In this study, it is aimed to develop scheduling software based on genetic algorithm for the resource constrained course scheduling. In the Universities, preparing the lesson program (schedule) is a difficult NP-hard optimization problem that must be solved under the a lot of constraints as without a student, lecturer, or class conflict. Preparation of an algorithm that gives the exact solution is quite difficult for this kind of NP-hard optimization problems. Therefore, we need to heuristic algorithms that gives the simple and optimal solution to solve this kind of NP-hard optimization problem. Genetic algorithms which are based on the logic of science and subjected to genetic selection, are these kind of algorithms which use to solve NP-hard optimization problem and give the good results.In this study, a software for preparing automatic course scheduling has been developed to obtain optimal results using genetic algorithm. The Software was developed via MS Visual Studio 2010 using the C # programming language. To find the most appropriate approach as soon as possible, full genetic algorithm and part-genetic algorithm has been tested together. Real and randomly generated data has been used for the tests. Observed that when full genetic algorithm has been used since the start population that was randomly generated, is taking quite some time to find the appropriate solution. With part genetic algorithm which is used, appropriate solution is obtained much more quickly.