Performance analysis of meta - heuristic approaches for traveling salesperson problem

Abstract

ÖZET Gezgin satıcı problemi, olasılık optimizasyonunun en ünlü problemlerinden bir tanesidir. Sade tanımı ve zor olmasıyla bilinen kötü şöhretinden dolayı hep kıştırtıcı olmuş ve problem için etkili bir algoritma bulabilmek amacıyla çok güç sarfedilmiştir. Gezigin satıcı probleminde, NP doğasından dolayı sadece yaklaşık çözümler beklenebilir. Geleneksel çözümlerin herhangi bir iyi çözüm bile bulamamalarından dolayı araştırmacıları farklı yaklaşımlar bulmaya yöneltmiştir. Bu tez çalışmasında problemin çözümünde 2-OPT, Simulated Annealing, Genetik Algoritma gibi yaklaşımlar ve bu yaklaşımların Hill Climbing gibi farklı operatörler ile birleştirerek problemin çözümünde bir fayda sağlanmak amaçlanmaktadır. Seçilen yaklaşımı probleme uygulayan bir yazılım aracı dizayn edilmiş ve geliştirilmiştir. Kullanıcı dostu arayüz, kullanıcının seçtiği algoritma ile ilgili olan parametreleri girerek programın işleyişi srasında algoritmik adımların takibine olanak kılmaktadır. XI

ABSTRACT The traveling salesman problem (TSP) is one of the most prominent problem in combinatorial optimization. Its simple definition along with its notorious difficulty has stimulated (and still stimulates) many efforts to find an efficient algorithm. Due to the NP-completeness of the TSP, only approximate solutions can expected. The traditional algorithms fail to make even a good approximation, leading researchers to apply meta- heuristic approaches. In this thesis, the performance analysis of 2-OPT, Simulated Annealing and Genetic Algorithms, utilizing different operators, combined with hill climbing for solving TSP is provided. A tool designed and developed, offering a graphical user interface for applying the chosen meta-heuristic to TSP. The friendly interface allows users to enter all related parameters for the chosen algorithm and follow the algorithmic steps in action. X