An overall-regional competitive self-organizing map neural network for the Euclidean traveling salesman problem

详细信息	查看全文 | 推荐本文 |

• 作者：Junying Zhang^a ; ^{jyzhang@mail.xidian.edu.cn}  ; [Author Vitae] ; Xuerong Feng^b ; ^{sherry_fong65@yahoo.com}  ; [Author Vitae] ; Bin Zhou^a ; ^{notbob@sohu.com}  ; [Author Vitae] ; Dechang Ren^a  ; [Author Vitae]
• 关键词：Euclidean traveling salesman problem ; Self-organizing map ; Overall-regional competitive self-organizing map ; Optimal tour
• 刊名：Neurocomputing
• 出版年：2012
• 期刊代码：95_09252312
• 类别：cp
• 出版时间：15 July, 2012
• 卷：89
• 期：Complete
• 页码：1-11
• 文件大小：668 K

摘要

The paper proposes a novel overall-regional competitive SOM (ORC-SOM) algorithm for solving symmetric Euclidean traveling salesman problems (TSPs). Two novel rules, overall and regional competition rules respectively, are introduced in the ORC-SOM. Overall competition is designed to make winning neuron and its neighborhood neurons less competitive for outlining the tour, and regional competition is designed to make them more competitive for refining the tour, both compared with the standard SOM. An increasing radius with respect to iteration is designed for a smooth transition from more focus on outlining to more focus on refining the tour. Besides topology preservation property and convex-hull property, an additional significant property of an optimal tour for a complex TSP, referred to as infiltration property, is introduced, and the feasibility of the ORC-SOM algorithm on these properties are studied. Computational comparisons with typical SOM-based counterparts on two sets of benchmark TSP instances from TSPLIB demonstrate the superiority of the ORC-SOM in solution quality.