Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde, özellikle hesaplama alanında kullanılan algoritmalardan birisidir. İsmini demir tavlamak veya demiri ısıtmak anlamına gelen annealing (tavlama) kelimesinden almıştır. Algoritmanın amacı, herhangi bir problem için genel iyileştirme (global optimization) elde etmektir. Diğer bir deyişle, herhangi bir fonksiyonun ya da ölçümün genel minimum veya maksimum (global minimum) elde etmek olarak düşünülebilir.

1. Simulated annealing (benzetilmiş tavlama) nerede işe yarar?

Genellikle hesaplamalı bilimlerde bir deneyin yada nümerik sonuçların anlık değerleri elde edilir. Örneğin aşağıdaki grafiği ele alalım:

Yukarıdaki şekil herhangi bir indis değerlerine sahip fonksiyon olabilir. Yukarıdaki 2 boyutlu grafiğin indisleri yada formüllendirilmesi ile ilgilenmeden grafiğin en küçük olduğu değeri bulmaya konsantre olalım. Şayet yukarıdaki grafiği veren bir formül elimizde varsa, bu formülün üzerinde çeşitli matematiksel yöntemler uygulayarak (örneğin türev alarak) bir sonuç elde edebiliriz. Ancak yukarıdaki grafiği veren bir formülümüzün olmadığını ve yukarıdaki değerleri ancak belirli aralıklarla yapılan ölçümler sonucu elde ettiğimizi düşünelim.

Örneğin yukarıdaki noktalar ile gösterilen değerlerin ölçüldüğü ayrık bir (discrete) sistemimiz olduğunu düşünelim. Bu duruma yapay zeka problemlerinde sezgisel sonuçların (heuristic) elde edildiği problemlerde veya gerçek hayattaki farklı zamanlarda yapılan ölçümlerde sıkça rastlanır. Benzer bir durum olarak ölçme maliyetinin yüksek olduğunu da kabul edilebilir. Örneğin her ölçümün yüksek maliyet getirdiği ve dolayısıyla kısıtlı sayıda ölçüm yaparak en düşük değeri bulacağımız x ekseni değerini aradığımızı düşünelim.

İşet yukarıdaki 2 boyutlu grafikte kullanılabilecek benzetimli tavlama (simulated annealing) algoritması, matematiksel olarak bir fonksiyonla modellenemeyen, nümerik ve ayrık uygulamalarda kullanılabilir. Ayrıca problemin kaç boyutlu olduğunun da bir önemi yoktur. Örneğin 3, 4 veya daha fazla boyutlu problemlerde de kolaylıkla uygulanabilir.

2. simulated annealing (benzetilmiş tavlama) nasıl çalışır?

Algoritmanın çalışması aslında isminin de geldiği demir tavlama işlemine benzer. Yani nasıl demir tavlama işlemi sırasında bir demir parçayı ısıtıp sonra soğumaya bırakıyorsak, herhangi bir sayısal ölçüme de benzeri yaklaşım uygulanabilir.

Şayet demir tavlama problemini, demiri oluşturan ufak hücrelerin ısınması ve soğuması olarak düşünecek olursak, ki bu hücreler daha sonra problemimizin örneklendiği her bir deney veya nümerik sonuç olarak modellenecektir, hücreler arası geçiş ve hücrelerin zamana bağlı değerlerini elde etmek mümkündür.

Amacımız genel bir minimum noktası bulmak olduğuna göre, problemin farklı zamanlardaki sonuçlarını ele alıp bu sonuçlardan iyi olanına doğru hareket etmemiz gerekir. Örneğin s durumu ve s’ durumları arasından, P(e,e’,T) olasılık değerine göre seçim yapılır. Buradaki e= E(s) ve e’=E(s’) olarak hesaplanan s ve s’ için enerji değerleridir. Yani grafikteki karşılık değerleri veya deneyimizin sonuç değerleri olarak düşünülebilir. T değeri ise ısı olarak geçer ki bunu da deneydeki ölçüm zamanları olarak kabul etmek mümkündür.

Kısacası P(e,e’,T) değeri bir olasılık sonucu çıkarır. Bu sonuç bize s durumundan s’ durumuna geçişin ne kadar kabul edilebilir olduğunu olasılıksal olarak verir.

Burada daha basit bir açıklama olarak şöyle düşünebiliriz. Şayet e’ değeri, e değerinden yüksekse, yani yeni durumumuzdaki enerji daha yüksek bir enerjiyse, sistem soğumuyor ısınıyor demektir. Bu ise sistemin daha kötüye gittiğinin bir işaretidir ve doğal olarak kabul edilir bir durum değildir.

Ancak sistemin hep iyiye gitmesi hiç kötüye gitmemesini istememiz durumunda yerel minimumla (local minimum) karşılaşırız. Örneğin yukarıda temsili resmi verilen şekli hatırlayalım:

Yukarıdaki şekilde düşey ekseni enerji olarak kabul edersek, soldaki okun gösterdiği değer soğuma olarak düşünülebilir. Yani farklı durumlar için enerji değerleri azalmıştır. İkinci okta ise enerji değerleri artmış yani elde edilen durumlarda ısınma olmuştur. Şimdi yukarıdaki örnek için, şayet ısınan durumları, yani okun yukarı yönlü olduğu durumları kabul etmez ve grafikte sağa doğru hareket etmezsek 1 numaralı çukurda takılıp kalma ihtimali olur. Bu durumda sistemimiz hiçbir zaman, daha iyi sonuçlar olan 2 ve 3 numaralı çukurlara ulaşamayabilir.

Bu yazı şadi evren şeker tarafından yazılmış ve bilgisayarkavramlari.com sitesinde yayınlanmıştır. Bu içeriğin kopyalanması veya farklı bir sitede yayınlanması hırsızlıktır ve telif hakları yasası gereği suçtur.

Bu şekilde elde edilen sonuçlara yerel minimum (local minimum) ismi verilir ve algoritmamızın yukarıda açıklanan şekilde davranması durumuna açgözlü yaklaşımı (greedy approach) ismi verilir. Kısaca ilk bulduğu minimum değerine atlayan ve dolayısıyla sistemdeki daha düşük minimum değerleri bulamayan algoritma haline gelir. (açgözlülük insanı kör ettiği gibi algoritmaları da kör eder)

Bu duruma çözüm olarak e’-e değerindeki değişimler gözlenir. Bu değerler arasındaki değişimlerin artması, bu değerleri üreten s ve s’ durumlarının kabulünü zorlaştırır. Ancak iki durumda ölçülen enerji değerlerinin birbirine çok yaklaşması durumunda sistem kabul edilir. Bu sayede sistemin yükseldiği durumlarda da sistem dolaşmaya devam eder ancak enerji değerlerinin birbirine iyice yaklaşması sonucunda minimum değerler bulunmuş olunur.

3. Simulated annealing’in kodlanması

Yukarıdaki tanımı müsvedde kod olarak yazalım:

Yukarıdaki kod, görüldüğü üzere komşu durumlar üzerinde hareket ederek (yada olasılık durumuna göre etmeyerek) en iyi sonucu bulmaya çalışır.

Yukarıdaki kodun diğer bir özelliği ise sezgi üstü yaklaşımlar için kullanışlı olmasıdır. Dikkat edilirse, algoritmanın taradığı bütün durumlar s ve s’ durumları olarak geçmekte ve dilenirse kaydedilebilmektedir. Bu durum normal bir soğuma sürecinden farklı olarak (gerçek hayatta herhangi bir t anında sadece bir durum vardır) çok durumu tutabilme imkanı sunar.

Ayrıca yukarıdaki algoritmada yapılacak deneme sayısı kodun 7. Satırındaki döngü ile limitlenebilmektedir. Dolayısıyla bir kişi en iyi ama en maliyetli çözüm için bu MAX değerini arttırabilir. Elbette en iyi çözüm demek daha çok deneme demek ve bu da yüksek maliyet demektir. Maliyetin düşürülmesi için deneme sayısının kısılması ise, en iyi genel sonucun bulunamaması ihtimalini yükseltir. Elbette şanslıysak ve genel minimum f(0) değeriyse hiç deneme yapmamıza da gerek yoktur J

Benzetilmiş tavlama yönteminin ( simulated annealing), bir özelliği de, aynı problem için birden fazla çözümü olmasıdır. Bunun sebebi yukarıdaki kodda da belirsiz olarak bırakılan, komsu(), P(), T() fonksiyonlarının (functions) problemin çözümündeki seçilme şeklidir. Yani aynı problemi iki farklı bilgisayar bilimcisi iki farklı komşuluk fonksiyonu, ısı değeri ve olasılık değerine göre çözebilir. Burada probleme özgü olarak modelleme yapmak ve problemin karakteristiğinin doğru analiz edilmesi önem taşır.

439 views