Benzetimli Tavlama (Simulated Annealing) Algoritması

BENZETİMLİ TAVLAMA ALGORİTMASI

Herkese merhabalar, optimize kelimesi aslında günlük hayatta çok sık karşımıza çıkan bir kelimedir. Takdir edersiniz ki optimizasyon kelimesi aslında bir olayın, problemin veya bir durumun içerisindeki olasılıklardan mümkün olan en iyiyi seçmesi durumudur 📈.

Genel bir minimum noktası bulmak amacı ile problemin farklı zamanlarındaki sonuçlarını elde ederek bu sonuçlardan iyi olan değere doğru hareket edip birden fazla çözümü test ederek en iyi sonucu bulmaya yardımcı olan yöntem olan Simulated Annealing (Benzetimli Tavlama) yöntemi de bir optimizasyon problemi çözüm yöntemidir [1].

[gdlr_core_space height=”30px”]

🔎Simulated Annealing Algoritması Hakkında

Benzetimli tavlama (Simulated Annealing) yöntemi, ayrık ve daha az ölçüdeki sürekli optimizasyon problemlerini ele almak için kullanılan popüler bir metasezgisel yerel arama yöntemidir.

Benzetimli tavlama algoritmasının temel özelliği, küresel bir optimum bulma umudu ile tepe tırmanma hareketlerine (amaç fonksiyon değerini kötüleştiren hareketlere) izin vererek yerel optimumdan kaçma aracı sağlamasıdır [2].

Algoritmaya tavlama ismi verilmesinin sebebi, demircilerin demiri döverken belirli bir dereceye kadar ısıl işlemden geçirmesi sonucu demirin istenilen kıvama gelmesini esas almasından kaynaklanmaktadır. Aynı mantık ile bir problem ele alınarak tavlama derecesi ile ısıtma sürecinden geçiriliyor ve ardından istenilen noktaya geldiğinde sonuca ulaştığı kabul ediliyor. (Local Objective Function)  

Demirin ısıl işlemden geçirilerek tavlanması [3]

[gdlr_core_space height=”30px”]

Amaç fonksiyonunda Δ kadar bir yükselmeye yol açan hareketin kabul edilme olasılığını veren fonksiyon kabul (accept) fonksiyonu olarak adlandırılır [4].

Olasılık formülü

[gdlr_core_space height=”30px”]

Sıcaklık yüksek olduğunda, amaç fonksiyonunda artışa neden olabilecek hareketlerin kabul edilme olasılığı çok yüksek olacak, sıcaklık düştükçe bu olasılık da azalacaktır. Bu sebeple, aramaya yeteri kadar yüksek bir sıcaklık değeri ile başlamak gereklidir [4]. Ben çalıştığım projede kullanılacak başlangıç sıcaklık değerini T= 100000 olarak belirledim 🌡️.

Algoritmada, sıcaklık yavaş yavaş azaltılırken her sıcaklık değerinde belli sayıda hareket deneyerek arama işlemi sürdürülmektedir [4].

[gdlr_core_space height=”30px”]

Algoritmanın Akış Şeması 🖋️

Benzetimli Tavlama Algoritması Akış Diyagramı

[gdlr_core_space height=”30px”]

Algoritmanın Çalışma Prensibi 🔨

Benzetimli algoritmanın çalışma mantığında en önemli işlem, sıcaklığın zamanla soğutulması gerektiğidir. Çünkü başlangıç sıcaklığı zamanla azalmazsa enerji sürekli yüksek kalacak ve yüksek orandaki entropi ile tüm ağacın aranması sağlanacaktır, bu istenmeyen bir durumdur.

Algoritmada soğuma işlemi gerçekleştirilene kadar her çözümde enerji seviyeleri karşılaştırılır. Enerji değişimi hesaplanmasında pos’ olarak olası bir yapılandırmadan mevcut yapılandırma farkından faydalanılır [5].

Enerji değişimi hesaplanması [5]

Daha sonra kabul edilecek pozisyonun hesaplanması için Şekil 4’ de görüldüğü gibi bir hesaplama olasılığı sunulmuştur. Boltzmann sabiti olan k değeri göz ardı edilerek denklem sadeleştirilmiştir. Bu sayede yeni aday çözümün hesaplanmasına imkân sunulmuştur.

Yeni aday çözümün olasılık hesabı [5]

[gdlr_core_space height=”30px”]

Bu durumlarda T sıcaklığı ise yinelenen belirli bir aralıkta sıcaklığını azaltmaya devam etmektedir. Bu projede kullanılan veri seti ‘gr137.tsp’ olarak seçilmiştir.

Bu veri seti TSP alt yapısı ile çalışmakta ve gezgin satıcı problemlerini baz almaktadır. Bu veri seti Amerika alt yapısındaki 666 tane şehir problemi için bilgi içermekte ve içerik boyutunda 137 tane X ve Y koordinatları verilmektedir.

Benzetimli tavlama yönteminde çalıştırılan düğümleri öncelikle swap yöntemi ile değiştirerek karşılaştıracağız ve en iyi sonucu elde etmeye çalışacağız 👩🏻‍🏫

Koordinatların yer aldığı “gr137.tsp” dosyasından ön izleme

[gdlr_core_space height=”30px”]

Amaç fonksiyonu olarak gösterilen Objective Function ’da karşılaştırılacak düğümlerin mesafelerini aşağıdaki gibi hesaplayacağız. Burada hesaplanacak mesafeyi ise öklid mesafesi olarak alacağız 📏

Optimizasyon algoritmalarında çok sık kullanılan bir dil olan Python dilinde kodlamaya devam edeceğiz. Haydi birlikte amaç fonksiyonunu öklid mesafesi baz alarak yazalım 👍

[gdlr_core_space height=”30px”]

Amaç fonksiyonu mesafe hesaplanması

Swap Yöntemi ile Hesaplama 🧮

Şekil 8’ de görüldüğü üzere N ile gösterilen değer koordinatların boyutunu ifade etmektedir. N boyutunda rastgele değerler üreterek swap1 ve swap2 değişkenlerine atayacağız. 

Kontrol edilecek iki değer birbiri ile aynı ise yeni olasılık değeri oluşturmak üzere swap2 olasılığı yeniden değer oluşturacak demektir. Bu veri setinde p ile ifade edilen değer bir bakıma Id sütununa denk gelmektedir. 

Üzerinde değişiklik yapılmaması için copy( ) fonksiyonu ile değerler kopyalanmaktadır. Her aşamada enerji hesaplaması yapılmasının sebebi, Simulated Annealing algoritma mantığındaki sıcaklık ( temperature ) değerinin belirli bir değere kadar ısıtılması ve sonra cooling factor denilen soğuma faktörü ile belirli bir seviyeye kadar soğutulması gerektiğinden kaynaklanmaktadır.

Benzetimli tavlama örneğindeki ısınma sürecinde içerisindeki partiküllerin hareketliliğinden dolayı enerji yükselmesi olacaktır ve enerji hesabı her süreçte yapılarak yüksek enerjiye sahip olup olmadığı kontrol edilmek istenmektedir ⚡

[gdlr_core_space height=”30px”]

Swap yöntemi ile hesaplama

Algoritmada kullanılan bu yöntemde sıra ile (order) işlem yapılmakta olduğundan rastgele değerler üzerinde hesaplama yöntemine gidemez böylelikle doğru sonuçlara diğer arama operatörlerinin kullanımı ile gidilmesi zaman açısından da çok önem arz etmektedir.

Değerler arasında swap değişim yöntemi

Veri Seti Optimal En iyi En kötü Ortalama Standart Sapma
gr137.tsp 69853 854.7855305691671 868.838856972194 863.77245981144 3.9530597090364

İterasyon çıktılarındaki ilk çözüm ve elde edilen en iyi çözüm değerleri ise sırasıyla aşağıda gösterilmektedir. Optimum değerleri ulaşmayı hedefleyerek 10 iterasyon boyunca ilk çözüm ve son çözüm değerlerini elde edeceğiz.

Objective değerler tablosu

Objective değerlerin grafikselleştirilmesi

[gdlr_core_space height=”30px”]

Örneğin 5.iterasyon çalıştırılırken değer değişimlerini gözlemlemek amacı ile hesaplama sırasında farklı zamanlarda alınan sonuçlar aşağıda gösterilmiştir. Böylelikle swap işlemi mantığını ve bu süreçteki enerji değişimleri (ΔE) gözle görülebilmektedir.

Swap işlemi devam ederken enerji değerlerinin gösterilmesi

5 ve 102 nolu bağdaki hesaplamaya bağlı result değerleri

113 ve 127 bağındaki hesaplamaya bağlı olarak result değerleri

[gdlr_core_space height=”30px”]

🔎 2-OPT ALGORİTMASININ SA ÜZERİNDE UYGULANMASI

2-opt algoritması, GSP problemlerinin çözümüne yönelik, muhtemelen en temel ve çok geniş kullanım alanına sahip bir algoritmadır [6]. Temel olarak tur içerisindeki iki kenarın silinmesi ve iki parçaya ayrılan turun maliyetleri düşürecek şekilde, farklı olarak bağlanması şeklinde tanımlanabilir (Gutin ve Punnen, 2002).

✔️Benzetimli tavlamanın swap yönteminde iki değer birbiri ile kontrol edilmekte ve olasılık değerine göre hafızaya alınmaktadır. Fakat tüm işlemler sırası ile yapılacağından çalışma zamanı açısından çok verimli olmayacaktır.

✔️2opt algoritması ile örneğin tour olarak adlandırılan indis değerlerinde (initial_p) 4. düğümden sonra 17. düğüme geçiş yapmakta olduğu görülmektedir. 2opt algoritması devreye 4 ve 5. düğümler arasındaki bağı kırıp d ile 17 düğümleri arasındaki bağı oluşturmakta girer. Böylelikle çalışma zamanı daha verimli sonuçlar üretir.      

[gdlr_core_space height=”30px”]

Tour bağlantısındaki farklı değerlerin bağlanması

two_opt_python fonksiyonunda şehirlerdeki indis değerleri 2 artırımlı olarak kontrol edilerek değişimi vermektedir. Tour üzerindeki yolda herhangi bir değişim yaşandıysa bu değişim tour değişkenine atanmaktadır. dist( ) fonksiyonu sonucunda iki şehir arasındaki ( 4-17 gibi) Öklid uzaklığı hesaplatılarak tour içerisindeki koordinatlar döndürülmektedir. Bu sayede en iyi çözüm üzerinde iyileştirme sağlanmaktadır ⭐

REFERANSLAR

[1] Sadi Evren Şeker, Bilgisayar Kavramları, “Simulated Annealing (Benzetilmiş Tavlama)”, https://bilgisayarkavramlari.sadievrenseker.com/2009/11/23/simulated-annealing-benzetilmis-tavlama/ adresinden alınmıştır.

 [2] Darrall Henderson, Sheldon H Jacobson, Alan W. Johnson, The Theory and Practice of Simulated Annealing, April 2006.          

 [3] Orhan Baylan, “ISIL İŞLEM NEDİR? ÇELİĞE NİÇİN ISIL İŞLEM YAPILIR?”, https://www.metaluzmani.com/isil-islem-nedir-celige-nicin-isil-islem-yapilir/ adresinden alınmıştır.     

 [4] Tavlama Benzetimi Algoritması (Simulated Annealing), BMÜ-579 Benzetim ve Modelleme, Yrd. Doç. Dr. İlhan AYDIN.

[5] Hefei University, Thomas Weise, Metaheuristic Optimization, 7. Simulated Annealing.

[6] Timur KESKİNTÜRK, Barış KİREMİTCİ, Serap KİREMİTCİ, 2-OPT Algoritması ve Başlangıç Çözümünün Algoritma Sonuçları Üzerindeki Etkisi, 2016.

Leave a Reply

Your email address will not be published. Required fields are marked *