（计算机应用技术专业论文）tsp问题的算法与应用的研究.pdf

上海大学硕士学位论文 摘要 t s p 问题是一个典型的组合优化问题。近些年来，研究人员试图运用各种 方法对该问题进行求解。由于该问题的可行解随着顶点数的增加会成指数型增 长，容易产生组合爆炸，所以试图使用精确算法求解t s p 问题的研究基本销声 匿迹，取而代之的是各种近似方法。 本文是结合上海市公安部第三研究所8 6 3 子项目所进行的研究。论文首先介 绍了t s p 问题及其涉及的数学模型。在求解该问题的众多算法中，着重对遗传 算法和蚁群算法进行了分析和研究：采用最优个体保留策略的选择算子，双点交 叉的交叉算子并加入移民思想实现了遗传算法；采用经大量实验得出的最优化参 数、下一个城市的轮赌法选择策略和a n t - c y c l e 模型信息素更新策略实现了蚁群 算法。通过算法的比较和t s p l i b 的验证，给出了在算法执行次数和运算结果最 优化之间有良好平衡的蚁群算法的实现方法。 其次，对t s p 算法应用的实现方式也作了详细研究。本文提出了网络浏览 器运行的实现方法，给出了系统实现的b s 三层架构，并就以数据执行和结果存 取为核心功能的实现技术作了深入讨论，该方法在用户使用的方便性、应用的广 泛性和系统的可维护性上得到了较大的提高。 最后，针对e r p 系统中的物流配送路径的优化问题，运用本文研究的算法 和实现的技术，作为应用实例实现了e r p 物流配送路径决策支持系统的原型， 以良好的系统性能和满意的运行结果进一步证明了本文针对t s p 问题的算法与 应用研究的正确性、创新性和实用性。 此研究结果将对t s p 问题在其它应用领域的算法与应用的研究起到抛砖引 玉的作用，并具有重要的理论指导意义和应用价值。 关键词：t s p ，遗传算法，蚁群算法，轮赌法，t s p l i b 上海大学硕士学位论文 a b s t r a c t 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 ) i sat y p i c a lp r o b l e mo f c o m b i n a t i o na n d o p t i m i z a t i o n f o rm a n yy e a r sr e c e n t l y , r e s e a r c h e r sh a v et r i e dt ol l s ea l lk i n d so f m e t h o d st od e a lw i t ht h i sp r o b l e m a l o n gw i t ht h ea d d i t i o no ft h ep o i n t s ，t h e p r o p e rr e s u l t so ft h ep r o b l e m - w i l li n c r e a s ea ta ne x p o n e n t i a ls p e e d ，a n de v e n b r i n gi n t ot h ec o m b i n a t i o ne x p l o s i o n s ot h er e s e a r c h e sw h ot r yt ou s et h ee x a c t a r i t h m e t i ct od e a lw i t ht h ep r o b l e mh a v ed i s a p p e a r e dw i t h o u tt r a c e a l lk i n d so f a p p r o x i m a t em e t h o d sh a v er e p l a c e dt h e ma st h em a i nr e s e a r c hd i r e c t i o n t 1 1 i sp a d e ri sb u s e do nt h e8 6 3s u b p r o j e c to ft h et h i r dr e s e a r c hi n s t i t u t eo f t h em i n i s t r yo fp u b l i cs e c u r i t yi ns h a n g h a i f i r s t l y , t h i sp a p e ri n t r o d u c e st h e t r a v e l i n gs a l e s m a np r o b l e ma n dt h em a t h e m a t i c sm o d e lt h a ti sr e l a t e dt 0i t s e c o n d l y , a m o n gk i n d so f a l g o r i t h m sd e a l i n g 、) l r i t ht s p , t h ep a p e rf o c u s e so nt h e r e s e a r c h e so fg e n e t i ca l g o r i t h m ( g a ) a n da n tc o l o n yo p t i m i z a t i o n ( a c 0 ) ： u s i n gt h es e l e c tf a c t o ro fp r e s e r v i n gt h eb e s ti n s t a n c ea n dt l l ec t o s sf a c t o ro f d o u b l ec r o s s i n gt or e a l i z eg a ；u s i n gt h eo p t i m i z e dp a r a m e t e r sg a i n e db yag r e a t d e a lo fe x p e r i m e n t s ，s e l e c t i n gs t r a t e g yo fb e t t i n gb yt u r nm e t h o da n d i n f o r m a t i o nu p d a t i n gs t r a t e g yo fa n t - c y c l em o d e lt or e a l i z ea c o a f t e rt h e c o m p a r i s o no ft h et w or e a l i z a t i o n sa n dt h ev a l i d a t i o no ft s p l i b ，t h ea c o r e a l i z a t i o nw h i c hb a l a n c e st h ee x e c u t i n ga m o u n ta n dt h eo p t i m i z i n gr e s u l ti s p r e s e n t e d s e c o n d l y , t h i sp a p e ra l s om a k e st h ed e t a i l e dr e s e a r c ho nt h er e a l i z a t i o n s t y l eo ft h ea r i t h m e t i ca p p l i c a t i o n t h i sp a p e rp r e s e n t sa ni n t e m e tb r o w s e r r u n n i n gs o l u t i o na n db r o w e r t s e r v e rs t r u c t u r ew i 也t h r e el a y e r st o r e a l i z et h e s y s t e m t h i sp a p e rn l s k e sad e e pr e s e a r c ho nt h et e c h n o l o g i e st h a tr e a l i z et h e f u n c t i o nm o d e l si nw h i c ht h ed a t ae x e c u t i o na n dr e s u l ts t o r a g ea r ct h ec o r eo n e s t h i ss o l u t i o nh i g h l yi m p r o v e st h eu s i n gc o n v e n i e n c e ，a p p l i c a t i o nu n i v e r s a l i t y a n ds y s t e mm a i n t e n a n c e f i n a l l y , a c c o r d i n gt ot h eo p t i m i z a t i o np r o b l e mo ft h el o g i s t i c sd i s t r i b u t i o n r o u t ei ne r p , t h i sp a p e rh a sr e a l i z e dt h ea r c h e t y p eo fe r pl o g i s t i c sd i s t r i b u t i o n r o u t i n gs u p p o r ts y s t e m 咄t h ea r i t h m e t i c r e s e a r c ha n dt e c h n o l o g i e s r e a l i z a t i o n s i tf u r t h e rv a l i d a t e st h ec o l t e c t n e s s ，p r a c t i c a b i l i t ya n di n n o v a t i o no f t h er e s e a r c ho fa r i t h m e t i ca r i da p p l i c a t i o no ft s pb yt h ee x c e l l e ms y s t e m p e r f o r m a n c ea n d s a t i s f i e de x e c u t e dr e s u l t s n 地r e s e a r c hr e s u l t sh a v em a d ea - g o o de x a m p l et ot h e r e s e a r c h e so f a r i t h m e t i ca n da p p l i c a t i o no ft s pi no t h e ra p p l i c a t i o nf i e l d sa n dh a v et h e i m p o r t a n tt h e o r ya n da p p l i c a t i o ns i g n i f i c a n c e s k e y w o r d s ：t r a v e l i n gs a l e s m a np r o b l e m , g e n e t i ca l g o r i t h m ，a n tc o l o n y o p t i m i z a t i o n , b e t t i n gb yt u r nm e t h o d , t s p l i b 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：旅。奇 本论文使用授权说明 日期： 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 日期： 上海大学硕士学位论文 1 1 课题研究背景 第一章绪论 组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件 的最优编排、分组、次序和筛选等。这类问题通常随着问题规模的扩大，问题 空间呈现组合爆炸特征，无法用常规的方法求解“】。 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，简称t s p ) 就是为人们所广泛 研究的典型组合优化问题【2 l ，问题要求求得一条遍历所有城市的最短路径，是 一个易于描述却难以处理的n p m r d 问题。随着城市数目的增多，求解问题的 空间和时间复杂度将呈指数级增长f ，】，若使用穷举搜索法求解，在现有条件下 是非常困难的。有效地解决t s p 阀题十分重要，它已成为比较各种启发式搜索 或优化算法的数值实验性质的一个间接标准。由于还没有在较快时间内找至u t s p 问题最优解的完美算法，人们将大量时间投入到快速产生近似最优解的算法研 究当中。 对算法研究的最终目的是为了更好的应用，采取什么样的应用策略，使用 什么样的应用方式，直接关系到算法本身效能发挥的强弱和利用频率的多寡： 另外，算法应用的策略和方式还涉及到使用对象操作的方便程度、应用的广泛 性和系统的可维护性等诸多问题。因此，对算法的应用策略和实现方式的研究 就显得十分必要了。 1 2 国内外研究现状 由于t s p 问题在交通运输、计算机网络、电路板设计以及物流配送等领域 内有着广泛的应用，国内外学者对其进行了大量的研究。早期的研究者使用精 确算法求解该问题，常用的方法包括：分枝定界法【1 ，线形规划法【”和动态规 上海大学硕士学位论文 划法6 1 等。但是，随着问题规模的增大，精确算法将变得无能为力。 随着对t s p 问题特性的认识和加深，试图使用精确算法求解t s p 问题的研 究基本销声匿迹，取而代之的是各种近似方法，特别是自然仿真算法和启发式 算法，研究者越来越多。1 9 7 5 年h o l l a n d 在其著作a d a p t a t i o ni nn a t u r a la n d a r t i f i c i a ls y s t e m s 中首次提出遗传算法。2 0 世纪9 0 年代，欧洲学者d o r i g o m a c r o 等人从生物进化论中得到启发，通过模拟自然界中蚂蚁集体觅食的行为 ( 群集智能) 提出了蚁群算法州。另外还有模拟退火算法l s 】、禁忌搜索算法、 贪婪算法1 9 1 和神经网络方法( 1 0 1 等诸多算法，其中最简单有效的方法为局部搜 索，如2 - 0 p t ”1 、3 - o p t t l ”、l k 1 以及一些基于这些局部搜索算法之上的宏启 发式算法，如循环l k f “】、链式l k ”】、多级归约算法【1 6 1 以及l k h ”1 算法等。但 随着问题规模的增大，以上算法都存在着扩大搜索空间与寻找最优解之间的矛 盾，容易陷入局部极值；再者，怎样在较少的运算次数内得到符合要求的解， 都是国内外学者研究的重点和解决的难点所在。 在算法应用的实现方面，大多直接在m a t l a b 等科学计算软件上运行程序或 者利用c 、c + + 、j a v a 等高级语言编写应用软件，使操作的方便性、应用的广泛 性、结果的维护性等都受到很大的制约，既不利于对算法本身研究成果的共享， 也不方便对运算结果的存储。因此，怎么构建一个科学有效的应用实现方案， 也就随之提上了日程。 1 3 课题研究的内容与意义 首先，对于求解n 个城市的t s p 问题存在( n - 1 ) ! 条闭合路径的排列方案， 对于这类问题很难用全局搜索法精确地求出其最优解，因此研究相应的有效算 法寻找其最优或近似最优解是非常必要的。 其次，很多实际应用问题，如计算机网络路由器遍历、印刷电路板的钻孔 路线、连锁店的货物配送路线等经过简化处理后，均可建模为旅行商问题。因 2 上海大学硕士学位论文 此对寻找其最优解或近似最优解的典型旅行商问题求解方法的研究具有重要的 应用价值。 再次，一个商务决策的正确程度取决于所使用的事实和数字的正确程度。 随着竞争的加剧，决策往往需要在较短的时间内做出。因此，在该时间段内， 能够尽可能快地获得相关信息就变得越来越关键。那么，怎样在算法执行时间 和运算结果之间找到一个平衡点，使得算法能用尽量短的时问得到尽量好的结 果，以满足众多对时间要求较高的使用对象的需求，具有重要的理论指导意义。 本文通过对遗传算法和蚁群算法的研究、实现和比较，以及t s p l i b 经典数据 的验证，给出了能较好的平衡算法执行次数和运算结果最优化的蚁群算法的实 现方法。 最后，算法的研究成果需要通过良好的应用实现来展现，所以对应用策略 和应用方式的研究也有不可忽视的重要作用。怎样既能使t s p 应用问题快速方 便地运行于该系统，又能保证应用的广泛性和系统的可维护性，是本文研究的 另一个重要内容。 1 4 论文的组织结构 第一章：介绍了课题研究的背景、国内外研究的现状以及课题研究的内容 和意义。 第二章：首先介绍了t s p 问题及其涉及的数学模型，然后重点分析和讨论 了求解t s p 闯题的遗传算法和蚁群算法及实现，通过两种算法的比较和t s p l i b 经典数据的验证，进而给出了在算法执行次数和运算结果最优化之间有良好平 衡的蚁群算法的实现方法。 第三章：首先，通过分析诸多实际应用问题的求解思路，得出了t s p 问题 有很广泛的工程应用背景的结论。接下来，着重研究了算法的应用实现策略和 方式，给出了基于网络浏览器运行的三层实现架构，并针对数据执行和结果存 取等系统实现的难点问题作了深入的研究。 第四章：本章在介绍了实例提出的背景材料的基础上，给出了一个具体的 上海大学硕士学位论文 应用项目，描述了系统的功能要求和环境配置，提出了系统运行t s p 应用实例 的一般步骤。接着，给出了个具体的系统的原型- e r p 物流配送路径决策 支持，针对该系统的主要页面，绐出了系统的运行流程和使用方法，并对系统 功能实现所涉及到第二、三章的技术进行了说明。 第五章：总结与展望，总结本论文所做的研究工作和创新点，并给出了进 一步研究的目标。 1 5 本章小结 本章对课题的研究背景、国内外的研究现状以及本课题的研究内容与意义 等作了较为详细的阐述，然后说明了本支研究的理论意义和实用价值，最后给 出了本文的组织结构。 4 上海大学硕士学位论文 第二章t s p 问题的算法研究 2 1t s p 问题 2 1 1 问题描述 旅行商问题( t r a v e l i n g s a l e s m a n p r o b l e m ，t s p ) 是一个经典的组合优化问题，可 以描述为：一名商人欲到n 个城市推销商品，每两个城市i 和 之间的距离为d 。 ( i j = 1 ，2 ，n ) ，如何选择一条路径，使得商人从一个城市出发，经过所有城市一 次且仅一次后回到出发点，所行走的总行程最短。 t s p 问题是一个典型的组合优化问题。从图论的角度看，该问题实质是在一 个带权完全无向图中，找一个权值最小的h a m i l t o n 回路。由于该问题的可行解是 所有顶点的全排列，随着顶点数的增加，其可能的路径总数与城市数目n 是成指 数型增长的，会产生组合爆炸，是一个n p 完全问题，所以一般很难精确地求出 其最优解，因而寻找出有效的近似求解算法就具有重要的意义。 2 1 2t s p 的数学模型 ( = e ) 为一个带权图，v = 1 2 ：，n ) 为顶点集，e 2 。ff i j v ，i j 为边集。 d , j ( i j a v , i j ) 为顶点i 到j 的距离，其中d g o 且df ，同时d f 2 d ，( i j v ) ， 则经典t s p ( c l a s s i c a lt s p , c t s p ) 的数学模型嗍为： m i n f - 旬为 i x ，= ：燃径 嘞= 1 ，i j e v l j 式( 2 1 ) 式( 2 2 ) 式( 2 3 ) x 04 s l ，s 为g 的子图 式( 2 4 ) ，j e s 其中，l s l 为图s 的顶点数。式( 2 1 ) 为c t s p 的目标函数，求经过所有顶点的 回路的最小距离。式( 2 2 ) 和式( 2 3 ) 限定回路上每个顶点仅有一条入边和一条 出边。式( 2 4 ) 限定在回路中不出现子回路。模型实质上是在个带权图中 求一条h a m i l t o n 回路。若对所有的i j ，k v ，不等式或+ d 肚丸均成立， 则称该问题是满足三角不等式的。 2 2t s p 问题的遗传算法研究及实验结果 2 2 1 遗传算法的引入 t s p 问题是一个典型的容易描述但难以处理的n p 完全问题，同时t s p 问 题也是诸多领域内出现的多种复杂问题的集中概括和简化形式，已经成为各种 启发式搜索和优化算法的间接标准。遗传算法( g e n e t i c a l g o r i t h m , g a ) 就其本 质上说，主要是解决复杂问题的一种鲁棒性强的启发式随即搜索算法，因此遗 传算法在t s p 问题求解方面的应用研究，对于构造合适的遗传算法框架、建立 有效的遗传操作以及有效地解决t s p 问题等有着重要的现实意义。 按照达尔文( c d a r w i n ) 的生物进化论，生物界的进化遵循“物竞天择，适 者生存”的法则。按照盂德尔( gm e n d e l ) 和摩根( t m o r g a n ) 的遗传学理论，遗 传物质以基因的形式排列在染色体上，不同位置的基因控制着生物的不同特性， 不同的基因组合产生的个体对环境的适应性不同，通过基因杂交和突变能够产 生对环境适应性强的后代个体。总之，在一定的环境影响下，生物物种通过自 然选择、基因交换和变异等过程进行繁殖演化，构成了整个生物进化过程。 遗传算法的思想来自上述生物进化过程，该算法是一种模拟生物在自然环 境中遗传和进化过程而形成的自适应全局化概率搜索算法【1 9 】。它的基本思想是 基于d a r w i n 的进化论和m e n d e l 的遗传学说。该算法由密执安大学教授h o l l a n d 及其学生与1 9 7 5 年创建。研究发现，生物进化是一个不断循环的过程。在这一 6 上海大学硕士学位论文 过程中，生物群体不断完善和发展。所以生物进化过程本质上是一种优化过程， 这种认识启发着遗传算法的研究者将其应用到优化计算领域，创立新的优化计 算方法，并将这些方法应用到复杂的工程计算领域之中。此后，遗传算法的 研究引起了国内外学者的关注。 2 2 2 遗传算法原理及优化框架 基本原理：与传统搜索算法不同，遗传算法从一组随机产生的初始解，称 为群体，开始搜索过程。群体中的每个个体是问题的一个解，称为染色体。这 些染色体在后续迭代中不断进化，称为遗传。遗传算法主要通过选择、交叉、 变异运算实现。交叉和变异运算产生下一代染色体，称为后代。染色体的好坏 用适应度来衡量。根据适应度酊大小从上一代和后代中选择一定数量的个体， 作为下一代群体，再继续进化。这样经过若干代后，算法收敛于最好的染色体。 它很可能就是问题的最优解或次优解。遗传算法中使用适应度的概念来衡量群 体中的各个个体在优化计算中有可能到达最优解的优良程度。度量个体适应度 的函数称为适应度函数，适应度函数的定义与具体求解问题有关。 遗传算法除了具有自学习、自组织、自适应和本质并行性外，它还具有过 程性、多解性、非定向性、统计性、鲁棒性、整体优化、普适性和易扩充性、 搜索效率高等优越性能m 1 。 从图2 1 中的优化框架中可以看出，遗传算法的运行过程是一个非常典型 的迭代过程，其基本流程包括： ( 1 ) 选择编码策略，把参数集合s 转换为位串的结构空间x ； ( 2 ) 定义适应度函数f ( x ) ； ( 3 ) 确定遗传策略，包括选择群体大小，选择、交叉、变异方法，以及确 定交叉概率、变异概率等遗传参数嘲； ( 4 ) 随机初始化生成群体； 7 上海大学硕士学位论文 ( 5 ) 计算群体中个体位串解码后的适应度函数值； ( 6 ) 按照遗传策略，运用选择、交叉和变异等遗传算子作用于群体，形成 下一代群体； ( 7 ) 判断群体性能是否符合终止条件，或者已达到预定迭代次数，若满足 设定的条件，则结束运行；若不满足则返回步骤( 6 ) ，或者修改遗传策略再返回 步骤( 6 ) 。 图2 1 遗传算法的优化框架 2 2 3 遗传算法关键因素的研究与设计 本文采用以3 0 个城市的坐标作为算法研究和实现的样本，通过算法对实验 数据的执行来验证算法研究的成果和算法实现的优劣，所有的实验均在 m a f l a b 7 0 上运行。本实例给出的是3 0 个城市的坐标数据，它们分布在地图的 不同位置上，其坐标数据和所在地图的位置见表2 1 和图2 2 所示。 8 上海大学硕士学位论文 表2 13 0 个城市的编号和坐标 1 ( 8 7 ，7 ) 2 ( 9 1 ，3 8 ) 3 ( 8 3 ，4 6 ) 4 ( 7 1 ，4 4 ) s ( 6 4 ，6 0 ) 6 ( 6 8 ，5 8 ) 7 ( 8 3 ，6 9 ) 8 ( 8 7 ，7 6 ) 9 ( 7 4 ，7 8 ) 1 0 ( 7 1 ，7 1 ) 1 1 ( 5 8 ，6 9 ) 1 2 ( 5 4 ，6 2 ) 1 3 ( 5 l ，6 7 ) 1 4 ( 3 7 ，8 4 ) 1 5 ( 4 1 ，9 4 ) 1 6 ( 2 ，9 9 ) 1 7 ( 7 ，6 4 ) 1 8 ( 2 2 ，6 0 ) 1 9 ( 2 5 ，6 2 ) 2 0 ( 1 8 ，5 4 ) 2 1 ( 4 ，5 0 ) 2 2 ( 1 3 ，4 0 ) 2 3 ( 1 8 ，4 0 ) 2 4 ( 2 4 ，4 2 ) 2 5 ( 2 5 ，3 8 ) 2 6 似1 , 2 6 ) 2 7 ( 4 5 ，2 1 ) 2 8 ( 4 4 ，3 5 ) 2 9 ( 5 8 ，3 5 ) 3 0 ( 6 2 ，3 2 ) 鏖 剥 蒜 框 鬈 城市位置图 图2 23 0 个城市在地图中的位置 支撑遗传算法的几个关键因素是：编码方式，适应度函数，选择算子，交 叉算子，变异算子。 ( 1 ) 参数编码和初始群体设定 一般来说，遗传算法对解空间的编码大多采用二进制编码形式，但对于 t s p 一类排序问题，采用对访问城市编号序列进行排列组合的方法编码，更为 9 上海大学硕士学位论文 直观和有效。针对t s p 问题，编码规则通常是取n 进制编码，即每个基因仅从 l 到n 的整数里面取一个值，n 为城市总数。本文中。我们定义一个s * t 大小的 t s p 矩阵来表示群体，针对3 0 个城市的t s p 问题，这里t 取值3 1 。矩阵每一行 的前3 0 个元素表示经过的城市编号，最后一个元素表示经过这些城市要走的距 离；考虑到初始群体的多样性，s 取3 0 0 ，即解空间中有3 0 0 个染色体。在初始 化时，随机产生3 0 0 个序列，并计算其距离的长度，作为该数组的初始值。 ( 2 ) 适应度函数设计 在求解过程中，用遍历所有城市一次且仅一次所得到的路径距离作为适应 度函数计算的方式，所得结果越小，说明该染色体进化的越快，适应度越高； 所得结果越大，该染色体被淘汰韵几率也越大，适应度越低。 ( 3 ) 选择算子 选择的方法有很多，比如赌盘选择，排序选择，随机联赛选择，最优个体 保留方法等，本算法采用最优个体保留策略，将当前群体中适应度最差的k 个 染色体，用当前群体中适应度最好的k 个染色体代替( k = 2 5 ) 。该方法可保证迄 今为止所得到的最优个体不会被交叉、变异操作所破坏，它是保证遗传算法收 敛性的一个重要条件。 ( 4 ) 交叉算子 采用n 进制编码( n 是城市总数) ，对访问城市序列进行排列组合的方法编 码，即每个巡回路径的染色体，是该巡回路径的城市序列。因为在两条染色体 做交叉运算后，很有可能使染色体中出现重复的城市，所以要采用一定的算法， 清除重复城市。 所谓交叉运算“，是指对两个相互配对的染色体按某种方式相互交换其部 分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的 重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。在遗传算 法中，交叉算子的设计包括两个方面的内容：如何确定交叉点的位置? 如 何进行部分基因的交换? 交叉的方法有很多，比如单点交叉、双点交叉、循环 1 0 上海大学硕士学位论文 交叉、重组交叉等。 本算法采用的是双点交叉。双点交叉算法思想：假设在两条染色体的第i 个位置和第j 个位置城市之间进行互换。然后检查第一条染色体位于前i 至( i 一1 ) 的位置的城市是否和位于i 至j 位置之间的城市重复，如果出现重复，就选择另 一条染色体中位于i 至j 位置之间的且与第一条染色体出现城市重复相同位置 的城市去替换第一条染色体中位于前l 至( i 一1 ) 位置的城市中重复的城市。然后 继续进行下去。然后同理去处理位于( j + 1 ) 至r i 位置之间的城市。另一条染色 体同理处理。请参看下面的例子。 交叉算法举例： 7 ，1 ，1 2 ，3 ，4 ，1 6 ，5 2 ，3 ，1 6 ，7 ，1 ，1 4 ，5 ( 5 ) 变异算子 所谓变异运算 2 4 1 ，是指将个体编码串中的某些基因值用其它基因值来替 换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法， 但它是必不可少的一个运算步骤，因为它决定了遗传算法的局部搜索能力。交 叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。 变异运算的设计包括两方面：如何确定变异点的位置如何进行基因值替换。 常用的变异操作方法包括常规变异、倒位变异、交换变异、迁入变异等。 本算法采用的是倒位交异，即按照变异概率在染色体中随机选取两个位置 i 、j ( i ，j = l ，2 ，en ) ，将i 、j 位置之间的基因逆序排列，从两产生一条新的巡 回路线。 ( 6 ) 防止退化思想 n 5 5 巾巾d 1 1 3 7 2 6 4 7 劣， 毛 l 1 4 6 2 t 7 3 6 体 体 色 色 染 染 上海大学硕士学位论文 为了使随机产生的染色体的适应度不断提高，采取如下策略( 贪心选择策 略) ：在每次交叉和变异运算之后，如果产生的新染色体的适应度好于交叉和变 异前的个体，那么就留到新个体群中；如果产生的新染色体的适应度不如交叉 和变异前的个体，仍然用以前的染色体。 ( 7 ) 移民思想 为避免实验中过早地出现样本趋同现象，本文给出了移民思想的解决方法： 在执行算法若干次后，加入新的样本，取代当前种群中的不良样本，避免样本 趋于一致。在本实验中，采取在算法每执行3 0 次后，加入新样本的方法，新样 本的数量为种群样本数的1 5 ，即6 0 个新样本；选出当前种群中的前2 4 0 个不 良样本，将6 0 个新样本分散其中，即隔2 个不良样本，替换一个样本为新样本。 2 2 4 实验结果 在该实验中采用表2 1 的数据样本，定义一个3 0 0 3 1 的t s p 矩阵，其中矩 阵的3 0 0 行代表种群的染色体数，3 1 列中的前3 0 个元素表示经过的城市编号， 最后一个元素表示经过这些城市要走的距离。算法中使用的关键因素是：染色 体的适应度函数为遍历所有城市一次且仅一次所得到的路径距离长度、采用最 优个体保留策略的选择算子、采用双点交叉算子和倒位变异算子以及采用贪心 选择策略防止种群退化并实现移民思想避免过早地出现样本趋同现象。 ( 1 ) 未使用遗传算法前，经过3 0 个城市的最短路径如图2 3 。可以看到在 未使用遗传算法前，其运动轨迹相当杂乱，而最短距离达到了1 0 9 3 _ 7 。 ( 2 ) 使用遗传算法运行5 0 0 次后，经过3 0 个城市的最短路径如图2 4 。 从图2 3 与图2 4 中，我们可以清楚的看到，使用遗传算法运算5 0 0 次后， 3 0 个城市的遍历路径问题得到了二很好的解决，其行走路径得到了明显的优化， 由最初的1 0 9 3 7 减少到了现在的4 3 1 0 6 ，实现效果较为明显，大大节约了成 本，可见t s p 问题的该遗传算法研究和实现是有效的。 上海大学硕士学位论文 ! 耋 制 螽 e 鳞 e a 执行前最短距离：1 0 9 37 城市横坐标 图2 3 数据初始化时的最短路径图 o a 执行后最短距高：4 3 1 0 6 城市撤坐标 图2 4 经g a 运算后的最短路径图 馨剥意橹鬈 上海大学硕士学位论文 2 3t s p 问题的蚁群算法研究及实验结果 2 3 1 蚁群算法的引入 近些年来，研究人员从生物进化的机理中受到启发而提出的一种新型的模 拟进化算法一蚁群算法( a n t c o l o n yo p t i m i z a t i o n , a c o ) ，他们充分利用了蚂蚁 搜索食物的过程与旅行商问题( t s p ) 之间的相似性，为解决n p 难题提供了一条 新的途径。另外，蚁群算法还被用于作业车间调度问题、二次分配问题、多维 背包问题和数据的特征聚类过程等问题，取得了很好的寻优结果。 蚁群算法，又称蚂蚁算法，是自2 0 世纪5 0 年代中期创立了仿生学以来， 人们因从生物进化的机理中受到启发而提出的一种新型的模拟进化算法，是一 种用来在图中寻找优化路径的机率型技术。它由m a r c od o r i g o 于1 9 9 2 年在他 的博士论文中引入，其算法的提出借鉴和吸收了现实世界中蚂蚁种群的行为特 征1 2 5 1 。 2 3 2 蚁群算法原理 通过仔细研究蚂蚁集体觅食的复杂行为，发现每只蚂蚁并不是像我们想象 的需要知道整个世界的信息，它们其实只关心很小范围内的眼前信息，而且根 据这些局部信息利用几条简单的规则进行决策。这样，在蚁群这个集体里，复 杂性的行为就会凸现出来。下面做具体说明： ( i ) 范围 蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径( 一般是 3 ) ，那么它能观察到的范围就是3 * 3 个方格世界，并且能移动的距离也在这个 范围。 ( 2 )环境 蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信 息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到 1 4 上海大学硕士学位论文 窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。 环境以一定的速率让信息素消失。 ( 3 )觅食规则 在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看 是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就 朝信息素多的地方走，并且每只蚂蚁多会以犯小概率错误，从而并不是全往信 息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出 反应，而对食物信息素没反应。 ( 4 ) 移动规则 每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时 候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有 一个随机的小的扰动”。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些 点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。 ( 5 ) 避障规则 如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且 有信息素指引的话，它会按照觅食的规则行为m 1 。 ( 6 )撒播信息素规则 当蚂蚁在食源和巢穴之间往返时，它们会在经过的路线上敷设一种被称为 信息素的化学物质。经过这条线路的蚂蚁越多，这条线路上的信息素浓度也越 大，更多的蚂蚁就会选择这条线路。蚂蚁的这种“正反馈”行为能帮助它们很 快的找到最短觅食线路矧。 通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为， 完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点： 多样性，正反馈性。多样性保证了蚂蚁在觅食的时候不会走进死胡同而无 限循环；正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多 上海大学硕士学位论文 样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可 以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点的巧妙 结合才使得智能行为d o j 涌现出来了。 2 3 3 蚁群算法的数学模型 基本蚁群算法在t s p 问题中的实现过程如下。假设将m 只蚂蚁放到b 个随 机选择的城市中，每只蚂蚁根据一定的概率选择下一个它还没有访问过的城市。 蚂蚁选择下一个目标城市的主要依据有以下两点：t 。( f ) 为t 时刻连接城市i 和j 的路径上的信息素浓度。初始时刻，各条路径上的信息量相等。n 。为 由城市i 转移到j 的可见度，亦称启发信息，该启发信息是由所要解决的问题 给出和一定的算法实现的。在t s p 问题中，一般取r ly 2 1 d f ，d ，表示城市i 、 j 之间的距离。t 时刻位于城市i 的蚂蚁k 选择城市j 为目标城市的概率为： ， 露：肥= ，7 国“矿锄n 肛 式( 2 5 ) 彤( r ) = o 。删”“ 式( 2 5 ) l 其中，a l l o w e d 是待访问城市的集合。蚂蚁k 选中某个城市的可能性是问题本 身所提供的启发信息与蚂蚁目前所在城市到目标城市路径上残留的信息素的函 数。 为了避免对同一个城市的重复访问，每一只蚂蚁都保存一个列表t a b u ( k ) ， 用于记录到目前为止蚂蚁已经访问过的城市集合。t a b u ( k ) 随着蚂蚁寻优过程作 动态调整。为了避免残留信息素过多引起残留信息淹没启发信息，在每一只蚂 蚁走完一步或完成对所有n 个城市的访问后( 即一次循环结束) ，对残留信息进 行更新处理。这种更新模仿人类记忆的特点，在新信息素不断存入大脑的同时， 存储的大脑中的旧信息素随着时间的推移逐渐淡化，甚至忘记【3 ”。这样，锝到 ( t + n ) 时刻在ij 路径上的信息素浓度为： v o ( t + n ) = p r o ( t ) + a r f ( t + n ) 式( 2 6 ) 1 6 上海大学硕士学位论文 其中，p 表示信息素的保留率，则i - p 表示信息素的挥发率。为了防止信息素 的无限积累，p 的取值范围限定在o - - h 表示蚂蚊k 在时间段t 到( h m ) 的过 程中，在i 到j 的路径上的残留信息浓度。根据信息素更新策略的不同，有3 种不同的蚁群算法模型。 ( 1 ) a n t - q u a n t i t y 模型 o ，f + 1 ) = 燃警驴 式( 2 7 ) 其中，q 。是常量，信息素的增量与i j 之间的距离有关。 ( 2 ) a n t - d e n s i t y 模型， 弓( f ，f + 1 ) = 鼢戮端 式( 2 8 ) 其中，q ：是常量，信息素的增加量是一个固定值，与i j 之间的距离无关。 ( 3 ) a n t - c y c l e 模型 霄( f ，川) ；魄燃i 震嚣1 ， 式( 2 9 ) 其中，q ，是常量，l 。表示第k 只蚂蚁的循环路线，即如果蚂蚁经过i j 。则信息 素增量为一个常量除以蚂蚁k 的巡回路线长。这里，信息素增量只与蚂蚁的巡 回路线和q ，有关系，而和具体的d 。无关。 前两种模型利用的是局部信息，蚂蚁在完成一步( 从一个城市到达另外一个 城市) 后更新所有路径上的信息素，而最后一种模型利用的是整体信息，蚂蚁在 一个循环( 对所有n 个城市的访问) 以后，更新所有路径上的信息素。因此，在 求解t s p 问题时，a n t - c y c l e 模型性能比前面两种模型好，本算法采用该模型更 新信息素。 2 3 4 蚁群算法的研究与实现 本算法依然采用第2 2 3 节所提到的3 0 个城市的t s p 问题作为研究样本， 1 7 上海大学硕士学位论文 做了如下的研究与实现： ( 1 ) 蚁群算法实现的流程图 综合上面分析和讨论的蚁群算法的基本原理和数学模型，寻找其最优或近 似最优解的蚁群算法的流程图如图2 5 所示，其基本流程说明如下： 给运行所需要的参数赋初值，比如最大迭代次数c 、蚂蚁数量i l l 等； 启发信息矩阵e t a 、信息素矩阵t a u 和路径生成矩阵t a b u 等变量的初 始化； 将m 个蚂蚁随机地放到t a b u 矩阵上的d 个城市上，即n 1 个蚂蚁随机分 布在t a b u 矩阵的第一列上； 计算每只蚂蚁到其待访问城市的移动概率，并实现轮赌法策略将每只蚂 蚁选择的下一个城市放到t a b u 矩阵的相应位置中； 判断t a b u 矩阵是否全部填满。如果没有填满，说明蚂蚁还没有走完所 有的城市，则转到继续执行；如果已经填满，则说明所有城市均已走 完，跳到下一步继续执行； 保存本次运算的最佳路径并更新信息素矩阵t a u ； 判断是否达到规定的最大迭代次数。如果没有达到，则转到继续执行： 如果已经达到，则输出运行结果并终止执行。 下面就影响算法求解性能的关键因素进行分析与研究： ( 2 ) 参数赋值 本蚁群算法实现的参数主要有城市的坐标c 、最大迭代次数n cm a x 、蚂蚁 数量m 、信息素重要程度参数a l p h a 、启发信息重要程度参数b e t a 、信息素蒸 发参数g a m m a 、信息素增强参数q 等。a l p h a 值的大小表明留在每个结点上的 信息素受重视的程度，a l p h a 值越大，蚂蚁选择以前经过的路线的可能性越大， 但过大会使搜索过早陷入局部最小解；b e t a 的大小表明启发信息受重视的程度， b e t a 越大，蚂蚁选择离它近的城市的可能性也越大，g a m m a 表示信息素的蒸发 1 8 上海大学硕士学位论文 率，如果它的值取得不恰当，得到的结果会很差。 根据以上分析得知，参数赋值m 1 是比较关键的一个环节，