基于蚁群和人工鱼群算法融合的QoS路由算法.pdf

第 2 0 9 0 9 期 年 7月 计 算 机 技 术 与 发 展 cob 任， uter techn0l 0gy and devel opment v0 1 1 9 no 7 j u 1 2 0 0 9 基于蚁群和人工鱼群算法融合的 q o s路由算法 古明家， 宣士斌， 廉侃超， 李永胜 ( 广西民族大学 数学与计算机科学学院， 广西 南宁 5 3 0 0 0 6 ) 摘要： 针对多约束 q o s单播路由问题， 提出了一种改进蚁群算法和人工鱼群算法融合的 q o s路由算法。采用混合蚂蚁 行为使初始路径多样化， 根据 q o s 约束条件对蚂蚁可选路径集进行优化 ， 将人工鱼群算法加入到蚁群算法的每一次迭代 过程中， 利用人工鱼群算法全局快速收敛的优点 ， 来加快蚁群算法的收敛速度和人工鱼群算法的觅食行为， 帮助提高了蚁 群算法跳出局部最优的能力。仿真实验结果验证了该算法的可行性和有效性。 关键词： 多约束 ； 单播路由； 蚁群算法； 人工鱼群算法 中图分类号： 1 p 3 0 1 6 文献标识码： a 文章编号： 1 6 7 3 6 2 9 x ( 2 0 0 9 ) 0 7 0 1 4 5 一o 4 qo s r o u t i n g a l g o r i t h m b a s e d o n c o mb i n a t i o n o f mo d i f i e d an t co l o ny al g o r i t hm a nd ar t i f i c i a l fi s h s wa r m al g o r i t h m gu mi n g - j i a ， xu a n s h i b i n ， l i an k a n c h a o ， l i y o n g - s h e n g ( c o l l e g e o f ma t h e ma t i c s a n d c c n p u t e r s c i e n c e ， g u a n g x i un i v e r s i t y f o r na t i o n a l i t i e s ， n a n n i n g 5 3 0 0 0 6 ， c h i n a ) a b s t r a c t ： f o r t h e mu l t i p le qo s c o n s t r a in e d u n i e a s t mu t in g p r o b l e m， a n e w q o s mu t i n g o n t h m c o mb i n i n g mo d i f i e d a n t c o lo n y g o r i t h m( ma c a) wi t h a r t i f i c i a l f is h s -v a t n t h m( a a )w a s p r o p 0 s 。 d t h e p r o p o s e d a l g o ri t h m a d o p t e d h y b r i d a n t b e h a v i o r t o p r o d u c e d i v e r s e o r i g i n a l p a t h s ， o p t imi z a t in g o f c h o i c e n o b l es set a c c o r d i n g t o mu l t i p le qo s c o n s t r a i n ed 。 a d d s a f s a t o ma c a s e v e r y g e n e r a t i o n ， ma k i ng u s e o f afs a s a d v a n t a g e o f who l e q u i c k c o n v e r g e n c e aca s c o n v e r g e n c e s p e d wa s q u i c k e n e d， a n d afs a s p r e y in g behav i o r i mp r o v ed t h e a b i li t yo fmacat oa v o i d b e i ng p r e ma t u r e th ef e a s i b i l i t yand e f f e c t i v e n e s so fthe a lg o r i t hm a r ev alid a t ed b y s e rie so f s imu la t ed r esu l t s ke yw o r d s ： mult i p l e c o n s t r a in e d； u n i c a s t r o u t i n g；ant c o l o n y a l g o rit h m；a r t i f i c ia l fis h s ta lt n a l g o rit hm o 引 言 随着 i n t e me t 和多媒体技术的发展， 网络多媒体 业务迅速增长， 对网络服务质量( q o s ) 提出了更高的 要求 ， 如何充分利用网络资源来满足 日益多样化的 qo s 要求已成为人们关注和研究的热点。q o s网络路 由的目的就是在分布的网络中寻找一条最佳路径， 从 源节点 出发 。 历经所 有 目的节 点 ， 同时 满足所 有 q o s 约束以保证网络服务质量， 并且费用最小。目前 ， q o s 路由的研究主要分为： 单播路由( u n i c a s t r o u t i n g ) 、 组 播路由( mu l t i c a s t r o u t i ng) 和选播路 由( a n y c a s t r o u t i n g ) 。wa n g z和 c r o w c r o ： , j已经证 明具有 两个 及 以 上约束条件 的 o o s路 由问题是 一个 n p一完全问 题。近几年来 ， 国内外许多研究人员相继提出了许 收稿 日期 ： 2 0 0 8 1 1 1 3 ； 修回 日期 ： 2 0 0 9 0 22 o 基金项目： 国家民委科研项 目( 0 7 gx 0 4 ) 作者简介： 古明家( 1 9 8 0 一) ， 男 ， 广西平南人 ， 硕士研究生 ， 研究方 向 为智能计算及其应用； 宣士斌， 教授， 研究方向为图像处理与智能计 算 。 多 q o s 路由算法， 如： 蚁群算法 2 - 4 】 、 遗传算法 和模 拟退火算法【 6 j 等， 并取得了一定的成果。 蚁群算法是 m d o r i g o ， v ma n i e z z o和 a c o l o mi 等 人于 1 9 9 1 年提出的一种优化方法l 7 】 ， 它以蚂蚁觅食行 为为基础， 用蚂蚁的行走路线表示待求解问题的可行 解， 不依赖于具体问题的数学描述， 具有很强的全局优 化能力， 已广泛应用于组合优化 中的 n p一完全问题。 但蚁群算法本身也存在一些缺点， 如收敛速度慢、 易陷 入局部最优。许多学者提出了一些改进策略， 并应用 于 q o s路由优化上， 取得了一定的成果 2 - 4 j 。 人工鱼群算法是李晓磊等人于 2 0 0 2年提出的一 种优化方法 8 _ ， 它对初值和参数选择不敏感、 简单、 易 实现， 具有良好的全局优化能力 ， 已成功地运用于组合 优化 问题 引 。 根据多约束 q o s 单播路由问题的特性， 提出了一 种改进蚁群算法和人工鱼群算法融合的 q o s单播路 由算法。该算法采用混合蚂蚁行为使初始路径差异 化， 根据 q o s约束条件以及当前的最优路径对可选节 - 1 4 6 计算机技术与发展 第 1 9卷 点集进行优化 ， 将人工 鱼群算 法加入 到蚁群算 法的每 一 次迭代过程中 ， 利用 人工 鱼群算法 全局快速 收敛 的 优点， 来加快蚁群算法的收敛速度， 并且人工鱼群算法 的觅食行为， 帮助提高了蚁群算法跳出局部最优的能 力 ， 从而提高了整个算法的收敛速度， 减少了陷入局部 极值的可能性， 增强了寻优能力。 ( 2 ) 带宽约束 ： b a n d wi d t h ( p ( ， t ) ) b ( 3 ) 费用约 束 ： 在 所有 满足 ( 1 ) 、 ( 2 )条件 的路 径 中 ， c o s t ( p ( s ， t ) ) 最小。 其中， d， b分别是路径p ( 5 ， t ) 规定的延时、 带宽 约束， 即 o o s约束条件。 2 改进蚁群算法与 人工鱼群算法融 合的 1 oo s单播路 由ninon o o s路 由算法 文中只讨论包含带宽、 延时和费用三个 q o s约束 该算法的基本思想是在改进蚁群算法的基础上 ， 条件的网络模型， 如图 1 所示。 将人工鱼群算法加入到蚁群算法的每一次迭代过程 图 1 2 0个节点网络拓扑结构 图 用一个无 向赋权 图 g表示 网 络， 其中 v= 1 ， 、 厂 2 ， ， v _n 表示网络节 点集 ， n 表示 网络节点 数 ， e ： e l ， e 2 ， ， e m 表示双向链路集， m 表示网络链路数， 每条链路 e上包含三个属性， 用三元组 表示 ( b a n d w i d t h ， d e l a y ， c o s t ) ， 分 别 表示 链 路 的带宽、 延时和费用。 对于任一链路 e e， 定义 三种度量 ， 延时函数 d e l a y ( p ) ： e r ， 费 用 函 数 c o s t ( p ) ： e r ，带 宽 函 数 b a n d w i d t h ( p ) ： e一 尺 。 对 于给 定 的源 点 s v， 目的节点 v一 s ， s 和t 组成的 路径 p ( s ， ) 存在下列关系： 1 ) d e la y ( 户 ( s ， t ) ) = d e la y ( p ) r 户 ( j f ) 2 ) c o s t ( p ( 5 ， t ) )= c o s t ( p ) e c - ( j ， f ) 3 ) b a n d w i d t h ( p ( s ， t ) )= mi n b a n d w i d t h ( p ) ， p p ( 5 ， t ) q o s单播路 由就是要寻找一条从源节 点 s 到目的节点t v一 s 的一条路径 p ( s ， t ) ， 满足： ( 1 ) 延时约束： d e l a y ( p ( ， t ) ) d 中， 利用 人 工鱼 群算法 全 局快 速 收敛 的优 点 ， 来加快蚁群算法的收敛速度。算法流程 图如图 2所示。 文 中算法主要 分为三个部分 ： ( 1 ) 预处 理部 分。根 据 s约束 条件 把不符合约束的链路删除， 得到新的网络拓 扑图( 假设经过预处理后的网络拓扑图是连 通的) 。 ( 2 ) 改进蚁群算法部分。对基本蚁群算 法作了如下改进 ： ( a ) 使用节点计数器策略： 增加一个节 点使用计数器 n o & b u m( 1 ， n) ， 计数器 中 每个节点的使用次数初始化值都为 0 ， 即 n o d e n n ( 1 ， )=0 ， v n， 蚂蚁爬行时 图 2 改进蚁群算法和人工鱼群算 法 融合的算法流程 图 第 7期 占明家等： 基于蚁群和人工鱼群算法融合的 q o s路由算法 l 4 7 每经过一个节点 一次 ， 该节点 的计数值就增 加 1 ， 即 no d e s u m( 1 ， )= no d e s u m( 1 ， )+1 。 ( b ) 可选节点集 优化 策略 ： 在蚂蚁 由当前节 点选 择下一节点前， 先对下一初始可选节点集进行判断和 筛选， 把那些不符合 q 约束条件以及比当前最优路 径差的初始可选节点从 可选节点集 中删 除， 得到优化 后可选节点集。 这样做的目的是避免太多无效搜索， 使 当前最优路 径对后面蚂蚁产生除信息素更新外的又一 个搜索方向指示 信息 ， 使得后 面搜索方向更明确 ， 大大 节约时间和提高搜索速度。 如： 有 1 个蚂蚁爬行到当前路径为p a t h ， 当前搜索 到的最优路径为 p a t h t ， 由当前 节点选 择下一节点 的 初始节点集 为 a l lo w e d= ( 、 ， l ， ， 3 ， 、 ， 4 ) ， 根据上 面 的策略， 如果 p a t h +v i ( i =1 ， 2 ， 3 ， 4 ) 不符合 r m x ( 3 ) 人工鱼群算法部分。 在这里每次迭代只执行 觅食和追尾行 为。 ( a ) 邻域的定义。 文献 9 给出了人工鱼群算法在 解决组合优化 问题时邻域的定义 ， 这里采用它的方法 ， 即 ： 定义 l ： 对于组合优化问题( d， f， 厂 ) ， 决策变量 x1 和 x 2 之间的距离表示如下 ： d i s t a n c e ( x1 ， x2 )=i x1 一x 2 +i x2 一xl i ( 3 ) 表示不 同时属 于 x1 和 x2 的元素的个数 。 定义 2 e 】 ： 对于组合优化问题( d， f， f ) ， n( x， 忌 )= x i d i s t anc e ( x， x ) 点 ， x d ( 4 ) 称为 x的k一距离邻域， x n( x， 称为x的一个 邻居 。 根据定义 1 和 2 ， 假设有两 个路径 为 p a t h l= ( 1 ， 3 ， 5 ， 6 ， 7 ) ， p a t h 2= ( 1 ， 6 ， 7 ) ， 则 d i s t a n c e ( p a t h l ， p a t h 2 ) =2 ， p a t h 2 n( p a t h l ， 2 ) 为 p a t h l 的一个邻居。 ( b ) 邻域人工鱼的搜索办法。 在当代的 m 只蚂蚁 执行完一次搜索后， 对当前搜索到的符合 q o s约束条 件的从源点到目的节点的路径作为人工鱼群算法的初 始鱼群。 通过对初始鱼群进行变异和二次蚁群算法搜 索来找到邻域范围内的人工鱼。 具体策略如下： 假设某 条合格路径为 p a t h=( 1 ， 1 7 ， 3 ， 1 2 ， 2 0 ) ， 该路径长度为 l e n g t h ( p a t h )= 5 ，则 其 变 异 长 度 定 义 为 l = r o u n d ( 1 e n g t h ( p a t h ) 3 ) ， 即变 异 长度 为接 近 总长 度 的 1 3的整数 ， 在本例 中， l( p a t h )= 2即变异长度 为 2 。 mu t a t e d为变异的次数 ， 固定 为一常数 ， 每次根据变异 长度 l( p a t h ) 随机产生两个变异点 rl 和 r 2 ， r2 =r1 +l， 然后蚂蚁爬行规则， 执行二次蚁群算法搜索 r， 和r2 之间的路径。 如果变异后搜索到的路径p a t h u 诅 n( p a t h ， k ) ， 则 p a t h m 吲就属于 p a t h的一个邻居。 然后进行下一次搜索， 如此重复， 直到执行完 t r y n u m b e r 次搜索。 ( c ) 觅食行为和追尾行为按照文献 9 所描述的执 行。 上述的两种算法的融合既保证了在下一周期搜索 时倾向于部分较优解附近， 提高算法的收敛速度， 又保 证了使蚂蚁倾向于未搜索过的链路 ， 减少算法陷人局 1 4 8 计算机技术与发展 第 l 9卷 部极值 的可能性 ， 增强 了算法的全局寻优能力 。 3 仿真实验 文中算法用图 1所示的网络模型进行仿真， 只考 虑链路的带宽、 延时和费用约束， 链路属性用三元组表 示 ( 带宽 、 延时、 费用) 。 有 1 个 q o s单播路由请求， 源节点为 1 ， 目的节点 为2 0 ， 约束条件为 b：8 ， d =1 2 。 文中算法和基本蚁群算法参数设置为： = 1 ， = 2 0， m： 8， di e d a i nu m = 2 0， afs adi e d a i nu m ： 1 0， s h e d i n g di e d a i =3， m u t a t e d nu m=5， 0 =l， n o d e s u m0=0 ， o t =1 ， 卢=1 ， q 0 =0 4 ， q 1 =0 7 ， a 0 = 0 1 ， q 0=3 ， ld=0 3 ， q ：1 0 ， q q=0 4 ， k=6 。 仿真 结果如表 l 和图 3 所示 。 表 1 算法运行结果比较 延时 费用 算法 最优路径 代数 ( 秒) ( 千元 ) 文 中算法 1 1 7 1 22 o 9 2 7 1 0 基本蚁群算法 1 1 73 一l 62 0 1 1 3 3 1 3 迭代次数( 次) 图 3 两种算法仿真结果 图 由上仿真示例可见， 文中算法在 1 0次迭代内就能 收敛到全局最优解( 1 ， 1 7 ， 1 2 ， 2 0 ) ， 收敛速度快 ； 而基本 蚁群算法在 2 0次迭代 内只 收敛 到局部最 优解 ( 1 ， l 7 ， 3 ， 1 6 ， 2 0 ) ， 收敛速度慢， 陷入局部最优。仿真结果验证 了文中算法是可行和有效的， 并且能够跳出局部最优， 快速 收敛到全局最 优解 。 4 结束语 针对 q o s单播路由问题 ， 提出了一种改进蚁群算 法和人工鱼群算法融合的 q i s 单播路由算法。该算 ( 上接第 1 4 4页) b p e l we b 鲫 c e s c i n p r o c e e d i n g o f t h e 1 3 t h i n t e r n a t i o n a l wo r l d wi d e we b c o n f e r e n c e n e w y o r k ，u s a： s n ， 2 0 0 4 ： 6 2 1 6 3 0 1 2 z o u z h i l e ， d u a n z h e n h u a b u i l d i ng b u s i n e s s p r o c e s s e s o r a s 法采用混合蚂蚁行为使初始路径差异化 ， 根据 q o s约 束条件以及当前的最优路径对可选节点集进行优化， 将人工鱼群算法加入到蚁群算法的每一次迭代过程 中， 利用人工鱼群算法全局快速收敛的优点， 来加快蚁 群算法的收敛速度， 并且人工鱼群算法的觅食行为， 帮 助提高了蚁群算法跳出局部最优的能力， 从而提高 了 整个算法的收敛速度， 减少了陷入局部极值的可能性， 增强了寻优能力。仿真实验结果验证了该算法的可行 性和有效性。 参考文献 ： 1 wa n g z ， c r o w e r oft j q u a l i t y o f s e r v i c e r o u t i n gf o r s u p p o r t i n g mu l t i m e d i a a p p l l c a t i o n s j i e e e j o u r n a l o f s d t e d ar e a s i n c o mmu n i c a t i o m， 1 9 9 6， 1 4 ( 7 ) ： 1 2 2 81 2 3 4 2 高坚 基于 自 适应蚁群算法的多受限网络 q 路由优化 j 计算机工程 ， 2 0 0 3 ， 2 9 ( 1 9 ) ： 4 0 4 1 3 林晖 ， 郑荣 ， 万晓瑜， 等 一种新的基于自适应蚁群算 法的q o s单播路由策略 j 微计算机应 用， 2 0 0 7 ， 2 8 ( 4 ) ： 3 8 63 8 9 4 陈岩， 杨华江， 沈林成 基于再励学习蚁群算法的多约束 q o s路由方法 j 计算机科学， 2 0 0 7 ， 3 4 ( 5 ) ： 2 5 2 7 5 何小燕， 费翔， 罗军舟 ， 等 i n t e me t 中一种基于遗传算法 的 q d s 路由选择策略 j 计算机学报 ， 2 0 0 0 ， 2 3 ( 1 1 ) ： 1 1 7 1 1 1 7 8 6 崔勇 ， 吴建平 ， 徐恪 基于模拟退火的服务质量路由算 法 j 软件学报， 2 0 0 3 ， 1 4 ( 5 ) ： 8 7 7 8 8 4 7 3 d o r i g o m，ma r l i e z z o v， c o t o mi a t h e a n t s yst e r n ：o p fi mi z a t i o nb y a c o l o n y o f o 0 o w _ r a t i n g a g e