改进的求解旅行商问题的自组织特征映射网络

Modified self-organizing map network for Euclidean travelling salesman problem

对自组织特征映射(SOM)网络进行改进,要求神经元在训练过程中不仅数目保持不变而且在每次迭代中保持其权的均值与样本数据均值相同。当训练结束时,每一个城市都会对应于一个神经元的标号。此时,可能会出现两个及两个以上的城市对应于一个神经元的情况。为避免这个问题,采用小数标号代替整数标号。此时,每一个城市就对应于一个不同的实数索引标号,从而按照这个索引标号排列城市就得到了一条合理的路径。用此方法对旅行商问题(TSP)实验数据库(TSPLIB)中算例进行计算,实验结果表明所提算法是有效、可行的。

The Self-Organizing Map（SOM） was modified in this paper： the number of the neurons did not change with time and the neurons collectively maintained their mean to be the mean of the data point in the training phase.After training,every city was associated with a label of a neuron.Then there may be a problem that one or more than one cities have the same neuron.In order to avoid that,a dot labels index was adopted instead of the integer index.The virtue of this scheme is that different city has different index.Then the label would contribute to make sure the order of the city in the tour.Then the algorithm was applied to solve problems taken from a Traveling Salesman Problem Library（TSPLIB）.The experimental results show that the proposed algorithm is feasible and effective.