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

管 琳，张 博，黄冬梅（河北农业大学理学院，河北保定 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]也得到了不错的结果。本文改进了SOM算法的学习率和邻域函数，并将仿真结果与SETSP及MSTSP两个算法作比较。

1 自组织映射网络

自组织映射网络（Self-organizing Map，即SOM）是由Kohonen教授提出的一种竞争式学习网络，能将任意维输入模式在输出层映射成一维或二维离散图形，并保持其拓扑结构不变。在无教师示教的情况下，通过对输入模式的自组织学习，在竞争层将分类结果表示出来。此外，网络通过对输入模式的反复学习，可以使连接权矢量空间分布密度与输入模式的概率分布趋于一致[5]。

SOM的学习算法由两部分组成，分别是获胜神经元的选择和网络权系数的更新。

1.1 获胜神经元的选择

设X＝(x1, x2, …, xn)T表示输入信号，Wi＝(wi1, wi2, …, win)T表示连接输入信号和神经元i的所有连接权值，则获胜神经元j可以表示为οj=max{οi}=max{f (X,Wi)}。这里，f是预先确定的判定函数，也是神经元的输出函数。通常f取f(X,Wi)=−||X−Wi||，其中‖X −Wj‖是欧氏距离。

1.2 网络权系数的更新

1984年Kohonen提出了一个权值修正公式[9]

其中rj和ri分别是获胜神经元j及相邻神经元i的位置向量，α(t)和σ(t)都是随时间而递减的函数。在获胜神经元邻域范围内的神经元都会受到激励，它们的连接权值都将被调整。邻域半径随着时间逐渐减小。

1.3 TSP问题的自组织映射网络

文献[7]构造了一个二层的自组织映射网络求解TSP问题。输入层有两个神经元，分别代表TSP问题中城市的位置坐标，输出层由m个神经元（节点）组成一个闭合路径。通过Kohonen自组织学习算法，使得路径上的节点向距离最近的城市移动。每次输入一个城市进行学习，离城市最近的节点成为获胜节点。由下式来计算获胜节点J

其中xi表示城市的坐标，yj表示环节点的坐标，|| . ||表示Euclidean距离。

获胜节点和它的邻域按照下面的公式向相应城市移动

α 和σ 是学习率和邻域函数变量，d = min{| j −J |, m − | j −J |}表示在环上节点j 和 J 的距离，| . | 代表绝对值，m代表节点数。当网络达到稳定时，每个城市均对应于一个获胜节点，此时节点构成的闭合回路就是TSP的遍历路径，同时可以求出近似解。

2 算法改进

2.1 学习率和邻域函数变量的改进

自组织映射网络的学习过程分为两个阶段。第一阶段为粗学习和粗调整阶段。在这一阶段内，各随机方向的连接权矢量朝着输入模式的方向进行调整，并大致确定了各输入模式在竞争层中所对应的映射位置。一般此阶段的学习率大于0.5。一旦各输入模式有了相对的映射位置后，则转入第二阶段——精学习和细调整阶段。在这一阶段内，网络学习集中在对较小范围内的连接权进行调整，学习率应随着学习的进行而不断减小。一般此阶段学习率的初始值选为0.5[5]。

SOM有两个更新参数，学习率α 和邻域函数变量σ 。1990年Kohonen又建议了一个指数的参数更新公式[10]

这里，k是迭代次数，τ1和τ2是指数时间常数，α0= 1, σ0= 10 , τ1= 20 , τ2= 10 。公式(4)、公式(5)的参数更新过程如图1、图2所示。

文献[7]中的MSTSP算法建议采用的参数更新公式如下

k是迭代次数, σ0= 10。公式（7）有一定的局限性，σ 随着迭代次数的增加而减小，但是如果k等于100，那么σ = 0，则无法再进行迭代了。

图1 SOM算法的学习率Fig. 1 Learning rate of SOM

图2 SOM算法的邻域函数变量Fig. 2 Neighborhood function variance of SOM

本文提出一种新的参数更新公式：

其中k是迭代次数，T取常数，与运算时间有关，一般可以取为迭代次数的倍数。本文取k的最大迭代次数为60，T = 1 000，σ0= 10。公式(8)、公式(9)的参数更新过程如图3、图4所示。

图3 学习率Fig. 3 Learning rate

图4 邻域函数变量Fig. 4 Neighborhood function variance

从图1和图3的对比可以看到，Kohonen建议的学习率在前30次时减小得非常快，在第40次迭代时取值已接近0.1，这可能使得公式（2）的值很小，也就是说获胜节点以及它的邻域位置的改变量很小。如果此时节点还没有靠近城市位置，就有可能导致迭代结束了，但此时的节点还没有覆盖城市位置。改进后的学习率在前30次迭代时变化较快，从1减小至0.5左右，这是粗学习和粗调整阶段，大致确定了节点对应的城市位置；而30次以后的变化率比前一阶段小，这是精学习和细调整阶段，最终确定了获胜节点对应的城市位置。

从图2和图4的对比可以看到，Kohonen建议的邻域函数变量的值在迭代20次时就接近于1，迭代40次以后接近于0，那么邻域函数的值则趋近于0，从而使获胜节点以及它的邻域的位置改变量几乎为0，因此可能导致节点还没有找到相应的城市位置时就停止不动了。改进后的邻域函数变量通过实验能够保证节点收敛到城市位置，对于城市规模较大的实例也适用。

2.2 改进后的算法

本文提出了一种求解TSP问题的LNSOM (imoproved learning rate and neighborhood function varience of SOM) 算法。

(1) 输入：确定城市位置坐标，随机排列城市的输入顺序，城市个数记作n，迭代次数记作k，独立运算次数记作j。

(2) 输出层，即网络初始化：输出层初始化为一个具有m个节点（m = 2n）的圆形闭合路径，圆心位于城市坐标的重心处，半径取n个城市横坐标平均值的五分之一，节点的坐标作为输入层与输出层的连接权值。

(3) 网络训练过程

(3.1) 参数更新——按照公式(8)，公式(9)更新学习率αk和邻域函数变量σk；

(3.2) 竞争——通过竞争，选择离第i个城市欧式距离最近的节点，记作获胜节点J；

(3.3) 邻域更新——用公式(2)和公式(3)更新获胜节点和它的邻域；

(3.4) i: = i+1, 如果i ＜ n+1, 转向(3.2)；否则, k: = k+1转向(3.1)；

(3.5) 当k ＞ kmax时, 转向 (1)，j: = j+1；当j = jmax时，转向(4)。

(4) 网络测试过程：取独立运算j次中最好的解作为连接权值，再进行一次运算，结束。

LNSOM算法计算复杂度分析：每一个城市平均计算的邻域节点数为0.3m ，在一次迭代中需要计算0.3mn次。随着邻域函数变量的减小，每个城市需要计算的邻域节点数也在减少，而且减少的速度很快，如图4所示。因此，LNSOM算法保持了SOM算法具有的较低计算复杂度的特点。

3 实验结果与分析

我们对LNSOM算法进行了计算机仿真，利用matlab 2011a软件得到了7个TSP实例的近似解，并与最优解以及文献[7]中MSTSP、SETSP算法的解进行了比较，如表1所示（表1中的数据是TSP实例独立运行10次的最小值）。为了验证LNSOM算法的有效性，对另外10个实例进行了计算机仿真，实验结果见表2（表2中的数据是TSP实例独立运行10次的统计结果）。其中4个实例得到了最优解，其他6个实例也得到了较好的近似解。10个实例的平均误差为1.445 6 % 。实验结果表明LNSOM算法在求解城市个数为200左右的TSP问题上是非常有效的。

实验数据来源：http://www2.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/。

表1 7个TSP实例的运算结果（无单位）Tab. 1 Results of 7 TSP instances

表2 10个TSP实例的运算结果（无单位）Tab.2 Results of 10 TSP instances

4 结论与展望

本文提出了一种改进的SOM算法，通过改进学习率和邻域函数变量使得邻域更新过程更加合理有效，从而能够找到更好的近似解。实验表明，LNSOM算法在计算200个城市及以下规模的TSP问题上比SETSP和MSTSP算法的误差更小，并且保持了较低的计算复杂度。

今后，可以尝试将该算法应用于求解大规模的TSP问题或者车辆路径问题等。

[1] 胡运权. 运筹学教程[M]. 北京： 清华大学出版社, 1998.

[2] 高海昌, 冯博琴, 朱利. 智能优化算法求解TSP问题[J]. 控制与决策, 2006, 21(3)： 241-247.

[3] 张军英, 周斌. 基于泛化竞争和局部渗透机制的自组织网TSP问题求解方法[J]. 计算机学报, 2008, 31(2)： 220-227.

[4] 吴婷, 陈玉旺, 汪烨. 基于极值动力学的自组织优化算法求解TSP问题[J]. 控制理论与应用, 2010, 27(6)： 715-720.

[5] 闻新, 周露. Matlab神经网络应用设计[M]. 北京： 科学出版社, 2002.

[6] 白艳萍. 人工神经网络在组合优化与信息处理中的应用[D]. 中北大学博士论文, 太原： 中北大学, 2005： 68-73.

[7] BAI Y P, ZHANG W D, JIN Z. A new self-organizing maps strategy for solving the traveling salesman problem[J]. Chaos, Solitons & Fractals, 2006, 28： 1082-1089.

[8] BAI Y P, ZHANG W D. A new elastic net learning algorithm for travelling salesman problem[C]//International Symposium on Test and Measurement. International Academic Publishers World Publishing Corporation, 2005, 6： 5882-5888.

[9] Kohonen. Self-organization and associative memory[J]. Springer-Verlag, Berlin, 1984, 45： 256-260.

[10] Kohonen. The self-organizing map[J]. Proceedings of the IEEE, 1990, 78： 1464-1480.

An Improved Self-organizing Algorithm for Solving the Traveling Salesman Problem

GUAN Lin, ZHANG Bo, HUANG Dong-mei
(School of Science, Agriculture University of Hebei Province, Hebei 071000, P. R. China)

There are no effective corresponding solutions to the traveling salesman problems (TSP). To address the problems, a new algorithm by improving learning rate and neighborhood function variance of the self-organizing map (SOM) is presented. The solutions of five instances are better than MSTSP and SETSP in matlab2011. The average error is only 1.445 6 % of anthor ten. The new algorithm has the advantage of smaller error and maintaining low SOM algorithm computational complexity.

traveling salesman problem; self-organizing map; learning rate; neighborhood function variance

TP18

A

1001-4543(2012)01-0048-05

2012-11-28;

2012-02-09

管琳（1981－），女，河北保定人，讲师，硕士，主要研究方向为神经网络算法与应用，电子邮箱sxguanlin@hebau.edu.cn。

河北省软科学计划项目（No. 104572108）；河北农业大学非生命课题（No. FS201008）；保定市科学技术研究与发展指导计划软科学项目（No. 11ZR004）