Tepe Tırmanma (Hill Climbing)

Tepe Tırmanma nedir?

Tepe tırmanma (hill climbing), bir optimizasyon probleminde en iyi çözümü bulmak için kullanılan basit bir yerel arama algoritmasıdır. Rastgele ya da belirli bir başlangıç çözümüyle başlar, sonra her adımda mevcut çözümün "komşularına" bakar ve daha iyi olan bir komşuya geçer. Daha iyi bir komşu kalmadığında durur.

Adı sezgisinden gelir: Yoğun sisli bir dağda olduğunu ve zirveye ulaşmak istediğini düşün. Uzağı göremiyorsun; sadece bulunduğun yerin etrafına bakabiliyorsun. Her adımda en çok yükselen yöne doğru bir adım atıyorsun. Hiçbir yön yukarı çıkmıyorsa, bir zirvede olduğunu düşünüp duruyorsun.

Nasıl çalışır?

Algoritmanın temel adımları şöyledir:

• Başlangıç: Bir başlangıç çözümü seçilir.
• Komşuları değerlendirme: Mevcut çözümde küçük değişiklikler yapılarak komşu çözümler üretilir. Örneğin bir gezgin satıcı rotasında iki şehrin yerini değiştirmek.
• Geçiş: Komşular arasında mevcut çözümden daha iyisi varsa ona geçilir.
• Durma: Daha iyi komşu kalmadığında algoritma durur ve mevcut çözümü döndürür.

Farklı türleri vardır. En dik tırmanma (steepest ascent) tüm komşuları değerlendirip en iyisini seçer. Basit tırmanma, bulduğu ilk daha iyi komşuya geçer. Stokastik tırmanma ise daha iyi komşular arasından rastgele birini seçer.

Tepe tırmanmanın en bilinen sorunu yerel maksimumlara takılmasıdır. Bulunduğun tepe, dağın en yüksek zirvesi olmayabilir; ama etrafındaki her yer daha alçak olduğu için algoritma orada durur. Ayrıca düzlükler (plato), yani komşuların hepsinin aynı değere sahip olduğu bölgeler de algoritmayı yönsüz bırakır.

Bu sorunları hafifletmek için rastgele yeniden başlatma (farklı başlangıç noktalarından birçok kez çalıştırıp en iyi sonucu almak) ya da benzetilmiş tavlama (simulated annealing) gibi, zaman zaman kötü adımlara da izin veren yöntemler kullanılır.

Neden önemli?

Tepe tırmanma, uygulaması çok kolay, bellek ihtiyacı düşük ve çoğu zaman makul derecede iyi sonuçlar veren bir yöntemdir. Gradyanın hesaplanamadığı ayrık problemlerde özellikle kullanışlıdır. Ayrıca gradient descent'in sezgisini anlamak için de iyi bir başlangıç noktasıdır: Gradient descent, sürekli bir uzayda "aşağı doğru" yapılan bir tür tepe tırmanmadır.

"Hill climbing" terimi, makine öğrenmesi topluluğunda bir benchmark üzerinde küçük iyileştirmeler peşinde koşmayı eleştirmek için mecazi olarak da kullanılır.

Kullanım alanları

• Kombinatoryal optimizasyon: Rota planlama, çizelgeleme ve atama problemleri.
• Hiperparametre arama: Basit ve hızlı yerel iyileştirme.
• Oyun yapay zekası: Hamle ve strateji değerlendirmesi.
• Özellik seçimi: Model başarısını artıran özellik alt kümelerini aramak.
• Prompt optimizasyonu: Bir prompt'u küçük değişikliklerle adım adım iyileştirmek.