（应用数学专业论文）蚁群算法的改进及仿真研究.pdf

摘要 摘要 蚁群算法是一种新型的仿生类算法，具有较强的鲁棒性它采用分布式计算 机制，易于实现，已在众多领域取得了广泛的应用本文主要围绕蚁群优化算法 的理论及应用，就如何求解旅行商( t s p ) i h - 题、多目标优化问题进行了研究本文 的主要工作概括如下： 首先针对蚁群算法存在停滞现象的缺点，提出一种基于动态权重的选择策略， 以强化其全局搜索能力改进的初始选择策略以信息素为主扩大搜索范围，迭代 一定次数后则以路径期望为主，从而提高蚁群算法的求解性能并将改进后的蚁 群算法与基本蚁群算法分别应用于旅行商问题( t s p ) 进行仿真实验结果表明，改 进后的算法具有优良的求解性能，可抑制算法过早收敛于次优解，有效防止了停 滞现象 其次为保持多目标优化问题p a r e t o 最优解的多样性，提出了一种新的蚁群算 法选择策略采用多信息素权重，信息素更新结合了局部信息素更新与全局信息 素更新其中，全局信息素更新采用了两个最好解此外，通过设置外部集来存 储p a r e t o 解，并将改进的算法应用在双目标t s p 上仿真实验结果表明新方法比 n s g a i i 和s p e a 2 更有效 关键词：蚁群优化算法；旅行商问题；多目标优化；双目标t s p ；动态权重 a b s t r a c t 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 ) i sa l la l g o r i t h m i ca p p r o a c h , i n s p i r e db y t h ef o r a g i n gb e h a v i o ro ft h er e a la n i m a l s ，w h i c hh a db e e na p p l i e dt om a n yp r o b l e m s t h ed i s s e r t a t i o nf o c u s e so nt h ep r i n c i p l e s ，t h e o r y , a n da p p l i c a t i o n so fa n tc o l o n y o p t i m i z a t i o na l g o r i t h m ( a c o ) ，e s p e c i a l l y , a l li n d e e pa n ds y s t e m i cs t u d yo nh o wt o i m p r o v et h eb a s i c a c oa l g o r i t h m , p a r a l l e li m p l e m e n t a t i o no fa c o ，s o l v i n gt h e p r o b l e m ss u c ha st h et s pp r o b l e ma n dm u l t i p l eo b j e c t i v eo p t i m i z a t i o n f i r s t ，a si sk n o w ns t a g n a t i o nb e h a v i o ri sad i s a d v a n t a g eo ft h ea n tc o l o n ya l g o r i t h m a d y n a m i cw e i g h tb a s e d o ns e l e c ts t r a t e g yi sp r o p o s e dt oe n h a n c ei t sg l o b a ls e a r c h i n g a b i l i t y t h es e a r c hr a n g ei si n i t i a l l ye n l a r g e db yt h ep h e r o m o n ed i f f u s i o n a f t e rc e r t a i n i t e r a t i o n s ，t h es e a r c hr a n g ei sm a i n l ye n l a r g e db yp a t he x p e c t a t i o n a sar e s u l t , t h e p e r f o r m a n c eo f t h ea n tc o l o n ya l g o r i t h mi si m p r o v e d 。t h en e w a l g o r i t h ma n dt h e c l a s s i c a la n tc o l o n ya l g o r i t h ma r ea p p l i e dt ot h et s pp r o b l e m n u m e r i c a lr e s u l t ss h o w t h a tt h en e w a l g o r i t h mi sf e a s i b l ea n dt h es t a g n a t i o nb e h a v i o ri sa v o i d e d s e c o n d l y , i n o r d e rt o p r e s e r v e t h ed i v e r s i t yo fp a r e t oo p t i m a ls o l u t i o n si n m u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m s ，an e wa n tc o l o n ya l g o r i t h mi sp r o p o s e d i nt h e p r o p o s e da l g o r i t h m , t h e s e l e c t i o n s t r a t e g y i s m u l t i - p h e r o m o n e w e i g h t e d , a n d p h e r o m o n eu p d a t eu s e st h ec o m b i n a t i o no ft h em e a la n dg l o b a lp h e r o m o n eu p d a t e e s p e c i a l l y , t h eg l o b a lp h e r o m o n eu p d a t ea d o p t st h eb e s ts o l u t i o na n dt h es e c o n d - b e s t s o l u t i o n i na d d i t i o n , a ne x t e r n a ls e ti ss e tu po u t s i d et os t o r et h ep a r e t os o l u t i o n , a n dt h e i m p r o v e da l g o r i t h mi su s e dt os o l v et h eb i - c d t e f i o nt s ea f t e rt h es i m u l a t i o n e x p e r i m e n t , i ti s s h o w nt h a tt h en e wa l g o r i t h mi sm o r ee f f i c i e n tt h a ns p e a 2a n d n s g a i i k e y w o r d s ：a n tc o l o n yo p t i m i z a t i o n ；t s p ：m u l t i p l eo b j e c t i v eo p t i m i z a t i o n ； b i - c r i t e r i at s p ：d y n a m i c w e i g h t 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：趟赴 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在年解密后适用本授权书。 本人签名： 导师签名：雄l 日期抖 第一章绪论 第一章绪论弟一早三百下匕 1 1 引言 自然界一直是人类创造力的源泉，人类认识事物的能力来源于与自然界的相 互作用之中自然界中的许多自适应优化现象不断给人以启示：生物体和自然生 态系统可以通过自身的演化，使许多在人类看起来高度复杂的优化问题得到完美 的解决近些年来，一些与经典的数学规划原理截然不同的、试图通过模拟自然 生态系统机制以求解复杂优化问题的仿生优化算法相继出现，如遗传算法、蚁群 算法、微粒群算法、人工鱼群算法、混合蛙跳算法等大大丰富了现代优化技术， 也为那些传统最优化技术难以处理的组合优化问题提供了切实可行的解决方 案伴随着模拟自然与生物机理为特征的仿生优化算法时代的悄然兴起，一些仿 生优化算法已在经典n p c 问题的求解和实际应用中显示出强大的生命力和进一 步的发展潜力 生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，看起来 没有集中指挥，但它们却能协同工作，集中事物，建起坚固漂亮的蚁穴，并抚养 后代，依靠群体能力发挥出超出个体的智能蚁群算法是最新发展的一种模拟蚂 蚁群体智能行为的仿生优化算法i l 】，它具有较强的鲁棒性、优良的分布式计算机制、 易于与其它方法相结合等优点 2 - 3 】尽管蚁群算法的严格理论基础尚未确定，国内 外的相关研究还处在实验探索和初步应用阶段，但是目前人们对蚁群算法的研究 已经由当初单一的旅行商问题( t s p ) 领域渗透到了多个应用领域，由解决一维静态 优化问题发展到解决多维动态组合优化问题，由离散域范围内的研究逐渐拓展到 了连续域范围内的研究卜5 1 并且在蚁群算法的硬件实现上也取得了许多突破性的 研究进展，从而使这种新兴的仿生优化算法展现出勃勃生机和广阔的发展前景 本章首先阐述了蚂蚁觅食的生物学行为，接下来阐述蚁群优化算法的思想起 源，紧接着评述蚁群算法的国内外发展现状，最后给出了本文的主要工作和内容 安排 1 2 蚁群觅食的生物学行为 自然界中蚁群的自组织行为很早就引起了昆虫学家的注意1 6 - 7 1 d e n e u b o u r g 及 其合作者设计了“双桥实验 s - z o ，用以模拟蚁群的觅食行为该实验采用一个双 桥连接蚁穴和食物源第一个实验中，桥的两个分支长度相同，如图1 1 ( a ) 所示最 初，两条分支不存在信息素，蚂蚁以相同的概率随机选择某一分支，并独立地释 放信息素由于随机波动的存在，选择某一分支的蚂蚁数量可能会多于另一分支， 导致此分支的信息素浓度较另一分支高，因此又会促使更多的蚂蚁再次选择这一 2 蚁群算法的改进及仿真研究 分支，释放更多的信息素，使此分支的信息素浓度变得更高反复进行这一过程， 最终大部分蚂蚁都集中到某一分支路径上值得注意的是，d e n e u b o u r g 等对此实 验重复多次其统计结果表明，蚂蚁最终选择某一分支的概率大约为5 0 此实 验较好地显示了蚁群觅食的自组织行为，最终出现的宏观有序结构，即蚁群向某 一分支集中的现象，这源于蚂蚁个体之间的局部多重交互作用同时，此自组织 行为需要依赖随机波动的存在，这种波动经自催化和正反馈机制得以扩大，最终 形成蚁群的自组织行为 第二个实验中，桥上的两个分支长度不同，如图1 1 ( b ) 所示最初，两条分支 均不存在信息素，蚂蚁以相同的概率随机选择某一分支，并独立地释放信息素由 于选择短分支的蚂蚁首先到达食物源并返回蚁穴，释放到短分支上的信息素早于 并多于长分支路径，这将增大后续蚂蚁选择短分支的概率，形成正反馈机制，最 终大部分蚂蚁都会选择短分支路径g o s s 等【9 】基于此实验现象构建了如下模型 假定在某个瞬间时刻，m ，和m ：分别为选择过双桥上第一、第二分支的蚂蚁个 数，那么一只蚂蚁选择第一分支的概率如式( 1 1 ) 所示： p l2 而赫( 1 1 ) 2 瓦高意可 u j 而选择另一分支的概率为： p 2 = 1 一p l( 1 2 ) 式中k 和h 为两个待估计参数，用来匹配真实实验数据 为了求得参数k 和h ，通过蒙特卡罗模拟证实【1 1 】，当七2 0 ，h 2 时，公式( 1 1 ) 与实验数据相一致 ( a ) 两条分支具有襁网的长度( b ) 两条分支具有不圈的长度 图1 1 双桥实验的设置 在第二个实验中( 两座桥的长度不相等) ，绝大多数蚂蚁选择较短的桥，随机 波动的影响大大减少，主要是间接交流机制、差异路径长度( d i f f e r e n t i a lp a t hl e n g t h ) 、 正反馈等机制占主导地位【1 2 】同时，据实验观察，并不是所有蚂蚁都选择较短分 第一章绪论 3 支，仍有小部分蚂蚁会选择较长分支，可用自组织理论中的波动扩大要素予以解 释，这是一种所谓“路径探索( p a t he x p l o r a t i o n ) 行为，这一点可以为算法设计提 供仿生意义的指导 上述两个实验，均是基于信息素的间接交流机制，进而实现蚁群的自组织行 为，d o r i g o 等将这种间接交流机制称为“s t i g m e r g y ，并定义为【1 2 】：社会昆虫群体 用于协调它们行为的一种独特的间接交流方式 除了能够找到蚁穴和食物源之间的最短路径外，蚁群还有极强的适应环境的 能力，如图1 2 所示在蚁群经过的路线上出现障碍物时，蚁群能够很快重新找到 最优路径 纽) 蚁群在奴穴和食物源之问的路径上移动；d ) 路径上出现障碍物蚊群以同样的概率向左、 右方向行进；扣较短路径上的信息素以更快的速度增加：d ) 所有的蚂蚁都选择较短的路径 图1 2 蚁群的自适应行为 8 1 1 3 蚁群优化算法的思想起源 通过研究蚁群觅食的群体行为，意大利学者d o r i g om a c r o 等【l 】于19 9 1 年在巴 黎召开的第一届欧洲人工生命会议上最早提出了蚁群算法的基本模型1 9 9 2 年 d o r i g om a c r o 又在其博士论文中进一步阐述了蚁群算法的核心思想【2 】 像蚂蚁这类群居昆虫，虽然没有视觉，却能找到由蚁穴到食物源的最短路径， 原因是什么呢? 虽然单个蚂蚁的行为极其简单，但由这样的简单个体所组成的蚂 蚁群体却表现出极其复杂的行为，能够完成复杂的任务，不仅如此，蚂蚁还能够 适应环境的变化，例如：在蚂蚁运动线路上突然出现障碍物时，蚂蚁能够很快找 到最优路径蚂蚁是如何完成这些复杂任务呢? 4 蚁群算法的改进及仿真研究 仿生学家经过大量研究发现，蚂蚁个体间通过一种被称为“信息素 ( p h e r o m o n e ) 的物质进行信息传递，从而能够相互协作，完成复杂任务因此， 蚁群的集体行为表现为一种信息正反馈现象，即某条路径上经过的蚂蚁数越多， 其上留下的信息素的痕迹也就越多( 当然，随时间的推移会逐渐蒸发掉一部分) ， 后来蚂蚁选择该路径的概率也越高，从而更增加该路径上信息素的强度这种根 据其他蚂蚁所释放的化学物质信息来影响蚂蚁群体路径选择的行为方式正是a c o 算法的灵感来源 a c o 算法就是从自然界中真实蚂蚁觅食的群体行为得到启发而提出的，其很 多观点都来源于真实蚁群【s j 算法中一群简单的人工蚂蚁通过信息素( 一种分布 式的数字信息，与真实蚂蚁释放的信息素相对应) 进行间接通讯，并利用该信息 和问题相关的启发式信息逐步构造问题的解因此a c o 算法中所定义的人工蚂蚁 与真实蚂蚁存在一定的异同 人工蚂蚁具有双重特性：一方面，它们是真实蚂蚁的抽象，具有真实蚂蚁的 特性；另一方面，它们还有一些真实蚂蚁不具备的特性，这些新的特性使人工蚂 蚁在解决实际优化问题时，具有更好地搜索较好解的能力 人工蚂蚁与真实蚂蚁具有如下共同尉8 1 3 】： ( 1 ) 存在一群相互协作的个体与真实蚁群一样，a c o 算法由一群人工蚂蚁 组成，人工蚂蚁之间通过同步异步协作来寻找问题的最优解虽然单只人工蚂蚁 可以构造出问题的解，但只有当多只人工蚂蚁通过相互协作，才能发现问题的最 优( 次优) 解 ( 2 ) 使用信息素的迹和s t i g m e r g y 机制同真实蚂蚁一样，人工蚂蚁通过改变 所访问过的问题的数字状态信息( 在a c o 算法中被称为信息素) 来进行间接的协 作在a c o 算法中，信息素是人工蚂蚁之间进行交流的唯一途径另外，a c o 算法还用到了挥发机制，以对应于真实蚂蚁中信息素的挥发现象挥发机制使蚁 群逐渐忘记过去的历史，使后来的蚂蚁在搜索中较少地受过去较差解的影响，从 而更好地指导蚂蚁的搜索方向 ( 3 ) 随机状态转移策略如真实蚂蚁样，人工蚂蚁也是按照概率决策规则从 一种状态转移到另一种邻接状态其中的概率决策规则是与问题相关信息和局部 环境信息有关的函数在状态转移过程中，人工蚂蚁与真实蚂蚁都只用到了局部 信息，没有使用前瞻策略来预见将来的状态因此，所使用的策略在时间和空间 上是局部的 ( 4 ) 搜索最短路径人工蚂蚁和真实蚂蚁具有相同的任务，即以局部移动的方 式构造出从初始点到目的点之间的最短路径 人工蚂蚁与真实蚂蚁具有如下不同点【8 】： ( 1 ) 人工蚂蚁具有一定的记忆能力，能够记住过去的行为状态 第一章绪论5 ( 2 ) 人工蚂蚁存在于离散的空间中，它们的移动是从一个状态到另一个状态的 转换 ( 3 ) 人工蚂蚁存在于与时间无关联的环境中 ( 4 ) 人工蚂蚁释放信息素的数量是其生成解的质量的函数 ( 5 ) 人工蚂蚁更新信息素的时机依赖于特定的问题例如，有的问题中人工蚂 蚁仅在找到一个解之后才更新路径上的信息素，而有的问题中人工蚂蚁每做出一 步选择就更改信息素无论哪种方法，人工蚂蚁都不是完全盲从的，它受到问题 空间特征的启发 ( 6 ) 为了改善算法的优化效率，可以给人工蚂蚁增加一些真实蚂蚁所不具备的 特性，例如简单预测、在局部优化过程中相互交换信息等 1 4 蚁群优化算法的研究现状 群智能已成为分布式人工智能研究的一个重要领域在美国，成立了专门的 组织研究群体仿真由欧洲联盟资助的群智能相关研究项目也于2 0 0 1 年在欧洲多 个研究机构启动在国内，国家自然科学基金“十五期间学科交叉类优先资助 领域中认知科学及其信息处理的研究内容就明确列出了群智能的进化、自适应与 现场认知 1 9 9 1 年，m d o r i g o 等提出了第一个a c o 算法一蚂蚁系统( a s ) ，但当时并 未引起国际学术界的关注直到1 9 9 6 年，d o r i g o 发表了 t h ea n ts y s t e r m ：o p t i m i z a t i o n b yac o l o n y o f c o o p e r a t i n ga g e n t s ”一文【3 j ，蚁群算法开始进入它的蓬勃发展期1 9 9 8 年首届蚁群优化国际研讨会在比利时布鲁塞尔召开此后，每两年都会召开一次 这样的国际研讨会，为蚁群算法的研究提供了一个很好的交流平台2 0 0 0 年， d o r i g o 和b o n a b e a u 等【1 4 1 在国际著名杂志 n a t u r e ”上发表了蚁群算法的综述，把这 一领域的研究推向了国际学术最前沿近几年， n a t u r e ”曾多次对蚁群算法的研究 成果进行报道i l s a 6 ， 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 ”和“i e e et r a n s a c t i o n s e v o l u t i o n a r yc o m p u t a t i o n 等国际著名杂志也出版了蚁群算法的专刊2 0 0 4 年， d o r i g o 和s t u t z l e 出版了关于蚁群算法的第一部专著 a n tc o l o n yo p t i m i z a t i o n ” 8 1 ， 为蚁群算法的研究提供了一部权威、系统的参考资料 蚁群算法自提出以来，国外许多学者的研究重点在基本蚁群算法的改进方 面除了上述算法之外还有一些有效的改进算法，如最优解保留策略蚂蚁系统( a n t s y s t e mw i t he l i t i s t ，a s e l i t e ) 3 ，引，该算法通过使用最优蚂蚁来提高蚂蚁系统中解的 质量，每次迭代完成后，全局最优解得到更进一步的利用，即在对信息素的迹进 行更新时，就好像有许多的最优蚂蚁选择了该路径与a s 算法相比，该算法在信 息素更新时加强了对全局最优解的利用b e m db u l l n h e i m e r t l 7 】等人提出了基于排序 6 蚁群算法的改进及仿真研究 的蚂蚁系统，该算法在完成一次迭代后，将蚂蚁所经路径的长度按从小到大的顺 序排列，并根据解的质量赋予不同的权重，根据解的级别对信息素进行有差别的 更新蚁群算法的理论研究相对于算法改进和算法应用方面的研究要滞后一 些g u t j a h r 于1 9 9 9 年撰写的学术报告【1 8 】和2 0 0 0 年发表的学术论文【1 9 】在一些假设 的前提下，首次对蚁群算法的收敛性进行了证明，在蚁群算法的发展史上具有重 要意义而后，g u t j a l l r 又提出了g b a s t d e v 和g b a s t d i b 2 0 1 ，证明了通过自适应 调整挥发系数或者信息素下界值算法最终能收敛到全局最优解s t u e z l e 和d o r i g o 2 l 】 针对具有组合优化性质的极小化问题提出了一种简化的蚁群算法，指出当迭代次 数趋于无穷时，算法总能找到全局最优解b a d r 等瞄j 将蚁群算法视为分支随机过 程，从分支随机路径和分支过程对蚁群算法的收敛性进行了研究 国内对蚁群算法的研究从上世纪末开始也一直处于不断上升的过程覃刚力、 杨家本【2 3 j 和王颖、谢剑英【2 4 】等通过自适应改变蚁群算法的挥发度等参数，在保证 收敛速度的前提下提高解的全局优化性能吴庆洪1 2 5 j 等针对基本蚁群算法计算时 间长的缺点，提出了一种具有变异特征的蚁群算法，充分利用2 交换法简单高效 的特点，加快算法的收敛速度，节省了计算时间熊伟清【2 6 】、张徐亮1 2 7 1 、庄昌文 1 2 8 j 等通过改进路径选择策略，全局修正信息量规则，引入蚁群中蚂蚁分工与协同 学习，协同工作的思想，提高算法的自适应能力邵晓魏【2 9 】等将遗传算法和蚁群 算法相结合，用遗传算法生成信息素分布，利用蚁群算法求精确解，形成了一种 时间效率和求解效率都比较好的启发式算法段海滨 3 0 】等以离散熵为研究工具， 对基本蚁群算法的全局收敛性问题进行了研究孙熹等【3 l 】将遗传算法与蚁群算法 进行了融合，并从m a r k o v 随机过程的角度对所提出的蚁群算法的收敛性进行了分 析此外，在蚁群算法方面国内还出现了不少著作，吴启迪和汪镭【3 2 】，李士勇【3 3 】， 段海滨 1 3 1 ，高尚【3 4 j 等都先后出版了关于蚁群算法方面的专著，为蚁群算法进一步 研究提供了系统，完整的参考资料 1 5 蚁群算法的主要应用领域 从蚁群算法成功求解著名的t s p 问题以来，目前已陆续渗透到其他许多新的 领域蚁群优化算法的主要应用领域有： ( 1 ) 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) v r p 问题是一类交通运 输优化问题，即给定车辆的载重量及各个需求点的需求量，优化目标在保证各个 需求点需求的前提下，通过车辆的调度，使车辆的总行程最短目前，除了一些 经典的智能算法以外，蚁群算法同样可求解v r p ，求解时可将车辆模拟成蚂蚁近 年来，国内外学者 3 5 , 3 6 在用蚁群算法求解v r p 方面的研究取得了许多成果，但模 拟效果距现实中的v r p 问题还有一定的差距因此，这方面的研究还有待于进一 第一章绪论 7 步加深 ( 2 ) 生产调度问题( j o bs c h e d u l i n gp r o b l e m ，j s p ) j s p 是一个复杂的动态管理 优化问题因为蚁群算法机制可以不断从过去的加工经历中学习，能自然地适应 车间内外部环境的变化，从而实现动态调度所以，它能适应动态的工件到达， 不确定的加工时间以及机床故障等扰动，比静态确定性算法具有更好的应用背景 3 7 , 3 8 蚁群算法可求解动态任务多目标分配问题1 3 9 1 ，并对车间内外部环境变化具 有良好的自适应性但这些应用研究大多是针对小规模实例的仿真，用蚁群算法 解决大规模生产调度和多目标分配问题是今后进一步的研究方向 ( 3 ) 网络路由问题蚁群算法在动态组合优化问题研究中的应用主要集中在通 讯网络方面 4 0 1 随着i n t e r a c t 上广泛的分布式多媒体应用对服务质量( q u a l i t yo f s e r v i c e ，q o s ) 需求的增长，各种服务应用对网络所能提供的q o s 提出了不同的要 求，而路由是实现q o s 的关键之一将蚁群算法用于解决受限路由问题，目前可 以解决包括带宽、延时、包丢失率和最小花费等约束条件在内的q o s 组播路由问 题【4 1 4 4 1 ，比现有的链路状态路由算法具有明显的优越性应用蚁群算法求解更复 杂的q o s 问题还需要深入讨论 ( 4 ) 电力系统优化问题电力系统优化是一个复杂的系统工程，它包括无功优 化、经济负荷分配、电网优化及机组最优投入等一系列问题，其中很多是高维、 非凸、非线性的优化问题h o u 等【4 5 】将蚁群算法成功地应用于解决经济负荷分配 问题；文献 4 6 】n 解决了该算法在配电网优化规划中的初步设计问题电力系统优 化中的机组最优投入问题是寻求一个周期内各个负荷水平下机组的最优组合方式 及开停机计划，使运行费用最小利用动态、决策及路径概念，将机组最优投入 问题设计成类似t s p 问题的模式 4 7 1 ，从而可方便地利用蚁群算法来求解t e n g 等 4 8 1 针对分布式系统中开关重定位问题对蚁群算法进行了遗传变异改进，但未能给 出解决这类非线性、不可微目标函数优化问题的蚁群算法参数选择原则文献1 4 9 】 将蚁群算法编入水利发电规划能源管理软件，可很好地节约能源，但对于蚁群算 法在实际应用中的可靠性问题还需进一步探讨 ( 5 ) 连续空间函数优化问题其核心思想是将连续的搜索空间离散化，用一个 从起始点出发的运动矢量集合来描述蚂蚁的移动路径，这样就可以用一个离散的 结构来表示蚁群的连续运动区域已有一些学者对其进行了研究【5 0 - 5 4 1 ，但算法的 优化性能有待进一步提高 ( 6 ) 无线传感器网络路由协议问题作为一种新的信息获取方式和处理模式， 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ，w s n ) 目前已经成为国内外备受关注的研 究热点w s n 是由众多具有通讯和计算能力的传感器节点，以多跳通讯、自组织 方式形成的网络、节点传感器电池供电、电源能量、通讯能力、计算能力都是有 限的w s n 路由协议研究中的一个重要问题是路由的选择要结合节点的能量信息， 8 蚁群算法的改进及仿真研究 使得节点的能量消耗能够均衡，延长网络生命周期蚁群优化算法求解模式将问 题求解的快速性、全局优化特征以及高度的自组织性等特点合理结合，与无线传 感网低能耗、自组织的大规模网络路由快速建立要求极其相似，有助于建立面向 数据为中心的路由协议目前，已有许多学者研究蚁群优化算法在w s n 路由协议 中的应用【5 5 - 5 引 此外，蚁群算法还在数据挖掘【5 9 1 、图像处理【6 0 l 、参数辨识【6 1 1 、凸整数规划问 题 6 2 1 、机器人路径规划问题【删和图形着色【删等领域的应用取得了很大进展 1 6 本文的主要工作和内容安排 课题研究过程中，在西安电子科技大学理学院寇晓丽博士的帮助下，研究了 新的蚁群算法，并将其应用到单目标和双目标t s p 问题中本文分为以下几个部 分： 第一章：绪论，主要介绍了蚁群算法的生物学行为、思想起源，阐述了蚁群 算法目前国内外的研究现状以及主要应用领域 第二章：介绍了蚁群算法的基础知识，包括蚁群算法模型，复杂度分析以及 基本蚁群算法的收敛性证明 第三章：对基本蚁群算法进行改进，研究了两种新的蚁群算法，并将其应用 于单目标t s p 和双目标t s p 中进行计算机实验仿真，结果证明了算法的有效性 最后是结束语、致谢、在读期间发表和撰写的论文 第二章蚁群算法的基本知识9 第二章蚁群算法的基本知识 2 1 蚂蚁系统模型的建立 为了说明蚂蚁系统模型，首先引入旅行商( t s p ) 问题旅行商问题就是指给定疗 个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路 线其图论描述为：给定图g = ( 矿，a ) ，其中y 为顶点集，彳为各项点相互连接组 成的边集，已知各顶点间的连接距离，要求确定一条长度最短的h a m i l t o n 回路， 即遍历所有顶点当且仅当一次的最短回路 选择旅行商问题作为测试问题的原因主要有： ( 1 ) 它是一个最短路径问题，蚁群优化算法很容易适应这类问题； ( 2 ) 很容易理解，不会因为有太多的术语而使得算法行为的解释难以理解； ( 3 ) t s p 是典型的组合优化难题，常常用来验证某一算法的有效性，便于与其 他算法比较对于其他问题，可以对此模型稍作修改便可应用虽然它们从形式 上看略有不同，但基本原理是相同的，都是通过模拟蚁群行为达到优化的目的 首先引入如下记号： m ：蚁群中蚂蚁的数量； 包o ) ：，时刻位于城市f 的蚂蚁个数，m = 包o ) ； d 一两城市f 和，之间的距离； 5 1 t 7 可：边( f ，) 的能见度，反映由城市礴专移到城市_ ，的启发程度，这个量在蚂蚁 系统的运行中不改变； f 盯：边( f ，) 上的信息素轨迹强度； f 打：蚂蚁k 在边( f ，) 上留下的单位长度轨迹信息素量； p ：蚂蚁后的转移概率，是尚未访问的城市 每只蚂蚁都是具有如下特征的简单主体： ( 1 ) 在从城市f 到城市歹的运动过程中或是在完成一次循环后，蚂蚁在边( f ，歹) 上释放一种物质，称为信息素轨迹； ( 2 ) 蚂蚁概率地选择下一个将要访问的城市，这个概率是两城市间距离和连接 两城市路径上存有轨迹量的函数； ( 3 ) 为了满足问题的约束条件，在完成一次循环以前，不允许蚂蚁选择已经访 问过的城市 简单蚁群算法的流程如下： ( 1 ) 初始化彳f ) 初始化蚁群； ( 2 ) 评价彳( r ) 根据目标函数对每只蚂蚁的适应度做一评价； ( 3 ) 释放信息素根据适应度，对蚂蚁所经过的路径按一定的比例释放信息素， 1 0 蚁群算法的改进及仿真研究 适应度越高，所释放的信息素越多； ( 4 ) 蚂蚁移动蚂蚁依据前面蚂蚁所留下的信息素和自己的判断选择路径； ( 5 ) 信息素的挥发信息素会随着时间不断消散 初始时刻，各条路径上的信息素量相等，设r 。，( o ) = c ( c 为常数) 蚂蚁 k ( k = 1 , 2 ，脚) 在运动过程中根据各条路径上的信息素量决定转移方向蚂蚁系统 所使用的状态转移规则称为随机比例规则，它给出了位于城市f 的蚂蚁k 选择移动 到城市，的概率在t 时刻，蚂蚁k 在城市f 选择城市，的转移概率p f , ( ) 为 f p ；o ) = 【揣小枷p 畋 亿。， 0 ， o t h e r w i s e 其中，a l l o w e d k = o ，1 ，刀一1 表示蚂蚁k 下一步允许选择的城市由上式可知，转 移概率p ：o ) 与f ；7 7 岁成i e l l 7 7j | ：为能见度因数，a 和卢为两个参数，分别反映了 蚂蚁在运动过程中所积累的信息和启发式信息在蚂蚁选择路径中的相对重要 性与真实蚁群不同，人工蚁群系统具有记忆功能为了满足蚂蚁必须经过所有刀 个不同的城市这个约束条件，为每只蚂蚁都设计了一个数据结构，称为禁忌表( t a b u l i m 禁忌表记录了在f 时刻蚂蚁已经走过的城市，不允许蚂蚁在本次循环中再经 过这些城市当本次循环结束后，禁忌表被用来计算该蚂蚁当前所建立的解决方 案( 即蚂蚁所经过的路径长度) 之后，禁忌表被清空，该蚂蚁又可以自由地进行选 择 经过刀个时刻，蚂蚁完成一次循环，各路径上信息素量根据下式调整 f ，) = p r i ，o ) + f 口o ，t + 1 ) ( 2 2 ) a r 1 6 f ，+ 1 ) = t o ，t + 1 ) ( 2 3 ) 其中，r ：( f ，f + 1 ) 表示第k 只蚂蚁在时刻f ，h 1 ) 留在路径i 9 j ) 上的信息素量，其 值视蚂蚁表现的优劣程度而定路径越短，信息素释放的就越多；a r ，甩，f + 1 ) 表示 本次循环中路径( f ，) 的信息素量的增量；( 1 一p ) 为信息素轨迹的衰减系数，通常设 置系数p 1 来避免路径上轨迹量的无限增加 根据具体算法的不同，a r ”r ：及p ： ( f ) 的表达形式可以不同，要根据具体 问题而定m d o r i g o 曾给出三种不同模型f 6 5 1 ，分别成为蚁周系统( a n t c y c l es y s t e m ) 、 蚁量系统( a n t - q u a n t i t ys y s t e m ) 、蚁密系统( a n t d e n s i t ys y s t e m ) 3 5 】 2 2 蚁量系统和蚁密系统的模型 蚁量系统和蚁密系统的模型的差别仅在于r ；o ，f + 1 ) 的表达式不同在蚁密 第二章蚁群算法的基本知识 系统模型中，一只蚂蚁在经过路径g ，) 上释放的信息素为每单位长度q ；在蚁量 模型中，一只蚂蚁在经过路径( f ，歹) 上释放的信息素为每单位长度旱从而： “l ， 在蚁密系统模型中 啪川) = 舻第帜蚂蚁篙循环幄过路磁 ( 2 4 ) 在蚁量系统中 瞄+ 1 ) _ 詈，若徽蚂蚁在本次循种经过路径) ( 2 5 ) 10 ，否则 从以上定义中可以很清楚地看出，在蚁密系统模型中，一只蚂蚁从f 向着，移 动的过程中路径o ，) 上信息素轨迹强度的增加与d ，无关而在蚁量模型中，它与 d 。，成反比，就是说，在蚁量模型中短路径对蚂蚁将更有吸引力，因此进一步增加 了方程式( 2 1 ) 中能见度因数叩。的值 蚁密和蚁量模型的实现过程可以用伪代码表示如下： ( 1 ) 初始化过程 设f = 0 ；t 时间计数器 n c = 0 ；n c 循环次数计数器 f 打= c ；为每条路径( f ，) 设一个轨迹强度的初始值 f ；，= 0 ：轨迹强度增量的初始值设为0 1 t 7 f 由某种启发式算法确定；在t s p 中，r l l = 口玎 t a b u 。= 咖；在初始阶段，禁忌表为空 将m 只蚂蚁随机地置于刀个节点上： 设置s = 1 ；s 为禁忌表索引，将各蚂蚁的初始城市置于当前禁忌表中 f o r 七= 1t o d o f o r 七= 1t ob f ( f ) d o t a b u g ) = f ( 2 ) 重复直到禁忌表满为止，这一步要重复刀一1 次 设置s = s + 1 f o rf = lt o ，ld o f o r 七= lt o 匆( ，) d o 以概率p ：( f ) 选择城市，； 将蚂蚁七移到，； 1 2 蚁群算法的改进及仿真研究 将刚刚选择的城市 j n 至= l jt a b u 中； 在蚁密模型中，f l ，o ，r + 1 ) = a i - o ，f + 1 ) + q ； 或在蚁量模型中，f 驴o ，f + 1 ) = a z o o ，f + 1 ) 4 - 万q ； 对于每一个路径( f ，j ) ，根据方程式( 2 2 ) 计算f 打( f ，t + 1 ) ； ( 3 ) 记录到目前为止的最短路径 i f c c 一则清空所有禁忌表 设置s = 1 f o rf = 1t o 行d o f o rk = 1t o 饥o ) d o t a b u 。( s ) - - - i 一次循环后蚂蚁又重新回到初始位置 设，= f + 1 对于每一条路径( f ，j ) ，设置f 盯( f ，f + 1 ) = o 返回步骤( 2 ) e l s e 输出最短路径 2 3 蚁周系统模型 蚁周模型与上述两种模型的差别在于a i ；的表达式不同在蚁周模型中， f 。k ( t ，r + 刀) 表示更新蚂蚁七所走过的路径，o ，f + 刀) 表示蚂蚁经过栉步完成一次循 环，具体更新值由下式给出： f ；( v + 行) ：詈，如果蚂蚁硅本次循环中经过路径o ，) ( 2 6 ) 1 0 ，否则 其中，丘为第k 只蚂蚁在本次循环中所走的路径长度 在蚁密系统和蚁量系统中，蚂蚁在建立方案的同时释放信息素，利用的是局 部信息而蚁周系统是在蚂蚁已经建立了完整的轨迹后再释放信息素；利用的是 整体信息信息素轨迹根据如下公式进行更新： f o + 以) = p 。f ，o ) + f ( f ，t + n ) ( 2 7 ) a r o ，f + 珂) = f ；o ，t + n ) k = l ( 2 8 ) 上式中的p l 与p 不同，因为该方程式不再是在每一步都对轨迹进行更新，而 是在一只蚂蚁建立了一个完整的路径( 刀步) 后再更新轨迹量 蚁周模型算法的实现过程可以表示如下： 第二章蚁群算法的基本知识 ( 1 ) 初始化过程 设r = 0 ；t 时间计数器 札= 0 ； n c 循环次数计数器 f 玎= c ；为每条路径( f ，) 设一个轨迹强度的初始值 a r 。，= 0 ；轨迹强度增量的初始值设为0 1 叩口由某种启发式算法确定；在t s p 中，叩盯= t a b u 。= 妒； 在初始阶段，禁忌表为空 将m 只蚂蚁随机地置于万个节点上； 设置s = 1j 为禁忌表索引，将各蚂蚁的初始城市置于当前禁忌表中 f o rk = 1t o 刀d o f o rk = 1t ob i ( f ) d o t a b u t o ) = f ( 2 ) 重复直到禁忌表满为止这一步要重复刀一1 次 设置j = j + 1 f o rf = 1t o 刀d o f o rk = 1t o 玩o ) d o 以概率p ：o ) 选择城市歹； 将蚂蚁k 移到j ； 将刚刚选择的城市加到砌中； ( 3 ) f o r 七= 1t o 朋d o 根据禁忌表的记录计算三。； f o rs = 1t o 力一ld 0 搜索蚂蚁七的禁忌表 设积，1 ) = ( t a b u 七( s ) t a b u 。g + 1 ) )o ，) 是在蚂蚁k 的禁忌表中连接城市 ( s ，s + 1 ) 的路径 f 埘o + 聍) ：r 脚( f + 刀) + 导 l k ( 1 ) 对于每一路径( f ，j ) ，根据方程式( 2 7 ) 计算f 打o + 疗) 设f = ，+ 刀 对每条路径( f ，) 设f 。( f ，h - 甩) = 0 ( 2 ) 记录到目前为止的最短路径 i f n c 0 ，p ，= 1 ( 2 1 2 ) i = o 记e g ) = x ，p ，若e g ) ，则称e g ) 为考的数学期望 j = 0 定义2 5 3 离散型随机变量的条件期望：设售，7 7 ) 为离散型随机变量，其概率 函数为 p ( f ，k ) - p 传= x 。，7 7 = y k , i ，k = 1 ，2 ， ( 2 1 3 ) 条件概率函数为 p 伍1 f ) = 尸加= y 。，善= 毛) ，p ( 4 后) = 尸 专- - - - x ，7 = 儿 ，i ，k = 1 ，2 ，( 2 1 4 ) ( ，7 i 薯) = y 。p ( k l i ) = k ( 引儿) = 薯p ( 啦) = k = 1 ，2 ，3 ， ( 2 1 5 ) = 1 ，2 ，3 ， 设( q ，f ，尸) 是一个概率空间，ecf 也是一个仃函数， 是q 上可测与可积 的随机变量，考关于互的条件期望e 售i 互) 是可测可积的，且对于w e ，有 工e 售l 曩如= 缈 ( 2 1 6 ) 很明