Gezgin Satıcı Problemi (GSP) - Travelling Salesman Problem (TSP)

Gezgin satıcı problemi, en önemli algoritma problemlerinden biridir. Gezgin satıcı problemi iki şehir arasında mümkün olan en kısa yolu bulmaya çalışır, bu şehirler arasındaki her noktaya maximum bir kez uğramalı. Şehir sayısı artarsa problemimizde üstel bir şekilde artar. Gezgin Satıcı Problemi (GSP), üzerinde yoğun olarak çalışılan kombinasyonel eniyileme problemlerinin başında gelmektedir. Çözümü için birçok sezgisel algoritma geliştirilmiştir.

Gezgin Satıcı probleminin çözümü;
• Başlangıç için seçilebilecek n tane şehir vardır.
• Bu şehirlerden birisi başlangıç noktası olacağı için, satıcı n-1 farklı şehirde satış yapabilir.
• İkinci şehire geçince satıcının satış yapabileceği şehir sayısı n-2 olur.

Karınca Koloni Algoritması

Karınca koloni algoritması Gezgin Satıcı Problemi gibi problemlerin çözümü için ortaya çıkarılmış bir algoritmadır. Karıncalar , yiyecek bulmak için en kısa yolu görme duyusunu kullanmadan bulurlar. Karıncalar yiyecek ararken ,yiyecege ulaştıkları yollara buharlaşma özelliği olan, feromon adında bir salgı bırakırlar. Feromon, aralarındaki haberleşmeyi sağlayan kimyevi maddenin adıdır, bununla yiyeceğin olduğu yere kadar giden bir koku izi bırakır.

1- Yuvadan çıkan karıncalar, bulundukları yerde diğer karıncalardan kaynaklanan baskın bir koku yoksa tamamen rastgele hareket ederler.
2- Eğer herhangi bir yönden diğer karıncaların yaydığı bir kokuyu alabilmişse, karınca o tarafa yönelir. Birden çok yönden koku alıyorsa kokunun geldiği en baskın tarafa yönelir.
3- Karıncanın yaydığı koku bir süre o bölgede kalabilir. Bu sayede bir yolu birden çok karınca tercih etmişse aradan belirli bir süre geçmiş olsa bile daha çok tercih edilen bölgeden daha baskın bir koku gelir.

Karınca Koloni Optimizasyonu(KKO)
Gerçek karınca koloni davranışından yola çıkarak karıncanın besin arayışını matematikselmodellerle ifade eden algoritmadır. Karıncaların besin arayışında kısa yolu bulabilme yeteneklerini Gezgin Satıcı Problemimizdeki kısa yolu bulma olayıyla eşleştiriyoruz.

Gezgin Satıcı Problemi, KKO algoritmaları için oldukça önemlidir. İlk KKO algoritması olan Karınca Sistemi (Ant System), ilk olarak bu problem üzerinde denenmiştir. Çünkü bu problem, önemli bir Np-zor eniyileme problemidir. Ayrıca kolay anlaşılabilir ve yeni algoritmaların denenebileceği, etkinliklerinin ölçülebileceği standart bir deneme ortamıdır.

6 adımda algoritmamızı oluşturmak istersek;
1- Başlangıç fenomen değerlerini belirle
2- Karıncaları random bir şekilde her bir noktaya koy
3- Her karınca turunu tamamlar
4- Karıncaların aldıkları yol hesaplanır ve local feromen değeri güncellenir
5- En iyi çözüm hesaplanır ve gloabal feromon değeri güncellenir
6- İstediğimiz sonucu elde edene kadar 2. adıma geri dön

Feromon guncellemesı; Turunu tamamlayan karınca feromonunu günceller. Yollardaki feromonlar buharlaşma oranı kadar buharlaştırılır. Geçiş yapılan yolda ise feromonları artırırız bu artırma yolun uzunluğu ile ters orantılı olarak gerçekleşir.
Daha kısa yolda böylece feromon miktarı daha fazla olur.

Local Feromon Güncellemesi;
Geçilen yolda buharlaşma oranı kadar feromon buharlaştırılı ve yolun uzunluğu ile ters orantılı olacak şekilde feromon artırılır. Feromon miktarına bağlı olarak sürekli değişen rota sonunda en kısa yol bulunmuş olur.

Global Feromon Güncellemesi;
Global feromon güncellemesi geçerli adımda en iyi sonucu yapmış karıncanın yolunun feromondüzeyinin artırılması. Böylece bulunan en iyi sonuç bir sonraki adıma aktarılmış olur.

Karınca sayısı;
Sayıyı artırmak hem iyi hem kötü. İyi tarafı çözümde iyileşme sağlar kötü tarafı fazla hesap gerekir karmaşıklık ve zaman artar.

Sezgisel Algoritma;
Gercek uzaklık bilinmese de tahmin edilir. Bu tahmin Heuristic(Sezgi) denir. Optimal çözüm değil fakat optimal çözüme yakın değer aranır. Kesin çözümü garanti etmez. Sezgisel algoritmaların buradaki kullanım amacı hedefe varmak için doğal fenomenleri kullanmamız.
Belirli sayıdaki karıncılarımızı random seçtiğimiz şehirlere yerleştiririz. Bu şehirlerden hedef şehire ulaşmak için aradaki şehirlere uğramalıyız. Böylece bir tur gerçekleşir.

Bir şehirden diğer şehire giderken gidilecek bu şehri seçme faktörleri;
Feromon izi miktarı, yol uzunluğu ve sezgisel bilgisi kullanılır. Tur sonunda ise feromon miktarı güncellenir. Bir sonraki karıncanın bu yolu tercih etmesinde bu feromon oranı etkilidir.