Simulated Annealing Algorithm ( Benzetilmiş Tavlama Algoritması)

Simulated Annealing Algorithm

( Benzetilmiş Tavlama Algoritması)

Benzetim tavlama algoritmasını anlamak için öncelikle Tepe Tırmanma algoritmasına  (Hill climbing Algortihm) bakmamız gerekir.

Tepe Tırmanma Algoritması

Tepe tırmanma algoritması, iki boyutlu bir grafikte tarif edecek olursak aradığımız sonuca daha yakın olan yöne ilerleme mantığı ile çalışan bir optimizasyon algoritmasıdır.

ezgif.com-video-to-gif (1)

Rastgele bir başlangıç noktası ile komşu değerler (noktalar) değerlendiriliyor.Aradğımız Global maximum noktası ise komşu değerlerden yüksek olan tarafa doğru bir tırmanış başlıyor. Her iki komşunun da mevut olan değerimizden daha düşük  olduğu durumlarda maximum noktaya ulaşmış bulunuyoruz. Fakat bu nokta global yani tüm değerler için maximum olabileceği gibi local (yerel) maximum da olabilir.

Yukarıdaki resimde görüldüğü üzere bu algoritma ile çalışırken yerel maximum noktalarına takılma olasılığımız yüksektir.

Benzetilmiş Tavlama Algoritması

Yerel noktalardan kurtulabilmek için çeşitli yöntemler geliştirilmiştir.Bu yöntemlerden biri ise BT algoritmasıdır. BT algoritması, katıların fiziksel tavlama işlemi il optimizasyon problemlerinin çözümü arasındaki benzerlik ilişkisi üzerine dayalıdır.

qwed-1

BT Algoritmasının Grafik Üzerinde Gösterimi

Belirli aralıkta global max. noktasını  aradığımız fonksiyon = f(x)= x+10*sin(5*x)+7*cos(4*x)+sin(x)

ginput(1);
valueFunction = @(x) value(x);
figure(1);
grid on;
x=5:0.01:10;
plot(x,valueFunction(x))
Temp=1000;
best_Cost = 0;
best_Val = 0;
 
 
 
for T=1:100
 
 
    Rand_Val = randi([5 9])+rand;
    cost_Val(T) = valueFunction(Rand_Val);
 
    if cost_Val(T) > best_Cost
        best_Cost = cost_Val(T);
        best_Val = Rand_Val;
 
    elseif exp((cost_Val(T)-best_Cost)/Temp) > rand
        best_Cost = cost_Val(T);
        best_Val = Rand_Val;
    end
 
 
 
 
 
 
    hold on;
    h(T)=plot(best_Val, best_Cost, 'r*','MarkerSize',20);
    title(['Temperature = ' num2str(Temp) '  BestCost =' num2str(best_Cost) '  BestValue = ' num2str(best_Val) '  It' num2str(T)])
     pause(0.2)
     delete(h(T)) 
 
    Temp = Temp/log(100);
 
 
end

 

Daha Detaylı Bilgiler için Bağlantılar:

Tavlama Benzetimi Algoritması/Fırat Üniversitesi

Simulated Annealing (Benzetilmiş Tavlama)/sadievrenseker.com

Tepe Tırmanma Algoritması (Hill Climbing Algorithm)/.sadievrenseker.com

http://www.cse.iitm.ac.in/~vplab/courses/optimization/SA_SEL_SLIDES.pdf

http://dergipark.org.tr/erciyesfen/issue/25602/270171

https://www.amazon.com/Algorithm-Collections-Digital-Processing-Applications/dp/9048176301

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

This site uses Akismet to reduce spam. Learn how your comment data is processed.