神经网络算法
神经网络解决TSP 问题
题目:
基于Hopfield 网络算法的TSP 问题的分析与实现 学 号: 2220150496 姓 名: 陈帅
一、预备知识
1、TSP 问题
旅行商问题,简称TSP ,即给定n 个城市和两两城市之间的距离,要求确定
一条经过各城市当且仅当一次的最短路线。其图论描述为:给定图G=(V ,A ),其中V 为顶点集,A 为各顶点相互连接组成的边集,设D=(dij )是由顶点i 和顶点j 之间的距离所组成的距离矩阵,要求确定一条长度最短的Hamilton 回路,即遍历所有顶点当且仅当一次的最短距离。
旅行商问题可分为如下两类:
(1)对称旅行商问题(d ij =dji ,Πi ,j=1,2,3,⋯,n );
(2)非对称旅行商问题(d ij ≠d ji ,ϖ。 i ,j=1,2,3,⋯,n )
非对称旅行商问题较难求解,我们一般是探讨对称旅行商问题的求解。
若对于城市V={v1,v 2,v 3,⋯,v n }的一个访问顺序为T={t1,t 2,t 3,⋯,t i ,⋯,
t n },其中t i ∈V (i=1,2,3,⋯,n ),且记t n +1=t1,则旅行商问题的数学模型为:minL=。 。
TSP 是一个典型的组合优化问题,并且是一个NP 完全难题,是诸多领域内
出现的多种复杂问题的集中概括和简化形式,并且已成为各种启发式的搜索、优化算法的间接比较标准。因此,快速、有效地解决TSP 有着重要的理论价值和极高的实际应用价值。
2、Hopfield 网络
Hopfield 网络是一种互连型网络的一种,它引入类似于Lyapunov 函数的能量函
数概念,把神经网络的拓扑结构(用连接权矩阵表示) 与所求问题(用目标函数描述) 相对应,并将其转换为神经网动力学系统的演化问题。其演变过程是一个非线性动力学系统,可以用一组非线性差分议程描述(离散型) 或微分方程(连续型) 来描述。系统的稳定性可用所谓的“能量函数”进行分析。在满足条件的情况下,某种
“能量函数”的能量在网络运行过程中不断地减少,最后趋于稳定的平衡状态。
因为人工神经网络的变换函数是一个有界函数,故系统的状态不会发生发散
现象。目前,人工神经网络经常利用渐进稳定点来解决某些问题。如果把系统的
稳定点视为一个记忆的话,那么从初态朝这个稳定点的演变过程就是一个寻找记
忆的过程。如果把系统的稳定点视为一个能量函数的极小点,而把能量函数视为
一个优化问题的目标函数,那么从初态朝这个稳定点的演变过程就是一个求解该
优化问题的过程。因此,Hopfield 神经网络的演变过程是一个计算联想记忆或求
解优化问题的过程。实际上,它的解决并不需要真的去计算,而是通过构成反馈
神经网络,适当地设计其连接权和输入就可以达到这个目的。
二、HopField 神经网络分析
1、离散型HopField 神经网络
Hopfield 最早提出的网络是二值神经网络,神经元的输出只取1和0两个值,
也称为离散Hopfield 网络。在离散Hopfield 网络中,采用的神经元是二值神经元,
输出的离散值1和0分别表示神经元处于激活和抑制状态。
离散Hopfield 神经网络是离散时间系统,它可以用一个加权无向图表示,图
的每一边都有一个权值,图的每个节点都有一个阈值,网络的阶数相应于图中的
节点数。
Hopfield 网络的基本结构如图1所示,这种网络是一种单层网络,令网络由n
个单元组成,N 1,N 2,... ,N n 表示n 个神经元,这些神经元既是输入单元,也
是输出单元,其转移特性函数为f 1,f 2,... ,f n ,门限值(阈值) 为θ1,θ2,... ,θn 。
图1 Hopfield 网络结构图
对于离散型Hopfield 网络,各节点一般选取同样的转移函数,且为符号函数,
即:
f 1(x ) =f 2(x ) =…=f n (x ) =sgn(x ) (式1.1)
为了分析方便,选取各节点的门限值(即阈值) 全部为0,即:
θ1=θ2=…=θn =0 (式1.2)
同时,x =(x 1, x 2, …, x n ) ,x ∈{-1, +1}n 为网络的输入;y =(y 1y 2, …, y n ) ,y ∈{-1, +1}n
为网络的输出;v (t ) =(v 1(t ), v 2(t ), …, v n (t )) ,v (t ) ={-1, +1}n 为网络在t 时刻的状态,其中t ∈(0,1,2…)为离散时间变量;w ij 为从N i 到N j 的连接权值,Hopfield 神经
网络是对称的,即有
w ij =w ji ,i , j ∈(1,2,3,…,n ) (式1.3)
整个网络所有n 个节点之间的连接强度用矩阵W 表示,显然W 为n ×n 方阵。
由图1可见Hopfield 网络为一层结构的反馈网络,能处理双极型离散数据(即
输入x ∈{-l,+1}),及二进制数据(x∈{0,1})。当网络经过训练后,可以认为网络
处于等待工作状态,而对网络给定初始输入x 时,网络就处于特定的初始状态,
由此初始状态开始运行,可以得到网络输出即网络的下一状态。然后,这个输出
状态通过反馈回送到网络的输入端,作为网络下一阶段运行的输入信号,而这个
信号可能与初始信号x 不同,由这个新的输入又可得到下一步的输出,这个输出
也可能与上一步输出不同。如此下去,网络的整个运行过程就是上述反馈过程的
重复。如果网络是稳定的,那么,随着许多次反馈运行,网络状态的变化减少,
直到后来不再变化,达到稳定状态,此时,在网络的输出端可得到稳定的输出,
可用以下公式表示为:
v j (0)=x j
⎛n ⎫v j (t +1) =f j ∑w ij v j (t ) -θj ⎪ (式1.4) ⎝j ⎭
其中f j 是由(1.1)定义,为方便,一般θj 值取0。从某个时刻t 之后网络状态
不再变迁,既有v (t +1) =v (t ) ,那么,输出有
y =v (t ) (式1.5)
网络神经元状态的演变有两种形式:
(1)串行方式
在某一时刻t ,只有某一神经元N ,的状态按照式(1.4)更新,而其余j-1个神
经元状态保持不变,即
⎛n ⎫v (t +1) =sgn ∑w ij v i (t ) ⎪ (式1.6) ⎝i =1⎭
对于某个特定的j 单元来说,下式成立
2, ,n i ≠) , j (式1.7) v i (t +1) =v i (t ) i ∈(1, …
若以某种确定性次序来选择N ,,使其按照(1.6)变化,称顺序更新;若按照预
先设定的概率来选择神经元N j ,,则称其为随机更新。
(2)并行方式
在任一时刻t ,部分单元按(1.4)改变状态,其中有一种重要的特殊情况是在某
时刻,所有神经元同时按照(1.4)改变状态,即:
⎛n ⎫2, ,n } (式1.8) v j (t +1) =sgn ∑w ij v j (t ) ⎪ j ∈{1, …⎝i =1⎭
这时,可把状态转移方程写成向量形式:
v (t +1) =sgn(v (t ) w ) (式1.9)
2、连续型Hopfield 神经网络
这种网络的每个神经元的输入与输出关系为连续可微的单调递增函数,它的
每个神经元的输入是一个随时间变化的状态变量,它与外界输入和其他神经元来
的信号有直接关系,同时也与其它神经元同它之间的连接权有关系,状态变量宜
接影响输入变量,使系统变成一个随时间变化的动态系统。
连续型Hopfield 神经网络在网络的结构上与离散型相同,其状态方程在形式
上也一样。若定义网络中第j 个神经元N j 的总输入为u j ,输出状态为v j ,那么
网络的状态转移方程可写为:
⎛⎫v j =g (u j )=g ∑w ij x i -θj ⎪ (式1.10) ⎝i ⎭
其中g 为S 型函数,一般常用的有
g 1(x ) =1/(1+e -λx )
g 2(x ) =th (λx )
这两个函数的共同特点是x →+∞。和x →-∞。时,函数值饱和到两极,限
制了网络中状态v j 及流动信息u j 的增长范围。函数g 1,g 2中的参数λ以控制S
型函数在零点附近的斜率变化。函数g 2可看做符号函数。
在网络的整个运行过程中,所有节点状态的演变有异步、同步和连续更新三
种形式。与离散Hopfield 网络比较,多了一种连续更新的形式,表示网络中所有
节点都随连续时间并行更新。网络中状态在一定范围内连续变化。
连续型hopfield 神经网络在时间上是连续的。所以,网络中各神经元是处于
同步方式工作的。考虑对于一个神经细胞,即神经元i ,其内部膜电位状态用u j
表示,生物神经元的动态(微分系统) 由运算放大器来模拟,其中微分电路中细胞
膜输入电容为Ci ,细胞膜的传递电阻为Ri ,输出电压为Vi ,外部输入电流用I i 表
示。神经元的状态满足如下动力学方程:
U i (t ) n ⎧d U i (t ) =-+∑W ji V j (t ) +I i ⎪C i d t R ⎨j =1i ⎪⎩V i (t ) =g i (U i (t )) i =1, 2,..., n (式1.11)
则连续型Hopfield 神经网络模型可用图2所示的电路来模拟实现。
图2 连续型Hopfield 神经网络的电路形式
电路中微分系统的暂态过程的时间常数通过电容Ci, 和电阻Ri 并联实现,
跨导T ij 模拟神经元之间互连的突触特性。
n (V -u ) ⎧du i u i j i +=∑+I i ⎪C i ∙dt R R j =1i ij ⎨⎪V =f u (i )⎩i (式1.12)
n I i 11⎧du i =-u ++∑i j ' ⎪dt R C R C C i j =1i i ij i ⎨⎪V =f u (i )⎩i (式1.13)
其中:
N 111=+∑R i ' R i j =1R ij (式1.14)
v i =V i , τ=R i ' C i , w ij =
可得到: I 1, θi =i (式1.15)R ij C i C i
n du i u i =-+∑w ij v j +θi dt τj =1 (式1.16)
v i =f i (u i ) i =1⋅2⋅3⋅4⋅⋅⋅⋅⋅⋅N (式1.17)
先设定初态(u i ),运行至稳定,得到稳定状态。对应输出:
u i ⎤1⎡v i =⎢1+tan ⎥2⎣u 0⎦ (公式1.18)
微分方程(式1.12)反映了网络状态的连续更新的意义,随着时间的增长变化,网络逐渐趋于定态,在输出端可以得到稳定的输出。
三、实际应用
Hopfield 神经网络有很多成功的应用,这种网络的主要应用形式有联想记忆和优化计算两种形式。用Hopfield 网络解决具体的优化问题,需要按以下步骤进行:
1.对于待定的问题,选择一种合适的表示方法,使得神经网络的输出与 问题的解对应起来;
2.构造神经元网络的能量函数,使其最小值对应于问题的最佳解;
3.由能量函数倒过来推出神经网络的结构;
4.由网络结构建立起网络,令其运行,那么稳定状态就是在一定条件下 问题的解。
对于TSP 问题若用传统的穷举搜索法,则需要找出全部路径之组合,再对其进行比较,找到最佳路径。这种方法随着城市数目的增加,计算工作量急剧增加。这是用传统的串行计算机难以在有限时间内得到圆满解决的问题。在实际应用中,这类问题往往不要求得到严格的最优解,只要是接近最优的解就可以了。 开始首先把问题转化成适合于
Hopfield 网络来解决TSP 问题时体现了人脑的一些特征。开始首先把问题转
化成适合于神经元网络处理的形式。对于n 个城市的TSP 问题,用一个"n ×n ”的神经元矩阵,用神经元的状态来表示某一个城市在某一条有效路径中的位置。 神经元x i 的状态用v xi ,表示,其中x ∈{1,2,⋯, n }:第X 个城市用c x 表示,而i ∈{1,2,⋯,n}表示城市c x 在路径中是第i 个城市。状态v xi =1表示c x 在路径中第i 个位置出现;v xi =0表示c x 在第i 个位置不出现,说明此时第i 个位置上是其它城市。由此可见,n ×n 矩阵v 可以表示n 个城市TSP 问题一次有效的路径,即v 矩阵可以唯一地确定对于所有城市的访问次序。为了保证每个城市只去一次(出发点除外) ,那么关联矩阵v 上每一行只能有一个为1,其它必须为0,对应于每次访问而且只访问一个城市,所以对于关联矩阵的次序上,也是每一列只有一个元素为1,其它为0,全部非0元素的总和为n 。例如n=6,则一次有效路径可能构成v 矩阵如下表1所示。
表1 城市TSP 问题中一次可能的路径
由上表可见,访问次序为C 2→C 4→C 3→C 1→C 6→C 5,(最终再回到C 2)。由访问次序就可得到路径的总长度,对于这个例子来说,路径的总长度l 为:l =l 24+l 43+l 31+l 15+l 56
为了解决TSP 问题,必须构成这样的网络:在网络运行时,计算能量降低。网络稳定后其输出状态代表城市被访问的次序,即构成表1所示的换位阵。网络
能量的极小点对应于最佳或者较好的路径的形成,此时由输出换位阵能得到较好路径。
解决问题的关键一步是构成合适的能量函数。针对路径有效性,为了保证输出换位阵,因此有约束条件:
A n n n
E 1=∑∑∑v xi v xj (式2.1) 2x =1i =1j =1, j ≠i
其中A>0为常数。E 1保证当矩阵V 的每一行不多于一个1时,E 1达到最小E 1mi n =0。
同理构成列约束条件为
B n n n
E 2=∑∑∑v xi v yi (式2.2) 2i =1x =1y =1, y ≠x
其中B>0为常数。E 2保证当矩阵V 的每一列不多于一个l 时,E 2达到最小E 2mi n =0。
构成全局约束
E 3=C
2∑∑v
x =1i =1n n 2xi -n (式2.3)
其中C>0为常数。E 3保证当矩阵V 中的1的个数恰好为n 时,即整个矩阵有n 个1时,E 3达到最小E 3min =0。
式(2.1)、(2.2)和(2.3)之和达到最小时,能保证网络输出状态矩阵V 构成换位阵。 考虑路径的合理性,此项定义中应包含有效路径的长度信息,此项定义为
D n n n
E 4=∑∑∑l xy v xi (v y , i +1+v y , i -1) (式2.4) 2x =1i =1y =1, y ≠x
其中D>0为常数。下标运算定义为类似于以下的取模运算
k +r 若k +r ≤n
(k +r ) mod = n +k +r 若k +r ≤0
-n +k +r 若k +r >n
r 为模式平移量。表示一维模式平移r 位,往左移r 为正,往右移r 为负。原模式x 中的元素x i ,x k 现在移动为x i +r ,x k +r 。
这样从路径最后一个城市到第一城市的距离也包括在式(2.4)中。E 4实际数值就是一次有效路径总长度的倍数。若路径为最佳时,E 4达到最小点。若路径为较好时,E 4达到极小点。所以,构成用Hopfield 神经网络求解TSP 问题的能量函数为:
E =E 4+E 1+E 2+E 3
=∑∑∑d xy v xi (v y , i +1+v y , i -1) +
x y ≠x i C (∑∑v xi -n ) 22x i
(式2.5) +A B v v +v xi v yi ∑∑∑∑∑∑xi xj 2x i j ≠i 2i x y ≠x
将上式和Hopfield 神经网络电路标准能量函数公式
n n 1n n 1E (t ) =-∑∑W ji V j (t ) V i (t ) -∑V i (t ) I i +∑2i =1j =1i =1i =1R i ⎰V i (t ) 0g -1(V ) d V (式2.6)
相比较可得到神经元x i 与y j 之间的导纳值(相当于权系数) 为:
T xi , yj =-A δx , y (1-δi , j ) -B δi , j (1-δx , y ) -C -Dl xy (δj , i +1+δj , i -1)(1-δxy ) 其中δij 和δxy 定义为: (式2.7)
δi , j =⎨⎧1i =j
⎩0其它
其中偏流(外加激励)为
I xi =CN (式2.8)
将式(2.7)和(2.8)代入网络状态方程中,得到:
⎧dU xi ⎛⎫U xi =--A ∑v xj -B ∑v xj -C ∑∑-N ⎪-D ∑l xy (v y , i +1+v y , i -1) ⎪C xi dt R xi ⎨j ≠i y ≠x y ≠x ⎝x y ⎭⎪⎩v xi =g (u xi )
10
其中u xi 为神经元的时空综合输入,v xi 为其对应的神经元的输出,两者关系为: 当网络节点输出为连续型时
v xi =f (u xi ) =1
1+exp ⎛ -2u xi ⎫
⎝u ⎪
0⎭
当网络节点输出为离散型时:
v ⎧⎨1u xi ≥0
xi =⎩0u xi
其运行结果写入到Debug 文件夹下的result.txt 文件中。部分截图如下:
11