Back

ⓘ Tepe Tırmanma Algoritması, yapay zeka alanındaki matematiksel optimizasyon problemleri için kullanılan sezgisel bir algoritmadır. Çok sayıda verinin girilmesi v ..




Tepe Tırmanma Algoritması
                                     

ⓘ 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ısmaktadır. Bilgisayar bilimlerinde aktif olarak kullanılmakta olan arama algoritmalarından birisidir. Iki boyutlu bir grafikte en düsük noktaları arama esnasında yapmıs olduğu hareket tepe tırmanmaya benzemesinden dolayı bu isimi almıstır.

Yani bir sistemi veya programı daha verimli hale getirilmesi isteniyorsa, sistemin sonuçlarına göre arama yapılarak iyilestirilmesi hedeflenebilmektedir. Tepe tırmanma algoritması da dahil olmak üzere çesitli 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.

                                     

1. Özellikleri

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

  • Üret ve test et varyantı

Tepe tırmanma algoritması Üret Generate ve Test Et yönteminin bir çesididir. Ü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ü Yaklasım Greedy Approach*

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

  • Geriye Dönük Islem*

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 islem yapamamasına neden olmaktadır.

                                     

2.1. Çesitleri Basit Tepe Tırmanma Algoritması

Basit tepe tırmanma, tepe tırmanma algoritması uygulamanın en basit yoludur. Bir seferde yalnızca komsu düğüm durumunu değerlendirir ve cari maliyeti optimize etmektedir. Optimizasyon sonucunda komsu 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ç tekrardan baslar ve en iyisini bulana kadar devam etmektedir. Sıralama su sekildedir;

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

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

                                     

2.2. Çesitleri Stokastik Tepe Tırmanma Algoritması

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

                                     

3. 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 su sekilde tanımlanabilmektedir.

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

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

Seyyar Satıcı 4 adet sehre uğrayacaktır. Sehirler arası mesafeler su sekildedir;

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ı su sekilde yazmak uygudur; Bir noktanın birden fazla komsusu varsa, o zaman tüm komsular kontrol edilecek ve daha sonra o komsuya gitmek için en iyisine ihtiyaç duyulacaktır.

Yandaki yeni kodda bir noktanın birden fazla komsusu olduğu varsayılmıs ve tüm komsular dolastırılarak en iyi komsu alınmıs ve daha sonra daha iyi komsular bulunarak bu süreç devam ettirilmistir. Sonunda, hiçbir komsu bulunan son komsudan daha iyi olmadığında, program sonlandırılmıstır.