Tavlama Benzetimi ve Tabu Arama Algoritmaları ile Gezgin Satıcı Problemi (C#)

Gezgin Satıcı Problemi

GSP, n adet şehir arasındaki mesafelerin bilindiği durumda, şehirlerin her birine yalnız bir kez uğramak şartıyla, başlangıç noktasına geri dönülmesi esasına dayalı, tur boyunca kat edilen toplam yolun en kısa olduğu şehir sıralamasının (optimal rota) bulunmasının amaçlandığı bir problemdir. Dağıtım, rotalama, kuruluş yeri belirleme, planlama, lojistik gibi problemlerde geniş bir uygulama alanına sahip olan gezgin satıcı problemi, aynı zamanda optimizasyon alanında, araştırmacılar tarafından üzerinde uzun yıllardır çalışmalar yapılan NP-hard (çözümü zor) sınıfında yer alan bir problemdir.

Tavlama Benzetimi Algoritması (TB)

TB algoritması, ilk olarak 1983 yılında Kirkpatrick, Gelatt ve Vecchi tarafından sunulmuş olup, optimizasyon problemlerinin çözümü için geliştirilmiş bir yerel arama algoritmasıdır.

TB algoritması adını erimiş metalin soğutulması işlemi olan, tavlama işleminden almaktadır. Bu işlemde metalik yapıdaki kusurları azaltmak için bir materyal ısıtılır, daha büyük kristal boyuta ve minimum enerji ile katı kristal duruma yavaşça soğutulur. Tavlama işlemi, sıcaklığın ve soğuma katsayısının dikkatlice kontrolünü gerektirir. Tavlama işlemi sonucunda oluşan kristalleşme, metalin mekanik özelliklerini iyileştiren moleküler yapısındaki değişikliklerle oluşmaktadır. Tavlama işlemindeki ısının davranışı, optimizasyondaki kontrol parametresiyle aynı gibi görülür. Isının, daha iyi sonuçlara doğru algoritmaya rehberlik eden bir rolü vardır. Bu durum ancak kontrollü bir tutum içinde, ısının kademeli olarak düşürülmesiyle yapılabilir. Eğer ısı aniden düşürülürse, algoritma lokal minimum ile durur.

TB algoritması; birçok değişkene sahip fonksiyonların maksimum veya minimum değerlerinin bulunması için, özellikle de
birçok yerel minimuma sahip doğrusal olmayan fonksiyonların minimum değerlerinin bulunması için tasarlanmıştır.
Tavlama benzetimi algoritmasında; sıcaklık, sıcaklığın düşürülmesi, tekrar işlemi (döngü) gibi parametreler vardır. Algoritmada bir başlangıç aday çözümü belirlenip, bu çözüm başlangıçta en iyi çözüm olarak kabul edilir. Başlangıç aday çözümünün kopyasına "tweak" işlemi (başlangıç aday çözümüne ufak bir değişiklik yaparak yeni bir çözüm
üretme işlemi) uygulanır. Daha sonra ki adımlar da ise en iyi çözüm kabul edilen başlangıç aday çözümü ile yeni üretilen çözümün hangisinin daha iyi olduğu (kaliteleri) veya 0-1 arasında üretilen bir rassal sayının < 𝑒 ((Kalite(Y)− Kalite(B))/sıcaklık) durumu araştırılır. Eğer yeni sonuç daha iyi ise en iyi çözüm olarak yeni çözüm atanır. Sıcaklık
parametresi, tavlama yönteminde başlangıçta belirlenen bir değerdir. Bu değer, oluşturulan döngünün sonunda, belirli bir oranda (sıcaklığın düşürülme parametresi kadar) azaltılır. Bu işlemler en iyi çözüm bulunana kadar veya algoritmanın çalıştırılması için belirlenen bir süre bitene kadar veya sıcaklık parametresi sıfır veya sıfırdan küçük olana kadar sürdürülebilir.

Tabu Arama Algoritması (TA)

Glover tarafından ortaya atılan ve Hansen tarafından türetilmiş versiyonları bulunan TA algoritması, temelde son çözüme götüren adımın dairesel hareketler oluşturmasını engellemek için cezalandırılarak bir sonraki döngüde tekrar edilmesinin yasaklanması üzerine kurgulanmıştır.

TA algoritması döngü ya da çalışma süresi boyunca üretilen çözümler ile ilgili bilgileri saklamak üzere tasarlanmış dinamik bir hafızaya sahiptir. Tabu listesi olarak da adlandırılan bu hafızada saklanan bilgiler, araştırma uzayında yeni çözüm kümelerinin oluşturulması için kullanılır. TA algoritması, mevcut çözümlerden küçük bir değişim ile (tweak) elde ettiği denenmemiş bir çözüm kümesi üreterek optimizasyona
başlamaktadır. TA algoritmasında, çözüm uzayında bir yerel minimum noktada takılmayı engelleyebilmek için oluşturulan yeni çözüme, o anki çözümden daha kötü olsa bile müsaade edilmektedir. Ancak kötü çözüme izin verilmesi algoritmayı bir kısır döngü içerisine sokabilecektir. Algoritmanın kısır döngüye girmesine engel olmak için, bir tabu listesi oluşturulur ve o anki çözüme uygulanmasına izin verilmeyen tüm yasaklı hareketler tabu listesinde saklanır.

Bir hareketin tabu listesine alınıp alınmayacağını belirlemek için, tabu kısıtlamaları adı verilen bazı kriterler kullanılmaktadır. Tabu listesinin kullanılması, belirli bir iterasyon sayısınca daha önce denenmiş çözümlerin tekrar edilmesini engellediği için arama
esnasında bir bölgede takılma ihtimalini azaltmaktadır. TA, mümkün bir çözüm ile başlar. Bu çözüm, problemin matematiksel ifadesinde geçen kısıtları tatmin eden bir çözümdür. Tabu aramanın performansı başlangıç çözümüne bağlıdır. Bu nedenle mümkün olduğunca iyi olan bir çözüm ile başlamak gerekir. Tabu listesi ilk giren ilk çıkar (first in first out = FIFO) mantığında çalışan bir listedir. Algoritmada belirlenen karakteristik özelliklere göre tabu listesi sürekli olarak yukarıdan doldurulmaya başlar. Bulunan elemanların sayısı liste uzunluğunu aştığında yeni gelen elemanın listeye eklenmesi için listenin en sonundaki eleman listeden çıkarılır.

Konuyla ilgili yapılan çalışmanın kodları Github'dan inceleyebilirsiniz. Kodlar arasında yorum satırlarıyla konu hakkında fikir sahibiyseniz anlaşılır olacaktık.

Github Kodu: https://github.com/bulentsiyah/Tavlama-Benzetimi-ve-Tabu-Arama-Algoritmalari-ile-Gezgin-Satici-Problemi