- Tepe tırmanma algoritması, dağın zirvesini veya soruna en iyi çözümü bulmak için sürekli olarak artan yükseklik/değer doğrultusunda hareket eden yerel bir arama algoritmasıdır. Hiçbir komşunun daha yüksek bir değere sahip olmadığı bir tepe değerine ulaştığında sona erer.
- Tepe tırmanma algoritması matematik problemlerini optimize etmek için kullanılan bir tekniktir. Tepe tırmanma algoritmasının yaygın olarak tartışılan örneklerinden biri, satıcının kat ettiği mesafeyi en aza indirmemiz gereken Gezgin Satıcı Problemidir.
- Aynı zamanda açgözlü yerel arama olarak da adlandırılır çünkü sadece yakın komşu durumuna bakar ve onun ötesine bakmaz.
- Tepe tırmanma algoritmasında bir düğümün durum ve değer olmak üzere iki bileşeni vardır.
- Tepe Tırmanışı çoğunlukla iyi bir buluşsal yöntem mevcut olduğunda kullanılır.
- Bu algoritmada, yalnızca tek bir mevcut durumu koruduğu için arama ağacını veya grafiği korumamıza ve işlememize gerek yoktur.
Tepe Tırmanışının Özellikleri:
Tepe Tırmanışı Algoritmasının bazı temel özellikleri şunlardır:
Tepe Tırmanışı için Durum-Uzay Diyagramı:
Durum uzayı manzarası, algoritmanın çeşitli durumları ile Hedef fonksiyonu/Maliyet arasındaki grafiği gösteren tepe tırmanma algoritmasının grafiksel bir temsilidir.
Y ekseninde amaç fonksiyonu veya maliyet fonksiyonu olabilen fonksiyonu, x ekseninde ise durum uzayını aldık. Y eksenindeki fonksiyon maliyet ise, aramanın amacı global minimum ve yerel minimumu bulmaktır. Y ekseninin işlevi Amaç işlevi ise, aramanın amacı genel maksimumu ve yerel maksimumu bulmaktır.
Durum uzay manzarasındaki farklı bölgeler:
Yerel Maksimum: Yerel maksimum, komşu durumlarından daha iyi olan bir durumdur ancak ondan daha yüksek olan başka bir durum da vardır.
Küresel Maksimum: Küresel maksimum, durum uzay manzarasının mümkün olan en iyi durumudur. Amaç fonksiyonun en yüksek değerine sahiptir.
Mevcut durum: Bir peyzaj diyagramında bir etmenin halihazırda mevcut olduğu bir durumdur.
Düz yerel maksimum: Mevcut durumların tüm komşu durumlarının aynı değere sahip olduğu peyzajdaki düz bir alandır.
Omuz: Yukarıya doğru uzanan bir plato bölgesidir.
Tepe Tırmanma Algoritmasının Türleri:
- Basit Tepe Tırmanışı:
- En Dik Yükselişli Tepe Tırmanışı:
- Stokastik Tepe Tırmanışı:
1. Basit Tepe Tırmanışı:
Basit tepe tırmanma, tepe tırmanma algoritmasını uygulamanın en basit yoludur. Bir seferde yalnızca komşu düğüm durumunu değerlendirir ve mevcut maliyeti optimize eden ilkini seçer ve bunu mevcut durum olarak ayarlar. . Yalnızca bir ardıl durum olup olmadığını kontrol eder ve mevcut durumdan daha iyi bulursa, aynı duruma geçin. Bu algoritma aşağıdaki özelliklere sahiptir:
- Daha az zaman alıcı
- Daha az optimal çözüm ve çözüm garanti edilmez
Basit Tepe Tırmanışı Algoritması:
- Hedef durumu ise, başarıyı döndürün ve çıkın.
- Aksi takdirde mevcut durumdan daha iyiyse yeni durumu mevcut durum olarak atayın.
- Aksi takdirde mevcut durumdan daha iyi değilse 2. adıma dönün.
2. En Dik Yükselen Tepe Tırmanışı:
En Dik Yükseliş algoritması, basit tepe tırmanma algoritmasının bir çeşididir. Bu algoritma, mevcut durumun tüm komşu düğümlerini inceler ve hedef duruma en yakın olan bir komşu düğümü seçer. Bu algoritma birden fazla komşuyu ararken daha fazla zaman harcıyor
En Dik Yükseliş Tepe Tırmanışı Algoritması:
- SUCC öyle bir devlet olsun ki, mevcut devletin halefi ondan daha iyi olsun.
- Mevcut duruma uygulanan her operatör için:
- Yeni operatörü uygulayın ve yeni bir durum oluşturun.
- Yeni durumu değerlendirin.
- Hedef durumu ise, onu geri verin ve çıkın, aksi takdirde SUCC ile karşılaştırın.
- SUCC'den daha iyiyse yeni durumu SUCC olarak ayarlayın.
- SUCC mevcut durumdan daha iyiyse mevcut durumu SUCC olarak ayarlayın.
3. Stokastik tepe tırmanışı:
Stokastik tepe tırmanışı, hareket etmeden önce tüm komşularını incelemez. Bunun yerine, bu arama algoritması rastgele bir komşu düğümü seçer ve onu mevcut durum olarak mı seçeceğine yoksa başka bir durumu mu inceleyeceğine karar verir.
Tepe Tırmanma Algoritmasının Sorunları:
1. Yerel Maksimum: Yerel maksimum, peyzajdaki komşu durumların her birinden daha iyi olan bir tepe durumudur, ancak yerel maksimumdan daha yüksek olan başka bir durum da mevcuttur.
Çözüm: Geri izleme tekniği, durum uzayı manzarasında yerel maksimumun bir çözümü olabilir. Algoritmanın arama alanını geriye doğru izleyebilmesi ve diğer yolları da keşfedebilmesi için umut verici yolların bir listesini oluşturun.
2. Yayla: Plato, mevcut durumun tüm komşu durumlarının aynı değeri içerdiği arama uzayının düz alanıdır, çünkü bu algoritma hareket edecek en iyi yönü bulamaz. Plato bölgesinde bir tepe tırmanma araması kaybolabilir.
Çözüm: Yaylanın çözümü, sorunu çözmek için ararken büyük adımlar atmak ya da çok küçük adımlar atmak. Algoritmanın plato dışı bölgeyi bulabilmesi için mevcut durumdan uzakta olan bir durumu rastgele seçin.
3. Sırtlar: Sırt, yerel maksimumun özel bir şeklidir. Çevresine göre daha yüksek bir alana sahiptir ancak kendisi eğimlidir ve tek hamlede ulaşılamaz.
Çözüm: Çift yönlü aramayı kullanarak veya farklı yönlere hareket ederek bu sorunu çözebiliriz.
Benzetimli tavlama:
Hiçbir zaman daha düşük bir değere doğru hareket etmeyen bir tepe tırmanma algoritmasının, yerel bir maksimuma takılıp kalabileceği için eksik olması garanti edilir. Ve eğer algoritma bir ardılı hareket ettirerek rastgele bir yürüyüş uygularsa, tamamlanabilir ancak verimli olmayabilir. Benzetimli tavlama hem verimlilik hem de tamlık sağlayan bir algoritmadır.
Mekanik anlamda Tavlama bir metalin veya camın yüksek sıcaklıkta sertleştirilmesi ve ardından yavaş yavaş soğutulması işlemidir, böylece metalin düşük enerjili kristal durumuna ulaşması sağlanır. Aynı süreç, algoritmanın en iyi hareketi seçmek yerine rastgele bir hareketi seçtiği benzetilmiş tavlamada da kullanılır. Rastgele hareket durumu iyileştirirse aynı yolu izler. Aksi takdirde algoritma olasılığı 1'den küçük olan yolu takip eder veya yokuş aşağı hareket ederek başka bir yol seçer.