Tepe Tırmanma Algoritması

Tepe Tırmanma Algoritması, yapay zeka alanındaki matematiksel optimizasyon problemleri için kullanılan sezgisel bir algoritmadır. Çok sayıda verinin girilmesi ve iyi bir sezgisel fonksiyon verildiğinde, probleme yeterince iyi bir çözüm bulmaya çalışmaktadır. Bilgisayar bilimlerinde aktif olarak kullanılmakta olan arama algoritmalarından birisidir. İki boyutlu bir grafikte en düşük noktaları arama esnasında yapmış olduğu hareket tepe tırmanmaya benzemesinden dolayı bu isimi almıştır.

Yani bir sistemi veya programı daha verimli hale getirilmesi isteniyorsa, sistemin sonuçlarına göre arama yapılarak iyileştirilmesi hedeflenebilmektedir. Tepe tırmanma algoritması da dahil olmak üzere çeşitli arama algoritmalarının devreye girdiği yer burasıdır. Örneğin literatürde sıklıkla kullanılan seyyar satıcı problemi bu problemlerden biridir.

Özellikleri

Tepe Tırmanma Algoritmasının 3 ana özelliği şunlardır:

• Üret ve test et varyantı

Tepe tırmanma algoritması Üret (Generate) ve Test Et yönteminin bir çeşididir. Üret ve Test Et yöntemi, arama alanında hangi yöne hareket edileceğine karar vermeye yardımcı olan geri bildirim üretmektedir.

• Açgözlü Yaklaşım (Greedy Approach)*

Tepe tırmanma algoritmasının, arama esnasında maliyeti optimize eden yönde bir özelliği vardır. Başka bir deyişle en kısa mesafeyi bularak o yönde ilerlemektedir.

• Geriye Dönük İşlem*

Tepe tırmanma algoritması kullandığı bir yöntemi, o bölgeyi geçtikten sonra unutur ve hatırlayamaz. Bu da Tepe tırmanma algoritmasının arama alanında geriye dönük işlem yapamamasına neden olmaktadır.

Çeşitleri

Basit Tepe Tırmanma Algoritması

Basit tepe tırmanma, tepe tırmanma algoritması uygulamanın en basit yoludur. Bir seferde yalnızca komşu düğüm durumunu değerlendirir ve cari maliyeti optimize etmektedir. Optimizasyon sonucunda komşu düğümler arasından bir tanesini seçmektedir. Ardından bir varis durumu olup olmadığını kontrol eder ve mevcut durumdan daha iyi bulursa, o zaman süreç tekrar başlar ve en iyisini bulana kadar devam etmektedir. Sıralama şu şekildedir;

• Adım 1: Başlangıç durumunu değerlendirin, hedef durumsa, başa dönün ve durdurun.
• Adım 2: Bir çözüm bulunana veya uygulanacak yeni operatör kalmayana kadar bir döngü kurun.
• Adım 3: Mevcut duruma bir operatör seçin ve uygulayın.
• Adım 4: Yeni durumu kontrol edin:
  • Hedef durumsa, başa dönün ve çıkın.
  • Aksi takdirde mevcut durumdan daha iyiyse, yeni durumu mevcut durum olarak atayın.
  • Mevcut durumdan daha iyi değilse, 2. adıma geri dönün.
• Adım 5: Çıkış.

En Dik Tepe Tırmanma Algoritması

En dik Tepe Tırmanma algoritması, basit tepe tırmanma algoritmasının bir çeşididir. Bu algoritma, mevcut durumun tüm komşu düğümlerini incelemekte ve hedef duruma en yakın olan bir komşu düğümü seçmekte. Bu algoritma, birden çok komşuyu ararken daha fazla zaman tüketmektedir.

Stokastik Tepe Tırmanma Algoritması

Stokastik Tepe Tırmanma Algoritması, hareket etmeden önce diğer türlerin aksine tüm komşu düğümleri incelememektedir. Daha ziyade, bu arama algoritması bir komşu düğümü rastgele seçmekte, onu mevcut durum olarak seçip seçmemeye veya başka bir durumu inceleyip incelememeye karar vermektedir.

Tepe Tırmanma Algoritmasına ait Akış Diyagramı

Tepe Tırmanma Algoritmasına ait Akış Diyagramı

Algoritmaya ait akış diyagramı yan tarafta görüldüğü gibidir.

Seyyar Satıcı Probleminin Tepe Tırmanma Algoritması Kullanarak Çözülmesi

Optimizasyon problemleri denildiği zaman ilk akla gelen problemlerden birisi de seyyar satıcı problemidir. Gezgin Satıcı Problemi şu şekilde tanımlanabilmektedir.

Bir seyyar satıcı vardır ve mallarını n kadar şehirde satmak istiyor. Diğer bir taraftan, mantıklı bir şekilde, seyyar satıcı bu şehirleri mümkün olan en kısa şekilde ve her bir şehre maksimum bir kere uğrayarak ürünlerini satmak istemektedir. Bu problem, bir matematiksel problem olarak 1930'lu yıllarda formüle edilmiştir. Optimizasyon konusunda en derin inceleme konularından biridir.

Gezgin Satıcı Probleminin Tepe Tırmanma Algoritması kullanılarak C # programlama dili ile çözülmesi

C# programlama dilini kullanarak çözülen bu problem aşağıdaki gibidir.

Seyyar Satıcı 4 adet şehre uğrayacaktır. Şehirler arası mesafeler şu şekildedir;

1-3: 15,

1-4: 20,

1-2: 10,

2-4: 25,

2-3: 35,

3-4:40,

Problem çok boyutlu olduğu için algoritmayı şu şekilde yazmak uygudur; Bir noktanın birden fazla komşusu varsa, o zaman tüm komşular kontrol edilecek ve daha sonra o komşuya gitmek için en iyisine ihtiyaç duyulacaktır.

Yandaki yeni kodda bir noktanın birden fazla komşusu olduğu varsayılmış ve tüm komşular dolaştırılarak en iyi komşu alınmış ve daha sonra daha iyi komşular bulunarak bu süreç devam ettirilmiştir. Sonunda, hiçbir komşu bulunan son komşudan daha iyi olmadığında, program sonlandırılmıştır.

Gezgin Satıcı Probleminin Tepe Tırmanış Algoritması kullanılarak C # programlama dili ile çözülmesi