Stajyer Yerleştirme Probleminde Çok Kriterli Optimizasyon: Beam Search Algoritmasının Rolü ve Karşılaştırmalı Analizi

Bu proje Hasna Şahinoğlu ile beraber gerçekleştirilmiştir.

Stajyer yerleştirme problemi, kısıtlı kontenjanlara sahip firmalar ile farklı tercihlere sahip öğrenciler arasında optimal eşleştirmeyi hedefleyen karmaşık bir süreçtir. Günümüzde üniversitelerin staj koordinasyon merkezleri tarafından yürütülen bu süreçler, klasik haliyle öğrencilerin not ortalamalarına (GNO) deterministik yöntemlerle çözülmektedir. Ancak bu süreçlere, öğrencilerin aynı firmada staj yapma isteği gibi “sosyal faktörler” dahil edildiğinde problem, tek boyutlu bir tercih-kontenjan eşleştirmesinin ötesine geçerek çok kriterli bir optimizasyon haline gelmektedir.

Bu yazıda, söz konusu problemin çözümünde geleneksel Açgözlü (Greedy) algoritmanın sınırları incelenmekte ve çözüm uzayını daha geniş bir perspektifle tarayarak literatüre ve probleme alternatif bir bakış açısı sunan Beam Search tabanlı sezgisel (heuristic) yaklaşımın entegrasyonu ele alınmaktadır.

Geleneksel Yaklaşımın Sınırları: Neden Greedy Yetersiz Kalıyor?

Greedy algoritma, yerleştirme sürecini iteratif ve deterministik olarak yürütmektedir. Öğrencileri akademik başarılarına (GNO) göre sıralar ve tercih listelerindeki ilk uygun firmaya atar. Hesaplama maliyeti açısından oldukça verimli olan bu yöntem, zaman karmaşıklığı bağlamında öngörülebilir bir performans sunar.

Bununla birlikte, Greedy algoritmanın temel sınırlılığı, sosyal faktörleri (arkadaşlık grupları) aktif bir karar değişkeni olarak kullanamamasıdır. Algoritma, yerleştirme sürecinde sadece kontenjan ve GNO verilerine dayanarak ilerler; arkadaşlık bilgisi ise yerleştirme tamamlandıktan sonra yalnızca sonuç metriğine, yani memnuniyet skoruna yansır. Bu yapısal sınırlılık, algoritmanın yerel (local) kararlara hapsolmasına ve sistem genelindeki küresel memnuniyet potansiyelini kaçırmasına yol açmaktadır.

Beam Search Algoritması: Teorik Altyapı ve Çalışma Prensibi

Optimizasyon ve karar verme problemlerinde arama uzayının büyüklüğü, tüm olasılıkların tek tek değerlendirildiği kaba kuvvet (brute-force) yaklaşımlarını hesaplama maliyeti açısından imkansız hale getirebilmektedir. Bu darboğazı aşmak amacıyla literatürde sıklıkla başvurulan sezgisel (heuristic) arama algoritmalarından biri olan Beam Search, çözüm uzayını kontrollü biçimde tarayan bir yöntemdir. Temel olarak “En İyi Öncelikli Arama” (Best-First Search) algoritmasının bellek açısından sınırlandırılmış ve optimize edilmiş bir varyasyonu olarak kabul edilir.

Çalışma Prensibi

Beam Search, tek bir çözüm yolunu takip eden ve yalnızca yerel optimuma odaklanan deterministik algoritmaların aksine, her iterasyonda birden fazla aday çözümü (state) eş zamanlı ve paralel olarak değerlendirir. Algoritmanın genel işleyişi şu adımlara dayanır:

1. Başlangıç: Arama süreci tek bir başlangıç düğümü (state) ile başlatılır.
2. Genişletme (Expansion): Mevcut iterasyondaki düğümler genişletilerek, sistemin o ana kadarki durumu üzerinden yeni alternatif durumlar (çocuk düğümler) üretilir. Böylece çözüm uzayı kontrollü biçimde genişletilir.
3. Değerlendirme ve Budama (Pruning): Üretilen tüm yeni durumlar, probleme özgü tanımlanmış sezgisel bir skorlama fonksiyonu ile değerlendirilir. Arama uzayının üstel olarak büyümesini engellemek için, yalnızca en yüksek skora sahip belirli sayıdaki düğüm korunur ve diğer dallar budanır. Her iterasyonda korunan bu maksimum durum sayısına “Beam Width” adı verilir.
4. Sonlanma: Beam boşaldığında veya hedef derinliğe ulaşıldığında, en yüksek skora sahip state algoritmanın nihai çıktısı olarak seçilir.

Bu yapısal tasarım sayesinde arama uzayı bütünüyle taranmadan, yalnızca umut vadeden çözümler üzerinde yoğunlaşılmış olur. Küçük Beam Width değerleri algoritmayı daha hızlı ancak sınırlı bir arama yapısına iterken; büyük Beam Width değerleri çözüm uzayının daha geniş taranmasını sağlayarak daha yüksek kaliteli sonuçlar üretme potansiyeli sunar.

Literatürdeki Kullanım Alanları

Makine öğrenmesi ve yapay zeka literatüründe Beam Search, arama uzayının oldukça geniş olduğu ardışık (sequence) karar problemlerinde öne çıkmaktadır. Özellikle Doğal Dil İşleme (NLP) alanındaki makine çevirisi modellerinde, konuşma tanıma (speech recognition) sistemlerinde ve karmaşık çizelgeleme (scheduling) problemlerinde yaygın olarak kullanılmaktadır. Optimal çözüme ulaşmanın hesaplama açısından pratik olmadığı, ancak optimuma yakın çok kriterli çözümlerin makul bir sürede elde edilmesinin kritik olduğu problemlerde değerli bir altyapı sunmaktadır.

Optimizasyonda Beam Search Yaklaşımı: Nasıl ve Nerede Kullanıldı?

Küresel memnuniyet skorunu artırmak ve sosyal bağları karar alma sürecine doğrudan dahil etmek amacıyla Beam Search tabanlı bir sezgisel arama yöntemi tasarlanmıştır. Beam Search, tek bir yerleştirme kararı vermek yerine her iterasyonda birden fazla olası çözümü (state) eş zamanlı olarak değerlendiren kontrollü bir arama yöntemidir.

Algoritmanın işleyişindeki kilit noktalar şu şekilde kurgulanmıştır:

1. Genişletme Fonksiyonu ve “Arkadaşlık Toleransı” (Dallanma) Beam Search algoritmasının probleme en büyük katkısı, dallanma modülünde “arkadaşlık toleransı” parametresini kullanmasıdır. Bu parametre, bir öğrencinin arkadaşlarıyla aynı firmaya yerleşebilmek uğruna tercih listesinde kaç basamak aşağı inmeyi rasyonel olarak kabul edeceğini belirten bir eşiktir. Süreç sırasında öğrencinin tolerans aralığında kalan ve kontenjanı bulunan her bir firma alternatifi için ayrı bir state (yeni bir olasılık dalı) üretilir. Böylece, “1. tercihe tek başına gitmek” ile “3. tercihe 2 arkadaş ile gitmek” senaryoları paralel olarak değerlendirme sürecine alınır.

Beam Search ile yerleştirilen 8 öğrencinin yerleştirilmesini simüle eden Beam Tree şeması

2. Skor Hesaplama ve Budama (Pruning) Oluşturulan her state, sistemin ortak memnuniyet fonksiyonu kullanılarak değerlendirilir. Öğrencinin bireysel skoru, tercih puanı ve arkadaş bonusunun toplamından oluşmaktadır:

(Denklemde s tercih sırasını, t yerleşilen iterasyonu, k ise aynı firmadaki arkadaş sayısını ifade eder.)

Bu değerlendirme sonucunda, Beam Search döngüsünde yalnızca en yüksek skora sahip belirli sayıdaki state korunur ve diğer olası yollar budanır. Korunacak maksimum state sayısı “Beam Width” parametresi ile belirlenir.

Karşılaştırmalı Analiz ve Deneysel Bulgula

Simülasyon ortamında gerçekleştirilen çoklu deney senaryoları (50 bağımsız tekrar), iki algoritma arasındaki trade-off ilişkisini literatürdeki beklentilerle uyumlu biçimde ortaya koymuştur:

• Sosyal Yoğunluk Durumunda Performans: Öğrenciler arası grup (arkadaşlık) oranı artırıldığında, Greedy algoritmanın ürettiği memnuniyet puanında yalnızca sınırlı bir artış gözlemlenmiştir. Buna karşılık Beam Search, sosyal bağları aktif bir şekilde dallanma sürecine dahil ettiği için ortalama memnuniyet puanında tutarlı ve belirgin bir yükseliş sergilemiştir.
• Hesaplama Maliyeti ve Ölçeklenebilirlik: Yüksek çözüm kalitesinin bir bedeli olarak Heuristic yaklaşımın zaman karmaşıklığı O(I.B.P) seviyesine çıkmaktadır (İterasyon x Beam Width x Tercih Sayısı). Deneyler, Beam Width parametresinin optimizasyonunda 20 ile 40 değerleri arasının, hesaplama süresi ve çözüm kalitesi bağlamında optimum aralık olduğunu göstermiştir.

Bu sonuçlar, algoritmaların birbirine mutlak bir üstünlük sağlamaktan ziyade, problem koşullarına göre tercih edilmesi gereken farklı stratejiler sunduğunu kanıtlamaktadır. Yalnızca akademik başarının hedeflendiği senaryolarda Greedy algoritma verimli bir temel oluştururken; sosyal bileşenlerin kaliteyi belirlediği sistemlerde Beam Search yöntemi çok daha yüksek performans sergilemektedir.

Sonuç

Bu çalışmada ele alınan metodoloji, yalnızca stajyer yerleştirme süreçleri için değil; üniversitelerdeki kısıtlı kontenjanlı seçmeli ders kayıt sistemleri veya ekip uyumunun bireysel beceriler kadar kritik olduğu kurumsal işe alım senaryoları gibi benzer problemlere de uyarlanabilme potansiyeline sahiptir.

Geliştirilen sistemde, sezgisel algoritmaların “kara kutu” (black box) yapısından çıkması adına D3.js ile web tabanlı bir ağaç görselleştirme modülü ve Tkinter arayüzü entegre edilmiştir. Bu sayede, Beam Search algoritmasının genişlettiği çözüm uzayı ve seçtiği “kazanan yol” (winning path) şeffaf bir şekilde analiz edilebilir hale getirilmiştir. Literatürde çok kriterli optimizasyon ve sezgisel yaklaşımlar üzerine yürütülen çalışmalara, uygulanabilir bir model sunulması amaçlanmıştır.

Nihai durumda, Beam Search tabanlı sezgisel yaklaşımların; adaptif Beam Width mekanizmaları ve paralel hesaplama teknikleriyle desteklenmesi, gelecek araştırmalar için umut vadeden bir çalışma alanı olarak öne çıkmaktadır.

Açık Kaynak Paylaşımı ve Akademik Çıktılar

Geliştirilen algoritmaların matematiksel altyapısı, detaylı zaman karmaşıklığı (time complexity) analizleri ve tam kapsamlı deneysel sonuçlar, “Stajyer Yerleştirme Simülatörü: Greedy ve Heuristic Yaklaşımların Karşılaştırmalı Analizi” başlıklı makalemizde kapsamlı biçimde ele alınmıştır.

Projenin tüm altyapısını ve kaynak kodlarını *Stajyer Yerleştirme Simülatörü GitHub Reposu* bağlantısı üzerinden inceleyebilir, algoritmaları kendi veri setlerinizle test edebilirsiniz. Kavramsal çerçevenin ve algoritmik tasarımların detaylı incelendiği araştırma makalemizin PDF formatına yine aynı GitHub dizini üzerinden ulaşabilirsiniz.