Zeki Optimizasyon Teknikleri - 1 (Hill Climbing)



    Optimizasyon Algoritmalarımızdan ilki Stochastic(içerisinde rastgelelik bulunan) tekniklerden birisi olan Hill Climbing algoritması. Bu yöntem pek çok uygulamada uygulama kolaylığı nedeniyle seçilebilir.
   Optimizasyonu istenen problemin gösterimi, elde olan çözüme göre komşu çözüm üreteci, ilk çözüm üreteci ve çözüm değerlendirme fonksiyonu uygulama için yeterli olmaktadır.
  Algoritmanın dezavantajları olarak yerel çözümlere takılabilmesini ve  çözümün seçilen başlangıç noktasına çok bağlı olmasını sayabiliriz.
   Hill Climbing yöntemden bahsedersek:


 İlk olarak başlangıç çözümü üretilir ve bu çözüm eniyi çözüm olarak kabul edilir. (Bu çözümün üretimi probleme göre rastgele olabileceği gibi problem konusunda uzman görüşü veya daha önce yapılmış çalışmalar yardımıyla da olabilir.)

   Daha sonra bu probleme komşu bir çözüm kümesi üretilir.(Değişik sayıda olabilir.) Çözüm kümesi elemanları değerlendirilir. Çözüm kümesinin en iyi elemanı eğer bir önceki adımdaki eniyi çözümden daha iyi ise, eniyi çözüm güncellenir. Sonrasında en iyi çözüme göre yeni komşular üretilir ve iteratif olarak devam edilir. Belirli iterasyon sayısına ulaşıldığında, yeterli bir çözüm elde edildiğinde veya artık çözümler değişmediğinde iterasyon sonlandırılır.

 Hill Climbing yöntemini kullanarak derste geçen bir basit problem için C++ uygulama kodu hazırladım. Problem: bd 30 karakterlik bir binary dizisi olmak üzere f(bd) = |20 * dizideki_bir_sayisi(bd) - 100| fonksiyonunu max yapan bd değeri? (Problemimizin çözümünün "111111111111111111111111111111" olduğu rahatça görülüyor.)

Bu yazının hazırlanmasında hocam Doç.Dr. M.Ali Akcayol' un Zeki Optimizasyon Teknikleri Dersi ders notları kullanılmıştır.


Kod

1 yorum - yorum yaz:

software dedi ki...

mrb hocam benim iyileşrirme hakkında odevim yardımcı olursanız sevinirim

Bir kenar uzunlugu n^2 (n kare anlamında) birim olan eşkenar üçgen biçimindeki bir ülkenin her bir sınır dogrusu üzerinde işaretli n-1 nokta ile n eşit parçaya bolunmustur. Sınır dogrularından birisine paralel olmak kosuluyla bu işaret noktalarının ikisini birleştiren tüm dogru parçaları çizilerek her kenarı birim uzunlukta eşkenar üçgen olan n^2 şehri tanımlanmıştır. Ülkenin önde gelen bilgisayar üreticilerinden olan bir kuruluş bazı şehirlere depo kurmayı planlamaktadır. Ulaşım maliyetlerinin yüksekliği nedeniyle kurulan her depodan sadece bulundugu sehre ve ona komsu olan (ortak bir sınır çizgisi bulunan) şehirlere dagıtım yapılabilmektedir. Tüm ülkeye dagıtım yapmayı planlayan kurulusun en az kaç şehirde depo kurarak bu amacına ulaşabilecegini bulunuz.

Yorum Gönder