再上一篇:6. 4  其它遗传操作
上一篇:6. 5  习题
主页
下一篇:7.2  应用启发式搜索算法求解 TSP
再下一篇:7.3  应用模拟退火算法求解 TSP
文章列表

第 7 章  旅行商问题

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

在解决TSP 问题时,霍氏网因以大百分比生成无效解答而著称[11][138]。这是由于霍普费尔德能量函数,即等式(3.22)的参数选择得不好而造成的。这一章考察霍氏网经常失败而不能生成有效解答的原因,并给出改进的方法。前面各章介绍的不同算法在解决TSP中的应用也将在本章加以比较。选用TSP 进行算法比较是因为它有大量潜在应用,已被许多研究人员用为测试基准,并是一个众所周知的重要NP 完全问题。

7.1  为什么霍氏网经常不能生成有效解答?

这一节考察霍氏网在解决TSP 时的特点和动态特性以说明上述缺陷的原因。最关键的分析(引自[11])是基于对霍氏网稳态、霍普费尔德能量函数以及连接性矩阵的特征值之间关系的理解。回想第三章中给出的霍普费尔德能量函数

1 T T

E(S) = - 2S WS- I S (7.1)对称的N× N 连接矩阵W的特性完全由其本征值λi和正交本征向量ei决定,其中i= 1,2,…,M,而M是不相重复的本征值个数,且M≤N。一些本征值会退化为一个单一的值(即多重本征值)。在这种情况下,与此本征值相对应的就不再是一个本征向量了。取而代之的是一个子空间,称为该本征值的本征空间。另外,W可包含一个对应于退化到零的本征值的一个零空间。因此,每个向量都可以用W的本征向量/本征值以及零空间来表达:

M

S = si+ q (7.2)

i= 1

其中 i= i= i i, ∈ ( ),且 ( )是 的零空间。同理,

s Se λe q N W N W W

M

W= λiei(e)i T (7.3)

i= 1

为简化起见,忽略外部输入,可得

1 M 1 M 1 M

E(S) = - λiSTe(e)i i TS= - λi‖S¡¤e‖i 2= - λi2 (7.4)

2∑ 2∑ 2∑

i=1 i= 1 i= 1

注意,当

(1) γi对于λi> 0取最大值;

(2) i对于λi< 0被置零。

能量函数E(S)最小化。

如果网络按照上述原则改变S,则S移动的方向会越来越偏于较大的正数本征值。由于S 是以单位立方体为约束的,当S= γmaxemax时能量最小,其中emax是对应于最大正数本征值的本征向量。

#第58页-

让我们回到3.4.1节中讨论过的TSP 的连接矩阵W。回想每个神经元变量都是双下标的,而连接矩阵的元素都是四下标的。然而,从(7.1)式可知,S是一个向量而W是一个矩阵。这是否暗指某种表示方式的不一致呢?事实上,这纯粹只是表达上的取舍不同而已。只要知道了解答向量S可由一行行依次排列的{sXi}如下构成,本征值分析同样可以适用。

s11

s12

s1N

S= s21 (7.5)

s2N

sNN

在(3.22)式的第三项中不多不少正好有对应于旅程中N 个城市的N 个神经元处于激活状态,根据这个前提,(3.22)~(3.24)式给出的霍普费尔德能量函数可由N 取代N而改写为

E = A sXisXj + B sXisYi

2∑∑∑ 2∑∑∑

X i j≠i i X Y≠X

C 2

+ ∑∑sXi- N

2 X i

D (7.6)

+ ∑∑∑dXYsXi sY,(i+ 1) + sY,(i- 1)

2 X Y≠X i

1 C 2

= - ∑∑∑∑wXi,YjsXisYj - C∑∑NsXi+ N

2 X Y i j X i 2

其中

wXi,Yj = - AδXY(1- δij) - Bδij(1- δXY) - C- DdXY(δj,i+ 1+ δj,i+ 1) (7.7)基于第3章中所述的原因,(7.6)式中的最后一项可被忽略。连接矩阵W的前三项对应于约束,而最后一项则对应于TSP 的代价。一个无效解答使得(7.7)式的前三项中有一项或多项异常。因为前两项引入的是分别作用于sXi的行和列上的相似的约束,它们应有相同的权值,因此A= B。另外,由于只有前三项决定是否能得到有效解答,本征值分析最初是在去掉最后一项的连接矩阵上进行。由这些假定出发,连接矩阵变为

wXi,Yj = - AδXY(1- δij) - Aδij(1- δXY) - C (7.8)可以证明(7.8)式给出的连接矩阵W具有下列三个不同的本征值:

(1) 1= - 2- 2 ( - 1)对应的本征向量为

λ CN A N

1

1 1

e = ┆

1

#第59页-

(2) λ2= 2A对应于一个本征空间,称为有效子空间。亦即每一个有效解答都属于这一本征空间。

(3) λ3= - A(N- 2)对应于一个同时正交于e1 和有效子空间的本征空间。

7.5节给出了对本征值分析的概述,λ1的推导则作为7.6节中的例子。2 和λ3 的推导则留作习题(7.2和7.3)。

7.1.1  霍氏网的动力学

霍氏网在解决TSP 时的动态特性取决于下式:

¡¤ d

u= WS+ I 或 uxi= ∑∑wXi,YjsYj + CN (7.9)

dt Y j

其中

sXi= ζ(uXi) = 1 1+ tanh uXi (7.10)

2 β

霍普费尔德和坦客[86]选用的是 = 0.05。在揭示出 的本征值和本征空间与外部输

β W

入I 是怎样一起影响着・使S从超立方体中的一个点转移到一个最终解答的移动方向。就有可能预计网络到达有效解答的条件。因此,拉格朗日参数可被优化以确保网络收敛于有效解答。对(7.10)式进行泰勒级数展开可得

1 uXi

sXi= ζ(uXi) = 2 1+ tanh

β (7.11)

uXi 3 3

= 1 1+ - 1 uXi + 2 uXi - …

2 β 3 β 15 β

当uXi较小时,

β

2sXi= 2ζ(uXi) ≈1+ uXi (7.12)

β

它是一个线性方程,且有

dsXi 1 duXi ¡¤ ¡¤

2 dt ≈ β dt uXi≈2βsXi (7.13)

dsXi ¡¤

2β = wXi,YjsYj + CN 或 2βS= WS+ CNe1 (7.14)

dt ∑∑

Y j

将解答向量 分解为三项: 有效空间项 val,无效空间项 inv以及沿 1方向的 1 项:

S S S e S

S= S1 + Sval + Sinv (7.15)其中

1 1 1 1 1 T

S = (Se^ )^e ,^e = [1  1  …  1] ,

N

Sval∈ 有效子空间,且

Sinv∈ 无效空间

因此,

WS = λ1S1+ λ2Sval + λ3Sinv (7.16)

¡¤ 1

2βS= WS+ CNe

#第60页-

= λ1S1 + λ2Sval + λ3Sinv + CN2e1

= [CN2 + λ1(S^e1)]^e1+ λ2Sval + λ3Sinv

2 2 1 1 (7.17)

= [CN - (CN + 2A(N - 1))(S^e )]^e

+ 2ASval - A(N - 2)Sinv

・ 1

如果S使得S 向有效子空间移动而离开^e 和无效空间,则最终解答很可能会在有效空间。换句话说,

・ 1

(1) S的^e 项将S移向如下超平面:

CN2- (CN2 + 2A(N - 1))(S^e1) = 0 (7.18)迫使最终解答处于这一超平面。

(2) 因为 2= 2 > 0,・使得 向其有效子空间项靠近。这使得该项的幅值增大。

λ A S S

(3) 因为λ=3 - A(N- 2),S使得S向着远离其无效空间项的方向移动。因而该项的幅值会减小。

上述步骤可以确保霍氏网的能量最小化。回想霍氏网的能量函数为

1 T T

E(S) = - 2S WS- I S

2E(S) = - λ1‖S1‖2 - λ2‖Sval‖2 - λ3‖Sinv‖2 - 2CN2(^e1S)

= - λ1‖S1‖2 - 2CN2(^e1S) - 2A‖Sval‖2 + A(N - 2)‖Sinv‖2

2 2 2 2

1 CN (CN ) val 2 ¡¤ inv 2

= - λ1 ‖S ‖+ λ1 + λ1 - 2A‖S ‖ + A(N - 2)‖S ‖

2 2 2 2

2 1 CN (CN )

= (CN + 2A(N - 1)) ‖S ‖+ λ1 + λ1

- 2A‖Sval‖2+ A(N - 2)‖Sinv‖2 (7.19)由于A,C和N 都是正数,E(S)在如下情况下最小化:

CN2 CN2

‖S1‖= - = (7.20)

λ1 2

CN + 2A(N - 1)

‖Sval‖→∞ (7.21)

‖Sinv‖→0 (7.22)这与前面的讨论是一致的。显然,当©¦©¦ 大时,(7.13)式所给出的近似不再有效。然而,在©¦©¦ 大到足以破坏这种近似之前,©¦©¦ 多数情况下应该已经大致指向超立方体中处于有效子空间的顶点。为了确保这一情况的出现,我们可以从一个使得这种近似即(7.13)式有效的小幅值S出发,然后将其推向有效空间。当©¦©¦ 大时,非线性迫使网络稳定在有效空间的超立方体的顶点上。

当S向超平面移动时,由(7.18)式可得

(S^e1)(CN2 + 2A(N - 1)) = CN2

1 2A(N - 1) 2

(Se) CN + N = CN

2 (7.23)

1 CN N

(Se) = 2A(N - 1) = 2A(N - 1)

CN + 1+ 2

N CN

#第61页-

(7.23)式将稳态下被激活的神经元个数量化了。由于A> 0且C> 0,被激活的神经元个数小于N。这就满足了由(7.6)式中能量函数第三项给出的前提条件: 网络的最终解答有刚好N 个神经元被激活。这就是霍氏网经常无法收敛于有效解答的主要原因。这也是为什么霍普费尔德和坦客在解决他们的10城市TSP 时选用N= 15而不是N= 10的原因。网络不能到达有效解答的另外一个原因是λ1 和λ3 的限制效应与外部输入CN 之间以及它们与λ2 的扩张效应之间平衡得不好。换句话说,参数A与C选得不好。

7.1.2  拉格朗日参数的另一种表达方式

霍普费尔德和坦客在文献[86]中所选用的拉格朗日参数是通过实验获得的。不过,基于前述分析,可以开发出一种更稳健的方法以获取这些参数的值。将W和I 影响网络动态特性的成分分离出来,就可以推导出一个能够确保网络收敛于有效解答的拉格朗日参数的数学表达式。网络的动态特性在相当大的程度上是由具有如下效应的三个本征值λ1,λ2 和λ3 来决定的。

・ 1= - 2- 2 ( - 1)在理想情况下将 限制在由 1= 决定的子空间中。然

λ CN A N S Se N

而,从(7.23)式可知,Se≠N。因此,为使Se=1 1 N,λ1 应该刚好等于- CN2。这可由给W的每一项加上2 ( - 1)/ 2 而得到。

A N N

・ 正如(7.19)~(7.22)式所显示的,λ2= 2A 具有将S 经由有效子空间移出超立方体边的扩展效应,而λ3= - A(N- 2)则具有通过将S 从无效空间“反弹”回来从而将其约束于有效空间的限制效应。

为了引入一个附加的自由度以便更好地协调上述效应[11],从 的主对角线上再额外

W

减去一个常数2 1,相当于从 的每个本征值减去2 1。然而,要保证 1= - 2 必须在

A W A λ CN

的每一项上进一步加上2A1。经过如上调整,连接矩阵 被变换为

W N2 W

wXi,Yj = - AδXY(1- δij) - Aδij(1- δXY) - 2A1δXYδij

2(AN - A+ A1) (7.24)

- C+ 2 - DdXY(δj,i+1 + δj,i- 1)

N

且IXi总被置为CN,其中N 是城市个数。另外,B= A。相应的本征值为

λ1 = - CN2 < 0

λ2 = 2(A- A1) > 0

λ3 = - AN + 2(A- A1) < 0

像以前一样,这些本征值的正负号应该是一样的。一般来讲,由于解答在不受“限制”时变为无效,限制效应应该比扩展效应要求更严格。因此,埃亚(Aiyer)等人在文献[11]中建议©¦1©¦ 160©¦2©¦ ©¦3©¦ 160©¦2©¦ 到目前为止,我们只讨论了与“约束”条件有关的拉格朗日参数。如果不强行引入“代价”项,最终解答将是有效的,但却可能与最优解答南辕北辙。因为具有最小代价的旅程通常并非有效,这一代价项无疑将在网络的动态特性中引入使得S离开有效空间的分量。因此,D 的取值应使其影响远小于限制效应λλ1, 3 和I。通过实验,埃亚等[11]建议 = ©¦3©¦80。在连接矩阵本征值的大小与步进值 的大小之间需要有

D Δt

所权衡。实验数据表明,Δt 的值应该小到足以使得u在每一步(迭代)中的任何改变都小

#第62页-

于5%。总之,

A1 ≈A 1- N (7.25)

322

C≈ A (7.26)

N

D≈AN (7.27)

80

埃亚等[11]建议的用于求解10城市和50城市TSP 的参数分别为

10城市: A= 8;A1= 7.75;C= 0.80;D= 1;Δt= 0.02。

50城市: A= 8;A1= 7.75;C= 0.16;D= 5;Δt= 0.05。

7.1.3  霍普费尔德的 10城市问题

回顾第3章介绍的霍普费尔德10城市TSP。图7.1(a)给出了这10个城市的分布,而图7.1(b)则给出了对应于最短旅途2.691的旅程。由于拉格朗日参数选择得不适当,正如读者在解决习题3.7时已经体会到的,这一霍氏网以很大百分比生成无效解答。使用上一小节中建议的求解10城市问题的参数,生成的解答几乎100%有效。为了验证这些参数和(7.13)式给出的线性近似,这里介绍四组对应于四种非线性的模拟实验。其中一个非线性是如下定义的软限幅:

图7.1  霍普费尔德的10城市问题及其最短旅程

x+ 0.5 ©¦©¦≤0.5

ζ(x) = 1 x > 0.5 (7.28)

0 x < - 0.5

它是线性化近似的一种合理选择。另外三个非线性对应于令(7.11)式中β= 0.02,0.3和2所得的Sigmoid函数。这四个非线性的比较可见图7.2。对于每个非线性,从随机起始条

#第63页-

件出发模拟运行1000次。每次模拟都在下列条件之一满足时终止:

图7.2  四种非线性

(1) 霍氏网中的每个神经元无一例外地取值在[0.9,1]或[0,0.1]之中,分别对应于

神经元处于“激活”(取值落在[0.9,1]中)或“抑制”(取值落在[0,0.1]中)的状态。

(2) 模拟运行已经迭代了多于100000次扫描。

表7.1~7.3分别总结了软限幅以及对应于β= 0.3和0.02的Sigmoid非线性的模

拟运行结果。表中,出现次数指每1000次模拟中出现的次数,最小次数指获得解答所用的

最小扫描次数,最大次数指获得解答所用的最大扫描次数,平均次数指获得解答所用的平

均扫描次数,标准偏差指扫描次数的标准差,而旅程自然是指访问城市的顺序。图7.3中

的直方图描述了选中旅程的出现频率随旅途长度的变化。在β= 2的Sigmoid非线性情况

下,网络给不出任何有效解答。从图7.2可以看到,这是因为网络中的神经元无法收敛于

它们的稳态( 激活”和“抑制”)。相反,利用软限幅的霍氏网取得100%的有效解答,其中

76.7%对应于图7.1(b)所示最短旅程,且网络达到最佳解答所需的平均扫描次数为464。

其它有关软限幅霍氏网的统计数据可见表7.1。软限幅霍氏网在四个非线性中的出众表

现归功于软限幅与线性化近似极度相似。利用β= 0.3的Sigmoid非线性,网络生成的有

效解答占99.9%,其中55.5%获得最短旅程。当β= 0.02时,Sigmoid非线性接近硬限幅

因而收敛得更快。在这种情况下,网络生成的有效解答占58.2%,其中1.9%获得最短旅

程。图7.4给出了一些不同的旅程。

表7.1  利用软限幅求解10城市问题的统计

100%有效解答 旅程长度 出现次数 最小次数 最大次数 平均次数 标准偏差 旅  程

最优 2.691 767 299 1366 464 127 BCADEFGHIJ }

次优 2.752 73 366 1423 640 239 BCADEGFHIJ }

第三 2.769 5 475 616 547 57 BADEFGHIJC f

最差 3.658 1 670 670 670 0 ACBJEFGHID f

#第64页-

图7.3  利用软限幅和Sigmoid非线性求解霍普

费尔德10城市问题的旅程个数直方图

#第65页-

图7.4  各种有效旅程

表 7.2  利用β= 0.3的Sigmoid非线性求解10城市问题的统计

99.9%有效解答 旅程长度 出现次数 最小次数 最大次数 平均次数 标准偏差 旅  程

最优 2.691 555 289 896 405 83 BCADEFGHIJ f

次优 2.752 134 339 683 492 103 BCADEGFHIJ f

第三 2.769 38 340 605 436 64 BADEFGHIJC f

最差 3.697 1 2026 2026 2026 0 AJGFHEDICB }

#第66页-

表7.3  利用β= 0.02的Sigmoid非线性求解10城市问题的统计

58.2%有效解答 旅程长度 出现次数 最小次数 最大次数 平均次数 标准偏差 旅  程

最优 2.691 19 7 21 13 4 BCADEFGHIJ O

次优 2.769 1 20 20 20 0 BADEFGHIJC O

第三 2.778 225 6 25 25 3 ABCDEFGHIJ O

最差 4.737 1 11 11 11 0 AEFBGHICJD O