Dergiler / Mathematical and Computational Applications / 2011 / Cilt: 16 - Sayı: 1

Searching for the shortest path through group processing for TSP

Sayfa
53–65
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗

Özet

Türkçe Öz Yok

Abstract

Thanks to its complexity, Traveling Salesman Problem (TSP) has been one of the most intensively studied problems in computational mathematics. Although many solutions have been offerpd so far, all of them have yielded some disadvantages and none has been able to claim for the best solution. We believe that better solution could be obtained through iterative evaluations, until a certain number of islands are reached, if we could develop an algorithm which grows geometrically. Some algorithms have suggested random solutions and many suggested using the closest neighbors. In many cases islands exist in groups or chains in any length. Therefore they can be connected to any other island rather than the closest one. This can be better identified when we spot out the patterns and island chains. In this paper, we have searched for the identification of patterns and chains. We propose an iterative Group Processing (GP) approach which finds better paths in the 90% of the cases overall as we compare it to Random Logic (RL) programs and most up-to-date Artificial Neural Network based TSP programs.

🔖

Bu Makaleye Atıf Yap

MEŞECAN, İ., BUCAK, İ. Ö., ASİLKAN, Ö. (2011). Searching for the shortest path through group processing for TSP. Mathematical and Computational Applications, Cilt: 16 - Sayı: 1, 53–65. https://ajindex.com/articles/280500

📄 Tam Metin PDF Okuyucu

📄

PDF görüntüleyici hazırlanıyor...

Kaynakça (2)

  1. J.J. Hopfield and D. Tank, Neural Computation of Decisions in Optimization Problem, Biological Cybernetics, 5, 1994 [2]T.H. Cormen, C.E. Leiserson., R.L. Rivest, and C. Stein, Introduction to Algorithms, 2nd Edition,
  2. The MIT Press, McGraw-Hill, 2001 [3]Y. Li, Traveling Salesman Problem Based on DNA Computing, Third IEEE International Conference on Natural Computation, 4, 28-34, 2007 [4]R. Takahashi, A Hybrid Method of Genetic Algorithms and Ant Colony Optimization, International Conference on Machine Learning and Applications, 81-88,2009 [5]D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Pub. Co., 1989 [6]K. Helsgaun, An Effective Implementation of the Lin-Kemighan Traveling Salesman Heuristic, European Journal of Operational Research, 126, 106-130, 2000 [7]I. Mavroidis, I. Papaefstathiou, D. Pnevmatikatos, Hardware Implementation of 2-opt Local Search Algorithm for the Traveling Salesman Problem, 18th IEEE/IFIP International Workshop on Rapid System Prototyping, 41-47, 2007 [8]K. Fujimura, H. Tokutaka, S. Tanaka, T. Maenou, and S. Kishida, The optimization for TSP using SOM method of many cities (e.g., 532 cities in USA), Tottori University-Japan, 1997 [9]B. Angeniol, G. De-La-Croix, and J.-Y. Le-Texier, Self-organizing feature maps and the Traveling Salesman Problem, Neural Networks, 1. 289-293. 1988 [10]L. Brocki, Kohonen Self-Organizing Map for the Traveling Salesperson Problem,Polish-Japanese Institute of Information Technology, 2007 [11]T. Kohonen, Self-Organizing Maps, Berlin: Springer, 2001 [12]http://sourceforge.net/projects/neurondotnet/files/ http://neurondotnet.freehostia.com/download.html Program last updated: Aug, 2008. Last Viewed April, 2010 [13]http://neurondotnet.freehostia.com/manuaî/ Program last updated: Aug, 2008 Last Viewed on April 2010 [14]M. Lalena, http://www.lalena.com/AI/Tsp/ release date: 2006. Last viewed Apr,2010