Tepe Tırmanma Algoritması (Hill Climbing Algorithm)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde kullanılan arama algoritmalarından birisidir. Arama işleminin yapıldığı grafikteki tepelerden ismini alır. Basitçe bir grafikte bulunan en düşük noktanın aranması sırasında grafikte yapılan hareketin aslında tepe tırmanmaya benzemesinden ismini almaktadır.

Örneğin yukarıdaki şekilde gösterilen ok temsili bir tepe tırmanma işlemidir. Burada arama yapan algoritma aslında bir çukur bulmuş ancak daha iyisi için tepe tırmanmaktadır denilebilir.

Elbette olayı iki boyutlu bir grafik üzerinde yapılan bir arama veya tırmanılan bir tepe olarak görmek, algoritmanın önemini kavramayı engelleyebilir. Aslında burada anlatılmak istenen bilgisayar bilimleri de dahil olmak üzere, çeşitli bilim ve mühendislik alanlarında, birden fazla çözümü olan problemler için en iyi çözümün arandığı iyileştirme (optimization) problemleridir.

Yani şayet bir sistemin ya da bir programın daha iyi hale getirilmesi isteniyorsa, sistemin verdiği sonuçlara göre arama işlemi yapılarak iyileştirme amaçlanabilir. İşte bu noktada tepe tırmanma algoritması (hill climbing algorithm) de dahil olmak üzere çeşitli arama algoritmaları devreye girer. Örneğin literatürde sıkça kullanılan seyyar tüccar problemi (travelling salesman problem) bu problemlerden birisidir. Tepe tırmanma algoritması verilen bir harita için verilen bir sonucu iyileştirmeye çalışır. Elbette amaç bütün ihtimalleri denemeden iyi bir sonuç bulabilmektir.

Tepe tırmanma algoritması, arama algoritmaları arasındaki en iyi sonucu verene algoritma değildir. Ancak kodlanması ve tasarımının basit oluşundan dolayı sıklıkla kullanılır.

Tepe tırmanma algoritması çeşitleri

Algoritmanın üzerinde çeşitli iyileştirmeler yapılarak daha iyi sonuçlar elde edilmeye çalışılmıştır. Literatürde sıkça kullanılan bir iki tepe tırmanma algoritmasını farkları ile birlikte açıklamaya çalışalım.

Klasik tepe tırmanma algoritmasında amaç arama için merkez kabul edilen (veya başlangıç noktamız diyebileceğimiz) noktadan komşu olan noktaları gezerek daha iyi sonuçlar elde etmektir. Temel olarak bir grafikte rastgele seçilen bir nokta için 3 farklı ihtimal bulunmaktadır:

  1. Noktanın bir tarafında problem iyileşirken diğer tarafında kötüleşmektedir. Bu durumda iyi tarafa doğru tırmanma algoritmamız devam eder.
  2. Noktanın iki tarafında da problem sonucu kötüleşmektedir. Bu durumda bulunduğumuz nokta problem için en iyi noktalardan (optimum points) birisidir. Elbette bu en iyi sonuç olmayabilir yani bu sonuçtan daha iyi sonuçlar olabilir ancak klasik tepe tırmanma algoritması bu diğer sonuçları bulamaz ve bu noktada kalır.
  3. Noktanın iki tarafında da problem iyileşiyordur. Yani tesadüfen bulduğumuz nokta aslında problem için ulaşılabilecek en kötü noktalardan birisidir. Bu durumda tepe tırmanma algoritması yönlerden birisini seçerek tırmanmaya devam eder. Farklı bir çeşit olarak iki yöne de tırmanan algoritma bulunmaktadır.

Klasik tepe tırmanma algoritmasından farklı olarak steepest ascent hill climbing algoritmasında, bulunabilen bütün sonuçlar arasından bir seçim yapılır. Bu algoritmada da klasik tepe tırmanma algoritmasında da sorun aynıdır. Şayet arama işlemi sırasında bir yerel çukura (local minimum) rastlanılırsa bu durumdan algoritma kendisini kurtaramayarak en doğru sonucu bulamayabilir.

Buna karşılık olasılıksal tepe tırmanma algoritmasında ( stochastic hill climbing algorithm) bütün komşuların aranması ve komşuların verdiği sonuca göre hareket etmek yerine, rast gele olarak bir komşunun seçilmesi söz konusudur. Şayet gidilen bu komşu beklenen yönde bir iyileştirme sağlıyorsa, bu yönde aramaya (tırmanmaya) devam edilir, şayet beklenen iyileştirme sağlanamıyorsa, bu durumda daha farklı bir komşu denenir.

Yukarıdaki tepe tırmanma algoritmalarının yanında rastgele başlangıç tepe tırmanma algoritması (random restart hill climbing algorithm) şaşırtıcı derecede iyi sonuç veren bir algoritmadır. Bu algoritma basitçe bir x durumunu başlangıç kabul eder ve daha iyi bir durum bulunca başlangıç durumunu bu daha iyi duruma kaydırır. Algoritma iyi durum buldukça başlangıç durumunu kaydıran ancak bulamadığı durumlarda da aramaya devam eden bir yapıya sahiptir. Rastgele başlangıç tepe tırmanma algoritmasına bazı kaynaklarda pompalı tüfek tepe tırmanma algoritması (shotgun hill climbing algorithm) ismi de verilmektedir.

Tepe tırmanma algoritmaları genel olarak yerel bir başarı noktasında (local optimum point) takılmak gibi bir zafiyete sahiptirler. Daha iyi sonuçlar için simulated annealing gibi arama algoritmaları kullanılabilir.

Örneğin yukarıdaki şekilde x ve y noktaları arasında bir düzlük bulunmaktadır. Başlangıç noktası olarak bu aralıktaki herhangi bir noktadan başlanırsa algoritma komşuları aradığında daha iyi veya daha kötü bir sonuç bulamayacağı için hatalı karar verebilir.

Ayrıca tepe tırmanma algoritmaları problem sonuçlarında nadiren de olsa aynı sonucun elde edilmesi durumunda belirsizce hatalı sonuçlar verebilir. Bu şekildeki durumlara algoritmadaki düzlükler ismi verilir ve algoritma hangi yöne gidilirse gidilsin daha iyi bir sonuç çıkaramaz (hep aynı sonucu çıkarır). Elbette doğası gereği tepe tırmanmaya hazırlanmış algoritmamız, tepe bulamayınca hata yapmaktadır.

Algoritmanın kodlanması

Algoritma iki boyutlu bir grafik için rastgele yön seçimi yapılması durumunda aşağıdaki şekilde kodlanabilir:

Yukarıdaki kodda, basitçe başlangıç noktasından başlanarak, daha iyi sonuçlar bulunduğu sürece bir sonraki komşu noktaya hareket öngörülmüştür.

Ancak problemin çok boyutlu olması yani bir noktanın birden fazla komşusu bulunması durumunda bütün komşuların kontrol edilmesi ve en iyisinin bulunması daha sonra bu komşuya doğru hareket edilmesi gerekeceği için algoritmayı aşağıdaki şekilde yazmak mümkündür:

Yukarıdaki yeni kodda, bir noktanın birden çok komşusu olduğu kabul edilmiş ve bütün komşuları dolaşılarak en iyi komşu alınmış, ardından daha iyi komşu bulundukça bu işlem devam ettirilmiştir. Nihayetinde hiçbir komşu, bulunan son komşudan daha iyi olmayınca program sonlandırılmıştır.

Yorumlar

  1. kazimkanat

    merhabalar, acaba bu algoritmayı TSP(Travelling salesman problem) durumuna uygulamaya çalışırsak, ve bütün inputları bir dosyadan okuduğumuzu düşünürsek en başta algoritmaya dahil bir şekilde input okuyarak ilerleyebilmeyi nasıl yapabiliriz acaba?
    Bir de i ve j ikisi de başlangıç noktası 2 boyutlu olduğu için mi farklı değerler verdik bu kısmı anlayamadığımdan kodu maalesef anlayamadım ben.
    Teşekkürler.

  2. Şadi Evren ŞEKER Article Author

    evet ikiside aynı değerden başlıyor, daha iyi oludğu sürece i değeri değiştirlerek bir sonraki değeri seçiliyor. İki boyutlu olan algoritmada da iki değerde başlangıç değerinden başlanarak çalışıyorlar. Farklı değer verme durumu söz konusu değil.

  3. Suleyman Gunduz

    Merhaba hocam ben 3.ihtimal olduğunda yani seçilen noktanın her iki tarafıda iyileştiğinde bir seçim yapılıyor demişsiniz peki bu seçim neye göre yapılıyor hangisi en iyisi ise o noktadan mı gidiliyor yoksa random olarak bir yön mü seçiliyor

    Teşekkürler,Saygılar.

  4. Şadi Evren ŞEKER Article Author

    Tepe tırmanma algoritması özü itibariyle rastgele çalışan bir algoritmadır. Bu tip algoritmalarda başlangıçta bir nokta seçimi genelde rast gele olarak yapılır. Ve bahsi geçen durumlarda rast gele olarak seçim en çok izlenen yoldur.

    Zaten algoritmanın global optimum bulamayı garanti edememesinin sebebi de bu rast geleliktir.

    Ancak probleme göre özel iyileştirmeler yapılarak daha iyi çalışması sağlanabilir.

    Örneğin algoritmanın bir benzeri olan arı araması için diğer arıların durumuna bakarak bir seçim yapılabilir.

    http://www.bilgisayarkavramlari.com/2009/12/06/arilar-algoritmasi-bees-algorithm/

    Hatta bu nokta işaretlenerek sonra geri dönüşebilir (back tracking):

    http://www.bilgisayarkavramlari.com/2009/11/01/geri-izleme-algoritmasi-backtracking-algorithm/

    Kısaca sorunuzun cevabı rast gele, uzunca cevabı ise size, probleme ve ne yapmak istediğinize göre değişir. Yani daha iyi yöne doğru gitmenizin hata olduğunu söylemek hata olur.

    Başarılar

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir