Artificial Neural Networks For Solving The Travelling Salesman Problem

Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2003Thesis (M.Sc.) -- İstanbul Technical University, Institute of Science and Technology, 2003Gezgin Satıcı problemi, verilen bir şehir seti için, her bir şehrin sadece ve sadece bir kez ziyaret edileceği en kısa kapalı turun belirlenmesi problemini içermektedir. Söz konusu problem bir “NP-complete” optimizasyon problemidir. Bu ifade, makul büyüklükte bir problem için ele alınması gereken çok sayıda varsayımın varlığından dolayı optimum bir sonuç aramanın, hesaplama maliyetlerinin çok yüksek olması sebebiyle, mümkün olmadığı problemler için kullanılır. Bu nedenle bu tip problemlere, kısa hesaplama süreleri içinde optimum sonuca yakın çözümler bulabilmek iyi bir sonuç olarak görülür. Hopfield ağ modeli yada Kohonen’in öz-düzenlemeli ağ yapıları gibi bir Yapay Sinir Ağı, Gezgin Satıcı Problemine hızlı bir biçimde geçerli çözümlerin belirlenmesine imkan verir. Bu şekilde, makul hesaplama süreleri içinde elde edilecek sonuçlar en iyi çözümler olmasa bile en iyi çözüme yakın sonuçlar olmaktadır.The Traveling Salesman Problem consists in the problem of determining the shortest circuit which can be made visiting a list of cities, in such a way that each city is visited once and only once. This is an “NP-complete” optimization problem, which means that, for a problem with a reasonable dimension, there are so many hypothesis to consider that it is generally unpractical to look for an optimum solution, because the computation cost is too high. That is why, finding a “good” solution in a short computation time is considered to be a good result. A neural net like Hopfield net or Kohonen’s Self-organizing Map allows the fast determination of solutions that, when valid, are all among the best 30 or 40 of the hundreds of thousands of possible hypothesis. If we choose among them the one that corresponds to the shortest traveled distance, we will obtain in a fast way a solution which, if it is not the best, it “close to” the best.Yüksek LisansM.Sc