Simetrik gezgin satıcı problemi için yeni bir meta-sezgisel: kör fare algoritması

Abstract

Gezgin Satıcı Problemi (GSP), başlangıç ve bitiş şehirleri aynı olan ve her şehrin sadece bir kez ziyaret edildiği minimum mesafeli turu bulma problemidir. Problemin tanımı kolay olmasına rağmen şehir sayısı arttığında problemin çözümü zorlaşmaktadır. Bu nedenle Gezgin Satıcı Problemi üzerinde, en çok çalışılan kombinatoryel en iyileme problemlerinden biridir. Gezgin satıcı problemi NP-Tam kategorisine dahildir ve kesin matematiksel yöntemler ile çözüme ulaşmak problem büyüklüğü arttıkça imkânsızlaşmaktadır. Bu sebeple makul çözüm sürelerine sahip çok sayıda sezgisel yöntem geliştirilmiştir. Doğadan esinlenen sezgisel algoritmalar oldukça fazla çalışılan yöntemler arasında yer almaktadır. Bu çalışmada, kör farelerin doğadaki davranışlarından ve yaşadıkları tünellerde karşılaştıkları engelleri geçme stratejilerinden esinlenilerek geliştirilen bir meta-sezgisel arama yöntemi önerilmiştir. Ayrıca yöntemin kendisine özgü bir mutasyon operatörü bulunmaktadır. Yönteme ilişkin parametrelerin en uygun değerleri Taguchi L32 tasarımı ile belirlenmiştir. Önerilen yöntem farklı boyutlardaki simetrik GSP test problemleri için uygulanmış ve sonuçlar bilinen en iyi değerlerle kıyaslanmıştır. Bu yöntemle gerçekleştirilen deneylerden elde edilen sonuçlara dayanarak yöntemin umut verici olduğunu söyleyebiliriz. Traveling Salesman Problem (TSP) can be described as the problem of finding a minimum distance tour of n cities, beginning and ending at the same city and that each city are visited only once. Although the definition of the problem is quite simple; it is considerably difficult to solve the problem when the numbers of cities increase. Hence, Traveling Salesman Problem is one of the most widely studied combinatorial optimization problem. TSP is the member of NP-Complete class and the solution of TSP is impossible with exact methods when the size of problem increase. Hence, a large number of heuristics which have reasonable computation time were developed. In developed heuristic algorithms inspired by nature are quite popular. In this study, a new meta-heuristic called “blind mole-rat algorithm” was proposed. This heuristic inspired by behaviors and strategy of blind mole-rats in the nature. Additionally algorithm has specific mutation operator. The optimum values of parameters of algorithm were set with Taguchi L32 design. Then algorithm was applied to different size of symmetric TSP problems. The results of application benchmarked with known optimum solutions. Through the experiments carried out with this method, promising results were obtained.