（电路与系统专业论文）蚁群智能优化算法的研究与应用.pdf

，一 ，哆州，寸、。1， 硐 i i i ii i ii lll iii i i j i ii ii y 17 5 9 6 0 0 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：匦燧 日期：丝l ! ：兰：! 至 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：砬整筮日期：型! ! ：墨：! 至 导师签名： 翘公骂： ，若鸟sg o 弘1 删 sd 咖g r w 西e z - 式( 1 忉 其中，吼( o ，1 ) ，g 为( o ，1 ) 间的随机数，s 为按照式的概率所选择的节点。 在“探索 和“利用”之间建立一个平衡点是蚁群算法研究的关键问题之一 换言之，既要使算法的搜索空间尽可能大，以寻找那些可能存在最优解的空间， 又要充分利用蚂蚁群体内当前所拥有的有效信息，使得蚁群算法搜索的侧重点放 在那些可能存在较高适应值的个体所在的区间内，从而以较大的概率收敛到全局 最优解参数。就是用来平衡“探索新路径( 口 q o ) 和“利用 已有信息( 留q o ) 的相对重要程度的参数。 2 ) 信息素的局部更新 每只蚂蚁选择一个城市后，按式( 1 8 ) 更新该路径上的信息素。 7 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 巧o + 1 ) - ( 1 一p k o ) + 肚噶 式( 1 8 ) 。旁当蚂蚍走过城市时 【0 ， o t h e r w i s e 其中，p 表示信息素挥发因子，1 中表示信息素残留因子，p 【0 ，1 】： 弦是 蚂蚁k 从初始城市到当前城市已走过的路径长度1 1 4 1 。 3 ) 信息素的全局更新 经过n 个时刻，所有蚂蚁都完成了一次周游，清空禁忌表，并按式( 1 9 ) 更新 本次周游中最佳路径上的信息素。 一一( 1 一p ) 础+ o ) o ) 2 荟噶o ) x - ( 1 - 9 ) o ) 表示第k 只蚂蚁在本次循环中最优路径o ，d 上留下的信息素值， m d o r i g o 曾给出三种不同的蚁群算法模型1 1 5 l ：蚁周系统( 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 ) ，差别在于全局信息 素更新方式不同。对于求解t s p ，蚁周系统的性能较好，即 删。居当蚂蚍走过边科 【0 ， o t h e r w i s e 式( 1 1 0 ) 其中，q 为常数，厶表示第k 只蚂蚁在本次循环中走过路径的长度。 算法中通常设置一个周游次数计数器n c ，当达到设定值时算法结束，输出 迄今为i 匕发现的最短路径，即为所求t s p 的解。 1 3 3 最大最小蚂蚁系统 最大最小蚂蚁系统( m m a s ) ，是由s t u t z l e 等人为改善a s 的性能而提出的。 m m a s 在a s 的基础上主要做了如下三方面的改进： 1 ) 信息素的初值设为最大值f 一，信息素挥发系数p 取较小的值时算法有 较好的发现新解的能力； 2 ) 在蚂蚁完成一次解构造以后，只有最优解的蚂蚁才能更新信息素，这与 8 北京邮电大学硕士研究生学位论文 蚁群智能优化算法的研究与应用 a c s 的全局信息素更新策略类似； 3 ) 将信息素的值限制在p 曲，f 一】之间，对由于信息素挥发和更新导致的信 息素浓度偏高、偏低的值都强行限制在p 曲，f 】之间，避免算法过早收 敛至局部最优解。 此外，还采用局部搜索和当蚂蚁搜索停滞时重新开始新的搜索等技术以提高 算法效率。m m a s 已经得到了一些成功的应用0 2 - 1 5 l ，是目前解决t s p ，q a p 等 问题最好的蚁群算法之一。 1 3 4 蚁群算法其他改进策略 基于基本蚁群优化算法的改进策略，除上两小节的经典算法外，主要分为以 下三种策略1 3 2 1 ： 1 ) 单一种群的蚁群优化算法。这些算法能提高解的准确性和运行速度，大 多数改进通过平衡探索与开发来改进算法的性能。如采用带信息素排斥的蚁群优 化算法，基于群体的蚁群优化算法，带随机扰动的蚁群优化算法等。 2 1 混合蚁群优化算法。蚁群算法的缺点是由于对信息素的开发，会早熟收 敛于某个解。为了解决这个问题，人们将蚁群优化算法与其他搜索算法进行融合， 如禁忌搜索和定向搜索的融合；遗传算法与蚁群优化的融合策略；基于模糊系统 的融合；基于免疫系统的蚁群优化算法。 3 ) 并行蚁群优化算法。蚁群算法的群体特性使得其适用于高效的并行实现， 从而提高获取解的速度。如种群层次的并行化；蚂蚁层次的并行化；数据层次的 并行化；函数层次的并行化。 本文将在第二、三、四章提出新的蚁群改进算法，并与已发表文献的算法进 行收敛性比较，因此，在本节中将对文献【2 1 】、文献【2 3 】的算法做简要介绍。 文献f 2 1 1 中提出的改进算法是通过蚂蚁个体改变多条路径上的信息素浓度 以提高蚂蚁群体之间的合作效果， 文献【2 3 】中提出了一种求解连续空间优化问题的蚁群算法，它包括两个主要 部分，即全局搜索和局部搜索。蚂蚁个体先进行局部搜索，在自己的邻域中随机 搜索。当蚂蚁完成自己的局部搜索后，将决定是停在原地不动还是转移到别的蚂 蚁个体的邻域中搜索，或是进行进一步的全局随机搜索。其中在每个坐标方向上 进行探测性搜索，求得目标函数的变化规律以确定其搜索方向，进行模式移动。 以上两种改进策略在解的多样性和全局性上、防止早熟停滞上较基本蚁群算 法都有一定程度的提高，但在计算量、计算速度以及自适应性上都存在一定的局 限性，在本文以下的相关章节中，将对此结论做详细讨论与实验仿真验证。 9 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 1 3 5 蚁群算法的应用 蚁群算法的应用研究一直非常活跃，从最初的问题t s p 问题，陆续渗透到 其它领域，如指派问题、调度问题、车辆路由、连续优化、系统辨识、化学工业、 图象处理等。 1 )蚁群算法应用于静态组合优化问题，其典型代表有旅行商问题，二次 分配问题、车间调度问题、车辆路径问题等。 劲在图像处理方面，蚁群算法的离散性和并行性特点对于离散的数字图 像非常适用，可用于图像分割。 3 )数据聚类。聚类分析通常被用于模式识别、颜色量化和图像分类。它 可以帮助用户从海量的数据中辨别数据结构，简化数据的复杂度。在提取这些数 据之后，用户可以理解其内含的信息。使用蚁群算法可以自动搜索任意数据集中 的聚类中心【1 6 1 。 4 )生产调度问题。因为蚁群算法机制可以不断从过去的加工经历中学习， 能自然地适应车间内外部环境的变化，从而实现动态调度，所以，它能适应动态 的工件到达，不确定的加工时间以及机床故障等扰动，比静态确定性算法具有更 好的应用背景【1 7 】 5 )除离散型组合优化问题外，蚁群算法也可用于求解连续空间函数优化 问题，其求解的核心思想是将连续的搜索空间离散化，用一个从起始点出发的运 动矢量集合来描述蚂蚁的移动路径，这样就可用一个离散的结构来表示蚁群的连 续运动区域。 6 )蚁群算法在动态组合优化问题研究中的应用主要集中在通讯网络方 面，网络路由问题的基本特征如信息的分布式特性、动态性、随机性和异步性等 与蚁群算法的特征匹配得很好，能很好地运用于对均衡网络负载量以及提高网络 的利用率上。同时，随着因特网上广泛的分布式多媒体应用对服务质量的需求的 增长，各种服务应用对网络所能提供的q o s 提出不同的要求，将蚁群算法运用 于解决受限路由问题。本文将在第四章提出一种混合蚁群算法讨论求解q o s 路 由问题。 1 4 本文的主要工作 本文以国家自然科学基金项目“异构i p 网络中基于多目标决策理论的资源 优化技术研究”( 编号：6 0 7 7 2 1 1 2 ) 为背景，旨在探索新的优化算法。鉴于蚁群算 法的分布式计算特点及全局优化能力，本文重点研究蚁群算法在优化问题中的应 用，提出了三种改进的蚁群算法，并将其分别应用到离散空间优化问题、连续空 间优化问题以及网络路由问题。分别给出了三种算法的思想、构造以及仿真实验 1 0 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 结果，并验证其取得的良好的效果。 全文分为五章，主要内容如下： 第一章，绪论。深入讨论了蚁群算法的研究背景、数学模型、算法特点、发 展概况；对基本蚁群算法进行了深入分析，并对与下文相关的改进算法作简要介 绍与总结，为以下章节的算法改进做好理论基础。最后对论文的内容和组织进行 了说明。 第二章，基于协同合作的蚁群优化算法。提出一种新的信息素扩散模型，对 基本蚁群算法的信息素更新方式进行改进，详细描述了算法思想及优化步骤，并 通过仿真实验对结果进行分析，并与基本蚁群算法及其他改进算法进行对比，验 证本算法各方面的优越性。 第三章，蚁群优化算法求解连续函数优化问题。提出一种结合粒子群思想的 协同合作蚁群改进算法，将前一章提出的思想成功地运用到连续空间优化中，并 通过实验对一维及多维函数多个实例进行了仿真分析。 第四章，混沌蚁群算法在多约束q o s 路由问题中的应用。本章内容主要针 对蚁群算法在q o s 路由问题中的缺点提出了混合算法的思想，在蚁群算法中巧 妙融合混沌映射因子，同样通过实验验证取得一定进展。 第五章，总结与展望。总结了本文所做的工作，并对下一步工作进行展望。 嚣 ： 王 7 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 第二章基于协同合作的蚁群优化算法实现 2 1 引言 蚁群优化是一种模拟蚂蚁觅食的群集智能搜索算法。蚁群算法固然具有采用 分布式并行计算机制、易于与其他方法结合、具有较强鲁棒性等优点，但搜索时 间长、易陷于局部最优解是其最为突出的缺点【1 6 1 。为避免发生早熟或停滞现象， 很多学者提出了改进算法。文献【1 8 】提出的最大最小蚂蚁系统( m a x m i na n t s y s t e m ，m m a s ) 限定了信息量允许值的上下限，并在算法中采用了轨迹平滑机 制，初始时设定路径信息量最大值，同时将各条路径可能的信息量限制在最大最 小值区间之内，有效地避免了某条路径上的信息素远大于其他路径，控制了早熟 现象的发生。文献 1 9 1 提出了种具有变异特征的蚁群算法，采用逆转变异机制 加快局部搜索；文献【2 0 】研究了一种具有感觉与知觉特征的蚁群算法，模拟蚂蚁 的行为，使之在初始阶段接受自己经验的影响，逐步有条件地接受信息的影响， 同时自适应地修改路径上的信息量，在加速收敛和防止早熟停滞现象之间取得较 好的平衡。这些算法大多数改进通过平衡探索与开发来改进算法的性能，提高了 解的准确性和运行速度。 本章提出了一种基于协同合作的蚁群优化算法，该算法采用新的扩散模型实 现信息素局部更新，采用随机扰动机制实现信息素的全局更新，发挥了蚁群之间 的协同合作能力，使收敛速度更快，全局优化能力更强。实验结果表明，本章提 出的算法在控制参数的敏感性、寻优能力、以及防止早熟或停滞等方面均远远优 一于基本蚁群优化算法。 2 2 基于协同合作的蚁群优化算法 2 2 1 算法的主要思想 由大量蚂蚁组成的蚁群的集体行为本质上表现一种信息的正反馈现象，某一 路径上走过的蚂蚁越多，后面的蚂蚁选择该路径的概率就越大。引言中提到的现 有的蚁群算法模型中，蚂蚁与蚂蚁之间的协作是通过子解上的信息素来完成的， 即假设某一子解上的信息素浓度很高，它会对位于子解的两个城市上的蚂蚁起调 节作用，使蚂蚁选择它的概率较大，但对位于距离这两个城市比较近的其他城市 上的蚂蚁没有起到直接的调节作用f 2 l l 。因此，文献【2 1 1 提出了一种基于信息素扩 散模型的蚁群算法，在加快收敛速度的同时避免陷入搜索停滞。但是文献【2 1 】提 1 3 北京邮电大学硕士研究生学位论文 蚁群智能优化算法的研究与应用 出的扩散模型较复杂，使得寻优效率相对较低，而且无信息素的局部更新，只在 信息素全局更新时以扩散模型方式扩散，极易使蚂蚁越来越聚集于某几种较优的 路径上，而处于停滞状态。本章即提出一种在改善以上算法缺点基础上，增强蚁 群间协同合作的一种寻优搜索蚁群算法。以下章节将从提出的新颖的信息素扩散 模型、局部与全局更新机制来对该算法进行详细研究。 ，二f 、 牢， 、 f 。 、l l ，o； 、， i 2 2 3 基于协同合作的信息素局部更新机制 蚂蚁在爬行过程中每经过一个城市，都要向邻近路径扩散信息素。假设蚂蚁 k 走过两个城市f 和j ，其距离为幽，此时蚂蚁将分别以城市f 和j 为中心向周围 扩散信息素，蚂蚁在城市f 和j 的信息素浓度取为l 。在该圆形区域中，城市z 与f 、j 相连的路径g ，d 和( ，d 都会因信息素扩散而引起浓度的变化，变化量分别 为和f ：，下面推导和f ；的表达式。 设信息素吃- 肚露，为小于1 的参数：厂= d 2 d ，d 为所有城市的平均 距离。结合式( 2 - 1 ) ，可推得路径o ，d 、( | ，d 信息素浓度的变化z ：、f ：分别为 1 4 北京邮电大学硕士研究生学位论文 蚁群智能优化算法的研究与应用 峪i i j 1 1 ( 卜雩卜， 船动 卜o t h e r w i s e 喊。陉1 ( 卜等卜， 蛔， t o ，d t h e r w i s p 在本文提出的算法中，将式( 2 - 2 ) f f 市1 式( 2 3 ) 代k z - - - ( 1 - 9 ) ，采用新的信息素扩散 方式来对信息素进行局部更新。与基本蚁群算法的信息素更新机制相比，信息素 的扩散方式发挥了蚁群之间的协同合作能力，局部更新更加灵活，更加接近真实 情况。蚂蚁每走一步，改变了多条路径上的信息素浓度，加快了收敛速度。 2 2 4 加入随机扰动的信息素全局更新机制 蚂蚁在行进过程中采用了协同合作的信息素局部更新方式，加快了算法的局 部寻优速度，同时也增大了局部收敛的可能性。为了防止陷入局部最小解，应该 使解空间产生某种方式的随机扰动。值得注意的是，文献【2 2 】提出的随机扰动方 法，是指在蚂蚁寻路过程中，结合已有信息与搜索新的路径，采用了引入遗传算 法的方式，与本文提出的扰动机制在方法实现上是不同的，本文采用如下扰动方 式：改变基本蚁群算法的信息素全局更新机制，选取本次循环中最优的a 个解( 对 应a 只蚂蚁走过的闭合路径，本文取a = 0 2 m ) 进行信息素全局更新，从而防止早熟 或停滞。 实验表明，加入随机扰动策略，使得解的收敛速度更快，同时避免了局部收 敛的发生。 2 2 5 改进蚁群优化算法的步骤 综上所述，基于协同合作的蚁群优化算法的具体实现步骤如下： 步骤1 ：初始化参数，读入城市信息，计算城市距离矩阵；将历只蚂蚁随机 分配到刀个城市，将出发城市添加到每只蚂蚁的禁忌表中。 步骤2 ：按概率选择下一个城市：蚂蚁k 按式( 1 1 ) 和式( 1 2 ) ，计算城市的转 移概率，并根据赌轮盘规则选择下一个城市j ，将j f 加入禁忌表。 步骤3 ：信息素局部更新：根据信息素扩散模型，蚂蚁七分别按式( 2 2 ) 和式 ( 2 3 ) 更新相应路径上的信息素。 步骤4 ：蚂蚁k 的禁忌表未满，转至s t e p 2 。 步骤5 ：信息素全局更新：当m 只蚂蚁均完成一次周游以后，计算各蚂蚁走 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 过路径的长度，更新迄今为止最优解，并选取本次循环中最优的a 个解，按式( 1 - 9 ) 进行信息素全局更新。 步骤6 ：达到终止条件，输出最优解，比基本蚁群算法更加有效地收敛最小。 2 3 实验仿真结果与分析 2 3 1 算法收敛性验证 为了验证本文提出的蚁群优化算法的性能，选用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 e o m o p t s o f t w a r e t s p l i b 9 5 t s p ) 中的实例 o l i v e 3 0 进行仿真实验，并与基本蚁群算法、文献【2 1 】算法进行比较。实验独立 进行3 0 次，统计结果如表2 - 1 所示，取其中的1 6 组数据，优化结果如表2 2 所 示。 参数设置：m = 3 0 ，a = 6 ，n c , , 。= 1 0 0 ，a = l ，夕= 2 ，q o = o 9 8 ，p - - - o 6 ，= 0 4 ， q = l o o 表2 - 1 独立实验3 0 次的统计结果 指标本文算法基本蚁群算法 文献【2 1 】算法 最好解 4 1 54 1 84 1 5 最差解4 2 34 5 94 2 8 平均值4 1 7 5 3 3 34 2 7 4 3 5 44 1 8 6 5 5 1 达到最好解的次数 7 36 由表2 1 和表2 2 的数据可见：基本蚁群算法得到的最差解较多，表明基本 蚁群算法极易收敛到局部最小解。文献【2 1 】算法可得到较优的解，且相对稳定。 本文算法的实验结果与文献【2 1 】基本相当，均能有效改善基本蚁群算法的全局优 化能力。与文献【2 1 】算法相比，本文的算法规避了较为冗繁的计算模型，提高了 计算效率，具有较快的收敛速度。图2 3 为本文算法求解o l i v e 3 0 得到优化解为 4 1 5 时的闭合路径。 1 6 警 参 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 表2 - 2 两种算法实验结果比较 实验编号 12345678 本文算法 4 1 64 1 54 1 54 2 04 1 94 1 94 1 64 1 5 基本蚁群算法 4 2 34 2 24 3 24 2 54 1 84 3 24 4 44 3 9 文献1 2 1 1 算法 4 2 04 1 64 2 24 2 14 1 84 2 24 1 74 1 5 实验编号 91 01 11 21 31 41 51 6 本文算法 4 2 24 1 64 1 54 1 94 1 84 1 54 2 34 1 8 a c s4 2 24 3 34 2 24 1 84 2 64 2 54 2 44 2 3 文献 2 1 1 算法 4 1 54 1 54 1 54 2 0 4 2 24 2 2 4 2 2 4 1 9 选代次数 图2 - 2 本文算法与文献【2 1 】算法最优解进化比较 图2 - 3o l i v e 3 0 的路径图 2 3 2 算法鲁棒性 文献 1 7 1 指出，基本蚁群优化算法的性能受参数a 影响很大，算法的鲁棒性 1 7 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 较差。为考察本文算法的鲁棒性，令a 取值0 5 至4 ，分别用本文算法和基本蚁 群算法、文献【2 1 】算法对o l i v e 3 0 求解3 0 次并取平均值，结果如表2 - 3 所示。可 见，基本蚁群算法的优化解受a 值影响较大，且在3 0 次中有明显收敛于局部的 最小解的情况。 表2 - 3 不同a 值下的计算结果 a 值本文算法基本蚁群算法 文献 2 1 1 算法 o 54 1 5 2 24 2 6 4 1 4 1 6 5 1 14 1 6 6 04 3 0 0 34 1 5 2 3 24 1 8 4 14 3 3 6 04 1 9 6 7 34 1 8 0 14 4 0 4 24 1 8 5 5 44 1 8 9 64 3 8 2 3 4 1 8 7 8 2 3 3 算法的有效性 为了进一步验证本章算法有效性，选取不同的t s p 实例进行仿真验证。如 图2 4 ，2 - 5 ，2 - 6 ，2 - 7 所示是分别对u l y s s e s 2 2 ，b a y s 2 9 ，a t t 4 8 和s t 7 0 进行寻路 所得最优解。使用本章算法分别对每个路径进行了5 0 次独立实验，达优率分别 为1 0 0 ，1 0 0 ，9 9 7 1 ，9 8 9 7 ，可见，本算法在小规模城市寻优上体现了较 好的结果。 图2 - 4u l y s s e s 2 2 的路径图 图2 - 5b a y s 2 9 的路径图 1 8 ?， 北京邮电大学硕士研究生学位论文 蚁群智能优化算法的研究与应用 图2 - 6a r t 4 8 的路径图 2 4 本章小结 图”s t 7 0 的路径图 本章在基本蚁群算法的基础上，提出了一种基于协同合作的蚁群优化算法， 改进了基本蚁群算法的信息素更新机制，提高了蚂蚁在选路时的协同合作能力。 仿真实验表明，该算法性能远高于基本蚁群算法，能快速发现全局优化解，并具 有较快的收敛速度、较高的稳定性和较强的鲁棒性。 1 9 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 第三章协同合作蚁群优化算法求解连续函数优化问题 3 1 引言 函数优化问题是在工程、管理、经济、控制、决策中普遍存在的一类优化问 题，其优化目标函数可能包含多个在一定范围内的连续变量，蚁群算法在求解离 散优化问题( 即组合优化问题) 中已经得到越来越多的应用，但是在求解连续空间 优化问题方面的研究相对较少，主要有：高尚等提出了一种基于网格划分策略的 连续蚁群算法【矧；w a n gl 等将离散域蚁群算法中的“信息量留存刀过程拓展为 连续域中的“信息量分布函数并定义了用于连续函数寻优问题的改进蚁群算法 【刎；d 哟j 等提出了一种基于密集非递阶的连续交互式蚁群算法【矧； p o u r t a k d o u s tsh 等提出了一种仅依赖信息素的连续域蚁群算、法l 冽；陈烨等提出 的用于连续优化的蚁群算法，在算法中引入遗传机铝u t 2 n ；张勇德等提出了一种用 于求解带有约束条件的多目标函数优化问题的连续域蚁群算法，将信息素交流和 基于全局最优经验指导这两种寻优级方式相结合，保证了解的分布性能，提高了 算法的收敛速度【2 8 1 ；w e ny 等提出了一种结合遗传优化的动态窗口蚁群算法等 1 3 2 1 o 传统的优化手段对目标函数要求苛刻，如需要满足可导或者可微等等，导致 有些函数难以优化，容易陷入局部解而难以得到全局最优解，收敛速度较慢。近 年来，人们从仿生学的机理中得到启发，提出了许多用于求解函数优化问题的新 方法，如模拟退火算法、遗传算法、粒子群等等。然而对于函数优化问题的复杂 性，每种算法都表现出各自的优势和缺科3 l j 。同时算法理论研究的落后也导致了 单一算法性能改进程度的局限性，而基于自然机理来提出一种新的优化思想是一 件相对困难的事。指导性搜索算法具有较强的通用性，无需利用问题的特殊信息， 这也造成了对已知问题信息的浪费。尽管启发式算法对问题的依赖性较强，但对 特殊问题却能利用问题信息较快地构造解，其时间性能较为理想。所以，如何合 理结合两者优点来构造新算法，对于实时性和优化性同样重要的工程领域，具有 较强的吸引力。基于这种现状，算法混合的思想【3 3 】已经发展成为提高算法优化性 能的一个重要且有效的途径，其出发点就是使各种单一算法相互取长补短，产生 更好的优化效率。 蚁群算法在求解连续域优化问题上的主要缺点是初期信息素匮乏，求解速度 较慢。粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 的优势在于概念简单，容易 实现并且没有许多参数需要调整。p s o 可用于求解大量非线性、不可微和多峰值 的复杂函数优化问题。本章内容将在上一章提出的基于协同合作的蚁群优化算法 2 1 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 中加入粒子群算法的特点，使得蚂蚁的粒子性和初始的随机解很好地保证了全局 性，比较好的避免蚁群算法容易陷入局部解的缺点，应用于求解连续域空间函数 优化得到了很好的效果。本章下节首先对粒子群理论做简要介绍。 3 2 粒子群理论 3 2 1 基本粒子群概述 粒子群优化算法是基于群体智能的一种进化计算，由e b e r h a r t 博士和 k e n n e d y 博士基于一种社会心理学模型的社会影响和社会学习而提出的脚j 。粒子 群优化算法也是基于人口的最优化方法，该方法是随机产生一组数据，然后执行 最佳搜索路径，粒子群优化算法在运算过程通过其中最好的粒子找到最佳的解决 方案【3 4 1 。粒子群优化算法有较好的后台计算智能，而且运算更加简单，依照它的 优势，粒子群优化算法不仅适用于科学研究，而且还适用于工程应用，目前粒子 群优化算法在进化计算领域中已经吸引了众多人的注意，近几年来，有很多关于 粒子群优化算法的研究成果，粒子群优化算法已经被广泛地应用于最优化、人工 神经网络、仿生识别、模糊控制和其它一些领域。 粒子群优化算法源于对鸟群捕食的行为研究，研究者发现鸟群在飞行过程中 经常会突然改变方向，或散开或聚集，其行为不可预测，但其整体总保持一致性， 个体与个体之间也保持着最适宜的距离，通过对类似生物群体行为的研究，发现 群体中存在着一种信息共享机制，它为群体的进化提供了一种优势，这就是p s o 算法形成的基础。p s o 就是模拟鸟群的捕食行为，设想这样一个场景：一群鸟 在随机搜索食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里， 但是他们知道当前的位置离食物还有多远，那么找到食物的最优策略是什么呢? 最简单有效的就是搜寻目前离食物最近的鸟的周围区域。p s o 从这种模型中得 到启示并用于解决优化问题。p s o 中，每个优化问题的解都是搜索空间中的一 只鸟。我们称之为“粒子 。所有的粒子都有一个由被优化的函数决定的适应值 ( f i t n e s sv a l u e ) ，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们 就追随当前的最优粒子在解空间中搜索。p s o 初始化为一群随机粒子( 随机解) ， 然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值来更新 自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值p b e s t 。另一 个极值是整个种群目前找到的最优解。这个极值是全局极值降 g b e s t 。 孽 尊 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 3 2 2 算法原理与流程【3 5 1 一个由胁个粒子( p a r t i c l e ) 组成的群体( s w a r m ) 在d 维搜索空间中以一定的速 度飞行，每个粒子在搜索时，考虑到了自己搜索到的历史最好点和群体内( 或邻 域内) 其他粒子的历史最好点，在此基础上进行位置( 状态，也就是解) 的变化。 第f 个粒子的位置表示为： 毛一 1 ，鼍2 ，毛d ) 第f 个粒子的速度表示为： u 一“，u 2 ，) 第f 粒子经历过的历史最好点表示为： p i 一慨l ，只2 ，) 群体内( 或邻域内) 所有粒子所经过的最好点表示为： p s 一 g l ，以2 ，p g d ) 粒子的位置和速度根据如下方程进行变化： 瞄1 一屹+ c ( 比一吒) + c ：r 2 p 二一屹) 带1 呓1 + 瞄1 式( 3 1 ) 式( 3 - 2 ) 这里，c 1 和c ，称为学习因子，为正常数。学习因子使粒子具有自我总结和向 群体中优秀个体学习的能力，从而向自己的历史最优点以及群体内或邻域内的历 史最优点靠近。q n c ：通常等于2 。r l , r 2 e 0 ，1 是在【o ，1 n i n 内均匀分布的伪随 机数。 当把群体内所有粒子都作为邻域成员时，得到粒子群优化算法的全局版本； 当群体内部分成员组成邻域时得到粒子群优化算法的局部版本。局部版本中，一 般有两种方式组成邻域，一种是索引号相临的粒子组成邻域，另一种是位置相临 的粒子组成邻域。粒子群优化算法的邻域定义策略称为粒子群的拓扑结构。 基本粒子群算法的流程如下： ( 1 ) 在初始化范围内，对粒子群中各粒子进行随机初始化，包括随机位置和 随机速度。 ( 2 ) 计算每个粒子的适应值。 ( 3 ) 对于每个粒子，将其适应值与所经历过的最好位置的适应值进行比较， 如果更好，则将其作为粒子的个体历史最优值，用当前位置更新个体历史最好位 置。 h ) 对每个粒子，将其历史最优适应值与群体内或邻域内所经历的最好位置 的适应值进行比较，若更好，则将其作为当前的全局最好位置。 ( 5 ) 根据式( 3 1 ) 和( 3 2 ) 对粒子的速度和位置进行更新。 北京邮电大学硕士研究生学位论文 蚁群智能优化算法的研究与应用 ( 6 ) 若未达到终止条件，则转步骤( 2 ) 。一般将终止条件设定为一个足够好的 适应值或达到一个预设的最大迭代代数。 3 3 蚁群一粒子群混合优化算法解函数优化问题 3 3 1 解空间的划分 由于蚁群算法最初是针对离散优化问题提出的，其中表示解的变量值被约束 为固定的一组离散值，其中使用到的信息素分布就是以离散的方式存储的，为了 用蚁群算法来解决连续优化问题，主要问题在于选取一种合适的方式将连续空间 问题映射为图搜索问题，大致有以下三种途径【2 7 】：一是仍然将信息素离散分布到 各条路径上，因此就将解空间划分为几个离散的区间，并用区间中的一个特定的 解来表示该区间的优良程度，选出较好区间后，对每个区间再使用优化算法来优 化。另一种途径是，蚂蚁直接在连续的解空间上取值，因此就必须使用一定的函 数来表示连续的解空间上信息素的分布。还有一种是文献 2 3 q b 的划分方法，将 自变量划分分量，根据每个分量精确到的位数构造层次“城市”，解码时，对各 分量对应的层分别解码。 本文采用类似第一种方法的划分方式，考虑如下问题： m i n ，“，x 2 ，) 使得a f + q 2 x 2 + + 口妇毛- b , ， i = l ，2 ，r 。这里厂为任一非线性函数，约 束条件构成砌上的一个凸包。可以使用不等式变换的方法【3 6 】求得包含这个凸包 的最小的n 维立方体， 设该立方体为而。s 五s ( i = 1 ，2 ，n ) ，将变量毛分成 n 等份。 设系统中有m 只蚂蚁，将解的以个分量看成厅个顶点，第f 个顶点代表第 f 个分量，在第i 个顶点到第i + 1 个顶点之间有n 条路径，代表第f 个分量的取 值可能在n 个不同的子区间【3 7 1 。这就将连续问题转化成类似离散问题。 3 3 2 用于函数优化的蚁群算法模型 通过将函数优化转化为有向图，求解优化问题的蚁群算法中的信息素表示有 所变化，值不再是路径上的，而是每个节点上的。 采用上一章提出的基于协同合作的蚁群改进算法来进行搜索，主要包括解空 间的划分和信息素强度更新规则。 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 图3 - 1 改进算法流程图 3 3 3 改进算法步骤 步骤1 ：估计出各变量的取值范围； 而1s 而墨黾( i - 1 ，2 ”n ) 式( 3 3 ) 步骤2 ：对各变量n 等份； 红- 学( i = 1 ，玑n ) 式( 3 - 4 ) 步骤3 ：初始化给信息素矩阵赋一个相同的常数值；将所只蚂蚁随机地分 配到第一个分量的个子区间； 卤 北京邮电大学硕士研究生学位论文 蚁群智能优化算法的研究与应用 步骤4 ：设置循环计数器； 步骤5 ：每一个蚂蚁根据吼和比例选择规则确定第f 个分量在第j 个子区间； 步骤6 ：局部更新第j 个子区间的信息素； 步骤7 ：全局搜索，并对信息素强度进行更新； 步骤8 ：用粒子群算法对解进行修正，通过实验可知，蚂蚁在具有粒子性质 的情况下求的的最优路径长度比纯蚁群算法求出来的路径长度小很多。具体做法 是在初始路径时，选择m 个初始解单独保存。 3 4 实验仿真与分析 为了验证基于协同合作的蚁群一粒子群算法在函数优化上的有效性，求解了 多个连续函数优化问题，本章节分别选取一维和多维函数进行算法仿真。 算法参数设置：对于连续空间优化问题，蚂蚁的个数适当取大一些，搜索的 多样性使得搜索空间足够大，随着循环次数增加，搜索半径缩小，蚂蚁趋向于在 全局最优解附近进行越来越细密的搜索，最终收敛到全局最优解。因此设置以下 参数来进行仿真：n = 1 2 0 ，蚂蚁个体数量1 0 0 ，q = 1 0 0 ，a = l ，f l = 2 ，q o = o 9 8 ，p = 0 6 ， z = 0 4 。 分别对各个函数进行5 0 次仿真实验，分析其达优率。 3 4 1 一维函数实例的实验结果 5 函数1 ：e i c o s ( + 1 ) 防+ f 】 - 1 0 ，1 0 面 图3 2 为函数值变化情况，可得x = 6 2 8 2 7f b e s t = 7 0 0 0 0 。达优率：9 8 。 图3 - 2 函数变化规律 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 函数2 ：e 一( 1 - x ) x 2s i n ( 2 0 0 a x ) l o ，1 极大最值0 1 4 8 1最小值0 6 5 7 5达优率9 8 。 文献【2 3 】对此函数的求解达优率也较高，因此将文献【2 3 】与本章算法的收敛 过程进行比较得到如图3 3 所示结果，由此可知在具有相近达优率的情况下，本 章算法具有较强的收敛性。 图3 - 3 本章算法与文献【2 3 】算法收敛性比较 3 4 2 多维函数实例的实验结果 55 函数3 ：b i c o s ( + 1 ) + f 】 c o s ( + o x 2 + f 】 - - 1 0 ，1 0 ， 石= i面 仿真可得该函数有1 8 个极小值点，极小值为1 8 6 7 3 ，如图3 4 。 1 0 r 1 瑚 1 0 图3 4 函数变化规律 1 0 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 黼一o s + 高翳一一叫 函数5 - e 一- 0 8 ( 砰+ x 2 2 + 1 ) + o 2 ( x 2 + 缱+ 1 )毛卜3 3 】，x 2 e - 5 ，5 】 表3 - 1 统计函数4 ，5 结果 指标算法函数4函数5 基本蚁群算法 1 0 1 0 0 10 8 0 0 0 6 最值 本章算法 0 9 9 9 9 10 8 0 0 2 1 基本蚁群算法 0 0 0 8 1 ，0 0 1 0 1 ( - 1 0 0 0 0 ，0 0 0 6 ) 最值点 本章算法 0 0 0 7 8 ，0 0 0 5 3 ( 1 0 0 0 ，0 o o 0 0 1 ) ( - 1 0 0 0 ，0 o o o o ) 基本蚁群算法 8 8 7 6 5 1 8 4 达优率 本章算法 9 7 6 4 4 6 1 函数4 ，5 均为多峰函数，函数5 的最值点为( 1 ，0 ) 、( - 1 ，o ) ，函数4 的最值为 1 ，由表3 - 1 可以看出本章算法可以得到略好的优化效果。 3 4 3 结论 本节选用了五个函数来对蚁群粒子群优化算法进行验证，分别从一维和多维 函数优化两个角度，函数优化规律、优化实验达优率、与文献算法收敛性比较三 个方面进行了全面的仿真分析，验证了本章提出的基于蚁群粒子群的优化算法在 解决连续域问题上是有效的，并能获得较好的优化效果。 3 5 本章小结 本章首先介绍了蚁群算法在连续域优化问题上的研究现状以及局限性，提出 了一种嵌入粒子群特点的蚁群算法的思想；其次对粒子群算法的基本理论做了简 要总结叙述，旨在描述其适用于蚁群算法的粒子性特点；再次将第二章成功运用 于离散空间的基本协同合作的蚁群优化算法与粒子群算法相结合，提出新的解决 连续域优化问题的算法，并给出算法流程步骤；最后通过一维与多维函数示例进 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 行了仿真实验，从函数优化规律、优化实验达优率、与文献算法收敛性比较三个 方面说明了新算法的可行性。 北京邮电大学硕士研究生学位论文 蚁群智能优化算法的研究与应用 第四章混沌蚁群算法在多约束q o s 路由问题中的应用 4 1 引言 随着宽带技术的不断发展，f r p ，哪，s m t p 等传统的数据业务已经逐渐 无法满足人们对信息的需求，而视频点播，远程教学，新闻发布，网络电视等越 来越活跃于市场，成为各大运营商争相发展的新型业务。用户的数据要从一个终 端发送到另一个终端，首先要确定传输路由，不同的通信方式，其确定路由的方 式也不同。组播是一源节点向多个目的节点发送信息( 但不是所有节点) 的通信方 式，涉及组播技术的应用很多，如多媒体会议、远程教育、数据分发等【3 8 1 。组播 通信是以组播树形式实现组播通信。组播树是覆盖所有组播组成员的一棵生成 树，组播树有以下两个优点：信息以并行的方式沿着树枝发送到不同的组成员， 降低了信息传递的时延；网络中需要传送的复制信息最少，而且信息的复制只在 树权处进行，这样能够节省网络带宽资源，提高每次组播通信时的资源利用率， 并能减少拥塞，降低网络负载。 为了保证组播应用的q o s ，网络必须实施资源预约和资源控制。组播路由可 以看作是资源预约的第一步，即采用q o s 组播路由算法首先找到满足应用资源 要求的路由，而后实施资源预约过程。预约请求的成功与否在一定程度上取决于 路由算法能否找到合适的路径【3 5 1 。因此，组播路由算法是q o s 组播的核心部分， 对实现网络组播提供保证质量的服务起到了非常关键的作用，同时组播路由算法 也是平衡网络负载和充分利用网络资源的重要保证。 i e t f 已经提出了多种服务模型和机制来满足各种q o s 组播的需求，q o s 组 播路由是网络分布式多媒体实时信息传输的关键之一，在这方面已有不少的研究 成果。实时应用往往会对延时，延时抖动，带宽，丢失率，业务代价等多个参数 同时提出性能要求。这些参数相互独立时，选择满足多个参数限制的最优组播路 由就成为n p 完全问题【矧。 目前，在q o s 组播路由的研究领域中，研究人员已经提出了一些用于解决 多约束q o s 组播路由问题的算法。这些算法大体上可分为启发式算法、近似算 法和基于某种调度策略的多受限组播路由算法这三类。近年来，国内外许多学者 利用神经网络、蚁群算法、遗传算法等启发式智能算法来解决约束q o s 组播路 由问题，并且取得了一定的成果。各算法都有各自的优缺点，其中蚁群优化算法 以其健壮性、并行性、灵活性、搜寻过程不需要人工干预以及求解精度高的特点， 得到了广泛应用。 本章首先从两个方面介绍q o s 多播路由问题的问题描述，其次简要介绍两 3 1 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 类q o s 多播路由的两种算法思路，最后提出一种基于混沌蚁群的算法思路来求 解q o s 多播路由问题，并通过实验仿真比较提出新算法的优越性。 4 2q o s 多播路由问题描述 4 2 10 0 s 路由的网络模型 网络由交换节点、链路和主机组成，在研究当中往往将其抽象为有权图g ( v ， d ，节点集v 可以表示路由器、交换机、集线器等网络节点设备【4 1 1 ，在研究路 由问题时，y 中的元素为具有路由能力的交换节点；e 则为连接y 中两个节点的 链路及具有的k 个属性( q ，哆o o 魄) ，这些属性可以是可用带宽、时延、队列长 度、成本等参数。对于对称网络有勺( q ，：，魄) = p 乒( q ，( 0 2 ，( - o k ) ，而不对称 网络中通常e f t e 。，现实中的网络往往是不对称的，但在研究中为了简便起见， 常常使用对称网络模型以减少弧的数量。 业务q o s 可以用多种度量指标描述，如带宽、时延、抖动以及网络代价和 包丢失率等，这些q o s 度量用来刻画业务的各种需求特性，同时，也是对相应 网络状态的描述。 若按网络元素来划分，则可进一步分为节点的q o s 度量和链路的q o s 度量。 设r 表示实数集，r + 表示正实数集，表示r 非负实数集，用n y 表示网络节点， 用e e e 表示链路，则各q o s 度量【4 2 】的数学描述为： ( 1 ) 链路的q o s 度量 延迟d e l a y ( e ) ：e 叫r +延迟抖动d e l a y j i t t e r ( e ) ：e 叫尺 代价c o s t ( e ) ：e 一尺+ 带宽b a n d w i d t h ( e ) ：e 叫r + 包丢失率p a c k e t l o s s ( e ) ：e 叫尺+ ( 2 ) 节点的q o s 度量 延迟如伽o ) ：y 只+ 延迟抖动如l a y j i t t e r ( n ) ：y 一只 代价c o s t ( n ) ：y 一只+带宽b a n d w i d t h ( n ) ：y 一尺+ 包丢失率p a c k e t l o s s ( e ) ：e 一尺+ 对于路径p = b , c ，z g ) ，用d 似剀表示对应链路( 口，6 ) 的度量，则q o s 度量可以按性质分为以下三类【4 3 】： ( 1 ) 凹性度量。 北京邮电大学硕士研究生学位论文蚁群智能优化算法的研究与应用 如果d ( a , g ) = m i n d ( 口力) p p ，c ) ，p ( 船) ，