An Extended Self-Organizing Map based on 2-opt algorithm for solving symmetrical Traveling Salesperson Problem

详细信息    查看全文

• 作者：Rashid Ahmad ; DoHyeun Kim
• 关键词：Artificial neural network ; Self ; Organizing Maps ; Symmetrical Traveling Salesperson Problem ; 2 ; opt Algorithm
• 刊名：Neural Computing & Applications
• 出版年：2015
• 出版时间：May 2015
• 年：2015
• 卷：26
• 期：4
• 页码：987-994
• 全文大小：1,329 KB
• 参考文献：1.Garey Michael R, Johnson David S (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New YorkMATH
  2.Lawler EL, Lenstra JK (1985) The Traveling Salesman Problem-guided tour of combinatorial optimization. Wiley, New York
  3.Fujimura K, Obu-Cann K, Tokutaka H (1999) Optimization of surface component mounting on the printed circuit board using SOM TSP method. In: Proceedings of the 6th ICONIP, vol 1, pp 131鈥?36
  4.Fujimura K, Fujiwaki S, Kwaw OC, toktaka H (2001) Optimization of electronic chip-mounting machine using SOM TSP method with 5 dimensional data. Proc ICII 4:26鈥?1
  5.Ali MM, Kamoun F (1993) Neural networks for shortest path computation and routing in computer networks. IEEE Trans Neural Netw 4(6):941鈥?54View Article
  6.Onoyama T, Maekawa T, Kubota S, Taniguchi Y, Tsuruta S (2002) Intelligent evolutional algorithm for distribution network optimization. In: Proceedings of international conference control applications, pp 802-807
  7.Banasza KD, Dale GA, Watkins AN, Jordan JD (1999) An optical technique for detecting fatigue cracks in aerospace structures. In: Proceedings of the 18th ICIASF, pp 1鈥?7
  8.Barrel D, Perrin JP, Dombre E, Liengeois A (1999) An evolutionary simulated annealing algorithm for optimizing robotic task ordering. In: Proceedings of IEEE ISATP, pp 157鈥?62
  9.Cheng CH, Lee WK, Wong KF (2002) A genetic algorithm-based clustering approach for database partitioning. IEEE Trans Syst Man Cybern C Appl Rev 32(3):215鈥?30View Article
  10.Ascheuer N, unger MJ, Reinelt G (2000) A branch and cut algorithm for the asymmetric Traveling Salesman Problem with precedence constraints. Comput Optim Appl 17(1):61鈥?4View Article MATH MathSciNet
  11.Laporte G (1992) The vehicle routing problem: an overview of exact and approximate algorithms. Eur J Oper Res 59:345鈥?58View Article MATH
  12.WangWei Artificial (1995) Neural network theory applications. Beijing University of Aeronautic and Astronautic Science and Technology Press, Beijing
  13.Kirk SG, Jr Patrick, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671鈥?80View Article MathSciNet
  14.Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, ReadingMATH
  15.Yan XS, Liu HM, Yan et al (2007) A fast evolutionary algorithm for traveling salesman problem. In: Proceedings of the third international conference on natural computation, vol 4, pp 85鈥?0
  16.Brocki L, Korinek D (2007) Kohonen self-organizing map for the Traveling Salesperson Problem. In: Recent advances in mechatronics. Springer, Heidelberg, pp 116鈥?19. doi:10.鈥?007/鈥?78-3-540-73956-2_鈥?4
  17.Korte B (1989) Applications of combinatorial optimization. In: Mathematical programming, Volume 6 of Math. Appl. (Japanese Ser.). SCIPRESS, Tokyo, pp 1鈥?5
  18.Kohonen T (2001) Self-organizing maps, Springer series in information sciences, vol 30, 3rd edn. Springer, BerlinView Article MATH
  19.Xu X, Tsai WT (1991) Effective neural algorithms for the Traveling Salesman Problem. Int J Neural Netw 4(2):193鈥?05View Article
  20.Lin S, Kernighan BW (1973) An effective heuristic algorithm for the Traveling-Salesman Problem. Oper Res 21:498鈥?16View Article MATH MathSciNet
  21.Mitra S, Pal SK (1994) Self-organizing neural network as a fuzzy classifier. Syst IEEE Trans Man Cybern 24(3):385鈥?99View Article
  22.Reinelt G (1995) TSPLIB 95 documentation. University of Heidelberg, Heidelberg, Germany. http://鈥媤ww.鈥媔wr.鈥媢ni-heidelberg.鈥媎e/鈥媑roups/鈥媍omopt/鈥媠oftware/鈥婽SPLIB95/鈥?/span>
  23.Johnson DS, McGeoch ALA, Rothberg TAEE (1996) Asymptotic experimental analysis for the Held-Karp traveling salesman bound. In: Proceedings of the seventh annual ACM-SIAM symposium on discrete algorithms, Atlanta, Georgia, USA, pp 341鈥?50
  24.Michalewicz Z (1996) Genetic algorithms data structures evolution programs. Springer, BerlinView Article MATH
  25.Starkweather T, McDaniel S, Mathias K, Whitley D, Whitley C (1991) A comparison of genetic sequencing operators. In: Proceedings of the 4th international conference on genetic algorithms, San Mateo
  26.Burke Laura I (1994) Neural methods for the Traveling Salesman Problem: insights from operations research. Int J Neural Netw 7(4):681鈥?90View Article MATH
  
• 作者单位：Rashid Ahmad (1)
  DoHyeun Kim (1)
  
  1. Department of Computer Engineering, Jeju National University, Jeju-si, Jeju-do, Republic of Korea
  
• 刊物类别：Computer Science
• 刊物主题：Simulation and Modeling
  
• 出版者：Springer London
• ISSN：1433-3058

文摘

Self-organizing map (SOM) is a powerful variant of neural network for solving optimization problems. Many researchers have reported SOM for Traveling Salesperson Problem; however, problems still exist due to the trapping of the optimization techniques at the local optimal position. In this work, we propose an Extended Self-Organizing Map based on 2-opt algorithm with one-dimensional neighborhood to approach the Symmetrical Traveling Salesperson Problem (STSP). We elaborate our approach for STSP where weights of neurons represent nodes that are placed in the polygonal domain. The selection of winner neuron of SOM has been extended to overcome the problem of trapping of SOM at local optima. The results of SOM are improved through 2-opt local optimization algorithm. We briefly discuss self-organization in neural networks, 2-opt algorithm, and extension applied to SOM. Finally, the algorithm is compared with Kohonen Self-Organizing Map and Evolutionary Algorithm. The results show that our approach performs better as compared to other techniques.