（计算机应用技术专业论文）蚂蚁遗传算法研究及其在旅行商问题中的应用.pdf

摘要 本文对传统的蚂蚁算法和遗传算法进行了研究和改进，并将两者有机结合， 提出了一种新型的蚂蚁遗传算法。该算法有效地利用了蚂蚁算法的正反馈特性和 遗传算法的全局收敛特性，能快速有效地搜索最优解。将该算法应用到经典的旅 行商问题，并通过m a t l a b 仿真实现，并与经典算法进行比较分析，结果表明了 算法的可行性和有效性。 论文的主要工作如下： 一、对标准蚂蚁算法进行了改进。在蚂蚁算法中添加了三条假设，蚂蚁能通 过触角实时交流进而决定下一步选择。在触角实时交流中采用了长期记忆和短期 记忆的假设，从而提出可变挥发度来影响局部信息素和全局信息素的更新。 二、对标准遗传算法进行了改进。对具体问题采用不同的编码方式来优化数 据结构；通过修改适应度函数来减少计算量：提出了置顶增强因子来加速收敛： 提出了动态自适应方案来控制自然选择以防止早熟。 三、提出了一种新的蚂蚁遗传算法。首先，采用遗传算法求得初始路径种群； 其次，通过全局信息素更新策略将其转化为蚂蚁算法的初始信息素矩阵，从而加 速蚂蚁算法的收敛速度：最后，为了防止陷入局部最优解，用蚂蚁算法求得新的 路径来更新遗传算法的种群。 四、应用于旅行商问题。对蚂蚁遗传算法、标准遗传算法、改进遗传算法、 标准蚂蚁算法、改进蚂蚁算法这五种进化算法进行了仿真实验。结果表明蚂蚁遗 传算法的收敛率更高，表明具有更好的全局收敛性能，蚂蚁遗传算法在更少的迭 代次数达到全局最优解，具有更高的收敛速度。 关键词：旅行商问题；蚂蚁算法；遗传算法；蚂蚁遗传算法 a b s t r a c t s o m eu p s w i n g sh a v eb e e nd o n eb a s e do nt h er e s e a r c ha b o u tt h et r a d i t i o n a lg e n e t i c a l g o r i t h ma n da n to p t i m i z a t i o na l g o r i t h m an e wh y b r i da l g o r i t h mg a a c o i sb r o u g h t f o r w a r di nt h i st h e s i s ，w h i c hc o m b i n e st h ea n tc o l o n yo p t i m i z a t i o n sp o s i t i v ec h a r a c t e r a n dg e n e t i ca l g o r i t h m sg l o b a lc o n v e r g e n c ef o rf a s t e ra n db e t t e rs e a r c hc a p a b i l i t y t h e a l g o r i t h mi sa p p l i e dt ot h ec l a s s i ct r a v e l i n gs a l e s m a np r o b l e m c o m p a r e dt ot h ec l a s s i c a l g o r i t h mt h r o u g ht h et o o lo fm a t l a b ，t h er e s u l ts h o w st h a tt h ef e a s i b i l i t ya n d v a l i d i t yo ft h ea l g o r i t h m t h em a i nr e s e a r c hw o r ki nt h i sp a p e ri sa sf o l l o w s 1 i m p r o v eo nt h es t a n d a r dc o l o n yo p t i m i z a t i o na l g o r i t h m t h r e eh y p o t h e s i z e si s a d d e do nt h es t a n d a r da c o a n t sc a nc o m m u n i c a t ew i t ht h e i ra n t e n n aw h e nt h e ym e e t o nt h er o u t i n e ，w h i c hc a l lb eu s e dt oj u d g et h en e x ts t e p d u r i n gt h ec o m m u n i c a t i o n ， t h el o n g t e r mm e m o r ya n ds h o r t t e r mm e m o r yi st a k e ne f f e c t e do nt h ep h e r o m o n e s g l o b a la n dl o c a lu p d a t i n gs t r a t e g y 2 i m p r o v eo nt h eg e n e t i ca l g o r i t h m d i f f e r e n tp r o b l e m ss h o u l da d o p td i f f e r e n t c o d i n gs c h e m ei no r d e rt oo p t i m i z et h ed a t as t r u c t u r e t h ea d a p t a t i o nf u n c t i o ni s m o d i f i e di no r d e rt od e c r e a s et h ec o m p u t a t i o n t h et o ps t r e n g t h e n i n gf a c t o ri sg i v e na s t os p e e dt h ec o n v e r g e n c e 。t h ed y n a m i ca d a p t a t i o ns c h e m ei su s e dt oa v o i dt h e a l g o r i t h mp r e m a t u r e l y 3 p u tf o r w a r dan e wh y b r i da l g o r i t h mg a a c o f i r s t l y ，a d o p tt h eg e n e t i c a l g o r i t h mt oi n i t i a lt h ep o p u l a t i o n s e c o n d l y ，c o n v e r tt h ep o p u l a t i o ni n t ot h eo r i g i n a l p h e r o m o n em a t r i xi no r d e r t os p e e d i n gt h ec o n v e r g e n c e t h i r d l y ，u s et h er o u t i n eo fa n t c o l o n yo p t i m i z a t i o na l g o r i t h mt ou p d a t et h ep o p u l a t i o no fg e n e t i ca l g o r i t h m ， 4 a p p l y t o t r a v e l i n gs a l e s m a np r o b l e m i nt h i sp a p e r ，t h ea l g o r i t h m s a r e c o m p a r e dw i t he m u l a t i o n t h er e s u l ts h o w st h a tt h eg a a c oi sb e t t e rt h a na n yo t h e ro f s t a n d a r dg a ，i r e p r o v e dg a ，s t a n d a r da c o ，a n di m p r o v e da c o t h er e s u l ts h o w st h a t t h eg a a c oh a sh i g h e rc o n v e r g e n c ep r o b a b i l i t ya n dg l o b a lc o n v e r g e n c ec a p a b i l i t y i t c a nr e a c ht h eg l o b a lo p t i m a lv a l u ef a s tw i t h i nf e w e ti t e r a t i o nt i m 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 n ；g e n e t i ca l g o r i t h m ；a n tc o l o n yo p t i m i z a t i o n a l g o r i t h m ；g a a c o 插图和插表清单 表1 易访度参数变化的蜕变类型1 8 表2 s a c o 、i a c o 在旅行商问题中的应用比较3 3 表3s a c o 、i a c o 算法中蚂蚁数量对最优解的关系3 3 表4 s g a 、i g a 在旅行商问题中的应用比较3 4 表5 种群规模与最优解之间的关系3 5 表6 最大遗传代数与最优解之间的关系3 6 表7i g a 、i a c o 、i g a i a c o 在t s p 问题中的应用比较3 7 图1 标准蚂蚁算法的算法流程图一7 图2 标准遗传算法的算法流程图1 3 图3 改进蚂蚁算法的算法流程图2 0 图4 改进遗传算法的算法流程图2 3 图5 蚂蚁遗传算法的算法简图2 4 图6 蚂蚁遗传算法的算法流程图2 6 图7m a t l a b 开发编程调试环境实现过程图3 2 图8 对f o g e l 一3 0 用改进蚂蚁算法搜寻3 0 0 次的一次试验图3 4 图9 遗传算法中种群大小与最优解之间的关系3 5 图1 0 遗传算法中最大遗传代数与最优解之间的关系3 6 图1 1 对o l i v e r 3 0 用改进遗传算法迭代3 0 0 次的一次试验图一3 7 长沙理工大学 学位论文原创性声明 本人郧重， i 叫：所丛交的沦文是本人j a - 导师的指导下独立进行研究所取得的 彤 究成果。除了文r f l 特别加以标注引用的内容外，本论文小包含任何其他个人或 集体已经发表或撰弓的成果作品。对本文的研究做出重要贡献的个人和集体，均 已往文中以l j 确方式标i ! i j 。本人完全意识到本声明的法律后果由本人承担。 作名答名： 鸯雪季 【i 期：埘年牟月岁dh 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 i 、蒯。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：李季季 日期：蜥牟月如日 导师签名：剐哗识 日期：2 r 5 年弓月1 日 1 1 问题的提出 第一章绪论 旅行商问题f 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 ) 是一个典型的组合优化 1 9 题，其时间复杂度不能直接用多项式来描述，其可能的路径是一1 ) ! 2 ，运行的 时间将会成指数级增长，当问题达到一定的规模，如果要遍历所有的路线，那么 即使用当前最先进的计算机来求解，其求解的时间也是不能容忍的，于是寻找有 效的近似求解算法具有重要意义。 旅行商问题是指某旅行商出某城市出发，然后遍历若干个城市且每个城市仅 通过一次，最后又回到出发点，求最短的行程。旅行商问题的数学描述如下。 已知旅行商要经过的城市序列号为c i t y n u m 体2 ，, i f 】，并且已知这些城市的 坐标矩阵为c i t y p o s i zy ，求旅行商从某城市k 出发，经过所有城市且仅一次 后回到出发点的路程函数，妒) 的最小值。其中城市问的距离计算公式为： ，( 矿) = d ( k ，k + 。) + d ( v ，k ) ( 1 1 ) 这里v = 旷，y ：，y 。y ，) ，表示旅行商搜索过程中经过的城市序列，由于其构 成了封闭圈也叫做哈密顿圈，有点类似于计算机领域里路由寻址通讯过程， y ，( ，t 1 ，n ) 则表示相应的城市结点，且有v i - y f ( i j ) ，v fe c i t y n u m 。 因问题的不同，距离的计算公式会有差异。如果是平面上的几何距离，则有： d ，v ，) = d d ；( 工_ - - x v j ) 2 + y ，。m ( 1 - 2 ) 如果距离对称，则有d ( k ，k ) - d ( 匕，) ，若为非对称，则d k ，k ) ，d ( 一，) ， 如果计算的是球面距离，那么其定位方式通常采用经度和纬度值来描述。比如， 航空、航海求的最短航线，这时求解的是最短球面距离。球面上a 、b 两点的最 短距离是指过球面上a 、b 两点和球一i i , 0 的大圆劣弧长盈。 已知球面上a 、b 两点的经度及纬度坐标分别为4 ( 魄，b ) ，b ( ，吃) ，我们定义 东经为正，西红为负，北纬为正，南纬为负。 d = r 口 ( 1 3 ) c o s a = c o s 单o s 甲1 + s i n s i n q ，2 c o s a 8 ( 1 4 、 其中8 表示a b 两点的经度差，表示劣弧对应的球心角，且有a p 的算法公 式： 泓段二包 ：。i 蝥一0 宁掣 ( 1 ，) ”一 3 6 0 9 一慨一吼若协一见j ，】8 0 。 。 在航海的过程中，要考虑风速和海浪时变的条件，那么距离的计算方式就变 得较为复杂。本文研究的是平面上距离对称的静态旅行商问题，即旅行商往返任 意两城市间，城市问的距离不会因为来往的时间不同而发生改变。 在我们的生活中，有许多类似的旅行商问题，比如连锁店的货物配送路线、 生产调度、任务分配等等，它们都可以抽象转化为旅行商问题，因而旅行商问题 求解方法的研究具有重要实用价值。 1 2 研究的背景与现状 旅行商问题是一个典型的组合优化问题，是一个n p 完全问题。虽然理论上这 类问题的最优解可以枚举法找到，但实际上这往往是不可行的。随着问题规模的 增大，组合优化阀题的搜索空间也急剧扩大，从而会遇到组台优化中最具挑战性 的组合爆炸问题。人们己意识到应当把主要精力放在寻求其近似最优解或次优解 上。现在求近似最优解的传统方法主要有三种【2 】：枚举法、启发式算法和搜索算法。 牧举法：枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续 函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达 不到最优解。另外，当枚举法空蒯比较大时，该方法的求解效率比较低，有时甚 至在目前最先进的计算工具上都无法求解。 启发式算法：寻求一种能产生可行解的启发式规则，以找到一个最优解或近 似晟优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找 出其特有的启发式规则，这个启发式规则无通用性，并不一定适合于其它问题。 搜索算法：寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索 操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问 题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和求解效率上 达到一种较好的平衡。 随着问题种类的不同，以及问题规模的扩大，要寻求到一种能以有限的代价 来解决最优化问题的通用方法仍是一个难题。仿生学为我们解决这类问题提供了 一个有效的途径，开创了一种新的全局优化搜索算法的思路。 国外成立许多专门研究t s p 问题的小组。他们建立了网站收集相关算法和t s p 研究成果以供交流。其中有代表性的是，美国普林斯顿大学数学系的t s p 小组网 站( h t t p ：w w w m a t h p r i n c e t o n e d u t s p ) ，德国海德尔堡大学的t s p l i b 的公开数 据库( h t t p ：w w w i w r u n i h e i d e l b e r g d e g r o u p s c o m o p t s o f t w a r e t s p l i b 9 5 ) ，它们 包括许多不同来源和类型的t s p 及相关问题的样本实例，目前该数据库已成为国 际上t s p 算法研究的基准数据。现在有效的求解方法【2 】1 3 】有免疫算法、遗传算法、 蚂蚁算法、模拟退火算法、h o p f i e l d 算法、l k h 算法等等，在算法排行榜上高居 首位的是l k h 算法，其次就是蚂蚁算法和遗传算法。国内的研究还缺乏这种有组 织的研究小组，研究相对滞后。 2 1 3 论文的主要工作 本文针对旅行商问题，从应用的角度对遗传算法和蚂蚁算法分别进行分析与 研究后，设计了一种新型的蚂蚁遗传算法。 本文所做的研究工作如下： 一、对标准蚂蚁算法进行了改进。在蚂蚁算法中添加了基本假设，蚂蚁不仅 髓够通过路径上的信息素进行异步交流，且能通过触角实时交流进行下一步选择。 在触角实时交流中采用了长期记忆和短期记忆的假设，从而提出可变挥发度来影 响局部信息素和全局信息素的更新。 二、对标准遗传算法进行了改进。对具体问题采用不同的编码方式来优化数 据结构；通过修改适应度函数来减少计算量；提出了置顶增强因子来加速收敛： 提出了动态自适应方案来控制自然选择以防止早熟。 三、提出了一种新的蚂蚁遗传算法。首先，采用遗传算法求得初始路径种群； 其次，通过全局信息素更新策略将其转化为蚂蚁算法的初始信息素矩阵，从而加 速蚂蚁算法的收敛速度；最后，为了防止陷入局部最优解，用蚂蚁算法求得新的 路径来更新遗传算法的种群。 四、应用于旅行商问题，对蚂蚁遗传算法、标准遗传算法、改进遗传算法、 标准蚂蚁算法、改进蚂蚁算法这五种进化算法进行了仿真实验。结果表明蚂蚁遗 传算法的收敛率更高，表明具有更好的全局收敛性能，蚂蚁遗传算法在更少的迭 代次数达到全局最优解，具有更高的收敛速度。 1 4 论文的结构 本文的结构大致如下： 第一章绪论，在该章中介绍了旅行商问题及其研究背景，叙述了本文所做的 主要研究工作和论文的结构。 第二章蚂蚁算法与遗传算法的原理及研究动态。在该章中介绍了蚂蚁算法和 遗传算法的生物学基础和原理，给出了两种算法的步骤和流程图，论述了两种算 法的研究动态。 第三章蚂蚁算法、遗传算法的改进及混合研究。在该章中分析了传统的蚂蚁 算法和遗传算法的优缺点之后，提出了对传统的蚂蚁算法和遗传算法改进，并提 出了一种新型的蚂蚁遗传算法，给出算法的步骤和流程图。 第四章蚂蚁遗传算法在旅行商问题中的应用。在该章中以h o p f i e l d l 0 为例， 说明了算法的关键步骤的计算过程。 第五章数值计算和仿真实现。在该章中应用旅行商问题对算法进行了检验和 比较，给出了相关的试验仿真。 在结束语中总结了本文的工作，探讨了下一步的研究工作，叙述了论文的写 作过程中的体会和展望。 3 第二章蚂蚁算法、遗传算法的原理和研究动态 2 1 标准蚂蚁算法的原理 2 1 1 蚂蚁算法的生物学基础 蚂蚁是社会性昆虫【钔，具有合作，品极分化，个人利他等特点。蚂蚁是母系社 会，以雌性为中心。通常家族成员有雌蚁、雄蚁、工蚁。雌蚁是群体的创造者和 母亲。雄蚁经婚飞交尾，然后离巢死去。它们同是单个蚁后的女儿，蚁后产的卵 是同样大小的，而且遵从着一定的规律，受精卵孵出的是工蚁，未受精卵孵出的 是雄蚁。工蚁接受蚁后的统治，蚁后分泌种外激素来抑制工蚁的发育。工蚁是 生殖器官未发育的雌蚁，它们不事生育，只管劳作。工蚁是蚁群中辛勤的劳动大 军，担负觅食、建巢、育雏、保卫、防御、清洁等工作。 蚂蚁以集体的力量，进行觅食、御敌、筑巢的能力，群体所表现出来的“智 能”，我们称之为群集智能( s w a r mi n t e l l i g e n c e ) 。生活中还有许多类似的现象， 比如蜜蜂采蜜、筑巢等等。整个过程中，个体似乎仅仅按照简单的规则在运行， 但是群体表现出来的高智慧却远远超越了简单的迭加。 真实的蚂蚁外出觅食的时候会不断地在经过的路径上分泌外激素，记录自己 经过的路线，路径上的外激素浓度将影响后续蚂蚁的行进路线。对于较短的路径， 在单位时间内经过的蚂蚁数量较多，路径上的外激素浓度较高，吸引着较多的蚂 蚁沿该路径搜索；对于距离较长的路径，由于单位时间内经过的蚂蚁数量较少， 路径上的外激素浓度较低；而且外激素会随着时问而挥发，从而较长的路径的外 激素浓度弱化就会比较明显，而对于较短路径则由于经过的蚂蚁数量较多，外激 素浓度的衰减作用就显得次要，主要体现为外激素浓度被经过的蚂蚁增强，从而 形成了一种正反馈。这种正反馈机制为蚁群寻找最优路径提供了可行性。 2 1 - 2 标准蚂蚁算法的基本概念 在论述标准蚂蚁算法之前，定义一些变量。蚂蚁算法中的人工蚂蚁有别于真 实蚂蚁，采用信息索来替代外激素一词。 定义2 1 在蚂蚁外出觅食的过程中，路径上边的信息素浓度r ，其中f “表示 从结点，到结点的信息素浓度，且有 氍：；：； 定义2 2 在蚂蚁外出觅食的过程中， 点i 到结点j 的可见度，且有 4 ( 2 1 ) 路径上结点的可见度7 ，其中叼“表示结 t 1 i j 。1 ，d “i j t 2 2 ) 、 1 = 0 j j 定义2 3 在蚂蚁外出觅食的过程中，路径上边的可访度五，其中九表示蚂蚁 的从结点出发到未访问列表中结点“的可访度， 。= t i a 。 ，7 。r ，u 隹a n t v j s i t e d ( 膏，j ) ( 2 3 ) 式中口表示路径上的信息素浓度对结点的可访度的影响指数，其中口表示结 点的可见度对可访度的影响指数，“盛a n t v i s i t e d 膏，i ) ，表示结点u 不属于第k 只蚂蚁在造访结点j 后的已经访问列表，即u 属于未访问的结点列表。 定义2 4 在蚂蚁外出觅食的过程中，路径上边的可访度概率p ，其中p ；表示 第k 只蚂蚁从结点j 出发选择下个结点的概率，有 九： 露- i r 2 _ _ ( 2 4 ) 2 冶口口( ，) 山 标准蚂蚁算法的三个关键策略：下一个结点的选择策略、信息素的局部更新 策略和全局更新策略。 一、下一个结点的选择策略 蚂蚁构造可行解的过程是实旋n 步下一个结点的选择策略的过程。首先需要 确定起点，通常采用指定起点或者随机起点的方式。 迈出第一步以前，首先要初始化信息素矩阵，采用最近邻域法求得当前最优 路径z + ，计算得路径值r ，定义初始信息素浓度均为，有：1 l * 。引进一个 比例选择参数q 。( o c 吼c 1 ，一般取0 9 ) 。蚂蚁选择下一个结点时，以比例选择 可访度九。最大的结点，以( 卜q 。) 的按照可访度概率p 建立轮盘赌的方式选择下一 个结点，。下一个结点就可根据边的可访度或边的可访度概率来确定。第n 步则 是归巢或者回到起点。 ，8 r gm a x “t n t n i i t ( t j ) “) i r q g 。 ( 2 5 ) i ji f 譬) q o 二、信息素的局部更新策略 在蚂蚁迈出一步以后，路径上边的信息素会更新变化。信息素的变化分为两 部分，一个是信息素会随着时问而挥发，二个是蚂蚁经过后会对在路径上释放一 定的信息素。 f ，( f + 1 ) = ( 1 一p ) f “( t ) + p - r ， ( 2 6 ) 一口； 5 ( 2 7 ) 其中r ( 0 ) ：“：1 l + ，p 为当前求得的最优路径长度。当第k 只蚂蚁从结点i 访问结点j ，则口曼为1 ，否则为0 。p 则表示信息素的挥发度。 三、信息素的全局更新箢略 当蚂蚁外出觅食归巢以后，为了强化当前最优路径，采用了最优路径强化， 较差路径弱化的策略。在蚂蚁算法中，只有构成当前全局最优路径的那些边上的 信息素才能得到增强，其它边上的信息素浓度都会削弱。经过若干次外出觅食之 后，那些最优路径会逐渐被强化，从而加快收敛的速度。 f ，( + 1 ) = ( 1 一p ) 一盯( t ) + p a 百“ ( 2 8 ) 勺骘吒 ( 2 9 ) 其中f ( o ) = r o = 1 l + ，r 为当前求得的最优路径长度。假若第k 只蚂蚁搜索到 了当前最优值，第k 只蚂蚁从结点j 访问结点j ，则6 0 为1 ，否则为0 。式中p 表 示信息素的挥发度。 2 1 3 标准蚂蚁算法的算法描述 其算法流程图见图1 ，算法步骤如下。 s t e p l ：初始化结点的坐标，计算结点间的距离，边的可见度矩阵： s t e p 2 ：初始化蚂蚁的数量、信息素浓度矩阵，设定蚂蚁的外出觅食次数，设 定蚂蚁的初始起点选择方法； s t e p 3 ：初始化蚂蚁已访问结点列表空，未访问结点列表； s t e p 4 ：根据蚂蚁的起始点选择方法蚂蚁的确定起点，更新蚂蚁的已访问列表， 未访问结点列表； s t e p 5 根据可访度采用下一个结点的选择策略确定下一个结点，采用信息素 的局部更额策略、更新蚂蚁的已访问路径及未访问结点列表； s t e p 6 ：重薪计算当前未访问边的可访度； s t e p 7 ：判断蚂蚁的未访问结点列表是否为空，若否，转入s t e p 5 ，若是，则 转入s t e p s ； s t e p 8 ：回到出发点，采用信息素局部更新策略； s t e p 9 ：评估当前路径，更新当前最优路径，采用信息素全局更新策略； s t e p l 0 ：是否达到的蚂蚁外观觅食次数，若否，n # i - 出觅食次数加1 ，转入 s t e p 3 ，若是，则转入s t e p l l ； s t e p l l ：输出当前寻得的最优路径和最优值，程序运行报告，结束。 图l 标准蚂蚁算法的算法流程图 7 下一个结点的选择策略流程图 2 2 蚂蚁算法的研究动态 意大利学者m a r c od o r i g o 在研究中发现蚁群外出觅食的过程与旅行商问题存 在着极大的相似性，于是将蚂蚁搜索食物的方法运用到求解旅行商问题。1 9 9 1 年 d o r i 2 0 在论文中提出了蚂蚁系统1 5 】【6 】( a n ts y s t e m ，简称a s ) 、1 9 9 6 年又提出了 蚁群系统算法1 7 】( a n tc o l o n ys y s t e ma l g o r i t h m ，简称a c s 算法) 、1 9 9 9 年又提出 了蚁群优化算法【8 】 9 】( a n tc o l o n yo p t i m i z a t i o na l g o r i t h m ，简称a c o ) ，为了克服 基本蚂蚁算法的不足，人们对其作了若干改进，2 0 0 0 年t h o m a s 和d o r i g o 共同提 出了最值蚂蚁算法( m a x m i na n ts y s t e m ) 1 0 】。w a i t e r 和t h o m a s 先后对蚂蚁算法的 收敛性进行了证明( 1 1 1 一【1 5 ，为算法的收敛性奠定了理论基础。 蚂蚁算法是继模拟退火算法、遗传算法、禁忌搜索( t a b us e a r c h ) 算法、人工神 经网络算法等以后，出现的又一种应用于组合优化闯题的启发式搜索算法。蚂蚁 算法自提出以来，人们通过若干典型的对称型和非对称型t s p 问题的求解，用蚂 蚁算法与其它一些常用启发式方法作了一系列比较，除了l i n k e r n i g h a n 的局部改 进法之外，蚂蚁算法优于模拟退火算法、遗传算法、禁忌搜索法等其它方法。随 后，又在二次分配问题、工件排序问题、图着色问题、调度问题、大规模集成电 路、通讯网负载平衡、序列订货问题等相继得到测试、求解和应用。近年来，蚂 蚁算法又被应用于一些约束型问题和多目标问题的求解。 国内近年来有开始了蚂蚁算法的研究，获得了一些令人满意的成果。查凯提 出了蚂蚁的贡献度概念1 16 】：李勇对蚂蚁算法提出了三个方面的改进【1 6 】：f 1 1 动态目 标城市选择，( 2 ) 信息素挥发系数动态变化，f 3 ) 最差路线上的信息素弱化；丁建立 i i 叫【1 9 j 等人提出了混合蚂蚁算法，讨论了结合蚂蚁算法和遗传算法的结合，提出了 结合遗传算法的全局收敛特性和蚂蚁算法的正反馈特性的思想：吴斌【2 0 】等人提出 了基于分段方法的求解算法；陈峻【2 1 i 等人则提出了聚度的概念；郝晋【2 2 1 等人设计 了一个随机扰动函数来防止搜索停滞的现象；张纪会1 2 3 1 等人提出动态变化选择下 一步的随机抽样点系数：毕军i z 4 j 等人则提出了下一步结点的选择抽样点系数采用 分段调整的方法。 2 3 标准遗传算法的原理 2 3 1 遗传算法的生物学基础 遗传算法( g e n e t i c a l g o r i t h m ，简称g a ) 1 2 5 1 2 6 】是由美国m i c k i g a n 大学的j o h n h h o l l a n d 首先提出的。它来源于达尔文的进化论和孟德尔的群体遗传学说。生物 的进化是通过繁殖、变异、竞争和选择这四种基本形式实现的。 从远古时代的单细胞开始，历经环境的变迁，生命经过了从低级到高级、从 简单到复杂的演化之路，不但延续下来而且产生了人类这种有思维、有智力的高 级生命体。人类找到了生命的最佳结构与形式，它不仅仅可以被动地适应环境， 更重要的是他能通过学习、模仿与创造，不断提高自身适应环境的能力。神经网 8 络是人类对其大脑信息处理机制的模拟，模糊系统是人类对其思维的方式的类比。 除了自身结构学习以外，人类还可以向自身的进化这一更为宏观的过程学习，来 增强自己解决问题的能力，其代表性的方法就是进化计算。 众所周知，构成生物的基本结构和功能单位是细胞。细胞中含有一种微小的 丝状化合物称为染色体。染色体是生物所有遗传信息的载体。决定生物遗传性状 的染色体主要由d n a 和蛋白质组成。在d n a 中，遗传信息在一条长链上按一定 的模式排列，即所谓的遗传编码。d n a 长链中占有一定位置的基本遗传单位称为 基因。细胞在分裂时，遗传物质d n a 通过复制而转移到新产生的细胞中，新细胞 就继承了1 日细胞的基因。有性生殖生物在繁殖下一代时，两个同源染色体之间通 过交叉而重组，亦即在两个染色体的某相同位置处d n a 被切断，其前后两串分 别交叉组合而形成两个新的染色体。另外，在进行细胞复制时，虽然概率很小， 但也有可能产生某些复制差错，从而使d n a 发生某种变异，产生出新的染色体。 交叉和变异是生物进化的基础。生物在其延续生存的过程中，逐渐适应生存环境， 使得其品质不断得到改良，于是物种得到进化【2 】( e v o l u t i o n ) 。生物的进化是以集 团形式共同进行的，这样的一个团体称为群体( p o p u l a t i o n ) ，组成群体的单个生物 称为个体( i n d i v i d u a l ) ，每一个个体对其生存环境都有不同的适应能力，这种适应 能力称为个体的适应度( f i t n e s s ) 。由于对环境适应性好的染色体经常比适应性差的 染色体有更多的机会遗传到下代，因此物种将逐渐地向适应于生存环境的方向 进化，从而产生出优良的品种。按照遗传学的术语，个体也称为染色体 ( c h r o m o s o m e ) ，个体的分量称作基因( g e n e ) ，分量的取值称作等位基因( a l l e l e ) 。 虽然人们还未完全揭开遗传与进化的之间奥秘，既没有完全掌握其机制，也 不完全清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与 进化的以下几个特点却为人们所共识： ( 1 ) 生物的所有遗传信息都包含在其染色体中。染色体决定了生物的性状。 ( 2 ) 染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染 色体上。 ( 3 ) 生物的繁殖过程是由其基因的复制过程来完成的。 ( 4 ) 通过同源染色体之间的交叉或染色体的变异会产生新的特种，使其呈现 新的性状。 ( 5 ) 对环境适应性好染色体经常比适应性差的染色体有更多的机会遗传到下 一代。 遗传算法中，决策变量组成了问题的解空间，对问题的最优解的搜索过程是 通过对染色体的搜索过程来进行的，从而所有合理的染色体就组成了问题的搜索 空间。 生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受 其启发，人们致力于对生物各种生存环境特性的机理研究和行为模型，为自适应 系统的设计和开发提供了广阔的前景。 9 2 3 2 标遗传算法的基本概念 遗传算法中有五个基本要素：参数编码、初始群体的设定、适应度函数的设 计、遗传算子的设计、控制参数设定。 2 3 2 1 参数编码 标准遗传算法中采用了二进制编码，是因为它具有如下优点： ( 1 ) 二进制编码类似于生物染色体的组成，从而算法易于用生物遗传理论来解 释并使得遗传操作如交叉、变异等很容易实现： ( 2 ) 采用二进制编码时，算法处理的模式数较多。 但是，二进制编码同时也存在以下的缺点： ( 1 ) 相邻整数的二进制编码可能具有较大的h a m m i n g 距离，将降低遗传算子的 搜索效率； ( 2 ) - 进制编码时，一般要先给出求解的精度以确定串长，而一旦精度确定后， 就很难在算法执行中进行调整： ( 3 ) 在求解高维优化问题中，二进制编码串将非常长，从而使得算法的搜索效 率很低。 由于采用的是0 1 编码，于是要表达一个基因片段的发生可能就需要许多位来 表示，还有可能具有不同长度的位，处理起来相对的繁杂，通用采用基因属性的 最大位数来统一基因的属性编码长度。如果用a 来表示其中一位，口的值为0 或者 1 ，于是染色体的编码变成： 4 1 1 1 2 - a 日；口 口。1 口：a 。t , r r 弋一 编码的长度为： ；了z ；， 钎+ 采用统一的编码长度的方法，则有 l ，弹m a x l i ，i = 1 , 2 ，n 首先我们要将问题的决策变量转换成基因，然后对基因进行编码，由这些编 码组成染色体，通过染色体的遗传进化操作，产生新的优良的染色体，然后我们 需要把染色体转换成决策变量来解释，这个过程中就存在着编码和解码的问题。 如果问题的规模变得庞大时，其编码和解码的占用的耗费相当高的。遗传算法是 采用问题参数的编码集进行工作的，而不是采用问题参数本身。因此，在遗传算 法实现时首先要考虑的是参数的编码。目前的编码方式有：二进制编码、实数编 码、整数编码等。 1 0 2 3 2 2 初始种群 遗传算法中的每一条染色体代表着一个可行解，由这些可行解组成的集合， 称为种群。种群的规模则是指种群包含染色体的数目。种群规模越大，种群中个 体的多样性越高，算法陷入局部解的可能性就越小；种群的规模越大，由于不是 采用分布式计算方法，算法的迭代进化周期会延长，运算量大大增加。现在种群 规模的大小设定的方法是尝试法和经验法。 2 3 2 3 适应度函数 遗传算法的搜索过程中，基本不用外部信息，仅以适应度函数为依据，适应 度函数不受连续可微的约束且定义域可以为任意集合，对适应度函数的唯一要求 是，输出的函数值是能加以比较的非负结果。 在遗传算法中，个体适应度确定了该个体被遗传到下一代群体中的概率。个 体的适应度越大，该个体被遗传到下一代的概率也越大；反之，该个体被遗传到 下一代的概率也越小。个体的适应度与其对应的个体表现型的目标函数值相关联， 个体越接近于目标函数的最优点，其适应度越大：反之，其适应度越小。但实际 优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最 小值，因此，必须寻求出一种通用且有效的由目标函数值到个体适应度之间的转 换关系，由它来保证个体适应度非受。适应度函数是用来区分种群中个体好坏的 标准，是进行自然选择的唯一依据。适应度函数的设定要根据实际问题而定，目 前主要通过目标函数映射成适应度函数。 在旅行商问题中，目标函数就是求f ( v ) = d ( k ，+ ，) + d ( k ，k ) 的最小值，标 准遗传算法求解时，采用了目标函数的倒数，即1 f i t n e s s ( v ) = 1 ，( y ) 作为适应度函 数。路径越长，适应度越小；路径越短，适应度越大。 2 3 2 4 遗传算法的操作算子 遗传算法是种仿生算法，即模拟生命演化的算法。它是从一个初始种群出 发，不断重复执行选择、交叉和变异的过程，使种群进化越来越接近某一目标。 如果视种群种姓为超空间的一组点，选择、交叉和变异的过程即是在超空间中进 行点集之间的某种变换，通过信息交换使种群不断进化。 1 选择算予 从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。在生物的遗传和自 然进化过程中，对生存环境适应度较高的物种将有更多的机会遗传到下一代；而 对生存环境适应程度较低的物种遗传到下一代的机会就相对较少。模仿这个过程， 遗传算法使用选择算子对群体中的个体进行优胜劣汰操作。选择的目的是把优良 的个体直接遗传到下一代，或通过配对交叉产生新的个体再遗传到下一代。 选择操作需要确定如何从父代群体中选取个体遗传到下一代群体中，它是建 立在群体中个体的适应度评估基础上的。比例选择算子，是指个体被选中并遗传 到下一代群体中的概率与该个体的适应度大小成正比，也叫赌轮选择a 比例选择算子的具体执行过程： ( 1 ) 计算群体中每条染色体的适应度值f i t n e s s ( v = 1 ，i v 4 j ； ( 2 ) 计算出每个个体的相对适应度 f f 缓! ! 竺竺坚! ( 2 1 0 ) 1 砉只一 ( 3 ) 根据相对适应度的大小建立赌轮，适应度值高的个体占据的面积较大， 被选择复制到下一代的机率就高，而被选择参与交叉、变异操作的机率也高。通 过选择算子保证了优良个体在遗传操作中的不断传递，使整个群体不断向优良种 群进化。 2 交叉算子 在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色 体，从而产生出新的个体或物种。交配重组是生物遗传和进化过程中的一个主要 环节。模仿这个环节，在遗传算法中也使用交叉算子来产生新的个体。遗传算法 中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基 因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特 征，它在遗传算法中起着若键作用，是产生新个体的主要方法。每个基因具有不 同的属性，如果在进行交叉运算时，出现了基因丢失，这种异常行为相当于决策 变量的缺失，这种异常的染色体将会在自然选择中淘汰。 对于采用二进制编码而言，各种交叉算子都包括两步：首先按一定的概率最随 机地从选择算子操作后产生的新种群中取出要交叉的一对；然后选择一定的交叉 方法，将两个个体进行交换，从而产生一对新的个体。犀叫做交叉概率，它决定 了基因交换的概率。只越大，基因交叉的概率就越高；否则就越低。交叉的方式 大体分四种：单点式、两点式、多点式及环式。 3 变异算子 在生物的遗传和自然进化过程中，其细胞分裂复制环节有可能会因为某些偶 然因素的影响而产生一些复制差错，产生基因的逆转、换位，使得基因的在染色 体中的位置发生变化，使得基因在染色体中的权重发生变化，表现出新的生物形 状。虽然发生这种变异的可能性比较小，但它也是产生新物种的一个不可忽视的 原因。模仿生物遗传和进化过程中的这个变异环节，在遗传算法中也引入了变异 算子来产生新的个体。遗传算法中的所谓变异运算，是指将染色体编码串中的某 些基因座上的基因值用该基因座的其它等位基因来替换，从而形成一个新的个体。 变异算子的基本内容是对群体中个体串的某些基因位上的基因值作变动。尽 管选择和交叉很重要，在遗传算法中是第一位的，但不能保证没有丢失一些重要 的遗传物质即特定位置上的某种取值。为了防止种群中某些个体的值处于不变状 态，需要进行变异操作。变异的目的主要是改变搜索方向，扩大搜索空间，从而 1 2 防止遗传算法早熟。因此，变异在遗传算法中不可缺少的。 2 3 2 5 控制参数设定 在遗传算法的仿真和应用中，首先要 给定一组控制参数，如种群规模、杂交率、 变异率、进化代数等。控制参数的选取不 同会对遗传算法的效能产生很大的影响， 要想得到遗传的最优性能，必须确定最优 的参数设置。通常控制参数的设定有两种 方法： ( 1 ) 经验法：根据自己的经验，对控 制参数进行设定。 ( 2 1 尝试法：该方法就是首先选取有 限个控制参数表，然后对每个控制参数表 执行遗传算法以比较它们的性能，并选取 最优的控制参数表。有点类似于神经网络 的训练学习，可以采用动态的方法输入若 干组控制参数来训练，研究控制参数与最 优解之间的关系。 对于遗传算法的收敛条件不仅仅限 于遗传代数，还可以利用其它一些判别准 则。例如，连续几代的个体平均适应度差 为极小值，种群适应度的方差小于一个阀 值等。控制参数设定的目标是一方面要寻 求加快收敛的搜索策略，另