基于泛化竞争和局部渗透机制的自组织网TSP问题求解方法

Self Organizing Map with Generalized and Localized Parallel Competitions for the TSP

旅行商问题(TSP)是组合优化中最典型的NP完全问题之一,具有很强的工程背景和应用价值.文章在分析了标准SOM(Self-Organizing Map)算法在求解TSP问题的不足和在寻求总体最优解的潜力的基础上,引入泛化竞争和局部渗透这两个新的学习机制,提出了一种新的SOM算法---渗透的SOM(Infiltrative SOM,ISOM)算法.通过泛化竞争和局部渗透策略的协同作用:总体竞争和局部渗透并举、先倾向总体竞争后倾向局部渗透、在总体竞争基础上的局部渗透,实现了在总体路径寻优指导下的局部路径优化,从而使所得路径尽可能接近最优解.通过对TSPLIB中14组TSP实例的测试结果及与KNIES、SETSP、Budinich和ESOM等类SOM算法的比较,表明该算法既简单又能使解的质量得到很大提高,同时还保持了解的良好的稳健特性.

As one of the most typical NP-complete combinational optimization problems, TSP （Traveling Salesman Problem）, which has a diversity of applications in real world, has attracted extensive research lem has been paid interest. Recently, Self-Organizing Map（SOM） based approaches to this prob great attention for its simplicity and novelty. By analyzing drawbacks of stand ard SOM algorithm for solving TSP problem, it was found that the standard SOM has a great potential for finding overall optimal solution rather than globally optimal solution for a TSP problem. Based on this, the paper proposes a new SOM algorithm for solving TSP problem, the infiltrative SOM （ISOM）, by introducing two new learning schemes, competition generalization and local infiltration. By the collaboration of the two learning schemes in that both the schemes work together in the whole learning process and initial learning focuses more on overall optimization, which is conducted by the competition generalization, while the afterward learning focuses more on local optimization, which is conducted by the local infiltration, the near-optimal solution is much more easy to be found. Experiments on public TSPLIB data show that not only the quality of the solutions is higher, but also the solutions are more pared with those by several typical SOM-based methods robust, by the proposed method comsuch as the KNIES algorithms, the SETSP, the SOM developed by Budinich, and the ESOM.