Jump to content
  • entries
    55
  • comments
    2
  • views
    57,774

Stokastik Tepe Tırmanışı(Stochastic Hill Climbing)


Doğuhan ELMA

209 views

Stokastik Tepe Tırmanışı, bir tür optimize etme veya arama algoritmasıdır. Bu algoritma, bir çözümün kalitesini belirleyen bir hedef veya maliyet fonksiyonunu en iyi duruma getirmeye çalışır. Algoritma, başlangıç çözümünden başlar ve daha iyi bir çözüm bulmak için çözüm alanını araştırır.

Normal tepe tırmanışı algoritmasında, bir çözüm bulunduktan sonra, tüm komşu çözümler incelenir ve en iyi komşu çözüm (en düşük maliyetli veya en yüksek faydalı, hedefe bağlı olarak) yeni çözüm olarak seçilir. Bu süreç, daha iyi bir komşu bulunamayana kadar tekrar edilir.

Stokastik tepe tırmanışı ise, bir sonraki adımda hangi çözümün seçileceğine dair biraz rastgelelik ekler. Bir sonraki adımda en iyi komşu çözümün seçilmesi yerine, bir komşu rastgele seçilir. Bu yaklaşımın avantajı, algoritmanın lokal bir maksimuma (veya minimuma) takılıp kalmaktan kaçınma olasılığının daha yüksek olmasıdır, çünkü rastgele seçimler algoritmayı bu tür yerlerden çıkarabilir.

Stokastik tepe tırmanışı, daha genel bir stokastik optimizasyon sınıfına aittir ve genellikle karmaşık, gürültülü ve bilinmeyen maliyet fonksiyonlarında kullanılır. Ancak, bu algoritmanın dezavantajları arasında, en iyi global çözümü bulmayı garantileyememesi ve çok büyük çözüm uzayları için verimsiz olabileceği yer alır.

import random


def f(x):
    return -x ** 2 + 4 * x


def stochastic_hill_climbing(start, neighbors, max_iter):
    best_x = start
    best_y = f(best_x)

    for _ in range(max_iter):
        x = best_x + random.choice(neighbors)
        y = f(x)

        if y > best_y:  
            best_x, best_y = x, y

    return best_x, best_y


start = 0
neighbors = [-0.1, 0.1] 
max_iter = 1000

best_x, best_y = stochastic_hill_climbing(start, neighbors, max_iter)
print(f"En iyi x: {best_x}, En iyi y: {best_y}")
  1. import random: Bu satır, rastgele sayılar oluşturabilmek için random modülünü içe aktarır.
  2. def f(x): return -x**2 + 4*x: Bu satırda, optimize etmeye çalıştığımız hedef fonksiyonu f(x) tanımlıyoruz. Bu fonksiyon, girdi olarak bir x değeri alır ve -x^2 + 4*x hesaplamasını yaparak bir çıktı üretir.
  3. def stochastic_hill_climbing(start, neighbors, max_iter): Bu satırda, Stokastik Tepe Tırmanışı algoritmasını gerçekleştiren fonksiyonu tanımlıyoruz. Bu fonksiyon, başlangıç x değeri, komşu x değerleri ve maksimum iterasyon sayısını parametre olarak alır.
  4. best_x = start ve best_y = f(best_x): Bu iki satırda, en iyi x ve y değerlerini başlangıç değerleri olarak belirliyoruz. best_x, başlangıçta en iyi çözüm olarak kabul edilen x değerini ve best_y ise bu x değeri için hesaplanan hedef fonksiyon değerini saklar.
  5. for _ in range(max_iter): Bu satırda, belirlenen maksimum iterasyon sayısı kadar döngü başlatıyoruz. Her iterasyon, bir adım (yani bir çözüm güncellemesi) karşılık gelir.
  6. x = best_x + random.choice(neighbors): Bu satırda, mevcut en iyi x değerine rastgele seçilen bir komşu değeri ekleyerek yeni bir x değeri üretiyoruz.
  7. y = f(x): Bu satırda, yeni üretilen x değeri için hedef fonksiyon değerini hesaplıyoruz.
  8. if y > best_y: Bu ifade, eğer yeni hesaplanan y değeri, şimdiye kadar bulunan en iyi y değerinden daha iyiyse, bu bloktaki kodun çalışmasını sağlar.
  9. best_x, best_y = x, y: Bu satır, yeni hesaplanan x ve y değerlerini en iyi x ve y değerleri olarak günceller.
  10. return best_x, best_y: Bu satır, fonksiyonun çıktısını belirler. Algoritma sonunda, en iyi x ve y değerlerini döndürür.

Son 5 satır ise, Stokastik Tepe Tırmanışı fonksiyonunu başlatmak ve en iyi x ve y değerlerini yazdırmak için kullanılır. start, neighbors ve max_iter değerleri burada belirlenir ve fonksiyon bu değerlerle çağrılır. En iyi x ve y değerleri hesaplandıktan sonra, bu değerler ekrana yazdırılır.

Bu kod, Stokastik Tepe Tırmanışı algoritmasını uygular. Başlangıçta x = 0'da başlar ve her iterasyonda x'i 0.1 birim sola veya sağa hareket ettirir (bu hareketler komşular olarak tanımlanmıştır). Her hareket sonrasında, eğer bulunan yeni x değeri daha büyük bir y değeri (yani daha iyi bir çözüm) üretirse, en iyi çözüm olarak bu yeni çözüm kaydedilir. Bu işlem, belirlenen maksimum iterasyon sayısı kadar tekrar edilir.

Sonuç olarak, bu kod x ve y'nin en iyi değerlerini (yani hedef fonksiyonun en yüksek değerini veren x değeri ve bu en yüksek değer) döndürür.

Not: Bu basit örnekte, algoritmanın sonucu başlangıç noktasına, komşuların tanımlanmasına ve maksimum iterasyon sayısına bağlıdır. Ayrıca, bu örnekte hedef fonksiyon basit ve tek bir maksimuma sahip olduğu için, Stokastik Tepe Tırmanışı'nın avantajları tam olarak gösterilememektedir. Karmaşık bir hedef fonksiyonu ve daha büyük bir çözüm uzayı üzerinde Stokastik Tepe Tırmanışı'nın nasıl performans gösterdiğini görmek için daha karmaşık senaryolar incelenebilir.

Akış Diağramı:

 

1.png

 

Animasyon:

 

 

0 Comments


Recommended Comments

There are no comments to display.

Guest
Add a comment...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...