（计算数学专业论文）蚁群算法研究及其应用.pdf

西北大学硕士学位论文 摘要 本文主要讨论了繁本蚁群算法的改进及英应用。在第一章里介绍了蚁群算法 的思想起源及研究现状，并对本文的所做的主要工作做了总结。第二章详细的介 绍了基本蚁群算法的原理及模型建立，对蚁群算法中的三个基本参数的设鹭进行 了讨论磺究，最后绘出了基本蚁群算法的实现步骤。第三章讨论了基本蚁群算法 的改进及其应用。文中讨论了动态自适应调整信息素的蚁群算法及其在旅行商问 题中的应用帮带点交换的蚁群算法及冀在对称旅行商和菲对称旅行商中的应灞， 最后还讨论了一种求解非对称旅行商问题的迭代算法，对文献中的部分不确 切的内容作了修改完善。 关键词：基本蚁群算法，旅行商闷遂。a t s p ，信悫素，寤发式算法。 西北大学硕士学位论文 a b s t r a c t t h i sp a p e rm a i n l yd i s c u s s e st h ei m p r o v e m e n to fb a s i ca n tc o l o n y a l g o r i t h m ( a c a ) a n d i t sa p p l i c a t i o n t h ef i r s tc h a p t e ri n t r o d u c e st h ei d e a o r i g i n so ft h ea c a a n di t sd e v e l o p m e n t ，a n dp r e s e n t sas u m m a r yo ft h e m a i nw o r kd o n e t h es e c o n dc h a p t e rp r o v i d e sd e t a i l e dd e s c r i p t i o n so ft h e b a s i ca c ap r i n c i p l ea n dt h em o d e le s t a b l i s h m e n t ，d i s c u s s e st h et h r e e b a s i cp a r a m e t e r so fa c a ，a n dd e t a i l e di m p l e m e n t a t i o np r o c e s si sa l s o p r e s e n t e di n t h i sc h a p t e r t h et h i r dc h a p t e rd i s c u s s e st h ei m p r o v e m e n t s t r a t e g i e so fb a s i ca c aa n di t sa p p l i c a t i o n i nt h i sp a r tp r o v i d e sa n i m p r o v e da c a b a s e do nt h es e l f - a d a p t a t i o na d j u s t i n gp h e r o m o n ea n di t s a p p l i c a t i o no ft 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 ) ，a n d a p o i n t s e x c h a n g e da c a a n di t sa p p l i c a t i o n so ft h es y m m e t r i ct r a v e l i n gs a l e s m a n p r o b l e m ( s t s p ) a n da s y m m e t r i ct r a v e l i n gs a l e s m a np r o b l e m ( a t s p ) a r e a l s op r e s e n t e di nt h i sc h a p t e r f i n a l l yp r e s e n t sa ni t e r a t i v ea l g o r i t h mf o r a t s ea n dt h eb i b l i o g r a p h i c 【2 9 】i sc o m p l e t e d k e yw o r d s ：b a s i c a n t c o l o n y a l g o r i t h m ，t r a v e l i n g s a l e s m a n p r o b l e m ，a t s p , p h e r o m o n e ，h e u r i s t i c s i i 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后 学位论文作者签名 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果。据我所知，除了文中特别加以标注和 致谢的地方外，本论文不包含其他人已经发表或撰写过的研究成 果，也不包含为获得西北大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己 在论文中作了明确的说明并表示谢意。 学位论文作者签名：挺蜘； 沙o 年i 月日 西北大学硕士学位论文 第一章引言 1 1 蚁群算法的思想起源 自然界一直是人类创造力的丰富源泉，人类认识事物的能力来源于与自然 界的相互作用之中。自然界中的许多自适应优化现象不断给人启示：生物体和自 然生态系统可通过自身的演化使许多在人类看起来高度复杂的优化问题得到完 美的解决。近些年来，一些与经典的数学规划原理截然不同的、试图通过模拟自 然生态系统机制以求解复杂优化问题的仿生优化算法相继出现( 如遗传算法、蚁 群算法、微粒群算法、人工免疫算法等) ，大大丰富了现代优化技术，也为那些 传统的最优化技术难以处理的组合优化问题提出了切实可行的解决方案。伴随着 模拟自然与生物机理为特征的仿生优化算法时代的悄然兴起，些仿生优化算法 已在经典n p - c 问题的求解和实际应用中显示出了强大的生命力和进一步发展的 潜力。 蚁群算法( a n tc o l o n ya l g o r i t h m , a c a ) 是从自然界中真实蚂蚁觅食的群体行 为得到启发而提出的，其很多观点都来源于真实蚁群【1 l ，因此算法中所定义的人 工蚂蚁与真实蚂蚁存在如下的相同点和不同点。 1 1 1 人工蚂蚁与真实蚂蚁的异同点 1 1 1 1 相同点 1 都存在一个群体中个体相互交流通信的机制 人工蚂蚁和真实蚂蚁都存在一种改变当前所处月= 境的机制：真实蚂蚁在经 过的路径上留下信息素，人工蚂蚁改变在其所经过路径上存储的数字信息，该信 息就是算法中所定义的信息量，它记录了蚂蚁当前解和历史解的性能状态，而且 可被其它后继人工蚂蚁读写。 2 有着相同的任务 人工蚂蚁和真实蚂蚁都要完成一个相同的任务，即寻找一条从源节点( 蚁巢) 到目的节点( 食物源) 的最短路径。人工蚂蚁和真实蚂蚁都不能跳跃，只能在相邻 节点之间一步步移动，直至遍历所有城市。 3 利用当前信息进行路径选择的随机选择策略 第1 贝 西北大学硕士学位论文 人工蚂蚁和真实蚂蚁从某一节点到下一节点的移动都是利用概率选择策略 实现的，概率选择策略只利用当时的信息去预测未来的情况，而不能利用未来的 信息。因此，人工蚂蚁和真实蚂蚁所选用的选择策略在时间和空间上都是局部的。 i i 1 2 不同点 在从真实蚁群行为获得启发而构造蚁群算法的过程中，人工蚂蚁还具备了 真实蚂蚁所不具有的一些特性： ( 1 ) 人工蚂蚁存在于一个离散的空间中，它们的移动是从一个状态到另一个 状态的转换； ( 2 ) 人工蚂蚁具有一个记忆其本身过去行为的内在状态； ( 3 ) 人工蚂蚁存在于一个与事件无关联的环境之中； ( 4 ) 人工蚂蚁不是完全盲从的，它还受到问题空间特征的启发； ( 5 ) 为了改善算法的优化效率，人工蚂蚁可增加一些性能，如预测来来、局 部优化、回退等，这些行为在真实蚂蚁中是不存在的。 1 1 2 蚁群算法模型的建立 1 1 2 1 对蚂蚁个体的抽象 由于蚁群算法是对自然界中真实蚂蚁觅食行为的一种模拟，是一种机理上 的应用，因此首先必须对真实蚂蚁进行抽象，而不可能也没必要对蚂蚁个体进行 完全再现f 2 】。这样抽象出来的人工蚂蚁可以看作是一个简单的智能体，能够完成 所求问题简单解的构造过程，也能通过一种通信手段相互影响。 i i 2 2 问题空间的描述 自然界中的真实蚂蚁存在于一个三维的环境中，而问题空问的求解一般是 在平面内进行的，因此需要经蚂蚁觅食的三维空间抽象为一个平面。另外，真实 蚂蚁是在一个连续的二维平面中行走的，但是计算机无法直接束完整的描述一个 连续的平面，因此，必须将连续的平面离散化为由一组点组成的离散平面，人工 蚂蚁可在抽象出来的点上自由运动。 基于上述分析，很容易得到蚁群算法所求解的问题空间可用一个重要的数 学工具图( g r a p h ) 来描述，在工程实际中的很多问题都可以用途来描述，这便使 蚁群算法的广泛应用成为可能。 1 1 2 3 寻找路径的抽象 第2 贞 西北大学硕士学位论文 真实蚂蚁在觅食过程中主要按照所处环境中的信息量来决定其前进的方 向，而人工蚂蚁是在平面的节点上运动的，因此可把觅食过程抽象成为算法中解 的构造过程，将信息素抽象为存在于图的边上的轨迹。 1 1 2 4 信息素挥发的抽象 自然界中的真实蚂蚁总是在所经过的路径上连续不断地留下信息素，而信 息素也会随着时间的推移而连续不断地挥发。由于计算机处理的事件只能是离散 事件，所以必须使信息素的挥发离散发生。通常的做法是，当蚂蚁完成从某一节 点到下一节点的移动后，进行一次信息素的挥发，而这种在离散时间点进行信息 素挥发的方式与蚂蚁觅食过程的机理是完全相符的。 1 1 2 5 启发因子的引入 以上几点是对真实蚂蚁觅食行为的抽象，整个过程体现了蚁群算法的自组 织性，但是这种自组织系统存在一个缺陷，即系统的演化需要耗费较长的时间。 而实际应用时对算法运行时间的要求是必不可少的，因此在决定蚂蚁行走方向的 状态转移概率时，引入了一个随机搜索的过程，即引入了启发因子，根据所求问 题空间的具体特征，给蚁群算法一个初始的引导，这个过程极大地增加了算法的 时间有效性，从而使蚁群算法的有效应用成为可能。 1 2 蚁群算法的研究现状 1 9 9 1 年意大利学者d o r i g om 等人1 3 1 f 4 i 在首届欧洲人工生命会议上发表了 “d i s t r i b u t e d o p t i m i z a t i o n b y a n t c o l o n i e s ”一文，在这篇文章中，d o r i g o m 等人 提出了蚁群算法。在提出蚁群算法以后的五年时间罩，并没有在国际学术界引起 广泛关注，自然这段时期在蚁群算法理论及其应用上也没有取得突破性进展。到 了1 9 9 6 年，d o r i g om 等人在i e e et r a n s a c t i o n so ns y s t e m s ，m a n ，a n d c y b e r n e t i c s p a r tb 上发表了“a n ts y s t e m ：o p t i m i z a t i o nb yac o l o n yo fc o o p e r a t i n g a g e n t s ”一文阁，在这篇文章中，d o r i g om 等人不仅更加系统地阐述了蚁群算法 的基本原理和数学模型，还将其与遗传算法、禁忌搜索算法、模拟退火算法、爬 山法等进行了仿真实验比较，并把单纯地解决对称旅行商问题( s y m m e t r i c t r a v e l i n gs a l e s m a np r o b l e ms t s p ) 拓展到解决非对称旅行商问题( a s y m m e t r i c 第3 _ ! i f 西北大学硕士学位论文 t r a v e l i n g s a l e s m a n p r o b l e m a t s p ) 、指派问题( q u a d r a t i c a s s i g n m e n tp r o b l e m ，q a p ) 以及车间作业调度问题0 0 b s h o ps c h e d u l i n gp r o b l e m ，j s p ) ，且对蚁群算法中初始 化参数对其性能的影响作了初步探讨，这是蚁群算法发展史上的一篇奠基性文 章。自1 9 9 6 年之后的五年时间里，蚁群算法逐渐引起了全世界许多国家研究者 的关注，其应用领域得到了迅速拓宽，这期间也有大量有价值的研究成果陆续发 表。 对蚁群算法不断高涨的研究热情导致了1 9 9 8 年1 0 月1 5 日至1 0 月1 6 日在 比利时布鲁塞尔召开了第一届蚁群算法国际研讨会( a r c r s 9 8 ) ，会议由创始人 d o r i g om 负责组织。2 0 0 0 年，d o r i g om 和b o n a b e a ue 等人6 1 在国际顶级学术刊 物 n a t u r e ) ) 上发表了蚁群算法的研究综述，从而把这一领域的研究推向了国际 数学的最前沿。鉴于d o r i g om 在蚁群算法研究领域的杰出贡献，2 0 0 3 年1 1 月 欧盟委员会特别授予他“居里夫人杰出成就奖( m a r i ec u r i ee x c e l l e n c e a w a r d ) ”。 进入2 1 世纪后的最近几年，国际著名的顶级学术刊物 n a t u r e ) ) 曾多次对 蚁群算法的研究成果进行报道6 7 ”， f u t u r eg e n e r a t i o nc o m p u t e rs y s t e m s ) ( v 0 1 1 6 ，n o 8 ) 和 i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ) ) ( v 0 1 6 ，n o 4 ) 分别于 2 0 0 0 年和2 0 0 2 年出版了蚁群算法特刊。如今，在国内外许多学术期刊和会议上， 蚁群算法已经成为一个备受关注的研究热点和前沿性课题。 g u t j a h rwj 于1 9 9 1 年撰写的技术报告“ag e n e r a l i z e dc o n v e r g e n c er e s u l tf o r t h eg r a p h b a s e da n ts y s t e m ”吲和2 0 0 0 年发表的学术论文“ag r a p h b a s e da n t s y s t e ma n di t sc o n v e r g e n c e ”【1 0 首次对蚁群算法的收敛性进行了证明，在蚁群算 法的发展史上有着特殊的作用。 随着对蚁群算法研究的不断深入，人们已开始关注蚁群算法的硬件实现这一 新的研究方向。l s a a c s 等人i “l 将遗传算法和蚁群算法结合，提出了一种嵌入式硬 件随机数据发生器设计的新思路，但是他们只是做了离线仿真，并没有在硬件上 给予实现。s c h e n e r m a n n 等人 j 2 1 在深入分析了将蚁群算法映射到f p g a 难点的基 础上，提出了一种基于群体蚁群优化( p o p u l a t i o n - b a s e da n tc o l o n yo p t i m i z a t i o n 。 p - a c o ) 算法的仿生硬件实现方案，并详细给出了p a c o 算法f p g a 硬件总体结 第4 页 西北大学硕士学位论文 构中各主要模块的实现过程。 我国在蚁群算法领域的研究起步较晚，从公开发表的论文看，1 9 9 7 年1 0 月 东北大学控制仿真研究中心的张纪会博士与徐心和教授发表的“一种新的进化算 法蚁群算法”最先对蚁群算法做了研究l l ”。在国内蚁群算法的众多研究者中， 值得一提的是当时年仅1 7 岁的高二学生陈烨于2 0 0 1 年在 ) ( f ) 使期望值的作用无法体现。因此在通常采用 a n t c y c l e 模型作为蚁群算法的基本模型。 2 2 3 基本蚁群算法中参数口、芦、p 设置的研究 蚁群算法中a 、口、p 等参数对算法性能有很大的影响。a 值的大小表明 留在每个节点上的信息量受重视程度，口值越大，蚂蚁选择以阿经过的路线的可 能性越大，但过大会使搜索过早陷入局部最优解；芦的大小表明启发式信息受重 视的程度，口值越大，蚂蚁选择离它近的城市的可能性也越大：p 表示信息素的 残留因子，如果它的值取得不恰当，得到的结果会很差。根据以上分析，研究参 数口、口、p 的最佳配置，对发挥蚁群算法在实际问题中的作用有很重要的意义。 文献p g 采用1 0 0 0 次循环作为试验终止条件( 这里一次循环是指每只蚂蚁 完成一次遍历回到出发的城市) 。试验中采用改变一个参数、其它参数不变的策 略来探索参数的设置对算法效率的影响；蚂蚁的总数目总是设雹为城市的总数 第1 2 页 西北大学硕士学位论文 目，即初始时刻每个城市放置一只蚂蚁。缺省参数设置为a - 1 ，一1 ，p t 0 7 ， t 2 1 0 0 ，在得到每条备选路线概率的情况下，蚂蚁运用随机选择的方法确定下 一步要到达的城市。每组数据试验1 0 次取平均作比较，试验中所用的t s p 问题 数据来源于o l i v e r 3 0 城市问题。 口、卢的取值越大，计算量也越大计算时间就越长，所以在能获得满意解 的情况下， 口、芦取相对较小的值。根据文献【1 9 】的试验结果，有以下结论： a n t c y c l e 模型中最佳参数配置为：口- 1 ，芦- 5 ，d 一0 9 ；a n t d e n s i t y 模型中最佳参数配置为：口- 1 ，芦- 1 0 ，p 一0 9 ；a n t q u a n t i t y 模型中最佳参 数配爱为：口- 1 ，卢一5 ，p t 0 9 9 9 。 2 3 基本蚁群算法的实现步骤 2 3 1基本蚁群算法的计算步骤 以t s p 为例，基本蚁群算法的具体实现步骤如下： ( 1 ) 参数初始化。令时间f o 和循环次数。- 0 ，设置最大循环次数。， 将m 只蚂蚁置于n 个城市上，另有向图上每条边( f ，j ) 的初始化信息量f i ( o ) = c ， 其中c 表示常数，且初始时刻( 0 ) 一0 。 ( 2 ) 循环次数。一r + 1 。 ( 3 ) 蚂蚁的禁忌表索引号t 一1 。 ( 4 ) 蚂蚁数目k k + 1 。 ( 5 ) 蚂蚁个体根掘状态转移概率公式( 2 2 2 ) 计算的概率选择城市，并6 口进， ， c t a b u 。) 。 ( 6 ) 修改禁忌表指针，即选择好之后将蚂蚁移动到新的城市，并把该城市移 动到该蚂蚁个体的禁忌表中。 ( 7 ) 若集合中城市未遍历完，e p kc 朋，则跳转到第( 4 ) 步，否则执行第( 8 ) 第1 3 页 西北大学硕士学位论文 步。 ( 8 ) 根据公式( 2 2 4 ) 和式( 2 2 5 ) 更新每条路径上的信息量。 ( 9 ) 若满足结束条件，即如果循环次数。乏n c 。，则循环结束并输出程序 计算结果，否则清空禁忌表并跳转到第( 2 ) 步。 2 _ 3 2 基本蚁群算法的伪代码流程1 2 1 1 在初始的时候，m 只蚂蚁被放置在不同的城市上，赋予每条边上的信息素 量为h ( f ) - c ，其中c 表示常数，也就是说各条路径上的信息量相等。每只蚂蚁 的t a b u l i s t 的第一个元素赋值为它所在的城市。当蚂蚁完成一个循环后，计算 k ( r ) ，并且更新每条边上的信息量，然后开始新一轮的循环。当循环的次数达 到事先设定好的最大循环次数f 。时或者所有的蚂蚁都选择了同一种路径方式 时，整个程序终止。 a n t c y c l e 模型程序的伪代码如下： s t e p l ： 初始化： s e t t 一0 , n c 0 ，每条边上的b ( o ) 一c ，并且h ( o ) = 0 ，放置肌只蚂蚁 到n 个城市上 s t e p2 ： 令st 1 ，( s 是t a b u l i s t 的下标) f o rt 一1t omd o 把第七只蚂蚁的初始城市号码放置到加h 。( s ) 中 s t e p3 ： r e p e a tu n t i l t a b u l i s ti sf u l l s e ts s + 1 f o rk - 1t oj 竹d o 根据转移概率露( f ) 来选择下一步应该到达的城市，将第七只蚂蚁转移到 城市j ，并将，插入到缸缸。o ) 中 s t e p 4 ： 第1 4 噍f 西北大学硕士学位论文 f o ri lt o 历d o 计算第七只蚂蚁的总路径长度t ，更新找到的最短路径 f o r 七一1t o ，栉d o 更新表上的信息素量 s t e p5 ： 对每一条边计算( f + h ) s e tf t + 弹 s e tn 。- n t + 1 s e ta ( 0 ) 0 s t e p 6 ： i f ( ，( 。) a n d ( 不是所有的蚂蚁都选择同一条路径) t h e n 清空所有的t a b u l i s t g o t o s t e p2 输出最短路径 终止整个程序 如果程序终止于。次循环后，那么这个算法的复杂度为0 ( 。n 2 ) 。实 际上，第一步复杂度为o ( n 2 + 用) ，第二步的复杂度为o ( m ) ，第三步和第四步的 复杂度为o ( n 2 ，1 ) ，第五步的复杂度为o ( n2 ) ，第六步的复杂度为o ( n 肌) 。实 验证明m 的一般取值与n 为同一个数量级，因此整个算法的复杂度为o ( n ，n 3 ) 。 2 4 本章小节 蚁群算法是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算 法等启发式算法后的又一种利用群体智能解决组合优化问题的启发式搜索算法。 蚁群算法不仅能够智能搜索、全局优化，而且具有稳健性( 鲁棒性) 、正反 馈、分布式计算、易与其它算法结合等特点1 4 1 5 i 。利用证反馈原理，可以加快进 化过程；分布式计算使该算法易于并行实现，个体之问不断进行信息交流和传递， 第1 5 炙 西北大学硕士学位论文 有利于找到较好的解；该算法易于与多种启发式算法结合，可改善算法的性能， 由于鲁棒性强，故在基本蚁群算法模型的基础上进行修改，便可用于其它问题。 任何事物都具有两面性，蚁群算法作为一种新兴的仿生优化算法也不例外。 蚁群算法固然有上述的诸多优点，但搜索时间长、易陷入局部最优解是最突出的 缺点【l l 【3 删1 7 1 1 2 i 。针对这些缺陷，近些年来众多国内外学者在蚁群算法的改进方 面做了大量的研究工作，本文在下面的论述中也有体现。 第1 6 贞 西北大学硕士学位论文 第三章改进的蚁群算法及其应用 3 1 动态自适应调整信息素的蚁群算法 针对蚁群寻优过程中容易出现“停滞”和陷入局部最优等问题，文献1 2 3 研究了一种根据蚁群算法搜索情况来自适应动态修改信息素的方法，可在一定程 度上有效地解决扩大搜索空间和寻找最优解之间的矛盾，从而使得算法跳离局部 最优解。 3 1 1 算法改进 这里采用时变函数q ( f ) 来代替调整信息素( f ) 一中为常数项的信息 素强度a ，即选择 弓( f ) 。，( f ) ：掣 ( 3 1 1 ) - t 由状态转移概率公式( 2 2 2 ) 可知，当a 一0 时，只是路径信息起作用，算法 相当于最短路径寻优，从而有 芹( f ) - 叩乒( f ) ( 3 1 2 ) 当口- - - 0 时，路径信息的启发作用等于0 ，此时算法相当于盲目地随即搜索， 从而有 聃。器 ， 选用时变函数代替常数项q ，在路径上的信息紊随搜索过程蒸发或增多的 情况下，继续在蚂蚁的随机搜索和路径信息的启发作用之间继续保持“探索”和 “利用”的平衡点。这里，可选择如下阶梯函数 f a 。 耔s q o ) 。j q ：若t t 疋 ( 3 1 4 ) lq 3 若lt fs 毛 式中，q 对应阶梯函数的不同取值。q ( f ) 也可以选择连续函数，如t a n h ( t ) 等。 如果一段时间内获得的最优解没有变化，说明搜索陷入某个极值点中( 未必 第1 7 贞 西北大学硕士学位论文 是全局最优解) ，此时可采用强制机制减小要增加的信息量，力图使其从局部极 小值中逃脱出来，即减小公式( 3 1 1 ) 中的q ( f ) ；在搜索过程的初始阶段，为了避 免陷入局部最优解，缩小最优路径和最差路径上的信息量，需要适当抑制蚁群算 法中的正反馈，在搜索过程中可以加入少量负反馈信息量，如采取 q q l - - 0 0 0 0 1 ，以减小局部最优解与最差解对应路径上的信息素的差别，从而 扩大算法的搜索范围。由于信息正反馈及信息素随时间衰减这两个因素的存在， 在搜索陷入局部最优时，某组信息素相对其他路径弧段的信息素而言在数量上占 据绝对的优势，因此本算法还对各路径弧段上的信息量做最大和最小值的限制。 即对于v b ( f ) ，有 f p h r m r a i n m i n t o ( t ) 一f 日sf p h r m m a x ( ，j e l ，h i ) ( 3 1 5 ) 为了使算法对于不同的问题具有更强的适应性，有必要考虑路径弧段的归 一化。对于路径弧段的归一化，多采用线性映射方法，即对于d f 。1 ，其中 d 。【d 。，j 】，将其映射到d7 - f ：】，t s p 中路径弧段所对应的代价值不小于 0 ，因此，d ；- 4 d f + 6 【o 朋，从而 擘m 。o ，- a d ，一m + ：。j 44 必。一如。) ( 3 1 6 ) d ；一一l = 口吒一+ 6 。1名：薯。，：“ p j o 3 1 2 仿真算例 这里以t s p l i b 中的e i l 5 1 t s p 作为仿真算例。设置初始信息量 ，p r e d e f i n e d p h r m t l 5 ，最小信息量珊瑚一r a i n 。1 o e 4 ，最大信息量 e h r t n m a x t l 5 ，m n 。关于式( 2 2 2 ) 中参数4 和卢以及式( 2 2 4 ) 中参数p 的设 置在上文中已有讨论，这里采用a n t c y c l e 模型，其最佳参数配置为： 口一1 ，一5 ，p 0 9 。 选取如下的q ( f ) 函数进行了实验，并与基本蚁群算法获得的结果进行比较， 实验结果如下表所示。 第1 81 i ( 西北大学硕士学位论文 f 0 5 若t 1 0 0 q ( f ) 一 1 若l o o f 2 0 0( 3 1 7 ) i 2 若t 乏2 0 0 t a b1 r e s u l t sf r o md i f f e r e n t a n tc o l o n ys y s t e m s 算法平均解最优解最差解平均值误已知最优平均运行 差( ) 解时间( s ) 自适应蚁4 2 7 9 64 2 64 3 1 0 4 6 9 4 2 61 0 0 6 4 群算法 基本蚁群4 3 0 3 64 2 64 3 51 o ，b4 2 61 1 0 算法 由表4 可以看出，改进后的自适应蚁群算法平均值误差低于基本蚁群算法， 平均运行时间也少于基本蚁群算法。 3 2 基于点交换的蚁群算法 在使用基本蚁群算法求解问题的过程中，容易出现“停滞”现象：当找到 一个较好解以后，再增加循环次数也无法使解得到改善。为此引入线路改进法， 即通过对边进行交换，在解的邻域内进行调整，每次调整都能使可行解得到改进， 直到解在邻域内不能改进为止。 3 2 1 适用于对称旅行商问题的算法改进及应用 3 2 1 1 算法改进 旅行商问题分为对称旅行商问题( s t s p ) 和非对称旅行商问题( a t s p ) 。s t s p 是指叱= d 对任意的i ，= 1 , 2 ，h ；a t s p 是指d f d ，对任意的f ，= l 2 ，。 针对基本蚁群算法求解旅行商问题的过程中出现的容易陷入局部最优、计 算时间较长的问题，本文对基本蚁群算法进行修改，即加入了线路改进法。现有 的线路改进法有2 交换、3 - 交换、o r - 交换等。本文采用2 一交换法，因为2 交换 法实现起来较简单一些，而效果几乎相同。这里只对每次循环中产生的最好解进 行2 交换，这样可以极大地节约时间。 2 - 交换法如下：以( f ，) 、( f + 1 ，+ 1 ) 代替( f ，f + 1 ) 、( j ，+ 1 ) 交换后线路中的 路径( f + 1 ，j ) 被反向，如图2 所示： 第1 9 页 西北大学硕士学位论文 图2 ：2 交换示意图 豢魏伍m卅曲 当交换后线路长度缩短，即满足条件： d ( i ，) + d ( i + 1 ，+ 1 ) d ( i ，i + 1 ) + d ( ，+ 1 ) ( 3 2 1 ) 时，可使可行解得到改善。 采用固定循环次数或进化趋势不明显使迭代停止作为停止条件，为简便起 见这里采用固定循环次数作为迭代停止条件。 关于式( 2 2 2 ) 中参数a _ 币i q f l 以及式( 2 2 4 ) 中参数p 的设置在上文中已有讨论， 这里仍然采用a n t - c y c l e 模型，其最佳参数配罨为：口一1 ，芦一5 ，p - 0 9 。 3 2 1 2 求解结果 本文采用中国旅行商问题作为验证算法的例子，所谓中国旅行商问题 ( c h i n e s e t r a v e l i n g s a l e s m a np r o b l e mc t s p ) 是一个真实的地理问题，由靳藩教 授提出来的p 1 。它可以简单表述为：求一条从北京出发经过中国3 1 个省会，直辖 市最后又回到北京的最短回路。c t s p 的求解情况如下：靳藩在1 9 9 1 年的著作1 2 5 1 中提到用神经网络方法求出的一个满意解为l 。- 1 5 9 0 4 公里：在2 0 0 0 年的著作 中提到用神经网络、遗传算法求出的满意解为l m ；1 5 , 1 0 4 公里；王攀等人【2 7 1 用改进了的混合遗传算法求得的满意解也为l 。一1 5 4 0 4 公里。1 5 4 0 4 公晕也就成 为了c t s p 目前公认的最好解。 ( 1 ) 基本蚁群算法的求解结果。 本文采用基本蚁群算法求解，求得最好结果为l _ 一1 5 8 1 0 公罩，巡回路径 为：北京呼和浩特太原石家庄郑州西安银川兰州西宁乌鲁木齐 拉萨成都昆明贵阳南宁海口广州长沙南昌武汉合肥- 福州 台北杭州上海南京济南天津沈阳长春哈尔滨- 北京 此后，再怎样增加循环次数也不能使解得到改善：即使经过1 0 0 0 0 0 次循环、 第2 0 贰 西北大学硕士学位论文 长达1 2 3 9 7 秒的搜索后，它仍然未能找到目前公认的最好的解。 ( 2 ) 改进后的蚁群算法求解结果。 引入了随机选择、2 交换法后，经过多次试验发现，只需1 0 0 次循环、仅 3 1 秒的时间就能发现l _ - 1 5 5 1 6 1 5 4 2 6 燃_ 样的满意解，且经过1 0 0 0 0 次循 环、长达3 1 9 8 秒搜索后得到一个最满意解为工 1 5 4 0 4 公里，巡回路径为：北 京呼和浩特太原石家庄一郑州西安- 银川兰州西宁乌鲁木齐拉萨 成都昆明贵阳南宁海口广州长沙武汉南昌福州台北杭州 上海南京合肥- 济南天津沈阳长春哈尔滨北京 这和文献【2 6 】中求解的结果一致，而文献【2 7 】中给出的巡回路径中少了上海， 估计是排版错误。这在另一侧面证实了工m - 1 5 4 0 4 公里为c r s p 最优解的猜测。 3 2 2 适用于非对称旅行商闯题的算法改进及应用冽 3 2 2 1 算法改进 由于非对称旅行商问题( a t s p ) 中两城市i ，j 之间的距离是有“方向性”的， 也就是说从城市f 到城市j 的距离d f 与从城市j 到城市f 的距离d f 不相等： d d - d f ，于是如果对非对称旅行商问题使用2 - 交换技术，计算过程与上面所述 会有所不同。为了节约计算所需的时间，只对每次循环中产生的最好解进行2 交换。 2 ，交换法如下：以( f ，) ，( j , i + 1 ) ，o + 1 ，+ 1 ) 代替( f ，f + 1 ) ，( f + 1 ，) ，( j ，+ 1 ) 交换后线路中的路径( f + 1 ，) 被反向，如图2 所示。当交换后线路长度缩短， 即满足条件： d ( i ，) + d ( l i + 1 ) + d ( i + 1 ，+ 1 ) d ( i ，i + 1 ) + d ( i + 1 ，j ) + d ( j ，+ 1 )( 3 2 2 ) 时，可使解得到改善。 这罩采用进化趋势不明显作为交换停止条件。 关于式( 2 2 2 ) 中参数口和卢以及式( 2 2 4 ) 中参数p 的设置在上文中已有讨论， 这里仍然采用a n t c y c l e 模型，其最佳参数配置为：a 一1 ，芦- 5 ，p 一0 9 。 第2 1 页 西北大学硕士学位论文 3 2 2 2 改进算法的流程 s t e p l ：( 初始化) 对万个城市的a t s p 问题，为a t s p 图中的每一条弧o ，) 赋信息素初值h ( o ) - c ，其中c 表示常数，且初始时刻( 0 ) 一0 ；假设有m 只 蚂蚁在工作，所有的蚂蚁从同一城市f o ( i o e n ) 出发，默认当前最好解为 w q 2 ，n ) s t e p2 ：( 外循环) 如果满足算法的停止规则，停止计算并输出计算得到的最 好解。否则让蚂蚁t 从起点如出发，t a b u 。表示蚂蚁七行走的城市集合，初始 t a b u t 为空集，1 k m 。 s t e p3 ：( 内循环) 按蚂蚁1 s ks m 的顺序分别计算当蚂蚁在城市i ，若 t a b u i 。n ，完成第七只蚂蚁的计算；否则，j g t a b u t - na l l o w e d t 一 f o ) ，中， 则按式( 2 2 2 ) 的概率转移到下个城市j ，t a b u 。- t a b u 。u n ，i ：- j 。若 t a b u - 且a l l o w e d t 一 f o 一m ，则到达f o ，t a b u i - t a b u lu i o ，i 一f o ；重复 s t e p 3 。 s t e p4 ：( 点交换) 对1 s 女s 研，t a b u 。专n ，按缸加t 中城市的顺序计算路 径长度，t a b u 。- n ，路经长度是一个充分大的数。比较m 只蚂蚁的路径长度， 记走最短路径的蚂蚁为s 。若kc l ，则缈- s ，对路径上的顶点和顶点| b j 的距离，若满足式( 3 2 2 ) 则交换路径，重复s t e p4 直到所得的解不再满足点交换 条件无法交换路径，也即找到当前的最优解，由于帆o ，则形= l w o 。 s t e p5 ：( 更新信息素) 对生成的当前最优路径，用式( 2 2 4 ) 对上弧的信 息素痕迹加强，其它弧信息素痕迹挥发。得到新的( f ) ，t ：- t + 1 ，重复s t e p l 。 3 2 2 3 求解结果 例如：旅行商需要访问8 个城市，城市问的距离示于表5 中，求旅行商的 最优路线。 第2 2 撕 西北大学硕士学位论文 表2 各城市间距离矩阵 t a b2t h ed i s t a a c em a t r i x 1234 5678 l 0 3 671 21 01 11 21 5 2 8 6l o1 51 01 2l o 3 58 61 0851 5 4 91 57 0 0 42 01 01 2 51 2 1 7 93 1 51 41 2 61 3 71 01 71 8 1 01 0 7 1 21 171 1 1 l 8 0 0 4 81 71 41 21 6 1 5 85 假设所有的蚂蚁都从城市1 出发，取8 只蚂蚁用基本蚁群算法和改进的蚁 群算法都进行运算，当找到迭代最优解时，终止运算，输出最优结果。为了比较 各个算法在求解该问题时的有效性差异，本文在下表的运算结果中列出了其他几 种算法的求解结果： 表3 试验结果 t a b l e3r e s u l t sf r o me x p e r i m e n t s 优化算法达到最优路 最优路径最优路径长 径的平均运度 算次数 基本蚁群 7 3 次1 - 5 _ 4 _ 3 _ 7 - 8 46 - 2 _ 1 5 2 算法 改进蚁群 5 7 次1 _ 5 - 4 - p 3 _ 7 8 。6 _ 2 - - 4 1 5 2 算法 节约算法7 次1 2 6 8 7 3 5 4 16 0 最小生成7 次1 _ 5 _ + 4 _ 3 7 8 _ 6 - 2 _ l5 2 树算法 迭代算法4 5 次1 5 4 3 7 8 6 2 15 2 从实验结果可以看出，文献 2 9 1 q b 的节约算法没有找到该问题最好的解， 但是该文献中用的最小生成树算法找到该问题的最优解。最小生成树算法虽然也 是经过了7 步的运算，但是运算过程中的计算量相对来既较大了一点。文献 3 0 1 中的迭代算法其实也就相当于是本文中不使用蚁群算法而只简单的使用点交换， 因此该算法所得到的只是问题的局部最优解，它不能保证一定能获得全局的最优 解，并且迭代算法所得到的最优解对初始解的选取有很大的依赖性。从这些方面 来讲，改进的带点交换的蚁群算法能够更快的找到最优路径，可以节约运算的时 间，是求解a t s p 问题中首选的优化算法。 第2 3 贞 西北大学硕士学位论文 3 3 一个求解非对称旅行商问题的迭代算法 受文献【3 0 】中用迭代算法求解非对称旅行商问题的启发，本文采用启发式迭 代算法来求解该问题。启发式迭代算法其实也就是2 交换法，文中上述部分是把 2 交换法应用到基本蚁群算法中来，在求解t s p 和a t s p 的过程中都取得了较好 的解。在这一节中与文献 3 0 1 类似不用蚁群算法，只用点交换来求解a t s p 问题； 不过文献f 3 0 】中使用的是3 - 交换，本文不用3 - 交换而用2 - 交换，计算起来更加简 便，而且效果也很好。 3 3 1 启发式迭代算法 旅行商问题可以简单地用n 个城市的一个有向图g 一( ，l ) 表示，其中 - 伍2 ，) ，l 。 ，j ，城市间的距离d 一“口) 。，t s p 的目的是从有向 图g 中寻出长度最短的h a m i l t o n 圈。于是，用图论的术语来说，求解菲对称旅 行商问题就是在一个加权有向图g 中，找出一条总权和最小的有向w 回路。 不妨设个顶点围成的有向w 回路为：1 ，2 ，i ，i + 1 ，l j + 1 m ，l 。如果在 该回路上存在两条弧( f ，i + 1 ) ，( ，+ 1 ) ( 这两条弧可相邻也可不相邻) ，使( 3 2 2 ) 成立，则用o ，) ，( f + l y + 1 ) 代替( f ，i + 1 ) ，( j ，+ 1 ) ( 见图2 ) ，这样回路中的路 径( + 1 ，j ) 被反向，找到了更优的有向彬回路：1 , 2 ，ij ，i + l j + 1 ，n , 1 。 记有向回路上的h 条弧依次为爿r c ，a r c ：，a r c 。，由于从有向w 回路 的n 条弧上任取2 条弧必为形式一r g ，a r c “其中1s k ， ：n ，那么2 条弧 不同的组合共有c ：。竿中毗因此一次迭代最坏情况下的运算时 问为o ( n 2 1 。 设初始有向形回路的距离总长为工( 矽) ， 记 m m a x 臼d 4 f s ，l ，1 s ，n , i - j ，m - m i n 臼，b s f s 甩，1 s ，s n , i 一，j ，出于迭 代一次总权和至少减少 1 ，因此，总迭代次数 t l ( 矽) 一，l 埘n m 一1 1 m s n m 。可见t 为有限整数，从而，迭代能在有限 第2 4 贝 西北大学硕士学位论文 时间内完成，且总的时问复杂度为肘o ( n 3 ) 。 3 3 2 求解结果 本文中取的实例主要是为了给出迭代过程说明非对称旅行商问题可以用2 交换法进行计算，为了运算的简便性这里取5 个城市的非对称旅行商问题来计 算，城市间的距离示于表7 中，求旅行商的最优路线。 表4 各城市间距离矩阵 t h b i e4t h ed i s t a n o em a t r i