Self Organizing Map with Generalized and Localized Parallel Competitions for the TSP
Jun-Ying ZHANG, Bin Zhou · Chinese Journal of Computers · 2009
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 interest.Recently,Self-Organizing Map(SOM)based approaches to this problem has been paid great attention for its simplicity and novelty.By analyzing drawbacks of standard 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 robust,by the proposed method compared with those by several typical SOM-based methods such as the KNIES algorithms,the SETSP,the SOM developed by Budinich,and the ESOM.