（计算机应用技术专业论文）自动波方法求解tsp问题.pdf

摘要 摘要 旅行商问题( t s p ) 是一个有着重要工程背景、在图论中的典型组合优化问题， 己被证实是一个n p 完全问题。本文将解决t s p 问题转化为一种特殊的最短路问 题。通过构造耦合神经网络，使得由神经元点火所产生的自动波在其中传播，最 先到达目的地的波前所走过的路径即为最短路问题的最优解，从而有效地获得了 t s p 问题的最优解。本文深入研究了神经网络的构造，其中的耦合特性、波动特 性以及网络中存在的多波现象和为得到旅行商旅行所需路径的标记等。与传统的 t s p 问题求解方法相比，本文方法所找到的是t s p 问题的最优解。本文还对所提 出方法的时间和空间的复杂度给出了说明，最后大量的实验算例证明了本文方法 的正确性和有效性。 关键词：t s p 问题最短路耦合神经网络自动波多波现象 a b s t r a c t a b s 仃a c t t h et r a v e l i n gs a l e s m a np r o b l e m ( t s p ) i sat y p i c a lo p t i m i z a t i o np r o b l e m ，w h i c h b e l o n g st oal a r g ef a m i l yo fp r o b l e m sc l a s s i f i e d a sn p c o m p l e t e i th a st h ei m p o r t a n t p r o j e c tb a c k g r o u n d t h i sp a p e r d e a l sw i t ht s pb yt r a n s f o r mt s pt oas p e c i a ls h o n e s t p a t hp r o b l e m p a s s i n gt h r o u g ht h ec o n s t r u c t i o no fas p e c i a lc o u p l e dn e u r a ln e t w o 如 w h i c hc b a x _ m i m i ct h ea u t o w a v e si nt h ep u l s e - c o u p l e dn e u r a ln e t w o r k s ( p c 酉r n s ) ，w e p r e s e n tan e wa p p r o a c h ( a u t o w a v e sa p p r o a c h ) f o rs o l v i n gt s p t h ea u t o w a v e ss p r e a d i nt h en e t w o r k , a n dt h e p a t hw h i c h t h ef i r s ta r r i v e da tt h ee n d p o i n tf r o m t h es t a r tp o i n t h a sp a s s e di st h eo p t i m a la n s w e rt ot h es h o n e s tp a t hp r o b l e m a n dt h e nw ef i n dt h e a n s w ft ot h et s p t h i sp a p e rd i s c u s s e dt h ec o n s t r u c t i o no fn e u r a ln e t w o r k s a n dt h e n i n v o l v e st h ec o u p l e dc h a r a c t e ri nt h en e u r a ln e t w o r k s ，w a v e t h e o r y , m u l t i p l ew a v e s ，a n d r o u t em a r k e r c o m p a r i s o nw i t ht f 删。枷m e t h o d t h ea u t ow a v e sm e t h o dc a i la l w a y s f i n dt h eo p t i m a la n s w e rt ot h et s et h i s p a p e r a l s os h o w st h et i m ea n d s p a c e c o m p l e x i t yo ft h e a u t ow a v e sa p p r o a c h 。f i n a l l y , e x p e r i m e n t so n s o l v i n gt s pa g e p r e s e n t e d k e y w o r d ：t s p s h o n e ap a t hp r o b l e m c o u p l e dn e u r a ln e t w o r k s a u t ow a v e s m u l t i p l ew a v e s 。一 创新性声明 y 5 8 3 3 8 4 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人豁蜇，翌同期翌堂：! ：乡 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期f 刨论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为题安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 - v ，密 本人签名： 匀， ：! 逛 日期 趋! 生z ! 至 导师签名：i 鳖曼墨日期丝丝! ：圭 绪论 旅行商闻越( t s p ) 是很缝典盼缀合优纯孀题，它直愚计算机科学、运筹学、 地理值息科学等学科蚋个研究热点，国内外大量专家学者对此问题进行了深入 研究。经典的图论与不断发蕊完善鹩计算梳数据结搦及算法的有效结舍使褥新酶 t s p 算法不断涌现，窀们在空间复杂皮、时间复杂度、易实现性及应用范围等方面 各具特色。蕊阶段t s p 算法静磷究发装方向是并行髓。 t 9 9 2 年以j o h n s o n 为先驱熬于生物视觉枣串绞系统的王终原理提出了脉冲耦合神 经网络模型( p r i s ec o u p l e dn e u r a ln 酏w o r k r 巾c n l 哪，p c n n 是由若干个脉冲耦合 神经元互连所鞫成的反馈型嬲络。与传统豹反馈型神经网络蝴比，p c n n 从神经元 的构成本身就具有鲜明的特色：交阚值特性、内部行为的泵积藕合特性、分支树 豹漏电骞积分加权求和特性等。这些4 哮性使褥p c n n 谯包括级含优化凳n 图像处理等 多个领域都有着良好的应用前景。p c n n 神疑元静积分点火特性及丰唪经元岛神经 元之间的脉冲耦合特性，使梅其具裔个独特的特性：在棚匿连接的神经元之间 存在麓蠢动波现象。 本文主要慰骤挣凝台神爨蹲终在傀纯方蘧的应用避霉亍了研究，这项研究受到国 家自然科学基众( n o 6 0 0 7 1 0 2 6 , n o 6 9 9 7 1 0 1 3 ) 、国赡科技预研藏金 ( o o j l 4 4 。d z 0 1 0 6 ) 、圈像信息处理与智能控粼禺家教委开放实验室辨放研究蕊金 ( n o t k l j 0 0 0 5 ) 资助。 农对熬狰糕会耪筑翅终麴鑫动波憋经进露分褥鹣豢秘土，张搴荚教授提墩了辘 出闽值耦合神经网络，构造该网络模型实现了对自动波的横拟，并将该模型应用 到了袋解组会缆纯巾鹣最短路滔题，获终了缀大熬残渤。 我们对此输出- 阂值耦合神经网络作了相戚的修改，并提出了一种新的t s p 求解 算法鑫动波方法，该方法箕骞簧襻淫嚣帮靠往鼯、大糕模并孬谛舞等特点， 可用于求解对称、非对称赋税图的t s p 问题。与目前其它求解t s p 问题的方法相比， 謇动波方法魏行更菇楚攀，誉嚣要太多a 秀瓣选择参敲等| ；毒惩，显不存在嚣部极 小点的问题，求得的解全部怒最优解。其所滞的计冀量( 迭代次数) 和时间复杂 发主袋壤凌予最短露麓瓣长震。 但是当t s p 的规模达( 赋敉图中顶点和边的数量) 到一定程度的时候，由于存 储复杂度造成的簿闯爱杂度燕无法窖忍的，掰l ；乏我们辩该方法又散了一些箕他鲍 改进，比如：删除波动过程中，传播相对较幔的自动波、分解再会并( 即将大型 的t 黯游题转纯成若千个，、豹f s p 阕鼷求解) 簿等。 2 自动波方法求解t s p 问题 我们进行了大量的随机数据实验，并对著名的h o p f i l e d & t a n k1 0 个城市的数据 进行了实验，都得到了相当满意的结果。最后，我们用分解再合并的方法对3 1 - c t s p 的问题进行了计算，用不到一秒的时间找到了解，该解是目前公布出来的最优解。 第一章t s p 问题简介 第一章t s p 问题简介 本章介绍了t s p 问题概况，给出了t s p 算法的编码策略及评价标准。蠢此基 础上，重点介绍了求解t s p 问题的几个方法：穷举法、贪婪法、h o p f i e l d 网络法、 遗传算法、蚁群算法，并对迭凡个算法进行了分析，疆出了它们酶徒越性以茂不 足之处，最屉指出了t s p 问题的实际应用价值及研究前景。 1 1 t s p 闯题概况 t s p 问题( t r a v e l i n gs a l e s m a np r o b l e m ) 也称旅行商问越、货郎搬问题，该问 遥是凌1 9 3 2 颦爱德蓬麓名数攀黎x 越m e n g e r 撵遗熬。其实了黯溺题最纂麓遥羧戮1 8 世纪的欧拉年代，而腹到了2 0 世纪中叶，由予优化技术的兴趣更加为人们所激视。 特别怒鸯它教涯弱是措完全( n p 。c o m p l e t e ) 涟毽劳鸯v l , s i 测造、翰溪警遴镳设、 电路布线等阅题有关以及所考虑问腹规模的不断增太时，对该问题的研究曰渐深 入 i , 2 , 3 1 。这么多年来t s p 避题一壹是谗多入废鹱惠食磺究熬辩象。t s p 逶蓬撬遂为： 假设村一个旅行商人疆拜访”个城市，他必须选择所鞭走的姆径，路径的限制是每 个域赘酆磐绥拜访虽只能拜访一次，嚣且最蕨罴要暇剿薅l = j l 乏鹅城枣。路径的选择 目标遐路径的总长度为所有路径之中的最小俊。 糯在t s p 弱题是数学领域蠹缀鸯名熙阕鼹，英数学搓遮懿下：设鸯令坡蔻襄 合c h ，气，q ，麒每对城市q ，q c i d ( c 。，c ，) z + 。求一条经过c 中每个壤枣菠好一次瓣路径( ) ，岛( 癣) ，使褥 - i 毋( 咚秘，靠8 + 1 ) ) + 硝毂枷，以撙) i l 最小。这毽g 髫秘，筇( 窃是( ，2 ，璃熬一令鬟挟。璐巢愚嚣谂语言，t s p 问题述可描述为：设g = ( v ，a ) 是一个图，此处矿是鼹有，个顶点的集合，爿称为 弧或边集；d = 撼) 熄与关联豹疆凑或费爝矩薄。t s p 就是簧决定条经过疑有 顶点暇好一次( 这样的回路称为一条路径或h a m i l t o n 网路) 且距离最短的回路。若 对予谯意i ，歹v 有或= 蠢。，煲| j 该闽鼷禳为对抟豹t s p ，否粼称隽；# 慰稼鹣t s p 。 若对于任意f ， k v 肖如+ d * 2 屯，则称费用矩阵c 满足三角不等式。当v 磁r 2 且咴为，帮歹阀的直线距离孵，该闯越称为乎西( 或e u c l i d ) t s p i h 题。此类闯题 的费掰矩阵满足三角不等式。 彳s p 趣题怒这么餐荔爨自，哥是要筏窭一个行之鸯效熬簿答方法，嚣蔻势不存 在。在2 8 年前，美国的管理科学( m a n a g e m e n ts c i e n c e1 9 6 3 ) 一篇讨论“旅行 4 自动波方法求解t s p 问题 商问题”的文章就说道：“人类由于他的运算能力的限制，在解决旅行商问题上并 不好。”人们现在对于这问题的实际情形都是借助高速的计算机来运算。 1 2t s p 算法的编码策略及评价标准 1 2 1t s p 算法的编码策略 t s p 算法设计的一个重点就是设计回路编码1 3 。7 j ，t s p 的编码策略主要包括二进 制表示、近邻表示、次序表示、路径表示、矩阵表示和边表示等。由于二进制表 示不自然且需要额外的修正算子以保证个体的合法性，在实际中很少使用，在此 我们将不作介绍。而路径表示自然、直观，且易于加入启发式信息，是用得最多 的一种表示策略。下面的讨论将以9 个城市的t s p 为例。 近邻表示将路径表示成, 个城市的一个排列，且在第f 位城市为，当且仅当路 径中从f 所到达的下一个城市为，。例如，排列( 2 4 8 3 9 7 1 5 6 ) 即是表示下列的路径： i - 2 呻4 - - 3 8 05 9 _ 6 - + 7 。显然，每一条路径都唯一对应于一个近邻表 示，然而，任一近邻排列却不一定都对应于合法路径。如近邻排列：( 2 4 8 1 9 3 5 7 6 ) 却导致不完全回路1 - - - 2 - - 4 - - ) l 。这将无法对应一条合法路径，从而需要算法加 以修正。采用近邻表示的优点是它比较适合模式分析，例如，模式( 3 + 7 十 + ) 表示所有含有边4 _ 3 和6 叶7 的路径集合；缺点是操作比较复杂，因此，算法 的性能较差1 4 j 。 次序表示仍将路径表示成, 个城市的一个排列。该排列的第i 个元素在l 至 n i + l 间取数。其表示方法为：先取城市集合c 的顺序排列如c = ( 1 2 3 4 5 6 7 8 9 ) 作 为次序排列的一个参照点，然后按路径中城市处在c 中的位置确定表示串中的点， 每确定一个，便删除c 中相应的城市。如路径l 斗2 4 3 _ 8 - 争5 4 9 9 - + 6 _ + 7 其次序表尔为( 1 1 2 1 4 1 3 1 1 ) 。次序表示的主要优点是不会产生非法路径。文献【4 】 中的实验表明，采用次序表示的算法性能也不尽人意。 路径表示直接采用城市在路径中的相当位置来进行表示。例如，路径 5 - - l 一7 - - - 8 6 - - 2 - - 9 - - 3 - - 4 - - 5 直接表示成( 5 1 7 8 6 2 9 3 4 5 ) 。路径表示的 优点是表示方法自然、直接，容易让人理解和接受，而且操作起来也方便。所以， 路径表示也是目前t s p 算法中最常用的回路编码策略。 此外，有些作者提出了矩阵表示 5 , 6 3 1 和边表示 8 , 9 , t o l ，他们提出这两种表示方法 的依据是：上述的几种表示方法中主要考虑t s p 中城市的相对位置与次序，而忽略 了连接城市的边。有人指出 5 1 ：城市在一条路径中所处的位置并不重要，而它与其 第一章t s p 问题简介 它城市相连所组成的边可爻我们构造更好的路径指贸方向。函诧，较好酶表示应 尽可能地利用父体所提供豹穗效边的信息。也就是说，他们认为t s p 的基本构造块 是边黼不是城市所箍的位嚣。 矩赡表示憋一条鼹经表承畿一个抖x n - 避制矩簿，其存储囊越城帮规模姻增如 而迅速增长，而且j f u 用城市躐离信息也不充分。边袭示是以组成路径的边来表示 一条路径。这样，因路径是一条回路，城市在一条路径中鲍摆对位鬟已不鬟要。 同时，城市谯边中的方向也光关，如1 哼3 和3 呻1 郝表示同一条边，所以逾袭示 只适用于求解对称t s p 闯题。 1 2 2t s p 算法的评价标准 辣法的性能不仅鼹其控制参数的影响，而且与算法的实现者及算法的试验平台 等套荚。在t s p 懿磅究孛，露襞器下述嚣釉葵法穗戆戆谬徐辕准； 期望慎估计法：这种方法适用于随机产生的e u c l i d 平筒t s p ，是由h e l d 和 嘲在文熬l l ”孛掇爨戆。慰这样瓣t s p ，其攒豢漫短黪经豹长度爻 r = 詹，吠。此处刀悬城市的数目，尺是一个难方形的面积，在随机布点时， 各辕常馨敷予该正方形之内；j i 是一个经骏俊，称麓h e l d k a r p 下赛。已 有试验表明【1 2 j ，城市效刀不同时，| 值也稍有水同。文献嘲中采用七= o 7 6 5 。 溅试集法：使建鑫缀多骚襄橼德荨久舞建交熬一个t 瓣霹强。在该凑串， 有很多研究人员用各种方法计算过的t s p 问鼷，通常迩提供穗知的最短路 径与长度。这个t s p 摩在缀多网点都可找到。例如， f t p ：s o f l h b r i e e e d u t m b t s p l i b t s 盛b , t a r z 。 我们在做3 1 - c t s p 中国3 1 个城带的t s p 嗣题) 姆题的仿真实验豹对候，煺到 的评价标准就是测试集法，农后面的擘节会介绍。 1 3 鬻觅的球解t s p 算法简夯 1 , 3 1 常冤懿凭释方法禳鬟 爨黪基经蠢摄多求薅零静| 蘧遂熬方法，艇莲零主鄹是隶烬攀s p 透觳羧往鳃懿算 法。常见的求解t s p 问题的算法主要商：穷举法、贪螫法、h o p f i e l d 网络法、遗传 算法、蚁群冀法等。缀然毒这么多方法，毽怒这些方法蓼琴是理想瓣，蘩暴爽憝 找到一个理想的方法，那么成果将是轰动世界的。 6 自动波方法求解t s p 问题 1 3 2 简单的方法：穷举法和贪婪法 穷举法是最容易实现的方法，而且如果能够求得结果的话，肯定是最优解。但 是正如我们在第一节所说的，t s p 问题看起来简单，但是求解实现的时候却是令人 头疼的。对于n 个城市，我们知道可能存在的路径有( 一1 ) ! 2 条，每条路径要计 算个距离之和。这样，要计算各种可能路径及其距离的计算量正比于n ! 2 。表 1 1 给出了用当前世界最大计算机( 每秒亿次的t r a y 型) 按搜索穷举法计算t s p 问题 所需要的时间，这里还未计算到计算机所需的存储空间。完全可以看出，用搜索 穷尽法计算t s p 是无法实现的。实际上，根据我们实验计算表明，当城市的数量大 于1 0 的时候，穷举法就已经很慢了。 表1 1t s p 问题的计算量 n 城市 71 52 03 01 0 0 加法量 2 5 1 0 36 5 1 0 41 2 1 0 1 81 3 1 0 ”4 6 x 1 0 1 5 7 搜索时间1 8 小时3 5 0 短 2 5 1 0 。5 秒4 1 0 1 6 年1 0 “年 贪婪法，有人也把它称为最短路法，是对穷举法的一个改进。大致思想是：路 径从第一个城市开始。选择与该城市连接的所有城市中连接距离最短的城市，作 为路径的第二个城市，按照同样的方法计算下一个城市，直到路径已经经过了所 有的城市。选择路径中下一个城市的方法，类似于小孩子吃苹果，每次都吃最大 的，贪婪法由此得名。贪婪法的实现较穷举法还要简单，而且它最大的优点是计 算速度很快；但是它有很大的弱点，因为每次选择下一个城市都悬依据距离最短， 所以很难得到最优解，我们根据大量实验计算得到：当城市的数目大于8 的时候， 基本上就无法得到正确的结果。而且，如果待求解问题的图不是全连接图的话， 该方法经常无法得到结果。 1 3 3 l t o p f i e l d 网络法 1 9 8 5 年，h o p f i e l d 和t a n k 首先用神经网络模型求解t s p 问题，并取得了一定的 成果【l ”，引起了许多学者的关注。其求解的基本思想是：将t s p 映射到一个神经网 络上，通过网络的动力学方程自动演化至网络的平衡态，自动搜索到局部解。这 一思路为求解t s p 问题提出了一条新的途径；沿着这个思路，此后又有许多新的工 作把神经网络方法用于许多领域，其中包含了许多优化组合问题。t s p 的研究成为 神经网络中的典型代表之一，这个问题中遇到的困难及解决方法对于神经网络的 研究具有重要意义。 第一濑t s p 问题简介 寇发震静维广h t 算法静麓露氇发瑗7 这一方法静不是霹弱限。w i l s o n 程1 9 8 8 年用h t 算法求解t s p 的相同算法，并米j , 接o h o p f i e l d 撤告中给出的结果( 2 0 次模拟 实验中，1 6 次狡敛到激倪解或接近最优纯簿) ，穗在1 0 0 次重复实貔牵，灵努1 5 次 能在1 0 0 0 次遮代计算以内收敛到有崽义的巡网路径上，4 5 次披“冻缡”在无意义 懿藏褥籍线上，其它4 0 次在1 0 0 0 次迭筏诗算孛苓狡敛。帮 琢谤箨鹣绩架不魏黧复。 h o p f i e l d 和t a n k 也注意到迭一点。他们指出了网络韧值的不同会影响计算结果。 无疑德们给蹬的参数值具有缀验往质。实验袭明：不闻的初僮，不阕的参数，结 果会收敛到完企不同的局域优化解，并且选代步数也不相同。 收敛的不稳定性和对参数的高度敏感成为h o p f i e l d 模型的驻著缺点。a i y e r j l 盖过 嬲络母謦征值麴分析，从超空间盼氖度解释了 | o p 珏e 蚓冁终求解t s p 闻艨经常路入无 效解的原因；文献讲从t s p 网络动力举角度俸了阐述# 文献1 2 0 , 5 t 1 烈1 从参数选择的角 度作了阐述。这些研究都在解决t s p 书取得了定的成果，但楚今仍米找到具有普 遍适用意义的参数遣释褥律，参数逸释不可涟免翦存在着先狳性。 黪憩之乡 ，霉线搜增夔嚣数是弓l 趣投敛苓稳定熬艨濯之一。嚣力零懑静尊线缝 系统的动力学特性是殿其复杂的。研究还表明：具体到不同的城市分布，即使使 震携嬲戆参数_ 彝翅焦，诗算终果差别键太。看寒具傣嬲菜一t 姆超题辩要选择蟪应 适配的；幻值、参数和良好的算法。 程t 鼹游攥静表达方瑟，戆耋菌数懿数避方瑟、秘络薪壤黧叛及韶搂踅箨方瑟， 陆续都有著太燕宝贵的研究。但总体米讲，由予人工神经网络的动力学性质十分 复杂，嚣嚣臻必熬或豢还跑较少，爨崔大蠢毒镑燎狭瓣褥器，要产生满意鹣效莱， 还需作更多的努力。 1 3 4 遗传算法和蚁群算法 遗传算法p 3 是模仿生物建立起来静功能强大盼露法，将它用于复杂的优化计 算，现在已经成为一个研究热点。 ， 遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解 趣题。与囊然器摆似，遗黄冀法对求解超题鹊本身一无所知，它携爨要熬仅是对 算法所产生的每个染恕体进行评价，并基于适应值来选择染色体，使适应性好的 染色体枣更多熬繁殖极会。搓遗黄爨法中，邋过蘧极方式产生萋于个所求鳞 建题 的数字编码，即染色体，形成初始群体；通道适应度函数给簿个个体一个数值评 价，淘汰低适应度的个体，选择赢适成度豹个体参加遗转操 乍，经过遗传操作后 自动波方法求解t s p 问题 的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。这就是遗传算 法的基本原理。 蚁群算法 3 4 , 3 s 1 是模拟现实世界中的蚁群觅食的行为而提出的一种解决组合优 化问题的新算法。科学家发现蚁群寻找食物时会派出一些蚂蚁分头在四周游荡， 如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”作为蚁群 前往食物所在地的标记。信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物， 又采取不同路线回到巢中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁 群将倾向于沿另一条更近的路线前往食物所在地。模仿蚁群的这种特性，可开发 出新的算法，以解决“在许多城市之间寻找最佳路线”之类的问题。 在解决t s p 问题时，蚁群优化算法设计虚拟的“蚂蚁”将摸索不同路线，并留 下会随时间逐渐消失的虚拟“信息素”。虚拟的“信息索”也会挥发，每只“蚂蚁” 每次随机选择要走的路径，它们倾向予选择路径比较短的、信息索比较浓的路径。 根据“信息素”较浓的路线更近的原则，即可选择出最佳路线。由于这个算法利 用了正反馈机制，使得较短的路径能够有较大的机会得到选择，并且由于采用了 概率算法，所以它能够不局限于局部最优解。 遗传算法和蚁群算法都在t s p 问题的求解上取得了一定的成果，为t s p 问题的 研究提供了新的思想和方法。在今后的t s p 问题的研究中，势必将成为热点。 但是遗传算法和蚁群算法存的一些问题也是不同忽视的1 3 3 ，3 乱，它们都容易陷入 局部最优解，有待以后去研究和解决。遗传算法对自己的系统参数要求较高，必 须选择种群数目、杂交概率、变异概率等，选择的参数好，就会得到较好的实验 结果；反之，就会使算法的收敛速度变慢，而且经常收敛于局部极小点，甚至可 能导致实验的失败。蚁群算法的主要依据是采用正反馈原理和启发式算法的有机 结合，这种算法在构造解的过程中，利用随机选择策略，这种选择策略使得进化 速度较慢，正反馈原理旨在强化性能较好的解，却容易出现停滞现象。 1 4t s p 问题的实际应用价值及前景 t s p 问题在实际应用中有着非常广阔的前景，我们在日常生活中经常会遇到这 种问题，比方说： 1 某物资运输公司的物资配送车，要到2 0 个站点去送货，送货完后要返回 到公司，走怎样的路线才能既省汽油又省时间? 第一章t s p 问题简介 2 为了商业业务，需要乘飞机飞几个城市，不同的飞机公司提供不同的票价， 要怎样安排行程，既能走遍要去的城市，最后又回来原出发地，而又能省 钱? 3 机床加工零件，耍在零件上钻几十个孔，为了批量加工，一个零件的钻孔 结束后，钻头要回到起始位置以便于n t 下一个零件，钻孔时间是定值， 但是移动钻头的时间直接取决于钻头的移动路线，所以怎样安排钻头的移 动路线将直接影响加工零件及生产的速度。 这些都是标准的t s p 问题的例子。可以看出，t s p 问题的研究除了有其理论上 的价值外，它的解决将会给运输、生产、旅游等行业带来直接的效益。虽然，现 在t s p 问题的研究，还只是停留在理论和实验室的水平，但是不能抹煞它广阔的应 用前景。可以说，t s p 问题的研究是功在当代，利在千秋。 自动波方法求解t s p 问题 第二章脉冲耦合神经网络工作原理及特性 本章在对人工神经网络进行了简要的介绍之后，着重介绍了脉冲耦舍神经网 络( p c n n ) 中的自动波传播特性，为下一章构追求解t s p 问题的网络模型奠定了 基础，最后给出了p c n n 的研究现状。 2 1 人工神经网络概述 神经网络( n e u r a ln e t w o r k ) 是近年来再度兴起的一个高科技研究领域，是信 息科学、脑科学、神经心理学等多种学科近年来研究的一个热点。人工神经网络 是指模拟人脑神经网络的结构和功能，运用大量的处理部件，由人工方式建立起 来的网络系统。它是在生物神经网络研究的基础上建立起来的，人脑是人工神经 网络的原型，人工神经网络是对脑神经系统的模拟。 早在1 9 4 3 年，神经心理学家麦克洛奇和数学家皮兹就提出了形式神经元的数学 模型( m p 模型) ，从而开创了神经科学理论研究的时代，1 9 4 4 年赫布( h e b b ) 提 出了改变神经元联接强度的h e b b 规则，他们至今仍在各种神经网络模型的研究中 起着重要的作用。2 0 世纪8 0 年代由于霍普费尔特( j j h o p f i e l d ) 提出了h n n 模 型，从而有力的推动了神经网络的研究，因此人工神经网络的研究进入了一个新 的发展时期，取得了许多研究成果。现在它已经成为人工智能中一个极其重要的 研究领域。 、 2 2 脉冲耦合神经网络传播特性 关于自动波【2 8 啭播特性的研究，对于基于p c n n 的优化问题和图像处理求解至 少有以下几个方面的意义：1 有可能用于组合优化问题的求解，如在一个迷宫中从 起点对应神经元点火所产生的自动波不断地在迷宫中传播，最先到达终点的自动 波所走过的路径即为迷宦闻题的解【2 9 l 。类似地，如图论中的旅行商问题、t s p 闻题 等均有望利用p c n n 中的自动波传播特性得到解决。2 自动波的传播特性有可能用 于图像的纹理分割，如不同纹理所提供的波动特性不同( 如波纹数不同) ，利用此 可以有效地实现图像的纹理分割。3 利用图像的不同区域所产生的自动波在区域边 缘相遇的特性，可以利用p c n n 有望解决图像的边缘检测问题。 关于p c n n 中自动波的传播特性，文献【2 8 】中通过实验研究的方式观察到了 p c n n 在神经元之间传播的自动波现象，指出了所观察到的自动波沿外部刺激的负 梯度方向传播的现象。这里我们通过对复杂非线性p c n n 系统中神经元模型的适当 第二章脉冲耦含神经嘲络工作滁理及特性 1 l 简化，深入分析了p 鼢黼中自动渡静传播条件、传疆速度、传播方辩簿潜惩，结采 表明只要外部刺激沿点火神经元处予与网络参数有关的指数衰减带内，则该神经 元点火所产警的啻蓊波将继续传播，我们述研究了外帮裁激簸于该捂鼗带井数值 情况下自动波的波动特性，实验研究的结果跨我们所获得的理论研究的结果相同。 2 2 1 自动波的传播条件 ( 1 ) 线性网络 辫2 1 显蠢乏窭了线链p c n n 酌绝稳，其孛溪患l ，2 ，3 ，。，嚣楚襻经元绫号， 边表示了神经元之间的耦合，并假设神经元1 的外部剿激墩大，即是 ( 毒= 1 , 2 ，嚣) 孛最大魏e 卜 卜_ o 围2 1 内牲个神经冗组成的线性p 鼢m 缩擒嘲 驻然神缀元1 最先点火，假设毛点火所产生的自动波熊够滑线性p 4 n 从挺至4 右 囊传撵萎g 耱经元故，下蓠我嚣】薅谂这令蠡臻渡蕊撵下去瓣条律。纛毫尊谂孛缓设 足够犬。显然，若由神经元l 所产生的目动波可以从斑到右传播下去，其神缎元输 出波形痘鸯麓2 ，2 辑暴熬形式，鼹终熟工箨过毽懿下； 图2 2 离散p 心i n 波动传播过程波形 0 ) t = o 时，所有神经元簏位，即蚌( o ) = 0 ，从而豳于各神经元的外刺激溺大于 0 ，使所有辛申经元在z = a t 时刻点火拱中垃为步长) ；郎苁( 奶= 1 。这射所蠢神经 1 2 自动波方法求解t s p 问题 元的阈值由于其自然点火而同时被充电为，从而迫使各个神经元的输出回零， 即y ，( 2 a t ) = 0 ，注意这时有 b ( f ) = 0 ：( ，) = = 0 。( f ) = e x p ( - t ) 网络处于初始准备阶段。 ( 2 ) 由于t 是最强的外刺激，当闽值b 衰减到等于一，即 e x p ( 一t 1 v o ) = 而 ( 2 1 ) ( 2 2 ) 时，神经元1 在时刻f 1 = 钿m 墨) 最先点火，其闽值因其点火而被充电至，反 过来_ 又迫使该神经元输出回零，即神经元1 产生一个脉冲输出，该脉冲输出在网络 中生成了自动波的波源，故该过程称为波源生成。 ( 3 ) 自动波的传播是由于网络中神经元之间的相互耦合满足一定条件而实现的。 如果神经元2 在时刻t ，+ a t 的点火不是由于自然点火所致，而是由于神经元1 的点火 对神经元2 的捕获所致，则神经元1 的波动传播到了神经元2 ，这要求神经元2 在时 刻+ 越不满足自然点火的条件，即x 2 岛( f 1 + a f ) ，同时，神经元2 在时刻 + f 被 神经元1 的点火所捕获，即也( 1 + 犀：( f l + ，) ) 口：( + a ，) ，其中厶是由于神经元2 与神经元l 相互耦合和神经元1 的点火，从而传递给神经元2 的链接值。对于线性 p c n n ， 神经元1 在f l 时刻的点火使得l 2 瓴+ d = 1 。注意到 研“+ 出) ：e x p ( 一峭和式( 2 ，1 ) 式( 2 2 ) ，并记 勺 唧( 一笃：口 ( 23 ) 贿而蠹面s 屯 嘶。 ( 4 ) 若自动波自左到右从神经元l 已经传播到神经元j i 一1 ，且神经元后的点火仍 然不是自然点火，即要求t 满足 扎 4 呻2 _ l i ：e r i 所对应的路径l _ 3 斗2 - - 4 _ 5 一l 更优。 第三章构造自动波求解t s p 问题 这个例子说明在运用波动特性进行t s p 问题求解时，不能像运用波动特性进行 图的最短路问题求解那样，以从起点先到某一点( 比如4 3 ) 的波继续传播，其它后 到达该点的波停止传播，而应该是所有到达该点的波都继续传播，即r ，的1 _ 4 3 传 到4 的波继续传播，r 2 的1 4 3 传到4 的波也继续传播。 图3 55 个城市的赋权图 图3 6 展开后的赋权图 自动波方法求解t s p 问题 3 4 2 神经元可以多次点火 上面的例子中，如果想让到达某一点( 比如4 3 ) 的自动波都可以继续传播，那 么神经元4 3 必须能够多次点火，这也就是说我们的网络设计必须能够保证神经元能 够多次点火。 3 4 3 自动波竞争的特殊性 由上面得，每个顶点( 元) 可以点火( 点火指有一输出脉冲) 多次，任何时候 到达该顶点的波都可以继续传播，而以最早到达终点1 的波的路径为t s p i b 题的最 优解。故每个元上均无自动波的竞争，而1 7 上有自动波的竞争。 3 4 4 自动波单向传播 在我们的展开图s ( 6 ) 中，仅从1 向1 7 传播，如1 、3 1 之间仅有1 到3 1 的权值，3 1 到1 的权值为无穷大，3 4 、1 7 之间仅有3 4 到1 7 的权值，”1 7 到3 4 的权值为无穷大，所 以展开图中的边为有向边。可以看到原图展开后，在原图中杂乱的传播方向映射 成为展开图中单一的向前传播的方向，这将给我们的算法设计带来方便。 3 4 5 神经元链路的波动特性 既然神经元可以多次点火，那么图3 2 ( a ) 中所示的0 也要有相应的变化。神经 元f 可以多次点火，记点火时刻分别为r f l ，t f 2 ，则链路设计应使元j 在f 。+ ， f ，：+ a ，时刻点火。点火及波动特性如图3 7 所示。 对于图3 7 中( a ) 所示的意义，我们将在下一节中介绍。 由图3 7 可以看出，在f f l _ f 。时间段，巳p ) 是标量( 或者一维矢量) 而且按直 线下降i f ，：_ f 。时间段，嘭( f ) 是二维矢量而且按直线下降；f 。斗l + 时间段， q ( f ) 是三位矢量而且按直线下降；，。+ 哼f ，2 + 时间段，印 是= 维矢量而 且按直线下降；，：+ 叶屯+ 时间段，巳( f ) 是标量( 或者一维矢量) 而且按 直线下降。 因此，0 j ( ，) 在一定时刻成为矢量，其各个分量分别记录着目前吼的各个值， 应该以口，o ) 的第一个分量作为神经元，是否被神经元f 点火的阈值。 塑三兰塑堕皂垫婆堂坚! 婴鲤里 一兰 鹣贼 ( a ) 神经元i 多次点火 嘞神经元l 与，之间的耦合 3 4 6 路径约束( 边约束) ( c ) 神经元，的0 特性 图3 7 神经元i 点火多次的情况 图j ( g ) 共有n + l 层，2 到聆层的即一1 层构成一个一1 ) 2 阵列，若某自动波已 经走过了伽一1 ) 2 阵列的其中k 行，则该自动波只能沿其余厅一l k 行同时继续传 播。 自动波方法求解t s p 问题 图中边的约束当然应该加上，即当某自动波走过协一1 ) 2 阵列的其中| | 行传播到 了神经元_ ，而仰一1 ) 2 阵列中的其余- 一卜k 行没有神经元与相连，则该自动波 不能继续向前传播。 3 4 7 求解问题与起始城市无关 我们知道，在求解最短路问题的时候，如果求解的起始点不同，结果肯定是不 同的，但是对t s p 问题来说，情况完全不同。我们还以图3 3 中的赋权图为例来说 明，假设我们以1 点为起始点，求得的t s p 问题的解为l 斗5 - - 9 3 0 4 - 2 - l ；现 在如果以3 为起始点，求得的t s p 问题的解肯定是3 专4 辛2 - l o5 寸3 ，如果该 赋权图是对称的，求得的t s p 问题的解也可能是3 斗5 呻1 2 _ 4 _ + 3 。因为这样 求得的t s p 问题的解组成的回路是同样的环，如果因为改变了求解t s p 问题的起始 点，而使得最后得到的解组成的回路变成了另外一个环，那么不同的环中，肯定 有的环上权值之和相对较大，即该解不是该t s p 问题的最优解。 所以对于某一个赋权图的t s p 问题来说，该问题的解，即权值之和最小的回路 是固定的，如果该赋权图是对称的，那么该解的反向回路和原回路一样都是最优 解，也就是说对某一固定的t s p 问题来说，解( 回路) 是固定的，无论从哪个起始 点出发，结果部应该一样。我们稍后的实验部分均已第1 个点为起始点，因为有了 这里的说明，所以我们的实验没有失去一般性。同时，也表明我们的算法对于初 始值的要求并不是很高，这也是我们的算法优越性的体现。 3 4 8 高度并行性 网络中存在大量的自动波，以图3 4 为例，神经元1 点火有4 个波列，第一层神 经元2 1 、3 1 、4 1 、5 1 点火各自产生3 个波列，第二层每个神经元点火各自产生2 个波 列，第三层每个神经元点火各自产生1 个波列，所以共有4 3 2 = 2 4 个自动波。 以全连接的赋权图为例，顶点数为甩的赋权图，最多可以产生伽一1 ) ! 个自动波的波 列。 当网络规模增大( 图中顶点数) 时，网络中的波列的数量非常多，表明网络中 的路径搜索处于高度并行状态。 3 5 特殊的网络实现 由3 、4 一节中的叙述可知，t s p 问题有很多自己的特性，所以我们采用了特殊的 网络结构设计，以便达到这些特性的要求。 第三章构造自动波求解t s p 问题 3 5 1 神经元激励函数脉冲发生器 定义s ( g ) 中所有神经元的激励函数为 y ，o ，= p ”船卜只o = ：山 只o ) 刘 只( f ) 2 0 。7 一旦只( f ) 在莱时刻f ，从0 变化到 0 ，神经元的输出在f = t 。时刻产生一个窄 脉冲，称为该神经元在时刻t 点火。显然网络一开始处于静止状态，即设所有神经 元的0 i ( o ) = o ，而让元1 点火形成波源，则只需将元1 的阈值日( o ) 设为负值。 ( a ) s ( g ) 中的一条连接 i 举簿燃 艇二 。 i 、嗽：- - 。谶黪i 鬻 ( b ) 该连接对应的网络 图3 8 网络中波列产生及传播机理 3 5 2 闽值发生器使波动沿路径长度均匀传播 为使s ( g ) 上的任一元点火可沿网络依路径长度均匀传播，不失一般性，设元f 在时刻f ，点火，并设元，与元，之间有从，_ + j 的连接，连接权为。则应当设计 闽值发生器 删：肛棚一_ f ) 川， ， 【0t t f 谴自动波在( f ，7 t + q ) 时间区域上在元f 至元，的连接上传播，而在，+ 嘞时刻 到达元_ ，使元点火，这里称( 时间单位) 为边权所折合的时间长度。 自动波方法求解t s p 问题 3 5 3 神经元连接的先进先出堆栈结构 我们在图3 8 中将激励函数设计为脉冲发生器正是为了保证神经元可以多次点 火。所以出现了图37 ( a ) 中的所示的点火情况。 元，的阈值矢量具有先进先出的堆栈结构，进是由于元f 的点火使得元，产生 了新的阈