一种改进的自组织映射算法求解旅行商问题

管 琳，张 博，黄冬梅（河北农业大学理学院，河北保定 071000）

一种改进的自组织映射算法求解旅行商问题

管 琳，张 博，黄冬梅
（河北农业大学理学院，河北保定 071000）

目前，没有求解旅行商问题的非常有效的方法。提出了一种求解该问题的LNSOM算法，在自组织映射算法的基础上，改进了学习率和邻域函数变量。利用matlab 2011软件进行求解，其中5个旅行商问题实例的结果优于MSTSP和SETSP算法，另外，10个实例的平均误差为1.445 6 %。实验结果表明，新算法的误差更小，并保持了SOM算法较低的计算复杂度。

旅行商问题；自组织映射；学习率；邻域函数

0 引言

旅行商问题，即TSP（traveling salesman problem）是一个典型的组合优化问题，其要求很简单：在n个城市的集合中，找出一条经过每个城市各一次，最终回到起点的最短路径。TSP没有限定路径的方向，所以其旅行方案数为(n≥4)种[1]。由于TSP问题难以求解，所以至今尚未找到非常有效的求解方法。

由于TSP问题代表了一类组合优化问题，在实际工程中有许多应用，如计算机联网、电子地图、交通诱导、电气布线、VLSI单元布局、ATM分组交换网等。鉴于其重要的工程与理论价值，TSP常作为算法性能研究的典型算例，但求其最优解的代价是指数级的，因此，对其近似解的研究一直是算法设计的一个重要课题[2]。

近些年，智能计算也被应用于求解TSP的问题上，主要有遗传算法、蚂蚁算法、免疫算法、神经网络算法等。文献[3-5,8]都是在SOM算法的基础上融合了其他方法来求解TSP问题，取得了一定的成果。另外，2003年Frederico提出的SETSP (SOM Efficiently applied in the TSP) 算法[6]，以及2006年白艳萍提出的MSTSP (Modified SOM applied to the TSP) 算法[7]也得到了不错的结果。……