Yapay Zeka Hızlı Bakış & Çıkarımlar
AI InsightÖnerilen algoritma, performans açısından son teknoloji ürünü açgözlü buluşsal yöntemleri geride bırakıyor.
📌 3 Maddede Bu Makale
Özet
Bu çalışma, iyi bilinen Müfredat Tabanlı Ders Çizelgeleme Problemini optimize etmek için yeni bir açgözlü algoritmayı açıklamaktadır. Açgözlü algoritmalar, en iyi çözümü bulmak için yürütülmesi uzun zaman alan kaba kuvvet ve evrimsel algoritmalara iyi bir alternatiftir. Birçok açgözlü algoritmanın yaptığı gibi tek bir buluşsal yöntem kullanmak yerine, aynı problem örneğine 120 yeni buluşsal yöntem tanımlıyor ve uyguluyoruz. Dersleri müsait odalara atamak için, önerilen açgözlü algoritmamız En Büyük-İlk, En Küçük-İlk, En Uygun, Önce Ortalama Ağırlık ve En Yüksek Kullanılamaz ders-ilk buluşsal yöntemlerini kullanır. İkinci Uluslararası Zaman Çizelgesi Yarışması'nın (ITC-2007) kıyaslama setinden 21 problem örneği üzerinde kapsamlı deneyler gerçekleştirilir. Önemli ölçüde azaltılmış yumuşak kısıtlama değerlerine sahip 18 problem için, önerilen açgözlü algoritma sıfır sabit kısıtlama ihlali (uygulanabilir çözümler) rapor edebilir. Önerilen algoritma, performans açısından son teknoloji ürünü açgözlü buluşsal yöntemleri geride bırakıyor.
Abstract
This study describes a novel greedy algorithm for optimizing the well-known Curriculum-Based Course Timetabling (CB-CTT) problem. Greedy algorithms are a good alternative to brute-force and evolutionary algorithms, which take a long time to execute in order to find the best solution. Rather than employing a single heuristic, as many greedy algorithms do, we define and apply 120 new heuristics to the same problem instance. To assign courses to available rooms, our proposed greedy algorithm employs the Largest-First, Smallest-First, Best-Fit, Average-weight first, and Highest Unavailable course-first heuristics. Extensive experiments are carried out on 21 problem instances from the benchmark set of the Second International Timetabling Competition (ITC-2007). For 18 problems with significantly reduced soft-constraint values, the proposed greedy algorithm can report zero hard constraint violations (feasible solutions). The proposed algorithm outperforms state-of-the-art greedy heuristics in terms of performance.