Jump to content
Üyelik kaydınızı yaparak son yazılan içeriklerden haberdar olun! ×
  • entries
    55
  • comments
    2
  • views
    435,728

Simulated Annealing (SA)


Doğuhan ELMA

217 views

Simulated Annealing (SA), optimizasyon problemlerinin çözümü için kullanılan bir probabilistik tekniğe dayanan bir algoritmadır. Simulated annealing, adını malzemeler bilimindeki bir süreç olan tavlama işleminden alır. Tavlama, bir metali ısıtarak ve daha sonra yavaşça soğutarak, metali daha düşük enerji durumuna getiren ve böylece malzemenin iç yapısını iyileştiren bir süreçtir.

Bu algoritmanın temel prensipleri şunlardır:

1. İnitializasyon: Başlangıçta, algoritma rastgele bir çözümle başlar ve bir başlangıç sıcaklığı belirlenir.

2. Komşuluk: Mevcut çözümün bir komşusu, genellikle rastgele bir şekilde küçük bir değişiklikle oluşturulur.

3. Yeni Çözümün Kabulü veya Reddi: Eğer komşu çözüm mevcut çözümden daha iyiyse, bu yeni çözüm kabul edilir. Ancak, daha kötü bir çözüm de belirli bir olasılıkla kabul edilebilir. Bu olasılık, komşu ve mevcut çözümler arasındaki farka ve mevcut sıcaklığa bağlıdır. Bu, algoritmanın yerel optimumları aşmasına ve genel bir optimuma ulaşmasına yardımcı olur.

4. Soğutma: Her iterasyonda, sıcaklık soğutma oranı ile azaltılır. Sıcaklığın azaltılması, zamanla daha kötü çözümlerin kabul olasılığını azaltır ve algoritmanın optimal bir çözüme yakınsamasını sağlar.

5. Durma Kriteri: Algoritma, belirli bir durma kriteri karşılandığında sona erer. Bu genellikle belirli bir sayıda iterasyon gerçekleştikten veya sıcaklığın belirli bir eşik değerinin altına düştüğünde olur.

Simulated Annealing, genel olarak karmaşık ve yüksek boyutlu optimizasyon problemlerinde kullanılır ve genellikle yerel optimumlardan kaçınmak ve genel optimuma ulaşmak için etkilidir. Ancak, uygulamada, soğutma programının (sıcaklık azaltma hızı ve durma kriteri) ayarlanması genellikle dikkatli bir ayarlama gerektirir.
 

Kod:

import random
import math

# Çözümlemek istediğimiz problem (burada bir hedef sayıya en yakın sayıyı bulmak istiyoruz)
def problem(x):
    hedef = 20
    return abs(x - hedef)

# Başlangıç durumunu ve başlangıç sıcaklığını belirleyin
x = 0
T = 100

# Sıcaklık 0 olana kadar döngüyü çalıştır
while T > 1e-3:
    # Yeni bir komşu çözüm oluşturun
    x_komsu = x + random.uniform(-1, 1)

    # Yeni çözümle mevcut çözüm arasındaki farkı hesaplayın
    fark = problem(x_komsu) - problem(x)

    # Eğer yeni çözüm daha iyiyse, kabul edin
    # Eğer yeni çözüm daha kötüyse, belirli bir olasılıkla kabul edin
    if fark < 0 or random.random() < math.exp(-fark / T):
        x = x_komsu

    # Sıcaklığı azalt
    T *= 0.99

print("En iyi bulunan değer:", x)

Bu örnekte, hedef sayıya en yakın olan sayıyı bulmaya çalışıyoruz. Her iterasyonda, mevcut durumun bir komşusunu (mevcut durumdan biraz farklı bir durumu) rastgele olarak seçiyoruz. Eğer komşu çözüm daha iyiyse (yani hedef sayıya daha yakınsa), kabul ediyoruz. Eğer komşu çözüm daha kötüyse (yani hedef sayıdan daha uzaksa), belirli bir olasılıkla kabul ediyoruz. Bu olasılık, çözümün ne kadar kötü olduğuna ve mevcut sıcaklığa bağlıdır.

Algoritma, sıcaklık 0 olana kadar (veya yeterince küçük bir değere düşene kadar) bu işlemi tekrar eder. En sonunda, en iyi bulunan değeri yazdırırız.

Not:

`T > 1e-3:` ifadesi, Simulated Annealing (Simüle Tavlama) algoritmasının döngüsünün ne zaman sona ereceğini belirler. Burada `T` sıcaklığı temsil eder ve `1e-3` ise belirlenen bir eşik değeridir.

`1e-3` ifadesi, matematiksel olarak 0.001 sayısını ifade eder. Bu, `1 * 10^-3` veya "1 çarpı 10'ün negatif üçüncü kuvveti" anlamına gelir.

Bu durumda, `T > 1e-3:` ifadesi "sıcaklık 0.001'den büyük olduğu sürece döngüyü devam ettir" anlamına gelir. Yani sıcaklık 0.001 değerine düştüğünde veya bu değerin altına indiğinde döngü sona erer.

Bu, Simulated Annealing algoritmasının temel bir parçasıdır. Başlangıçta, sıcaklık yüksektir ve bu, algoritmanın daha kötü çözümleri kabul etme olasılığını artırır. Ancak zamanla sıcaklık azaltılır ve bu, algoritmanın zamanla daha az kötü çözüm kabul etmesini sağlar. Bu süreç, algoritmanın genel optimuma doğru yakınsamasına yardımcı olur. Bu nedenle, sıcaklık değeri genellikle başlangıçta yüksek bir değere ayarlanır ve her iterasyonda bir miktar azaltılır.

0 Comments


Recommended Comments

There are no comments to display.

Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  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...