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

🔎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)  

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

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].Probability Formula

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

Table1

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

First Five İteration

                                                                              Objective değerler tablosu

Visual                                                                         Objective değerlerin grafikselleştirilmesi

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

Table3

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

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

Table5

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

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

                                                     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)”, http://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.

                                                                                              Olasılık formülü

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

Algoritmanın Akış Şeması 🖋️Flowchart

                                                   Benzetimli Tavlama Algoritması Akış Diyagramı

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

Solution1                                                                  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]

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 👩🏻‍🏫

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 👍

Objective Function                                                              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 ⚡

Swap method

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

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

Table1

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

First Five İteration

                                                                              Objective değerler tablosu

Visual                                                                         Objective değerlerin grafikselleştirilmesi

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

Table3

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

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

Table5

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

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

                                                     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)”, http://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