计算机软件与理论硕士论文-蚁群算法及其应用研究.pdf

北京工业大学 硕士学位论文 蚁群算法及其应用研究 姓名：黄振 申请学位级别：硕士 专业：计算机软件与理论 指导教师：冀俊忠 20080401 摘要 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ，! ，_ i ，_ i - i _ i mm _ _ - i l _ 一 摘要 生物学家研究发现自然界的蚂蚁个体可以分泌一种称为“信息素“ 的化学物 质，蚂蚁群体通过“信息素”进行间接的通讯、协作来寻找从巢穴到食物的最短 路径。受其启发，意大利学者d o r i g o 等对蚂蚁的觅食行为进行仿真研究，提出 了蚁群算法。在随后的十多年时间里，蚁群算法已经在组合优化、网络路由、函 数优化、数据挖掘、机器人路径规划等领域获得广泛的应用，显示出蚁群算法在 求解复杂问题方面的优越性，有广阔的发展前景。 然而，蚁群算法仍然存在一些缺陷：如算法的收敛速度较慢，易陷入停滞等。 本文围绕蚁群优化的原理及应用，就如何改进基本蚁群算法以及蚁群算法在旅行 商问题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 ) 、多维背包问题m k p ( m u l t i d i m e n s i o n a l k n a p s a c kp r o b l e m ) q b 的应用进行了研究，并基于标准的数据集对一些已有算法和 提出的算法进行了效率和精度的比较和分析。 首先，提出一种基于信息素增量和扩散模型的蚁群算法。算法在已有信息素 更新机制的基础上给出了新的基于能量守恒的信息素更新机制，融合解的全局信 息和路径的局部信息对信息素的影响，以客观体现蚂蚁在不同路径上行走时产生 的信息素量的差异。同时，算法将已有的基于点的信息素扩散模型改进为基于路 径的信息素扩散模型，强化了蚁群个体间的影响和协作。另外，针对随机搜索机 制，采用高效率、低计算复杂度的变异策略，加强了局部寻优能力。 其次，针对传统蚁群算法在求解大规模t s p 问题耗时过长且求解精度欠佳的 问题，给出一种基于聚类和分段优化的蚁群算法。算法采取多阶段寻优策略，先 对t s p 问题的城市位置进行聚类处理，抽取出t s p 问题的区域分布的知识，然 后进行区域级的路径寻优和区域内的路径寻优，最后按区域连接顺序合成完整的 解路径，并通过分段策略进行局部优化。在此基础之上，引入粒度的概念，形成 多粒度的t s p 问题描述模型，即粗粒度可以继续划分为细的粒度，“粗”区域也 可以进一步划分为更“细”的区域，从而借鉴粒度的概念将问题划分为多个层面 子问题，对各个层面进行处理后再合成完整的解。 最后，对蚁群算法在多维背包问题求解中的应用进行了研究，提出了一种新 算法，算法利用t o p k 策略获取每次迭代中最优的k 个解，从中挖掘出对象间的 “关联距离“ ，然后借助“关联距离”建立基于对象的信息素扩散模型，最后辅 以简单的变异策略进行局部优化。 大量实例上的实验表明，这些改进的算法不仅加速了蚁群算法的收敛速度， 而且提高了所得解的质量。 关键词蚁群算法；扩散模型；变异策略；旅行商问题；多维背包问题 a b s t r a c t _ _ _ i l l ，i _ i i _ l i i _ l _ l _ _ i l i l _ _ _ l _ i a b s tr a c t b i o l o g i s t s s t u d yf o u n dt h a tn a t u r a la n t sc o u l dr e l e a s eac h e m i c a ls u b s t a n c ek n o w na s p h e r o m o n et h r o u g h w h i c ha n t c o l o n y c o n d u c ti n d i r e c tc o m m u n i c a t i o na n d c o o p e r a t i o ni no r d e rt of i n das h o r t e s tp a t hf r o mn e s tt of o o d i n s p i r e db yt h ea n t s b e h a v i o r ，i t a l ys c h o l a rd o r i g oa n dh i sc o l l e a g u e sd i ds o m es i m u l a t i o nr e s e a r c hb y c o m p u t e r f o rt h ef i r s tt i m e ，t h e yp r o p o s e da n tc o l o n ya l g o r i t h m i nt h ef o l l o w i n g10 y e a r s ，a n tc o l o n ya l g o r i t h mw a sa p p l i e dt oc o m b i n a t o r i a lo p t i m i z a t i o n , n e t w o r k r o u t i n g ，f u n c t i o no p t i m i z a t i o n ，d a t am i n i n g ，r o b o tp a t hp l a n n i n ga n ds oo n , w h i c h s h o w st h eg r e a ta d v a n t a g eo fa n tc o l o n ya l g o r i t h mi ns o l v i n gc o m p l e x p r o b l e m sa n da b r i g h tf u t u r ef o rf u r t h e rd e v e l o p m e n t h o w e v e r ，t h e r ea r es t i l ls o m ed e f e c t si na n tc o l o n ya l g o r i t h ms u c ha sc o s t i n gt o o m u c ht i m ea n de a s yt od r o pi n t os t a g n a t i o n t h i sp a p e rf o c u s e so nt h ep r i n c i p l eo fa n t c o l o n yo p t i m i z a t i o na n di t sa p p l i c a t i o n w ed os o m er e s e a r c ho ni m p r o v e m e n tu p o n a n tc o l o n ya l g o r i t h ma sw e l la sa p p l i c a t i o nt ot s p ( t r a v e l i n gs a l e s m a np r o b l e m ) a n d m k p ( m u l t i d i m e n s i o n a lk n a p s a c kp r o b l e m ) b a s e do ns t a n d a r dd a t a s e t sw ec o m p a r e a n da n a l y z et h e e f f i c i e n c ya n da c c u r a c yo fo r i g i n a la l g o r i t h m sa n dp r o p o s e d a l g o r i t h m s f i r s t ，an e wa 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 mb a s e do np h e r o m o n ei n c r e m e n ta n d d i f f u s i o nm o d e li sp r o p o s e d i ta d o p t san e wp h e r o m o n eu p d a t em e c h a n i s mb a s e do n e n e r g yc o n v e r s a t i o na n dt r a n s f o r mw h i c hi n t e g r a t e st h ei m p a c to fg l o b a li n f o r m a t i o n a n dl o c a li n f o r m a t i o no np h e r o m o n ea n de m b o d i e st h ep h e r o m o n ed i f f e r e n c ef o r d i f f e r e n tp a t h s m e a n w h i l e ，w ei m p r o v et h eo r i g i n a lp h e r o m o n ed i f f u s i o nm o d e la n da p a t hp h e r o m o n ed i f f u s i o nm o d e li se s t a b l i s h e dt of a i t h f u l l yr e f l e c tt h es t r e n g t hf i e l do f p h e r o m o n ed i f f u s i o nw h i c hs t r e n g t h e n st h ec o l l a b o r a t i o na m o n ga n t s am u t a t i o n s t r a t e g y 、 ，i t l ll o w e rc o m p u t a t i o n a lc o m p l e x i t yi sa d o p t e dt oo p t i m i z ee a c he v o l u t i o n r e s u l t s e c o n d ，a i m i n ga ts o l v i n gl a r g e s c a l et r a v e l i n gs a l e s m a np r o b l e m sw h i c hc o n s u m e l a r g ec o m p u t a t i o n ，an e wa l g o r i t h mi sp r o p o s e d i ta d o p t sas e to fm u l t i s t a g e s t r a t e g i e st ol o o kf o ra no p t i m a ls o l u t i o n f i r s t l y , t h ec i t i e so ft s p a r ec l u s t e r e di n t o s e v e r a ld i s t r i c t sb ym e a n so fd e n s i t y - b a s e da l g o r i t h m s e c o n d l y , t h ea n ta l g o r i t h m b a s e do np h e r o m o n ed i f f u s i o nm o d e li sa p p l i e di np a r a l l e l i z a t i o nt os o l v i n gt h e s u b p r o b l e mi ne a c hd i s t r i c t t h e n ，a l ld i s t r i c ts o l u t i o n sa r ei n t e g r a t e di n t oas o l u t i o n f i n a l l y , l o c a lo p t i m i z a t i o ni sc o n d u c t e db ym e a n so fp a r t i t i o no p t i m i z a t i o n o nt h i s i i i 北京t 业大学t 学硕十学位论文 b a s i s ，w ei n t r o d u c et h ec o n c e p to fg r a i n c o a r s eg r a i nc a l lb es u b d i v i d e di n t os m a l l g r a i n s n a m e l y , c o a r s ed i s t r i c tc a l lb es u b d i v i d e di n t os m a l l e rd i s t r i c t st of o r ma m u l t i p l e - g r a i nr e p r e s e n t a t i o n s ot h a tw ec a l ld i v i d et h el a r g e s c a l ep r o b l e mi n t o s u b p r o b l e m so fs e v e r a ll e v e l s ，t h e nm e r g et h es u b - s o l u t i o n si n t ot h ec o m p l e t e s o l u t i o n f i n a l l y , w ed os o m er e s e a r c hw o r ko na n tc o l o n ya l g o r i t h mf o rm u l t i d i m e n s i o n a l k n a p s a c kp r o b l e m a s s o c i a t i o nd i s t a n c e sa m o n go b j e c t sa r em i n e di ne a c hc y c l ew i t h at o p - ks t r a t e g y t h e n ，ap h e r o m o n ed i f f u s i o nm o d e lb a s e do ni n f of o u n t a i no fa l l o b j e c ti se s t a b l i s h e da n das i m p l em u t a t i o ns c h e m ei se m p l o y e dt oo p t i m i z et h e e v o l u t i o nr e s u l t s f o rt h ea b o v ea l g o r i t h m s ，l a r g ea m o u n to fe x p e r i m e n t so nt h eb e n c h m a r ks h o wt h a t t h ep r o p o s e da l g o r i t h m sc a i ln o to n l ye n h a n c ec o n v e r g e n c es p e e db u ta l s og e tm u c h m o r eo p t i m a ls o l u t i o n s k e y w o r d sa n tc o l o n yo p t i m i z a t i o n ；d i f f u s i o nm o d e l ；m u t a t i o ns t r a t e g y ；t s p ；m k p i v 独创性声明 本人声h ) j n 里交的论文是我个人在导师指导下进行的研究j ：作及取得的研 究成果。尽我7 衍知，除了文巾特别加以标注和致谢的地方外，论文中不包龠其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业火! 学或其它教育机构 的学位或诅：书i m 使 j 过的材料。与我一同工作的志对小研究i 做f 1 勺任何贝献均 已舀：论文中作了明确的蜕明并表示了谢意。 签名：益噬 ! 吼 关于论文使用授权的说明 z 0 8 i 本人完全了解北京工业大学有关保留、使用学位论文的舰定，即：学校有权 保尉送交论文的复印件，允许论文被查阅和借阅；学校叮以公撕n 仑文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后戍遵守此规定) 签名：童亟 导师签名：堑j 垒盛：e j 期： 2 嘴6 弓 第l 章绪论 第1 章绪论 1 1 课题的研究背景与意义 1 1 1 研究背景与研究意义 人工智能在经历了2 0 世纪8 0 时年代的兴旺发展之后，由于在方法论上未能 突破经典计算思想的藩篱，逐渐进入了一个低潮时期。然而，随着生物科学的迅 猛进步，人工智能的研究开始摆脱经典逻辑计算的束缚，人们纷纷尝试探索新的 非经典的计算途径。生物启发计算也随之成为一个研究热点，它给人工智能带来 了很多新的思想和启迪。在这种背景下，社会性动物的自组织行为引起了人们的 广泛关注。如蚁群、鸟群、蜂群的单个个体行为简单而且随机，但是它们可以凭 借集体的力量进行觅食、御敌、筑巢等复杂活动。这种简单个体的相互协作而使 群体表现出智能行为的特性就叫做“群集智能“ n q l 。 在诸多的群集智能行为中，以蚂蚁的觅食行为最引人注目，生物学家研究发 现自然界的蚂蚁在运动过程中能够在所经过的路径上留下一种叫做信息素的物 质，而且它们还能够感知到这种物质的存在，并以此指导自己的运动方向，蚂蚁 个体之间就是通过这种间接的信息交流方式达到搜索食物源的目的。意大利学者 m d o r i g o 等人用计算机对蚁群的觅食行为进行了仿真研究，首次提出了蚁群算 法。蚁群算法作为一种新型的解决组合优化问题的模拟进化算法，不仅能够执行 智能搜索，进行全局优化，而且具有鲁棒性、正反馈、分布式计算、易于与其它 算法相结合等特点。蚁群优化利用正反馈原理，可以加快进化过程；分布式计算 使算法易于并行实现；个体之间的间接通信使算法具有更好的扩充性；该算法易 于与多种启发算法相结合，可改善算法的性能；由于鲁棒性强，算法不会因为某 几个个体的故障而影响问题的求解。因此，蚁群算法的出现为解决复杂的优化问 题提供了有力工具，正是由于蚁群算法具有不同于传统算法的独特优点，使其在 许多领域可以达到比较理想的优化效果，所以具有广阔的应用前景。 然而，蚁群算法在求解问题时表现出收敛速度慢、易陷入停滞的缺点，这也 一直是制约其大规模应用的原因。因此，本课题对蚁群优化算法进行研究，通过 对信息素更新机制、信息素扩散模型及局部优化机制的改进，提高了蚁群算法求 解问题的能力，并给出了应用蚁群算法求解大规模t s p 问题和多维背包问题的有 效算法。 北京丁业大学t 学硕十学位论文 1 1 2 蚁群算法的产生 自然界中蚂蚁的食物源总是随机分布在蚁巢周围，生物学家观察发现，经 过一段时间后，蚂蚁总能找到一条从蚁巢到食物源的最短路径。蚂蚁的这种自组 织行为引起了昆虫学家的注意。6 0 s ss 等人于1 9 8 9 年做了著名的非对称“双桥“ 实验。如图1 - 1 所示，图中左部分为试验4 分钟之后的情况，右部分为试验8 分钟之后的情况。该实验的结果显示：最终绝大多数的蚂蚁会选择最短路径。 图卜1 双桥实验 f i g u r ei - 1 d o u b l eb r i d g e se x p e r i m e n t 除了能够找到蚁巢和食物源之间的最短路径外，蚁群还有极强的适应环境的 能力。如图1 - 2 所示，图中( a ) 表示正常情况下蚂蚁找到从巢穴到食物源的最短 路径，图中( b ) 表示在巢穴和食物源之间有了障碍物，蚂蚁以等概率选择从左端 和右端绕过障碍物，图中( c ) 表示在一段时间后蚂蚁以较大的概率选择从较近端 绕过障碍物，图中( d ) 表示最终所有的蚂蚁都选择从较近端绕过障碍物，最短路 径形成。由图例可见，在蚁群经过的路径上突然出现障碍物时，蚁群能适应该变 化，找到新的最优路径。经过科学家们大量的研究发现，蚂蚁在运动过程中，能 够在所经过的路径上留下信息素，而且能够感知到这种物质的存在及其强度，并 以此指导自己运动的方向，蚂蚁倾向于向信息素浓度高的方向移动。因此，相同 时间间隔内蚂蚁往返于较短路径上的信息量就积累得比较多，则随后选择较短路 2 第1 章绪论 b 图1 - 2 蚁群寻找食物的过程 f i g u r el - 2 p r o c e s so fa n t sf o r a g i n gf o rf o o d 径的蚂蚁也随之增多，表现为一种信息正反馈的现象，即某一路径上走过的蚂蚁 越多，后来的蚂蚁选择该路径的概率就越大h 1 。蚂蚁个体之间正是通过这种信息 交流机制来搜索食物源，并最终沿着最短路径行进。 基于以上的蚂蚁觅食行为，意大利学者d o r i g om 等在1 9 9 1 年第一次提出了 蚁群算法嵋6 1 。1 9 9 6 年d o r i g om 等又发表了另一篇奠基性的文章“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 o na g e n t s ”m ，该文系统地阐述了蚁 群算法的基本原理和数学模型，还将其与遗传算法、模拟退火算法、爬山法等进 行实验仿真比较，并把蚁群算法从解决对称旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e m ) 扩展到解决非对称旅行商问题、指派问题及车间作业调度问题，同时也 对蚁群算法中初始参数对算法性能的影响做了初步探讨。在此之后，蚁群算法迅 速引起了世界许多国家研究者的广泛关注，其应用领域不断拓宽，针对原算法的 改进的成果也大量涌现。 1 1 3 蚁群算法的发展 d o r i g om 等提出了第一个蚁群优化算法，即蚂蚁系统( a n ts y s t e m ，简称 a s ) 并成功应用于求解t s p 问题，其实验结果表明a s 算法具有较强的鲁棒性和 发现较好解的能力，但其存在的缺陷也很明显，如收敛速度慢、易陷入停滞等。 随后许多学者对如何改进基本的蚁群算法进行了研究，如基于蚂蚁等级的蚁群算 法嘲。随后，d o r i g om 等又提出了a n t - o 算法叫，该算法用伪随机比例状态转移 规则( p s u e d or a n d o mp r o p o r t i o n a ls t a t et r a n s i t i o nr u l e ) 替换a s 算法中 的随机比例选择规则( s t o c h a s t i cp r o p o r t i o n a lc h o i c er u l e ) ，使得该算法在 构造解的过程中能更好地保持探索( e x p l o r a t i o n ) 和利用( e x p l o i t a t i o n ) 之 间的平衡，另外算法还引入了全局信息素更新中的精英策略。在a n t q 算法的基 北京t 业大学工学硕十学位论文 础之上d o r i g om 等提出了蚁群系统( a n tc o l o n ys y s t e m ，简称a c s ) n 训，a c s 算法作为a n t q 算法的特例实现起来更为简单而且表现出很好的性能。s t u t z l e 和h o o s 提出了最大一最小蚂蚁( m a x - m i na n ts y s t e m ，简称m m a s ) n ，m m a s 的 特点是将信息素的大小限制在一定的范围内并使用信息素平滑机制以避免算法 运行时陷入停滞状态。随着人们对蚁群算法研究的不断深入，近年来d o r i g om 等提出了蚁群优化元启发( a n tc o l o n yo p t i m i z a t i o nm e t ah e u r i s t i c ，简称 a c o - m h ) n 副，把它作为用蚁群算法求解复杂问题的通用框架，并将所有符合a c o 框架的蚂蚁算法称为蚁群优化算法( a c oa l g o r it h m ) 。a c o m h 为蚁群优化的理 论研究和算法设计提供了技术上的保障。g u t j a h rwj 在蚁群算法的收敛性方面 做出了开创性的研究，他将蚁群算法的行为简化为在一幅代表所求问题的有向图 上的行走过程，进而从有向图论的角度对一种改进蚁群算法一图搜索蚂蚁系统 ( g r a p h - b a s e da n ts y s t e m ，g b a s ) 的收敛性进行了理论分析，证明了在一些合 理的假设条件下，g b a s 能以一定的概率收敛到所求问题的最优解n 3 。1 耵。b l u mc 和 d o r i g om 于2 0 0 4 年提出了蚁群优化的超立方体框架n 町。 国内的学者直到上个世纪末才开始关注蚁群算法，主要研究集中于对算法的 改进和应用方面。吴庆洪和张纪会等n 7 1 从遗传算法中变异算子的作用得到启发， 把逆转变异机制引入到基本的蚁群算法，利用2 一交换法简洁高效的特点，提出 了具有变异特征的蚁群算法。覃刚力和杨家本n 阳提出了一种基于自适应调整信息 素的改进蚁群算法，该算法根据蚂蚁所获得的解的情况，动态地调整路径上的信 息素，使算法跳离局部最优。王颖和谢剑英n 钔通过自适应地改变算法的挥发系数 以克服蚁群算法陷入局部最优的缺陷，并能够在保证收敛速度的前提下提高算法 的解全局最佳性。吴斌和史忠植啪1 在蚂蚁算法的基础上提出了相遇算法，提高了 蚁群算法中蚂蚁周游一次的解的质量，然后将相遇算法与采用并行策略的分段算 法相结合，提出了一种基于蚁群算法的t s p 问题分段求解算法。陈岐、沈洁、秦 岭等乜提出了基于分布均匀度的自适应蚁群算法，该算法根据优化过程中解的分 布均匀度，自适应地调整路径选择概率的确定策略和信息素更新策略，使算法具 有更好的收敛速度和稳定性。朱庆保和杨志军啪7 提出基于变异和动态信息素更新 的蚁群优化算法，该算法针对t s p 问题提出了三种策略：最近节点选择策略、信 息素动态更新策略和最优个体变异策略，大大提高了求解问题的速度。黄国锐、 曹先彬、王煦法提出了基于信息素扩散的蚁群算法，该算法建立了更加客观真实 的蚁群系统的信息素扩散模型，使相近的蚂蚁之间能更好地进行协作。 正是由于蚁群算法具有不同于传统算法的诸多优点，近年来蚁群算法已经被 成功应用到许多离散及连续优化问题口3 1 2 钔的求解中。d o r i g om 等首先将a s 算法 应用于t s p 问题中胁一。随后v m a n i e z z o 等将a s 算法应用于指派问题( 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 ) 田瑚1 。a c o l o r n i 等将a s 算法应用于车间作业 4 第1 章绪论 调度问题( j o b - s h o ps c h e d u l i n gp r o b l e m ，简称j s p ) 四1 。c o s t a 和h e r z 提出 增强的a s 算法跚1 并用它来求解图的着色问题，得到了完全可以和其它启发式算 法相媲美的结果。b u l i n e i m e r ，h a r t l 和s t r a u s s 用基于蚂蚁等级的蚁群算法来 求解车辆路径问题( v e h i c l er o u t i n gp r o b l e m s ，简称v r p ) 。由于网络中信 息的分布性、动态性、随机性和异步性与蚁群算法非常相似，蚁群算法在网络通 讯领域的应用受到很多学者的关注，d ic a r o 和d o r i g om 将蚁群算法应用于网 络路由问题，提出了a n t n e t 算法口别。除了各种组合优化问题外，蚁群算法在函 数优化、系统辨识、数据挖掘口5 3 8 1 、配电网规划b 引、化学工业m 1 、生命科学 等领域的应用h 订也取得了引人注目的成果。 1 2 课题的主要研究内容 围绕蚁群算法的改进及其应用，本文的研究工作集中在两个方面： 首先是对蚁群算法的运行机制进行研究，主要体现在信息素更新机制的改进 上。本文在原有信息素更新机制的基础上给出了一种新的基于能量守恒的信息素 更新机制，融合了解路径的全局信息和局部信息对信息素的影响，以客观体现蚂 蚁在不同路径上行走时产生的信息素量的差异。同时，我们也针对已有的点扩散 的信息素扩散模型改进为路径扩散的信息素扩散模型，更客观地强化了蚁群个体 间的影响和协作。另外，通过使用效率高且计算复杂度小的变异策略，随机搜索 机制，以加强局部寻优能力。 其次是对蚁群算法的应用研究，针对蚁群算法在求解有大规模的t s p 问题时 表现出时间和精度方面的不足，提出了多阶段的处理方法，先对问题先进行基于 密度的聚类处理，从区域的角度看待问题从而大大降低问题规模的复杂度，然后 进行区域级的路径寻优和区域内的路径寻优，最后按区域连接顺序合成完整的解 路径。在此基础之上，我们引入多粒度的概念，给出更具一般性的多粒度t s p 问题描述及其蚁群算法。随后，对蚁群算法在求解多维背包问题中的应用进行了 研究，提出一种新的基于信息素扩散和变异策略的多维背包问题的蚁群算法。 1 3 本文的组织结构 第一章：绪论。对课题的研究现状和研究意义进行了介绍，并详细阐述了蚁 群算法的产生及发展过程，随后简要介绍了本课题的研究内容。 第二章：基本蚁群优化算法及一些已有的改进算法。详细描述了基本蚁群算 法a n ts y s t e m 的模型与实现。并进一步介绍了一些已有的改进蚁群算法，如蚁 群系统a n tc o l o n ys y s t e m 、最大一最小蚂蚁系统m a x m i na n ts y s t e m 、基于变 异特征的蚁群算法、基于信息素扩散的蚁群算法。 北京下业大学t 学硕十学位论文 第三章：蚁群算法中信息素增量和扩散模型的研究。介绍了基于能量守恒的 信息素更新机制以及改进的信息素扩散模型，并给出相应的实验结果。 第四章：基于聚类及多粒度的蚁群算法。首先描述了基于聚类和分段优化的 蚁群算法，并通过实验进行了检验和分析，在此基础之上，详细介绍了基于多粒 度的蚁群算法。 第五章：蚁群算法求解多维背包问题。首先，简要描述了多维背包问题，然 后，详细阐述了利用t o p - k 策略获取当前蚁群的最优的k 个解，发现对象间的“关 联距离”，并通过建立扩散模型来实现信息素的更新过程，最后，对实验数据进 行分析。 6 第2 章基本蚁群优化算法及已有的改进算法 第2 章基本蚁群优化算法及已有的改进算法 受自然界蚁群觅食行为的启发，d o r i g om 等人首次提出了模拟进化算法 蚂蚁系统a s ，开创了蚁群算法研究的先河，并用它求解t s p 问题，其实验显示 a s 算法具有极强的发现较好解的能力。然而，a s 也存在着一些不足之处，如收 敛速度慢、易陷入停滞等。对此，许多学者也纷纷提出一些改进的蚁群算法，如 蚁群系统a c s ，最大一最小蚂蚁系统m m a s ，具有变异特征的蚁群算法等等。 本章首先介绍了a s 算法的基本模型，然后讨论了几种a s 的改进算法。 2 1 蚂蚁系统( a s ) 模型与实现 2 1 1 旅行商问题 旅行商问题( 即t s p ) 是一个经典的组合优化问题，n 个城市的t s p 问题求 解可描述为访问n 个城市各一次且最后回到出发点的最短路径。具体地讲，给定 一个城市集合v = q ，屹， ，每个城市坼v 用其对应的坐标点“，乃) 表示， d o = ( 一一x ，) 2 一( m y j ) 2 ( j ，j = l ，2 ，聍) 表示城市v 与城市巧之间的欧氏距离， t s p 问题的一个解就是遍历所有n 个城市后回到出发点的一个全连通图，可表示 为g ( n ，彳) ，彳= = ( v i , ，) | 0 2 r ，则信息素扩散的浓度场及扩散范围可如图3 1 ( a ) 中灰色区域所示， 图中小圆点表示城市位置，黑色圆点表示受扩散影响的城市，以i 、j 为 中心的同心圆表示扩散场内不同位置浓度场强的等势线。从图可见，城市信源作 为信息素扩散浓度场的中心，离信源越近，浓度场的场强越强( 等势线越密) 。 除所经过的城市i 和j 外，蚂蚁k 在本次行走中还会影响位于城市c 。、c ：、c 。、 c 。上蚂蚁选路的行为。然而，根据假设l ，信息素是滞留在蚂蚁所经过的整条路 径上的，所以信息素应以所依附的路径a 口为中心向外扩散，因而，图3 1 ( a ) 中的扩散模型存在一定的局限。因此，可对其进行改进，将扩散模型修正为以路 径为信源向周边扩散，如图3 - 1 ( b ) 所示，蚂蚁k 在从城市j 走到i 的过程中所 留下的信息素将形成更大范围的浓度场，影响的城市集合也扩大为c 、c ：、c 。、 c 。、c 。、c 。、c ，、c 。这种变化更客观地反映了信息素扩散的浓度场，扩大了信息 素扩散的作用范围。 l ( x o , y o i ，y o “1(x2,yo 图3 - 2 在信息素扩散浓度场内扩散距离求解的示意图 f i g u r e3 - 2 t h es k e t c hm a po fp h e r o m o n ed i f f u s i o ni ni n t e n s i t yf i e l d 设蚂蚁刚走过路径a f ，基于路径为信源的信息素扩散模型，下面推导由蚂 蚁的此次行走所影响到的相邻路径上的信息素浓度。为了求城市1 到路径的 垂直距离d ，我们分两种情况讨论： 1 ) 当t s p 问题中的城市位置用坐标给出时，如图3 2 所示，城市i 、 j 和 l 的坐标分别为( x 。，y 。) 、( x ：，y ：) 和( x 。，y 。) ，推导如下： 当x 1 = x ：时，由i 、j 两点形成的直线l 垂直于x 轴，l 的方程为：x = x - ； 当x 。x ：时，由i 、j 两点形成的直线l 的方程为： y - y 。= 警( x 一而) ； 2 一 将直线l 的表达式化为形如锻+ 砂+ c = 0 的标准形式，依据点到直线的距离 公式，可以得到1 点到直线l 的距离：d ：一l a x o + b y o + c l 。 口2 + 6 2 2 ) 当t s p 问题中城市间的距离已知时，即在图3 2 中已知吻、嘞， 此时，可以利用海伦公式求垂直距离d ，方法如下：令s = ( a u + 即+ 口f i ) 9 ， 则三角形i j l 的面积为a = s o 一) ( s - a j , ) o a i r ) ，又因为a = ( d 口 ) 2 ，所 以d = 2 a a 扩。 在得到城市l 离路径信源的距离d 后，我们就可判断城市l 是否位于蚂蚁k 在本次行走中所形成的信息素浓度场的扩散范围内，如果在扩散半径内，就依据 1 7 北京t 业大学工学硕士学位论文 它的值，计算扩散到相应路径上的信息素： 1 ) 当城市l 位于图3 1 ( b ) 中的a 区，且d f ， ( 扩散半径) 时，城市 i 对路径a 盯的影响群可按下式计算得到； 啦警”争如果九，( 3 - 3 ) 【0 ，。 否则 2 ) 当城市l 位于图3 1 ( b ) 中的c 区，且d f ls ，i ( 扩散半径) 时，城市j 对路径口，的影响d ：可按下式计算得到； 磁： 半”了d j r 棚果办，( 3 - 4 ) h 否则 3 ) 当城市1 位于图3 1 ( b ) 中的b 区，且d u ，时，d 刍为直线段气对 路径口，和路径唧上信息素的影响，其计算公式为： 珑： 警”争，如果d u ，( 3 - 5 ) 【0 ，“ 否则 从上述计算公式可知，无论是到城市，还是到所行走的直线段，只要与信源 等距的点都受等势的场强浓度的影响，因而，这种扩散机制更客观真实地再现了 自然界中信源扩散的过程。 3 3 变异优化策略 为了提高蚁群算法的寻优能力，常见的蚁群算法通常会使用局部优化的方法 ( 如2 - o p t ) 来改进原算法的性能。而吴庆洪、朱庆保等人提出了利用变异算法 局部寻优能力强的特点n 7 2 如，对所得到的解进行局部变异，加快最优解的获得。 这两种方法都是对当前解的有限邻域进行快速搜索以得到本次迭代的更好解，从 而减少蚁群算法的迭代次数。不同之处在于搜索空间及计算复杂度的差异，2 - o p t 局部搜索空间是当前解的某一有限邻域，其单次执行的计算复杂度 为d ( c ：) = o ( n 2 ) ，而变异策略搜索的仅是该有限邻域的一个子域，如文献 2 2 中变异算法的计算复杂度为o ( n 一2 ) + o ( n 一3 ) = d ( 刀)，由此可见，变异策略 的计算复杂度更小，搜索效率可能更高。因此，在本章算法中也采用类似的变异 策略以加快算法的求解。 3 4 算法描述 综合以上几点，这里提出了一种将信息素生成、扩散和变异策略相融合的求 解t s p 问题的新算法。新算法的基本框架如下： 1 8 第3 帝蚁群算法中信息素增量和扩散模型的研究 一p d m a c o爿三g o 彤7 ：h m 1 初始化阶段 初始化参数，赋给各条路径相同的信息素浓度，并将脚只蚂蚁随机放到月个城市节点上； 为每只蚂蚁设置起点和允许访问的城市列表； 2 蚁群的一次周游过程( 一次迭代) f o rp = 1t o 刀遍历所有城市，最后回到出发点 f o rk = lt o m 蚁群的一步转移 i f p 输出分段优化后的结果； 算法中函数a c s ( s t a r t ，s e c t i o n l e n g t h ) 是由a c s 算法稍加修改后得到， 其返回值是蚁群从分段始点出发，遍历完该段中所有其它城市后得到的最短路径 长度。 4 2 6 实验结果及分析 对新算法的性能进行测试，并将测试结果与基本的a c s 算法及c p a c a 算法进 行比较。实验中所使用的多个t s p 问题的数据来源于t s p l i b 标准库。本实验中 a c s 算法所使用的参数设置为a = 1 ，8 = 2 ，p = 0 1 ，y = 0 1 ，t 。= l n l 呻。本章 算法运行时的参数设置如表4 - 1 所示。( n 为城市的规模) 表4 - 2 为基本的a c s 算法与本章算法对不同t s p 问题求解的结果比较，表中 问题的解为两种算法各运行1 0 次所得到的最佳值，运行时间为得到最佳值所对 应的时间，误差为所得到的最佳值与问题实际最优解的相对偏差。从结果可见， 2 9 表4 - 1 本章算法求解不同问题时的参数设置 t a b l e4 1p a r a m e t e rd e p l o y m e n t su s e di ne x p e r i m e n t sf o rs e v e r a lp r o b l e m s 本章算法在较短的时间内就能得到误差更小的解，可见利用环境的启发信息设计 的基于聚类和分段寻优的蚁群算法，能够通过降低原问题的规模，缩短寻优时间， 并获得更满意的解。 表4 - 2a c s 算法与本章算法求解不同t s p 问题的结果比较 t a b l e4 - 2 c o m p a r i s o no fr e s u l t sb e t w e e na c sa n dt h ep r o p o s e da l g o r i t h mf o rs e v e r a lt s p p r o b l e m s 图4 2 为本章算法所求得p r l 0 7 、p r l 3 6 问题的最优解路径，其值分别为 4 4 3 4 6 2 和9 6 9 1 6 5 ，都好于文献 4 4 中的c p a c a 算法所得到出的最优解( 4 4 5 1 4 和9 7 2 1 8 ) 。实验结果说明：本章算法与c p a c a 算法相比，在学习精度上有一定 的优势。 图4 - 2 本章算法所求得p r l 0 7 、p r l 3 6 问题的解 f i g u r e4 - 2r e s u l t so f t h ep r o p o s e da l g o r i t h mf o rp r o b l e mp r l 0 7a n dp r l 3 6 3 0 第4 章基于聚类及多粒度问题描述的蚁群算法 4 3 多粒度t s p 问题描述模型及蚁群求解 基于密度聚类的蚁群算法给了我们个启示，即通过某种合理途径将原本规 模复杂的问题规约分解为规模简单的问题，这是我们常用的问题求解模式。一般 地，在面对复杂的、难于准确把握的问题时，人们通常不只是一味地追求精确的 最佳解，而是通过逐步尝试的办法达到满足一定精度的合理目标。这是一种概略 地、由粗到细、不断求精的多粒度分析法，利用多粒度分析问题可以避免求解大 规模问题时所遇到的计算复杂度过高的困难。然而，为利用多粒度分析来求解问 题，如何描述问题往往成为解决复杂问题的基础。对于大规模t s p 问题来说，描 述模型是否合理将直接影响算法求解的效率。而现有的t s p 问题描述模型无法满 足实际应用对求解速率的需要，为此，本节提出多粒度的t s p 问题描述模型，基 于该模型可以将原问题的规模大大降低，从而加快t s p 问题的求解。 4 3 1 多粒度t s p 问题描述模型 为方便描述多粒度t s p 问题模型，我们给出了商人最近城市选择假设以及超 城市，孤立城市和边缘城市的定义。 生物学家研究发现，在自然界的真实蚁群的觅食行为中，大部分蚂蚁会优先 选择离自己目前位置较近的食物源去觅食，如果存在较密集( 彼此间距离较