（计算机科学与技术专业论文）蚁群算法及其在ad+hoc网络路由寻址中的应用研究.pdf

k - l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 己在论文中作了明确的说明并表示了谢意。 签名：翘2 多终 日期：左吖虫上 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 导师签名： 摘要 摘要 a dh o c 网络是一种具有高度动态拓扑结构、节点任意移动的无线自组织网 络。网络灵活机动、适应环境能力强，对终端性能要求不高，不需要固定基础设 施的支持，具有较强的鲁棒性、抗毁性。然而，a dh o c 网络的特性也对路由协 议提出了更高的要求。因此，如何在网络拓扑结构动态变化、无线传输带宽有限、 终端使用可耗尽资源的情况下设计高效、合理、自适应的路由协议，便成为a d h o c 网络发展的一个重要性的研究课题。 蚁群算法是一种从自然界中的社会性昆虫的特性受到启发，发展而来的一种 群集智能的搜索算法，目前已在许多组合优化问题中获得了广泛的应用。其特有 的分布式计算、单个智能体实现简单、支持多路径等优点，能够很好地满足a d h o c 动态网络的路由需求。但是，为了获得更好的网络路由性能，需对已有的蚁 群算法进行改进和优化才能使其更好地适用于无线a dh o c 网络路由。因此，研 究基于改进蚁群优化的a dh o c 网络路由算法具有非常重要的理论和现实意义。 本文的主要工作包括：1 ) 系统地概述了蚁群算法的原理和模型；2 ) 在现有 蚁群优化算法基础上提出了一种动态自适应的蚁群算法( d s a c o ) 。d s a c o 算 法首先通过大量实验设定影响算法性能的重要参数( q 、b 和p ) ，当算法陷入 局部最优时，通过自适应调整参数来提高全局最优解的求解质量；然后根据信息 素值的不同自适应地调整各路径上的信息量强度；最后在典型的t s p 问题上进 行仿真验证，实验表明，该算法与基本蚁群算法相比，在收敛速度和全局寻优方 面都有较大的提高。3 ) 结合a dh o c 网络的动态特性，把d s a c o 算法应用于 a dh o c 网络的路由选择中，提出了一种基于d s a c o 算法的a dh o c 网络路由算 法( a n r b a ) 。a n r b a 算法把节点的负载，网络的拓扑变化和路径的时延作为 路径质量的度量，将路径质量的路由表用蚁群的信息素表示；在路由发现和路由 更新时，释放和更新信息素；转发概率由信息素和跳数来确定。仿真结果表明， a n r b a 算法在分组投递率、平均端到端时延、归一化路由丌销等方面都优于 a o d v 算法。 关键词a dh o c 网络；蚁群算法；路由算法；自适应 北京工业大学工学硕士学位 a b s t r a c t a b s t r a c t a dh o cn e r ki saw i r e l e s s s e l f - o 唱a i l i z i n gn e t w o r ko fh i g h l yd y n 锄i c t o p o l o g ya i l da n ym o b i l en o d e s n e 似o r kn e x i b i l 埘a n ds t r o n ga b i l i 够t oa d a p tt 0t h e e n v i r o n m e n t ，r e q u i r el e s st e m i n a lp e r f o m l a n c e ，d o e sn o tn e e df i x e di n 行a s t m c t u r e s u p p o r t ，h a ss t r o n gr o b u s m e s s ，s u r v i v a b i l i 何h o w e v e r a dh o cn e t w o r kr o u t i n g p r o t o c o lc h a r a c t e r i s t i c s a l s o p u tf o n v a r dl l i g h e rr e q u i r e m e n t s t h e r e f o r e ，h o w d y n 锄i cc h a l l g e si nm en e 铆o r kt o p o l o g y ，w i r e l e s st m s m i s s i o nb a n d w i d mi sl i m i t e d ， e n d u s eo fe x h a u s t i b l er e s o u r c e st 0d e s i g l le 伍c i e n t ，r a t i o n a la n da d a p t i v er o u t i n g p r o t o c o l s ，h a sb e c o m ea 1 1i m p o n a j l tr e s e a r c hi s s u ei na dh o cn e t w o r k s a n tc o l o n ya l g o r i t h mi sak i n do fs w a u r mi n t e l l i g e n c eh e u r i s t i c a l g o r i t h mt h a t i n s p i r e d 疳o ms o c i a li n s e c t si nn a t u r e ，w h i c hh 2 l sb e e n 、v i d e l yu s e di nm 甜l y c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s a sd i s t r i b u t e dc o m p u t i n g ，as i n g l e a g e n tt o a c l l i e v eas i m p l e ，m u l t i _ p a t hc h a r a c t e r i s t i c s ，a n tc o l o n ya l g o r i t l u ni sv e 叫s u i t a b l ef o r a dh o cn e t w o r kr o u t i n g h o w e v e r ，i no r d e rt oo b t a j nb e t t e rr o u t i n gp e r f o m a n c e ，t a k e o nt h ee x i s t i n g 趾tc o l o n ya l g o r i t l l mi si m p r o v e da 1 1 do p t i m i z e dt om a k ei tb e t t e rf o r w i r e l e s sa dh o cn e t 、v o r kr o u t i n g t h e r e f o r e ，t h er e s e a r c hi sb a s e do na n tc o l o n y o p t i m i z a t i o nr o u t i n ga l g o r i t h mf o ra dh o cr l e t w o r k si sv e 巧i m p o r t a n tt h e o r e t i c a l a n dp r a c t i c a ls i g n i f i c a n c e t h i sp a p e r sm a i nw o r di n c l u d e ：1 ) s y s t e m a t i co u t l i n e st h ep r i n c i p l e sa n dm o d e l s o fa 1 1 tc o l o n ya l g o r i t l l i i l ；2 ) np o s e sad y n 锄i cs e l fa d 印t i v e 眦c 0 1 0 n yo p t i m i z a t i o n a l g o r i t h m ( d s a c o ) b a s e do na ne x i s t i n ga n tc o l o r l ya l g o r i t h m t h ed s a c 0 a l g o r i t l u i lf i r s ts e t s u pa n d 甜r e c t st h ea l g o r i t h i i lp e r f o m a n c ep a r 锄e t e r s ( a ，pa n d p ) m r o u 曲al a 娼en u m b e ro fi m p o r t a n te x p e r i m e n t ，w h e nt h ea l g o r i t h m 仃印si n t oa l o c a lo p t i m u m ，t h r o u g ht h ea d a p t i v ea d j u s t m e n to fp a r 锄e t e r st oi m p r o v et l l eg l o b a l o p t i m u ms o l u t i o no fq u a l i t y t h e nu n d e rt l l ed i f f i e r e n tp h e r o m o n ev a l u e sa 由u s t st h e 锄o u n to fi i l f o n l l a t i o no nt h es t r e n g mo fe a c hp a 也f i n a l l y ，o nt h eq u e s t i o no fa t y p i c a lt s ps i m u l a t i o ne x p e r i m e n ts h o w st h a tt 1 1 ea l g o r i t h m ，c o m p a r e dw i t hb a s i ca m c o l o n ya l g o r i t l u l l ，t h ec o n v e 堵e n c es p e e da l l dg l o b a lo p t i m i z a t i o na s p e c t se n h a n c e d 3 ) c o m b i n e dw i t ht h ed ”锄i cn 籼eo fa dh o cn e 咖r k t h ed s a c oa l g o r i t l l i i li s a p p l i e dt oa dh o c n e t 、v o r kr o u t i n g ，p r o p o s e da i la dh o cn e t w - o r k sr o u t i n ga l g o r i t h m a n r b ab a s e do nd s a c o a l g o r i t h m t h ea n r b aa l g o r i t h ma d o p t sn l en o d el o a d ， n e t 、o r kt o p o l o g yc h a n g e sa n dt h ep a t hd e l a ya sam e a s u r eo ft h eq u a l i t yo ft h ep a t h ， t h e p a t ht 0m eq u a l i 哆o ft h er o u t i n g 讪1 e 谢t ht l l e a n t c o l o n yp h e r o m o n e i i i r e p r e s e n t a t i o n ；i n r o u t ed i s c o v e r ya n dr o u t i n g u p d a t e s ，r e l e a s e a n du p d a t et h e p h e r o m o n e ；f o 刑a r d i n gp r o b a b i l i t y ，p h e r o m o n ea n dt h en u m b e ro fh o p st od e t e n l l i n e s i m u l a t i o nr e s u l t ss h o wt h a t ，a n r b aa l g o r i t h mp a c k e td e l i v e r yr a t e ，a v e r a g ee n d t o e n dd e l a y ，n o m a l i z e dr o u t i n go v e r h e a d ，e t c 。a r es u p e r i o rt oa o d va l g o r i t h m k e y w o r d sa dh o cn e 帆o r k ；a n tc o l o n ya l g o r i t h m ；r o u t i n ga l g o r i t i l i l l ；s e l f - a d 印t i v e i v 目录 目录 摘要i a b s t r a c t i i i 第1 章绪论1 1 1 课题研究的背景及意义1 1 2 国内外研究现状2 1 3 本文的主要研究工作4 1 4 本文的组织结构安排5 第2 章蚁群算法的原理与模型6 2 1 蚁群算法简介6 2 2 蚁群算法原理。7 2 3 蚁群算法模型及实现步骤8 2 3 1 蚁群算法模型8 2 3 2 蚁群算法的实现步骤9 2 3 3 蚁群算法的程序流程1 0 2 3 本章小结1 0 第3 章蚁群算法的改进1 2 3 1 蚁群优化算法介绍1 2 3 1 1 蚁群系统1 2 3 1 2 最大最小蚂蚁系统( m m a s ) 1 3 3 2 基于参数自适应调整的改进蚁群算法1 5 3 2 1 参数0 【、b 的自适应调整1 6 3 2 2 参数p 的自适应调整1 6 3 3 基于信息素动念更新的改进蚁群算法1 8 3 4 动态自适应改进蚁群算法的实现步骤2 0 3 5 仿真结果及分析2 0 3 6 本章小结2 4 第4 章蚁群算法在a dh o c 网络路由中的应用2 5 4 1a dh o c 网络简介2 5 4 1 1a dh o c 网络的定义2 5 4 1 2a dh o c 网络的特点2 5 4 1 3a dh o c 网络路由协议2 6 4 2 蚁群算法在a dh o c 网络中的典型应用2 8 4 3 基于蚁群优化的a dh o c 网络路由算法3 0 4 3 1 相关术语说明3 0 4 3 2 算法设计思想3 3 4 3 3 算法的规则3 5 4 4 算法工作机制3 7 4 4 1 路由发现过程3 7 北京工业大学工学硕士学位 4 4 2 路由更新和维护过程3 7 4 4 3 拥塞处理过程3 8 4 5 仿真结果与分析3 8 4 5 1 节点移动性对性能的影响3 9 4 5 2 网络负载对性能的影响4 1 4 6 本章小结4 3 结j 沧4 5 本文工作总结4 5 未来工作展望4 5 参考文献4 7 攻读硕士学位期间所发表的学术论文5 1 致谢5 3 附录5 5 第1 章绪论 1 1 课题研究的背景及意义 蚁群算法是由意大利学者m d o r i g o 等人于2 0 世纪9 0 年代初提出的一种基 于种群进化的启发式搜索方法【l 】。蚁群算法最早用于解决著名的旅行商问题 ( t s p ) ，采用了分布式正反馈并行计算机制，易于与其他方法结合，并具有较强的 鲁棒性。这种算法的提出借鉴和吸收了现实世界中蚂蚁种群的行为特征：蚂蚁在 觅食过程中能分泌一种称之为信息素的物质，并能利用信息素的轨迹作为媒介与 其它的蚂蚁进行信息沟通。一条路径上留下的信息素轨迹的多少与这条路径上通 过的蚂蚁数成正比，当通过的蚂蚁越多，则留下的信息素轨迹就越多，从而导致 后来蚂蚁选择该条路径的概率提高。这样，没有视觉能力的蚂蚁在上述过程中展 现出了一种协作的自催化行为能力，蚂蚁正是基于此建立最短的移动路径。蚂蚁 的这种协作搜索行为为一些实际优化问题提供了一种新的计算方法，这种新型的 分布式智能模拟算法已逐渐引起包括计算机科学家在内的众多研究人员的兴趣。 蚁群算法在过去短短十多年的时间里，己在t s p 问题、分配问题、路径规 划问题、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛的 应用，并取得了较好的效果。蚁群算法特别适合求解规模较大的或问题状态随时 间变化的组合优化问题，如著名的旅行商问题( t r a v e l i n gs a l e s m a l lp r o b l e m ，t s p ) 、 二次分配问题( q u a d r a t i ca s s 追n m e n t p r o b l e m ，q a p ) 、作业调度问题( j o b s h o p s c h e d u l i n gp r o b l e m ，j s p ) 等复杂组合优化问题。 尽管目前对蚁群优化算法的研究刚刚起步，一些思想尚处于萌芽时期，严格 理论基础尚未确立，国内外有关研究仍停留在实验探索阶段，但人们己隐隐约约 认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然，因此，越 来越多的学者开始关注和研究蚁群优化算法，初步的研究结果已显示出该算法在 求解复杂优化问题方面的优越性。从当前的应用效果来看，这种模仿自然生物的 新型系统寻优思想无疑具有十分光明的前景。 a dh o c 网络【2 j 是由一组带有无线通信装置的移动终端节点组成的一个多跳 的、临时的、无中心、自组织的网络，可以随时随地快速构建移动通信网络，网 络中的每个终端可以自由移动，地位平等。a dh o c 网络的研究是因军事应用而 发起的，所以，军事应用仍是a dh o c 网络的主要应用领域，但随着信息技术的 不断发展，在紧急事故、临时场合、个人通信等民用方面，a dh o c 网络也有非 常广阔的应用前景。 北京工业大学工学五页士掌位论文 a dh o c 网络灵活机动、组网迅速、适应性及鲁棒性强的特点使其成为近年 来网络研究的热点。然而，目前无线自组网仍面临许多挑战。无线a dh o c 网络 中的节点使用的是可耗尽能源，传输带宽有限，节点需同时具备终端和路由器的 功能、网络拓扑结构动态变化等特点，使得自组网路由【3 】成为自组网的关键和难 点之一。 蚁群优化算法用于自组网路由的优势【4 - 5 】有：支持多路径、支持分布式的计 算、路由表简单，控制信息少，甚至可由一般数据分组携带。使用蚁群算法进行 无线自组网路由虽然可以得到较好的性能，但蚁群算法也存在着停滞和收敛较慢 的矛盾。停滞是指在路由过程中，由于某一路径在某一阶段质量较好，则此路径 上信息素浓度较高，更多的蚂蚁也就是数据分组更可能选择此路径，同时留下更 多信息素，最终使所有的数据分组都通过此路径传递，即此路径选择概率接近甚 至到达1 。这样即使路径质量变差，数据分组也很难选择其它路径传递，另外也 不利于新的更好路径的发现。而如果控制信息素的更新，限制信息素浓度，可在 一定程度上避免停滞，却又可能导致收敛速度变慢。 蚁群算法本身的性能使得蚁群算法是可以用于a d h o c 无线网络路由。但从 蚁群算法的分析和讨论来看，尚需要进一步的改进和优化才可以使得蚁群算法和 优化的蚁群算法更适用于a dh o c 无线网络路由。为了取得更好的网络路由性能， 因此，研究基于蚁群优化的a dh o c 网络路由算法具有非常重要的理论和现实意 义。 1 2 国内外研究现状 受自然界中真实蚁群集体行为的启发，意大利学者m d o “g o 于1 9 9 1 年首 次系统地提出了一种基于蚂蚁种群的新型优化算法一蚁群算法( a c o ) ，并成功 地用于求解旅行商( t s p ) 问题。自1 9 9 6 年之后的5 年时间里，蚁群算法逐渐 引起了世界各国学者的关注，在应用领域得到了迅速拓宽。 国内对蚁群算法的引入【6 】、介绍和开展研究起始于1 9 9 8 年术至1 9 9 9 年， 2 0 0 0 年开始逐渐引起关注，并很快于数年间发展成为热点领域。国内的早期研 究大都集中在组合优化问题上，对连续优化问题的研究则起步于2 0 0 0 年。 目前人们对蚁群算法的研究已由当初单一的t s p 领域渗透到多个应用领 域；由解决一维静态优化问题发展到解决多维动态组合优化问题；由离散域范围 内研究逐渐拓展到连续域范围内的研究，使这种新兴的仿生优化算法展现出勃勃 生机，并已成为可与遗传算法相媲美的仿生优化算法。根据求解的优化问题的性 质把蚁群优化算法的应用大致分为两类：静态优化问题和动态优化问题。 静态优化问题，顾名思义，就是一旦一个优化问题被给出，所有的内容也 第1 章绪论 就确定下来，在解决这个优化问题时这些内容也不会发生变化。这类问题的一个 典型例子就是经典的旅行商问题，在解决t s p 问题的时候，城市的位置以及它 们之间的相互距离等保持不变。对于静态优化问题的应用，蚁群优化算法的应用 研究一直非常活跃，从最初的t s p 问题陆续渗透到其他应用问题，如作业调度 问题是一种资源分配问题。这里的资源主要是指设备资源，问题的求解目标是要 找到一个将一组工件安排到设备上去，以使作业可为“最优”完成的方案。每个 作业可由一些任务完成，而每个任务必须由特定的设备处理。一个调度是指按先 后顺序条件将所有任务安排到设备上的一种方案。二次分配问题是继t s p 问题 后，a c o 算法在组合优化问题领域的又一个重要应用方面。目前针对q a p 问题 的算法多是利用q a p 和t s p 的相似性而对求解t s p 问题的a c o 算法的推广， 并针对q a p 问题的自身特点对a c o 算法做了相应的调整。多选择背包问题 ( m u l t i p l ek n 印s a c kp r o b l e m ，m p k ) 定义为有附加约束的背包问题，该问题带有互 不相关的多选择约束。问题就是从每类中选择一个项目使得项目总重量在满足背 包承重约束的前提下最小化费用。机器人路径规划是指机器人按照某一性能指标 搜索一条从起始状态到目标状态的最优或近似最优的无碰路径，它是实现机器人 控制和导航的基础之一。一般可将机器人路径规划算法分为全局规划和局部规划一 两大类。蚁群优化算法在路径优化方面的优异性能使得其在机器人路径规划的研 究上取得了丰富的研究成果。多机器人系统是一个松散结构的分布式系统，其优 点在于既可以独立工作，又可以在需要时进行协作。在任务未知的环境中，确定。 有哪些任务需要多个机器人协作完成是一个重要而艰巨的工作。蚁群优化算法特 有的协作方式使得研究者们对其在多机器人协作方面进行了大量的研究。电力系 统是一个国家经济发展的命脉，而配电网是电力系统的重要组成部分，其投资及 运行费用在整个电力系统费用中所占的比例十分可观。好的配电网规划方案可为 电力公司节约大量的资金，而配电网网络结构的规划是一个离散非线性的多约束 组合优化问题，长期以来，研究者们针对这一问题做了大量的研究，提出了多种 算法。近年来，a c o 算法在电力系统领域也得到了很好的应用。另外，蚁群算 法还在系统辨识、聚类分析、故障诊断、数据挖掘、图像处理、航迹规划、空战 决策、岩土工程、化学工业、生命科学以及布局优化等应用领域中得到了广泛的 研究，并取得了大量研究成果。 动态优化问题则可以认为是含有若干个时变参数的函数优化问题。因此解 决这些问题的优化算法必须能够及时地适应变化的环境。这类问题的一个典型例 子就是网络路由问题。蚁群优化算法在动态组合优化问题中的应用主要集中在网 络通信方面，特别是网络路由选择问题叫e t 、) r o r ki b u t i n gp r o b l e m ，n r p ) 上。网 络路由选择问题可以简单描述为在一个代表通信网络的全连接图中求解任何两 个节点的最短路径问题。虽然在静态环境下该问题可以通过多项式算法求解，但 北京工业大学工学硕士学位论文 在节点间流量( 边的权重) 随时间变化情况下，该问题的求解变得非常困难。因此 采用蚁群算法解决计算机中的网络路由问题受到众多学者的关注。n r p 问题是 典型的动态组合优化问题，其基本特征如信息的分布式特性、动态性、随机性和 异步性等与蚁群算法的特征匹配得很好，对均衡网络负载量以及提高网络的利用 率非常有益。s c h o o n d e 俐o e r d 和h o l l a n d 等人最早将a c o 算法应用到n i 心问题 中，将此算法称为a b c ( a n t b a s e dc o n t r 0 1 ) 【9 1 ，算法中采用跳数作为度量标准， 主要应用对象是面向连接的电话网络，并不适合于一般的数据网络。d ic a r o 和 d o r i 2 0 开发了一种应用在无连接数据网络的分布式自适应路由算法a n t n e t 【i ， 并与当前各种最好的适应性路由算法进行对比，研究结果表明，a n t n e t 在吞吐 量和数据包延迟方面都显示出良好的性能，对网络资源的影响几乎可以忽略。v a n d e rp u t 等人设计出了a b c - b a c k 、v a r d 网络。12 1 ，实验结果显示a b c - b a c k w a r d 在 代价对称和代价不对称网络系统中的性能都比a b c 好，并将其应用在了荷兰最 大的电话公司一k p n 电信提出的传真分配问题中。近年来，蚁群算法又被用于网 络负载平衡和a dh o c 自组网的路由问题中，并取得了一定进展。 基于蚁群算法的网络路由算法的研列1 3 。14 1 ，现在广泛使用的路由算法中，一 个问题就是其确定性静态本质，然而a dh o c 网络等却具有高度的动态性，由于 网络的动态性，特定路径的长度( 时延) 是随着流量的变化而变化的。因此，不断 的测试、发现所有可能存在的路径，并自适应此变化是很有必要的。另一个问题 就是现存的路由算法是通过固定间隔进行更新的方式，来确保一个相对较新最短 路径，但这种方式只能在问题出现时才来解决，而不是事先避免。通过一种连续 更新信息的方式，能更适合于解决这种类型的问题。这正是蚁群算法的特长，通 过在其环境中连续搜索找到最优解，能够适应a dh o c 网络的动态变化。 1 3 本文的主要研究工作 本文主要围绕网络路由问题对蚁群优化算法进行研究。首先对蚁群算法原 理、模型和实现步骤等进行分析。其次在现有蚁群优化算法基础上提出了一种动 态自适应的蚁群算法( d s a c o ) ，d s a c o 算法是通过自适应调整参数q 、b 、 p 和动态更新信息素来实现的，并在典型的t s p 问题上得到验证。d s a c o 算法 的思想能够满足a dh o c 网络的动态特性需求。所以本文在分析a dh o c 网络的 路由基础上，把d s a c o 算法应用在a dh o c 网络中，提出了一种基于d s a c o 算法的a dh o c 网络路由算法( a n r b a ) 。a n l 强a 算法把路由表用蚁群的信息 素表示；在路由发现和路由更新时，释放和更新信息素；转发概率由信息素和跳 数来确定。并通过仿真实验进行了验证。 第l 章绪论 1 4 本文的组织结构安排 本文的组织结构安排如下： 第1 章绪论。本章主要介绍本课题的研究背景与意义，以及国内外研究现 状，并对本文的主要研究内容和组织结构进行介绍。 第2 章蚁群算法的原理与模型。蚁群算法是一种新型的仿生优化算法，它 通过模拟蚁群搜索食物的过程，到达求解比较困难的组合优化问题的目的。本章 首先阐述蚁群算法的原理，然后对蚁群算法的模型和蚁群算法的实现步骤进行描 述。 第3 章蚁群算法的改进。本章首先在研究现有蚁群优化算法的基础上提出 一种动态自适应的蚁群算法( d s a c o ) ，d s a c o 算法是通过对关键参数q 、b 、 p 的动态调整和信息素的动态更新来实现的；然后介绍d s a c o 算法的实现步 骤；最后进行仿真实验及结果分析。 第4 章蚁群算法在a dh o c 网络路由中的应用。本章首先对a dh o c 网络作 简单介绍；然后提出一种基于d s a c 0 的a dh o c 网络路由算法( a n r b a ) ， a n i 氇a 算法把节点的负载，网络的拓扑变化和路径的时延作为路径质量的度量， 将路径质量的路由表用蚁群的信息素表示，在路由发现和路由更新时，释放和更 新信息素，转发概率由信息素和跳数来确定；最后进行仿真实验及结果分析。， 结论。对全文工作进行小结，提出本论文的工作结果，并对今后的工作进行 了展望。 最后，给出了参考文献及致谢。 北京工业大学工学硕士学位论文 第2 章蚁群算法的原理与模型 2 1 蚁群算法简介 自2 0 世纪5 0 年代中期创立了仿生学以来，人们从生物进化的机理中受到启 发，提出了许多用以解决复杂优化问题的方法，如遗传算法、进化规划、进化策 略等。蚁群算法( a n tc o l o n ya l g o r i t h m ，简称a c a ) 是人们对自然界中真实蚁群行 为研究而提出的一种基于种群的模拟进化算法，属于随机搜索算法。它首先由意 大利学者m d o r i g o 等人提出来，他们称之为蚂蚁系统( a n ts y s t e m ，a s ) o b j 。 到了19 9 6 年，m d o r i g o 等人在i e e et t 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 m e t i c s p 甜b 上发表了“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 ”一文，在这篇文章中，m d o r i g o 等人不仅更加系统地阐述了蚁群算法的 基本原理和数学模型，还将其与遗传算法、禁忌搜索算法、模拟退火算法、爬山 法等进行了仿真实验比较，并把算法由单纯地解决对称t s p 问题拓展到解决非 对称t s p 问题、指派问题以及车间作业调度问题，且对蚁群算法中初始化参数 对其性能的影响做了初步探讨，这是蚁群算法发展史上的一篇奠基性文章。 蚁群算法充分利用了蚁群搜索食物的过程与著名的旅行商问题( t s p ) 之间的 相似性，通过人工模拟蚂蚁搜索食物的过程( 即：通过个体之间的信息交流与相互 协作最终找到从蚁穴到食物源的最短路径) 来求解t s p 问题。像蚂蚁这类群居昆 虫，虽然单个蚂蚁的行为极其简单，但由这样的单个简单个体所组成的蚁群群体 却表现出极其复杂的行为，能够完成复杂的任务。不仅如此，蚂蚁还能够适应环 境的变化，如在蚁群运动路线上突然出现障碍物时蚂蚁能够很快地重新找到最优 路径。 蚁群算法来源于对自然界蚂蚁寻找从蚁穴到食物的最短路径并找到回穴路 径方法的研究，是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生进化算 法。蚁群算法中采用有记忆的人工蚂蚁，通过个体之间的信息交流与相互协作来 找到从蚁穴到食物源的最短路径。研究发现，蚂蚁个体之间是通过一种称为信息 素的物质进行信息传递，从而相互协作，完成复杂任务。蚂蚁在运动过程中能够 在所经过的路径上留下信息素，而且蚂蚁在运动过程中能够感知这种信息素的存 在及其强度，并以此指导自己的运动方向。蚂蚁是自然界中常见的一种生物，蚁 群寻找食物时会派出一些蚂蚁分头在四周游荡，它们总能找到一条从食物到蚁穴 之间的最优路径。 第2 章蚁群算法的原理与模型 2 2 蚁群算法原理 模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算机智能模式【1 6 1 7 】引 入的，具体的过程描述如下，如果一只蚂蚁找到食物，它就返回蚁穴中通知同伴 并沿途留下“信息素”( 外激素) 作为蚁群前往食物所在地的标记。信息素会逐渐 挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到蚁穴中，那么比较 绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往 食物所在地。用于旅行商问题的蚁群算法采用虚拟的“蚂蚁 ，让它们摸索不同 路线，并留下会随时间逐渐消失的虚拟“信息素”。根据“信息素较浓的路线更 近”的原则，即可选择出最佳路线。这种信息素起到了非直接通信的作用。因此， 由大量蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越 多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流 达到搜索食物的目的。 如图2 1 ，设蚁穴处于a 点，蚂蚁觅食时由蚁穴出发，可沿a c ，也可沿 a b c ，设各蚂蚁寻到食物后沿原路返回到蚁穴，并在路上留下外激素，那么因为 a c 路径短，故当它们沿a c 返回时，就在a c 上留下两次外激素。而沿a b c 返 回者，因其路径长，仅返回到d 点，于是a d 一段只留过一次外激素( 即其上的 外激素的浓度比a c 上的浓度淡) ，这时，从蚁穴出来寻食者就会沿浓度大的路 径a c 行走。最后大多数的蚂蚁都会沿着较短的路程进行寻食。利用这个原理， 科学家们就设计了蚁群算法来求解最短路径。 b 图2 1 蚁群算法基本原理 f i g u r e2 一lt h eb 嬲i cp r i n c i p i e so fa n tc o l o n ya l g o r i t h m 北京工业大学工学硕士学位论文 2 3 蚁群算法模型及实现步骤 2 3 1 蚁群算法模型 蚁群算法最初是在求解t s p 问题时提出的。现给定一个有n 个城市的t s p 问题，蚁群中蚂蚁的数量为m ，以此来建立基本蚁群算法的模型。为了表述方便， 首先引进如下记号：设有n 个城市组成的集合c ，m 为蚁群中蚂蚁的总数目，用 d i j ( i ，j = 1 ，2 ，n ) 表示城市i 和城市j 之间的距离，q j ( t ) 表示t 时刻在城市i 和城 市j 之间的路径上残留的信息量，以此来模拟实际蚂蚁的分泌物。初始时刻各条 路径上信息量相等，设q i ( 0 ) = c o n s t ( c o n s t 为常数) 。蚂蚁k ( k _ 1 ，2 ，m ) 在运动过 程中，根据各条路径上的信息量决定转移方向，同时用禁忌表t a b u k ( k = 1 ，2 ，n ) 来记录蚂蚁k 当前已走过的城市，集合t a b u k 随着进化过程作动态调整。在搜索 过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。 时( t ) 表示在t 时刻蚂蚁k 由城市i 转移到城市j 的状态转移概率，其表达如公式 ( 2 1 ) 所示。 ml 笔若舶w 以 ，) p ：e 磊吨m ，) 】( f ) 】日j “ 1 lo否则 在公式( 2 1 ) 中，a l l o w e d k = c t a b u k ) 表示蚂蚁k 下一步允许选择的城市； q 为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累 的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经 过的路径，蚂蚁之间协作性越强；b 为期望启发式因子，表示能见度的相对重要 性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度。1 1 i i ( t ) 为启发函数，其表达如公式( 2 2 ) 所示。 ( ，) = 士 ( 2 - 2 ) 在公式( 2 2 ) 中，d i i 表示相邻两个城市之间的距离。对蚂蚁k 而言，d i j 越 小，则r li i ( t ) 越大，p j k ( t ) 也就越大。显然，该启发函数表示蚂蚁从城市i 转移到 城市j 的期望程度。 为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一个 循环后，要对路径( i j ) 上的信息量按公式( 2 3 ) 和( 2 4 ) 进行更新处理。 o + 1 ) = ( 1 一p ) 乃o ) + 乃o ) ( 2 3 ) 8 第2 章蚁群算法的原理与模型 f 盯( f ) = f ：( f ) 七= l ( 2 4 ) 在公式( 2 3 ) 中，p 为信息素挥发系数，则1 p 表示信息素残留因子，为 了防止信息的无限积累，p 的取值范围为 0 ，l 】，舷示蚂蚁k 在本次循环中 在城市i 和城市j 之间的路径上留下的信息素增量，初始时刻礤。户o ，舷 示第k 只蚂蚁在本次循环中留在路径( i j ) 上的信息量。 根据信息素更新的策略不同，d o r i g om 曾给出了不同的蚁群算法模型，分 别为a n t - c y c l e 模型，a n t q u a n t 竹模型和a n t d e n s 埘模型。它们的差别在于 怕的求法不同。 在a n t c y c l e 模型中 硝垆援当蚂蚍在，秕“嗽i j 经瑚时 ( 2 - 5 ) io 其他 在公式( 2 - 5 ) 中：q 是信息素强度，它影响算法的收敛速度；l k 是蚂蚁k 在a n t - q u a n t i t y 模型中 相：挎当蚂蚍在，秕+ 1 嗽烃过( “) 时 ( 2 - 6 ) io其他 、j 芋当蚂蚁七在f 和，+ l 时刻经过( f ，) 时 ( 2 7 ) ( f ) = 嘞 。 叫7 io 其他 模型比较：在a n t q u a l l t 时、a n t d e n s i t y 模型中利用的局部信息，即蚂蚁完 成一步后更新路径上的信息素；而在a m c y c l e 模型中利用的是整体信息，即蚂 蚁完成一个循环后更新所有路径上的信息素。实验表明，基于a n t c y c l e 模型的 蚁群算法性能优于其他两种模型算法。因此本文采用的是a n t c y c l e 模型。 2 3 2 蚁群算法的实现步骤 以t s p 为例，基本蚁群算法的具体实验步骤如下： ( 1 ) 参数初始化。令时间t = 0 ，循环次数n c = 0 ，设置最大循环次数n 。m 越，将 北京工业大学工学硕士学位论文 m 只蚂蚁随机分配到n 个城市，初始化信息量t i i ( 0 ) = c o n s t ( c o n s t 为常数) ，初始时 刻碟0 户0 。 ( 2 ) 循环次数n c 州c + l 。 ( 3 ) 蚂蚁的禁忌表索引号k = 1 。 ( 4 ) 蚂蚁数目k = k + 1 ； ( 5 ) 蚂蚁个体根据公式( 2 1 ) 和公式( 2 2 ) 计算的概率选择城市j 井前 进。 ( 6 ) 修改禁忌表指针，即选择好之后将蚂蚁移动到新的城市，并把该城市移 动到该蚂蚁个体的禁忌表中。 ( 7 ) 若城市未遍历完，即k m ，则跳转到第( 4 ) 继续执行，否则执行第 ( 8 ) 步。 ( 8 ) 根据改进公