Zeki Optimizasyon Teknikleri - 2 (Tavlama Benzetimi)

        Optimizasyon algoritmalarımızdan ikincisi Simulated Annealing olarak ta bilinen tavlama benzetimi algoritması. İsmi Metalurji biliminden gelmektedir. Metallerin tavlanması işleminden esinlenerek ortaya çıktığı için bu ismi almıştır. Genellikle ayrık optimizasyon problemleri için kullanılır.

    Yöntemden kabaca bahsetmek için  Hill Climbing yöntemimizi hatırlayalım. Hill-Climbing yönteminde ilk çözüm üretmiş, bir komşu üreteci fonksiyonu ile ilk çözümümüze komşu olan yeni bir çözüm kümesi üretmiştik.*Bu yeni kümeyi kendi içerisinde değerlendirip en iyi elemanını seçmiştik. Eğer bu seçtiğimiz en iyi eleman bizim eski çözümümüzden daha iyi bir çözümse yeni çözümümüz olarak bu değeri kabul etmiştik. Ayrıca Hill-Climbing yönteminin kolay uygulanmasının yanında  kötü bir özelliği olarak local çözümlere takılma olarak belirtmiştik.
     Algoritmanın bu lokal çözümlere takılmasının nedeni bulduğumuz bir eğim doğrultusunda ilerlememiz, bu yönde çözümleri kısıtlamamızdır. Lokal çözüme doğru hızla ilerlerken çözüm kümesinin diğer kısımlarını göz ardı ederiz. Eğer şans eseri ilk çözüm üretecimiz başlangıç çözümünü global çözüme yakın bir bölgede üretirse muhtemelen global çözüme ulaşırız. Bundandır ki, Hill Climbing algoritması başlangıç noktasına çok bağımlıdır demiştik.

    Hill Climbing algoritmamız üzerine bir takım modifikasyonlar yaptığımızı düşünelim. Yine ilk çözüm üretecimiz bir çözüm oluştursun, komşu çözüm üretecimiz komşu çözümler kümesini oluştursun, yine üretilen komşu çözüm kümesini kendi içerisinde değerlendirerek buradan en iyi çözümü seçelim. Klasik Hill Climbing algoritmamızda komşu çözüm kümesinden seçilen en iyi çözüm eğer eski çözümümüzden daha kötü ise bu değeri kullanmayıp elimizdeki çözümü saklıyorduk. Şimdi biraz daha insaflı davranıp komşu kümeden seçilen kötü çözüme bir şans verelim. Bu şans P olsun. Belkide verdiğimiz bu şans hatırına kötü çözüm bizi komşusu olan daha iyi çözümlere götürebilir. Hem böylece Hill-Climbing in local çözümlere takılıp kalma özelliğinden kurtulabiliriz. Eğer kötü çözümlere verdiğimiz seçilme şansı(olasılığı) P çalışma boyunca sabit kalırsa bu sefer tam güzel çözümlere doğru ilerlerken oradan oraya oradan oraya atlarız. Bu nedenle bu P olasılığının(iyi çözümü feda ederek yerine kötü çözümü kabul etme olasılığı)  dinamik olması gereklidir. Bu dinamiklik iterasyonla P nin azaltılması şeklinde(ve daha pek çok şekilde) yapılablir. Böylece problem çözümünün ilk kısımlarında çözüm bölgeleri arasında sıçrayış daha fazla olurken iterasyon sayımız artıp elde ettiğimiz çözümler  iyice güzelleştikçe 0 a yaklaşır. (Arama bölgemiz daralır.)

    İşte yukarıda modifiye edilmiş bir Hill-Climbing algoritması gördük. Tavlama Benzetimi algoritmasının temel prensibi tam olarak budur. Kötü çözümü seçme olasılığı sistemli bir şekilde sıcaklıkla azaltılır. Sıcaklık iterasyona bağlı(genellikle düzgün veya logaritmik azalan) bir ifadedir.

Tavlama benzetimi algoritmasının temel amacı çözüm uzayında aranmadık bölge bırakmamaktır.

 Ayrıca Tavlama Benzetimi algoritmasında komşu çözüm kümesinin büyüklüğüde dinamik şekilde değiştirilebilir. (Probleme göre değişse de genel olarak çözümü çok fazla etkilememektedir) Bu şekilde bir kullanım benimsenirse yaygın kullanım küçük bir kümeyle başlayıp iterasyonla büyütmek şeklinde olur.

Sıcaklığın azaltılması, olasılık değerinin sıcaklıkla azaltılması, çözüm kümesinin değiştirilmesi için pek çok yöntem kullanılır.
    Bunlara girmeden basit bir problemi tavlama benzetimi algoritması ile çözelim. Aşağıda C++ kodu çözüm olarak string şeklinde "VOLKANSALMA@BLOGSPOT@COM" dizisini oluşturmaya çalışmaktadır.
   Örnek bu sitedeki genetik algoritma ile Hello! World yazısını oluşturma probleminden esinlenilmiştir. Çözümün kalitesini değerlendirmek için gerekli fonksiyon (Fitness function) linki verilen siteden direk alınmıştır. .

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

*Hill-Climbing için yazmış olduğum C++  kod örneğinde bir yanlışlık yaptığımın farkına vardım. Aslında çözüm kümesi kendi içerisinde değerlendirilip en iyi eleman seçilmesi gerekirken, ben ilk bulduğum iyi çözüm ile mevcut çözümü değiştirdim. Sonrada diğer iterasyona geçtim. Bu yanlışlık daha güzel çözümleri kullanamamıza neden oldu. Böyle bir hata çözüme yakınsama hızımızı düşürür.

Programın şu şekilde bir çıktısı oluyor: (Yıldızlarla gösterilen bölgelerde bulunan çözüm daha kötü olmasına rağmen olasılık değerlendirmesini geçmiş, çözüm olarak seçilmiştir. )

Kod
Output