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

Searching for the shortest path through group processing for TSP

Pages
53–65
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

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.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:Thanks to its complexity, Traveling Salesman Problem (TSP) has been one of the most intensively studied problems in computational mathematics.
📊
Key Findings & Data: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.
💡
Conclusion & Impact: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.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Domain Parameters

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.

Özet

Türkçe Öz Yok

🔖

Cite This Article

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

📄 Full Text PDF Viewer

📄

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

References (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