Ders Programı Algoritmaları: Graf Boyama, Genetik Algoritma ve Kısıt Çözücüler

Ders programı üretmek için beş algoritma ailesi kullanılır: açgözlü/graf boyama sezgiselleri, yerel arama (tavlama benzetimi, tabu arama), genetik algoritmalar, karışık tamsayılı programlama (MIP) ve kısıt programlama çözücüleri (CP-SAT). Küçük problemlerde hepsi çalışır; gerçek okul ölçeğinde ayrışırlar. Aşağıda her birinin ne yaptığını, nerede güçlü ve nerede zayıf olduğunu karşılaştırıyoruz.

1. Açgözlü yerleştirme ve graf boyama sezgiselleri

Nasıl çalışır: Dersler bir sıraya konur ve tek tek uygun bir zaman dilimine yerleştirilir. Graf boyama uyarlamasında dersler düğüm, çakışan dersler arası ilişkiler kenar sayılır; düğümler sırayla boyanır. Sıralama genellikle "en çok kısıtlanan önce" (largest degree first) sezgisiyle yapılır.

Güçlü yanı: Çok hızlıdır ve uygulaması basittir. Küçük okullarda saniyeler içinde kabul edilebilir sonuç verir.

Zayıf yanı: Geri dönemez. 400. dersi yerleştirirken yer kalmadığını fark ettiğinizde sebep 50. derste yapılmış bir seçimdir ve o seçim geri alınamaz. Sonuç genellikle eksik programdır. Ayrıca tercihleri (yük dengesi, boş saat) hiç gözetmez.

2. Yerel arama: tavlama benzetimi ve tabu arama

Nasıl çalışır: Önce herhangi bir program üretilir (çakışmalı olabilir), sonra küçük değişikliklerle iyileştirilir: iki dersin yerini değiştir, bir dersi başka saate taşı. Her değişiklik bir puanla değerlendirilir; iyileştirenler kabul edilir.

Tavlama benzetimi (simulated annealing) başlangıçta kötüleştiren hamleleri de belirli olasılıkla kabul eder ve bu olasılığı zamanla düşürür — böylece yerel bir tepede sıkışıp kalmaz. Tabu arama ise son yapılan hamleleri kısa süre yasaklayarak aynı döngüde dönmeyi engeller.

Güçlü yanı: Tercihleri optimize etmekte iyidir; boş saat azaltma ve yük dengeleme gibi hedeflerde başarılıdır. Büyük problemlerde ölçeklenir.

Zayıf yanı: Çözümün en iyi olduğunu kanıtlayamaz; yalnız "bulabildiğimin en iyisi" der. Ayrıca zorunlu kısıtların tamamının sağlandığını garanti etmek için ek denetim gerekir. Parametre ayarı (soğuma hızı, tabu süresi) deneyime bağlıdır ve kötü ayarlanırsa sonuç bozulur.

3. Genetik algoritmalar

Nasıl çalışır: Bir program adayları popülasyonu tutulur. Her adaya bir uygunluk puanı verilir; iyi olanlar seçilip "çaprazlanır" (iki programın parçaları birleştirilir) ve rastgele "mutasyon"lar uygulanır. Nesiller boyunca popülasyon iyileşir.

Güçlü yanı: Çok amaçlı optimizasyona doğal olarak uyar; birbiriyle çelişen hedefleri (denge, pencere, pedagojik sıralama) aynı anda değerlendirebilir. Paralelleştirmesi kolaydır.

Zayıf yanı: Ders programında çaprazlama sorunludur — iki geçerli programın parçalarını birleştirmek neredeyse her zaman geçersiz bir program üretir. Bunu onarmak için ek mekanizmalar gerekir ve bu, algoritmanın avantajını büyük ölçüde tüketir. Yakınsama yavaştır ve tekrarlanabilirliği düşüktür.

4. Karışık tamsayılı programlama (MIP)

Nasıl çalışır: Problem, ikili değişkenler ve doğrusal eşitsizliklerle ifade edilir. "Ders i, zaman dilimi j'ye atandı mı" sorusu 0/1 değişkeniyle temsil edilir; kısıtlar doğrusal denklemlere çevrilir. Ticari veya açık kaynak çözücüler bu modeli optimal biçimde çözer.

Güçlü yanı: Optimallik kanıtı verebilir. Matematiksel olarak sağlam ve iyi anlaşılmış bir çerçevedir.

Zayıf yanı: Ders programının doğal kısıtları (blok bütünlüğü, "aynı ders bir güne en fazla iki saat") doğrusal biçimde ifade edilirken model şişer. Değişken sayısı ders × zaman dilimi × derslik olarak büyür; gerçek okul ölçeğinde model devasa hale gelir ve çözüm süresi öngörülemez.

5. Kısıt programlama çözücüleri (CP-SAT)

Nasıl çalışır: Kısıt programlama, MIP'in doğrusallık zorunluluğunu kaldırır ve hepsi-farklı, kaynak kapasitesi, ardışıklık gibi kısıtları doğrudan ifade etmeye izin verir. Modern CP-SAT çözücüleri bunu SAT (boolean sağlanabilirlik) tekniğiyle birleştirir: kısıt yayılımıyla arama uzayını daraltır, öğrenilen çelişkileri kaydeder ve aynı hataya bir daha düşmez.

Güçlü yanı: Ders programı kısıtlarını en doğal biçimde ifade eder. Kısıt yayılımı sayesinde astronomik arama uzayını hızla daraltır. Zorunlu kısıtları garanti eder ve tercihleri optimize edebilir (COP kurulumu). Çözümü bulduğunda "bu geçerlidir" güvencesi matematikseldir; yeterli süre verilirse optimallik kanıtı da verebilir.

Zayıf yanı: Model kurulumu dikkat ister; kötü kurulmuş bir model gereksiz yere yavaş çalışır. Ayrıca çok büyük örneklerde optimallik kanıtı pratik sürede gelmeyebilir — bu durumda "iyi çözüm bulundu ama en iyi olduğu kanıtlanamadı" durumuyla yetinilir.

Karşılaştırma

Pratikte hangisi?

Gerçek okul ölçeğinde — yüzlerce ders, onlarca öğretmen, çok sayıda kısıt — CP-SAT çözücüleri bugün en dengeli seçenektir. Sebebi tek bir üstünlük değil, üç özelliğin bir arada bulunmasıdır: kısıtları doğal ifade etme, zorunlu kuralları garanti etme ve tercihleri aynı modelde optimize edebilme.

Apakademia'nın planlama motoru bu aileye dayanır. Zorunlu kısıtlar (öğretmen müsaitliği, üç çakışma türü, blok bütünlüğü, şubeler arası öğretmen) modele doğrudan yazılır; tercihler (boş saat azaltma, yük dengesi, ders yığılmasının önlenmesi) amaç fonksiyonunda puanlanır.

Neden tek bir en iyi algoritma yok?

Optimizasyon literatüründe bilinen bir sonuç vardır: hiçbir arama algoritması tüm problem sınıflarında diğerlerinden üstün değildir. Bir yöntemin bir problemde kazandığı avantaj, başka bir problemde dezavantaja dönüşür.

Ders çizelgeleme açısından bunun pratik karşılığı şudur: okulun yapısı algoritma tercihini değiştirir.

• Doluluk düşük, kısıtlar gevşek: basit sezgiseller bile iyi sonuç verir; karmaşık çözücüye gerek yoktur.
• Doluluk yüksek, müsaitlikler dar: yalnız kısıt tabanlı yöntemler geçerli çözüm bulabilir; yerel arama tıkanır.
• Çok sayıda çelişen tercih: optimizasyon destekleyen yöntemler öne çıkar.

Bu yüzden ürün değerlendirirken "hangi algoritmayı kullanıyor" sorusu tek başına yeterli değildir. Daha faydalı soru şudur: benim okulumun doluluk oranı ve müsaitlik esnekliğiyle bu sistem ne yapıyor? Cevabı ancak kendi verinizle deneyerek alırsınız.

Seçim ölçütleri: hangi kritere göre karar verilir?

Bir kurum için ders programı algoritmaları arasında seçim yaparken bakılması gereken beş ölçüt vardır ve bunların önceliği kuruma göre değişir.

1. Zorunlu kısıt garantisi. Çakışmasızlık pazarlık konusu değilse, garanti veremeyen yöntemler (açgözlü, saf genetik) elenir.
2. Revizyon hızı. Dönem içinde sık değişiklik yapılıyorsa, kısmi yeniden çözüm yapabilen yöntemler öne çıkar. Baştan çözen yöntemler her değişiklikte tam süre harcar.
3. Tercih optimizasyonu. Yalnız çakışmasızlık yetmiyorsa (ki genellikle yetmez), amaç fonksiyonu destekleyen yöntemler gerekir.
4. Açıklanabilirlik. "Bu ders neden buraya yerleşti" sorusuna cevap verilebilmesi. Kısıt tabanlı yöntemlerde bu izlenebilir; genetik algoritmalarda pratikte mümkün değildir.
5. Öngörülebilir süre. Üretimin ne kadar süreceğinin tahmin edilebilmesi. MIP'te süre öngörülemez; CP-SAT'te süre sınırı konarak yönetilir.

Çoğu okul için en kritik ölçüt ikincisidir. İlk program bir kez üretilir, ama revizyon onlarca kez yapılır.

Yaygın bir yanlış anlama: "daha akıllı algoritma"

Algoritma seçimi tartışmasında sık yapılan hata, sorunun kaynağını algoritmada aramaktır. Uygulamada karşılaşılan tıkanmaların çoğu algoritmadan değil veriden kaynaklanır: eksik müsaitlik, kapasite aşan ders dağıtımı, çelişkili kurallar.

Hiçbir algoritma, belirli bir saatte 17 sınıfa 15 öğretmenle ders yaptıramaz. Bu durumda daha güçlü bir çözücüye geçmek sonucu değiştirmez; değiştirecek olan şey veriyi düzeltmektir.

Bu yüzden iyi bir sistemin ölçütü yalnız hangi algoritmayı kullandığı değil, çözümsüzlüğü nasıl açıkladığıdır. Hangi kaynağın darboğaz olduğunu söyleyebilen bir sistem, sessizce eksik program üreten güçlü bir çözücüden daha faydalıdır.

Hibrit yaklaşımlar

Uygulamada saf yöntem nadirdir. Yaygın bir hibrit kurulum şöyledir: CP-SAT ile geçerli ve iyi bir çözüm üretilir, ardından yerel arama ile küçük iyileştirmeler yapılır. Bir diğeri, büyük problemi şube veya kademe bazında parçalayıp her parçayı ayrı çözmek, sonra parçalar arası çakışmaları ek bir turda gidermektir.

İkinci yaklaşımın kritik noktası şudur: parçalara ayırma, şubeler arası ortak öğretmen çakışmasını görünmez kılar. Bu yüzden parçalı çözümde ortak kaynakların mutlaka global bir kısıtla bağlanması gerekir.