（计算机应用技术专业论文）贝叶斯优化算法及其在qos组播路由中的应用研究.pdf

堡主兰笪丝苎 一：! 一 摘要 概率分析进化算法是将构造性模型引入进化算法进行研究而形成的+ 类新型 进化算法。贝叶斯优化算法是求解高阶难题中具有代表性的概率分析进化算法。 本文丰要研究贝叶斯优化算法及其在q o s 组播路由问题巾的应用，并讨论将贝叶 斯优化算法和多目标进化算法结合，求解计算机网络中的多约束o o s 组播路由问 题。 本文首先对概率分析进化算法进行了概述，在此基础上深入分析了贝叶斯优 化算法，讨论了如何将q o s 组播路由问题映射成为贝叶斯优化算法可求解的问题， 给出了一种问题的编码方式，提出一种基于决策图贝叶斯优化算法的q o s 组播路 由算法，实验结果表明，新的算法能够快速收敛到最优解，具有较好的性能。针对 传统遗传算法中交叉算子对多目标进化算法性能的影响，本文将贝叶斯优化算法 结合到多目标进化算法中，提出一种改进的强度p a r e t o 进化算法，本算法利用贝 叶斯网络实现对强度p a r e t o 进化算法的改进，对代表性的0 1 多目标背包问题的 测试结果表明，基于决策图贝叶斯的强度p a r e t o 进化算法具有较强的多目标优化 能力。本文分析了基于进化算法的单目标q o s 组播路由算法所存在的不足，在此 基础上，提出一种基于决策图贝叶斯的多目标q o s 组播路由算法，本算法在不需 要做预处理的情况下可以实现对多个不同的q o s 参数同时进行优化，实验结果表 明算法能够快速收敛于一组满足不同q o s 约束的非支配组播路由。 关键词：决策图贝叶斯网络，o o s 组播路由，多目标优化，p a r e t o 前沿，进化算 法 贝叶斯优化掉法及其在q o s 组播路由中的应用研究 a b s t r a c t p r o b a b i l i s t i c m o d e l i n g e v o l u t i o n a r ya l g o r i t h m s ( p m e a s ) t h a ti n c o r p o r a t e b u i l d i n g m o d e l si n t o e v o l u t i o n a r ya l g o r i t h m s h a v eb e c o m e an e wc l a s so f e v o l u t i o n a r ya l g o r i t h m s b a y e s i a no p t i m i z a t i o na l g o r i t h m ( b o a ) i s ar e p r e s e n t a t i v e a l g o r i t h mo fp m e a s t os o l v eh i g ho r d e rh a r dp r o b l e m s t h i sp a p e rm a i n l ys t u d i e s b o aa n di t s a p p l i c a t i o n s o nt h eq o s b a s e dm u l t i c a s tr o u t i n gp r o b l e mi n c o m p u t e r n e t w o r k s a l s o ，t h i sp a p e rd i s c u s s e sh o wt o s o l v et h eq o s - b a s e dm u l t i c a s tr o u t i n g p r o b l e m w i t h m u l t i p l e r e s t r i c t i o n s b yc o m b i n i n g b o aw i t h m u l t i - o b j e c t i v e e v o l u t i o n a r ya l g o r i t h m s f i r s t l y ，t h i sp a p e rs u r v e y st h er e s e a r c h i n gp r o g r e s so fp m e a s a n db o a o nt h e b a s i so f d i s c u s s i n g h o wt o m a pt h e q o s b a s e dm u l t i c a s tr o u t i n gp r o b l e mi n t oa p r o b l e m t h a tb o ac a ns o l v e ，aq o s b a s e dm u l t i c a s tr o u t i n ga l g o r i t h mb a s e do nb o a i s p r o p o s e d t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tt h en e wa l g o r i t h mc a nc o n v e r g e q u i c k l y t ot h e o p t i m a ls o l u t i o n s e c o n d l y ，i no r d e rt o o v e r c o m en e g a t i v e i m p a c t s c a u s e db y g e n e t i co p e r a t o r s i nt r a d i t i o n a lm u l t i - o b j e c t i v e e v o l u t i o n a r ya l g o r i t h m s ， t h i s p a p e rp r o p o s e s a ni m p r o v i n gs t r e n g t hp a r e t o e v o l u t i o n a r ya l g o r i t h m ( s p e a ) ， w h i c hc o m b i n e sb o aa n ds p e at oi m p r o v es p e a sp e r f o r m a n c e t h ee x p e r i m e n t a l t e s t so nt h e0 1m u l t i o b j e c t i v ek n a p s a c kp r o b l e ms h o wt h a tt h en f , wa l g o r i t h mh a st h e s t r o n g e rc a p a b i l i t yo fm u l t i o b j e c t i v eo p t i m i z a t i o nt h a ns p e a t h i r d l y ，i no r d e rt o o v e r c o m et h e d i s a d v a n t a g e s o f s i n g l eo b j e c t i v eq o s b a s e d m u l t i c a s t r o u t i n g a l g o r i t h m sb a s e do ne v o l u t i o n a r ya l g o r i t h m s ，am u l t i - o b j e c t i v eq o s b a s e dm u l t i c a s t r o u t i n ga l g o r i t h mb a s e d o n b a y e s w i t hd e c i s i o n g r a p h s i s p r o p o s e d ，w h i c h c a n o p t i m i z es i m u l t a n e o u s l ym u l t i p l eq o sp a r a m e t e r s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t t h en e wa l g o r i t h mi s c a p a b l e o f c o n v e r g i n gq u i c k l y t oas e to fn o n d o m i n a t e d s o l l l t i o n s k e yw o r d s ：b a y e s i a nn e t w o r kw i t hd e c i s i o ng r a p h s ；q o s - b a s e dm u l t i c a s tr o u t i n g m u l t i o b j e c t i v eo p t i m i z a t i o n ；p a r e t of r o n t ；e v o l u t i o n a r ya l g o r i t h m s i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：& 班今冉 日期：柚争年z c - , e 1 堪 - e t 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名： 擀跨日期：u 。卜年午月喀日 导师签名：鼍p 中雹蚤日期：沪叮年月寸日 f 堕主堂垡笙苎 第1 章绪论 遗传算法( g e n e t i ca l g o r i t h m s ，g a s ) 1 2 1 是2 0 世纪6 0 年代末期到7 0 年代初期 由美国m i c h i g a n 大学的j o h n h o l l a n d 与其同事和学生们研究形成的一个的理论和 方法。g a s 从解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来 构造人工系统的模型。经过近3 0 年的发展，遗传算法己取得了丰硕的应用成果和 理论研究的进展，已经成功应用于商业、工程和科学计算。但由于传统遗传算法 一般都是采用固定的遗传操作来生成子代，不目j 避免的会破坏许多重要构造块和 大量参数的人工设置，影响了算法性能的提高。近年来，一些研究者从统计学的 观点出发，将构造性模型引入进化算法进行研究，形成一类基于概率分析的进化 算法，称之为概率分析进化算法1 3 j ( p r o b a b i l i s t i cm o d e l i n g e v o l u t i o n a r y a l g o r i t h m s ， 简称p m e a s ) 。p e m a 算法在对许多方面表现了很好的性能，因此，引起许多研 究人员的研究兴趣，在进化计算领域中开辟了新的研究方向。目前理论上对贝叶 斯网络的研究十分活跃，许多相应的研究成果已经应用到了p m e a 算法中，贝叶 斯优化算法【4 】( b a y e s i a no p t i m i z a t i o na l g o r i t h m ，简称b o a ) 是其中较具代表性 的算法。本章主要介绍概率进化算法的研究概况，在此基础上引出本文所做的主 要工作。 1 1 连锁学习问题概述 由h o l l a n d 首先提出的基本遗传算法是基于人工选择和交叉变异等重组等操 作构成的一种优化方法，其基本依据是模式定理和“构造块”( b u i l d i n gb l o c k ) 假 设理论【2 7 4 - 5 。构造块是指群体中高于平均适应度，低阶，短距离的模式，也就是 构成问题解的基本部分。g a 通过对大量的构造块进行选择和重组操作，再生和 混合更多好的构造块，最后逼近解。但由于实际的重组操作常导致构造块破坏， 导致算法或者逼近局部最优或者早熟。构造块破坏问题一般称为连锁( 1 i n k a g e ) 问题【，具有识别构造块的算法称为连锁学习( 1 i n k a g el e a r n i n g ) 算法。下面简要介 绍连锁问题。 为叙述方便，先引入有关g a 算法的基本术语。设给定问题的解空间为s ，p f t l s 为g a 的第t 代群体，x i e p ( t ) ( 1 w ，则在适 应度上给相应的惩罚；计算组播树的代价c f n 。 3 2 4 适应度函数 适应废函数的设计是遗传算法的重要部分，它反映了具体求解问题的目标， 是遗传选择操作的依据，因此适应度函数设计的好坏是关系问题能否被解决的关 键。本文算法把组播树生成条件：无环、连通、覆盖基本结点、无非基本节点的 叶节点，以及时延及时延差别等q o s 限制均以惩罚函数的形式包含于适应度函数 中，在搜索过程中，对不可行解在适应度值上给以相应的惩罚，避免完全丢弃不可 行解。根据解码结果，构造适应度函数如下： f i t n e s s ( x ) = c o n s t 一( z 4 f o + 口 一声 f 2 一y 4 f 3 ) ( 3 6 ) 其中： r 一。c ( e ) ； 曩= ( 1 0 0 p s + c o m p s + ( q p ) + n o t l e a f ) 叫 叫 d d ( r ) d 尤0 ，)( 4 2 ) 对解x i x 而言，若不存在一个解x j x 一 x ，) 满足上， 。墨，则称x i 为一个非支配 解或p a r e t o 最优解，所有p a r e t o 最优解构成了p a r e t o 前沿或p a r e t o 最优解集合。 4 2 2s p e a 算法 s p e a 算法是一种基于p a r e t o 支配关系的多目标进化算法，它用固定规模的 外部群体来保存目前已搜索到的p a r e t o 最优解。算法首先随机产生一个规则群体 和空的外部群体，在以后的每一次循环中把菲支配解复制到外部群体中，并利用 刷新操作把外部群体中的支配解或者重复的非支配解删除，如果刷新后的外部群 体大小超过了最大上限，将采用聚类技术对外部群体中的个体进行删减；然后给 规则群体和外部群体中的个体分配适应度；最后执行交配选择操作，并利用交叉 重组和变异等遗传操作生成下代个体。 硕士学位论文 s p e a 算法存在许多缺陷，主要包括( 1 ) 同一个外部群体个体所支配的所有个 体具有相同的适应度；( 2 ) 如果同一代中有许多个体具有相同的适应度，则无法区 分它们之间的p a r e t o 支配关系；( 3 ) 利用聚类技术对外部群体中的个体进行删减 造成一些较优秀的非支配个体丢失。针对s p e a 算法的上述缺陷，s p e a 2 算法给 出了相应的改进方法，下面简要介绍s p e a 2 算法所采用的适应度分配策略和环境 选择技术。 4 2 2 1 适应度分配策略 s p e a 2 算法在计算个体适应度之前，首先给外部群体f 和规则群体p 中的 每一个体i 赋予一个强度s ( i ) ，代表其所支配的个体数目： s ( ) ；i _ ij 只+ p ta f 巾j ) i ( 4 3 ) 其中，| i 表示集合的规模；咖表示p a r e t o 支配关系。根据s ( i ) 值，个体i 的粗略适应度r ( i ) 定义为： r ( f ) ； s ( - )( 4 4 ) j t + ，f ，l 巾j 尽管粗略适应度分配策略提供了一种基于p a r e t o 支配关系的小生境机制，但 当大部分个体具有相同粗略适应度时，p a r e t o 支配关系将很难确定，所以要用附 加的解密度信息来区别这些个体。s p e a 2 算法中用到的密度估计技术是根据“k 近邻”方法变化而来。如果个体i 到外部群体和规则群体中所有其它个体之间的 距离已按升序排序，且i 到第k 个相邻个体的距离表示为盯? ，其中k - 万焉，。万 分别表示规则群体和外部群体的规模， 则个体i 的密度d ( i ) 可定义为式： d ( ) 。府 ( 4 5 ) 因而，个体i 的精确适应度定义为： f ( f ) = r ( f ) + d ( f )( 4 6 ) 4 2 2 2 环境选择策略 环境选择就是决定在整个进化过程中选择哪些个体保存到外部群体中的方 法。s p e a 2 算法在环境选择中允许支配个体参与选择，以保持解空间的多样性。 它首先按以下公式把外部群体和规则群体中所有非支配个体复制到下一代的外部 群体中： p f + 1 = fi f + p r f o ) “7 ) 若1 只+ t 1 篁，环境选择过程结束。否则，若l e + ，i c 丙，则把外部群体和规则群体中 贝叶斯优化算法及其在q o s 组播路由中的应用研究 较好的万一i m 1 个支配个体复制到下一代外部群体中；若l 瓦“l 万，则从一l + 。中删 除满足关系式( 4 8 ) 的个体i ；如此循环，直到i 芦ml - 万。 f 毛_ ：营比o 七q b d i ：0 ；砖v 孔o 尼q a 以i ：【唧，o 卅 其中w 叫，p u 表示第i 个背包中第j 个项目的重量和利益；c 。表示第i 背包的载 重限制：，i 伍) 表示第i 个背包的目标利益；x ，1 表示第j 个项目被放入背包。 4 4 2 实验结果 本章实验所用到的测试数据全部来自【5 9 ，并严格按照文献【3 6 】所给出的性 能评价标准来评价b s p e a 算法。为了比较s p e a 2 算法，本章采用c o v e r a g e 标 准f 删，该标准能够直接反映出两种多目标优化算法获得的p a r e t o 前沿之间的 p a r e t o 支配关系，进而判断所用测试问题能否充分测试出每种算法的指定性能以 及算法之间的性能优劣，该标准描述如下： c ( a 。监型宅鲁必( 4 1 0 ) l d l 其中a ，b 分别表示算法a 和算法b 所求的p a r e t o 前沿；c ( a ，b ) e 【0 ，1 1 ，c ( a ，b ) ；1 说明a 中的解支配或等于b 中的所有解，c ( 氏b ) 值越大则算法a 比算法b 的性 能越好，但c ( b ，a ) 1 一c ( a ，b ) ，因此要同时计算c ( a ，b ) 和c ( b ，a ) ，使评价更客 贝叶斯优化算法及其在q o s 组播路由中的应用研究 观合理。 4 3 0 0 4 0 0 0 3 7 0 0 邑3 4 0 0 3 1 0 0 2 8 0 0 2 5 0 0 2 5 0 0 2 8 0 03 l o o f 1 ( x ) 3 4 0 0 3 7 0 0 4 0 0 0 f 1 ( x ) 9 5 0 0 9 0 0 0 菩8 5 0 0 8 0 0 0 7 5 0 0 a ) 问题规模为1 0 0 7 5 0 0 8 0 0 0 8 5 0 0 9 0 0 0 9 5 0 0 f l ( x ) b ) 问题规模为2 5 0 3 0 堡主堂垡鲨塞 1 8 0 0 0 1 7 5 0 0 1 7 0 0 0 贫1 6 5 0 0 1 6 0 0 0 1 5 5 0 0 1 5 0 0 0 1 6 0 0 01 6 5 0 0 2 4 0 0 0 2 3 5 0 0 2 3 0 0 0 “2 2 5 0 0 2 2 0 0 0 2 1 5 0 0 1 7 0 0 01 7 5 0 01 8 0 0 0 f 1 ( x ) c ) 问题规模为5 0 0 2 1 5 0 02 2 0 0 02 2 5 0 0 2 3 0 0 02 3 5 0 0 2 4 0 0 0 f 1 ( x ) d ) 问题规模为7 5 0 图4 i 目标数量为2 ，问题规模分别为1 0 0 、2 5 0 、5 0 0 和7 5 0 时，两种算 法分别在3 0 代独立运行后所获得的p a r c t o 前沿，其中f l ( x ) ，f 2 ( x ) 分别表示 各个背包的目标利益； 3 1 贝叶斯优化算法及其在q o s 组播路由中的应用研究 3 8 0 a e ( x ) 3 6 3 4 3 2 溯 艄 硼 嘲 嘲 口( x ) 7 5 7 。 昭 阳 a ) 问题规模为1 0 0 n ( x ) 嘲7 渤 b ) 问题规模为2 5 0 3 2 硕士学位论文 1 日 17 5 a ( x ) 17 16 5 1 6 15 5 1 5 14 2 5 24 5 口( x ) 2 4 23 5 2 3 2 3 c ) 问题规模为5 0 0 2 4 1 。4 d ) 问题规模为7 5 0 图4 2 目标数量为3 ，问题规模分别为i 0 0 、2 5 0 、5 0 0 和7 5 0 时，两种算法 分别在3 0 代独立运行后所获得的p a r e t 。前沿，其中f l ( x ) ，f 2 ( x ) ，f 3 ( x ) 分另u 表示各个背包的目标利益。 贝叶斯优化算法及其在q o s 组播路由中的应用研究 图4 1 分别给出了目标规模为2 ，群体规模为8 0 0 ，问题规模( i t e m s ) 分别为 1 0 0 、2 5 0 、5 0 0 和7 5 0 时，两种算法分别在3 0 代独立运行后所获得的p a r e t o 前 沿。可以看出，随着问题规模的增大，b s p e a 算法与s p e a 2 算法所获得的p a r e t o 前沿差距也随之增大，说明b s p e a 算法在求解大规模问题上更具优势。相同条 件下，图4 2 给出了3 目标背包问题的测试结果，同样也得出上述结论，因此说 b s p e a 算法在解决高维大规模多目标优化问题上有很大优势，算法本身有很强的 鲁棒性，这主要由于贝叶斯网络的引入能够更好处理多变量间的交互，指导对解 空间搜索。 图4 3 群体规模不同时，b s p e a 算法分别在3 0 代运行后求解2 1 0 0 背包问题 所获得的p a r e t o 前沿，其中f l ( x ) ，f 2 ( x ) 分别表示各个背包的目标利益。 图4 3 给出了不同群体规模时，b s p e a 算法分别在3 0 代运行后求解2 1 0 0 背 包问题所获得的p a r e t o 前沿，可以看出，群体规模越大所获得的p a r e t o 前沿分布 越好，这主要由于群体规模越大使得构造的贝叶斯网络模型越精确的结果，但群 体规模增大同时也增加了算法的计算复杂度，本章从实验结果分析后得出群体规 模在8 0 0 时，b s p e a 算法在计算复杂度合理的前提下都能够收敛到很好的p a r e t o 前沿。 表4 1 给出了两种算法依据c o v e r a g e 标准所得出的性能对比结果，可以看出， 除了在4 1 0 0 和2 7 5 0 问题上c ( b s p e a ，s p e a 2 ) d x 于1 外，其它各种情况下 c ( b s p e a ，s p e a 2 ) 都等于1 ，也就是说本文算法在不同问题规模以及不同目标规模 的求解上都获得了比s p e a 2 算法更好的p a r e t o 前沿，在性能上比s p e a 2 算法有 很大的提高。 硕士学位论文 表4 i 依据c o v e r a g e 标准所得出的性能评价结果 c ( a ，b ) 算法测试问题( 目标规模问题规模) ab2 1 0 03 1 0 04 i 0 02 2 5 03 2 5 04 2 5 0 b s p e as p e a 21 0 0 1 0 0 9 6 3 7 1 0 0 1 0 0 1 0 0 s p e a 2b s p e ao 0 o 0 o 0 ab2 5 0 0 3 5 0 04 5 0 02 7 5 03 7 5 04 7 5 0 b s p e as p e a 21 0 0 1 0 0 1 0 0 9 3 7 5 1 0 0 1 0 0 s p e a 2b s p e a0 o oo 6 0 0 4 5 小结 本章把贝叶斯网络概率模型引进s p e a 2 算法中， 提出了一种新的多目标进 化算法，称之为b s p e a 算法。该算法通过构造和学习贝叶斯网络来替代s p e a 2 算法中交叉重组和变异等遗传操作，有效避免了对大量参数的人工设置和重要构 造快的破坏。本章用多目标0 1 背包t ；1 题分别对b s p e a 算法和s p e a 2 算法进行 了对比仿真测试，仿真结果表明，b s p e a 算法能够快速收敛到较好的p a r c t o 前沿， 性能明显优于s p e a 2 算法，表现出较强的鲁棒性。 第5 章基于决策图贝叶斯的多目标0 0 s 组播路由算法 研究 随着实时组播通信需求的不断增长，要求网络能够提供更加严格高效的q o s 路由保证，这就需要设计一个能够同时满足不同q o s 约束的高效组播路由算法， 该算法可归结为一个多目标优化问题加以求解，一般方法是把多个q o s 参数加权 合并为一单目标函数进行优化。在此，本章提出了一种基于决策图贝叶斯的多目 标q o s 组播路由算法b m o m r ，该算法在不需要傲预处理的情况下能够对多个不 同的q o s 参数同时进行优化。仿真结果表明，所提出的b m o m r 算法能够快速收 敛于一组满足不同q o s 约束的非支配组播路由。 5 1 引言 随着现场视频会议、视频点播等实时多媒体组播通信需求的增长，要求路由 必须具有严格的q o s 保证，主要包括带宽、时延、时延差别、代价、丢包率等， 而实现q o s 保证的关键之一就是组播路由机制，其最主要目标就是能够对网络资 源进行有效分配以找到满足不同q o s 要求下的最佳路由方案，但不同q o s 参数 之间存在着相互冲突和依赖关系，因而要在同时满足多个q o s 要求下对组播路由 进行优化则成为一个n p 难问题【蜘。除此以外，网络状态信息不精确性和不确定 性对组播路由也有很大的影响1 6 1 1 ，使问题更难于处理。解决该问题的一般方法 是采用启发式或近似算法在二次项时间内搜寻非精确信息网络状态下最大可能满 足给定q o s 约束的最佳路由。近年来，一些研究学者利用进化算法来求解q o s 路由问题【5 5 , 6 2 6 4 ，该方法在可行的计算时间内能够找到一个满足不同q o s 要求的 近优解，效率较高，表现出很强的优化能力；文献 6 4 】将免疫算法应用于组播路 由选择，通过基于遗传算法的基础上得到了更快的收敛速度，避免了计算过程中 的退化现象。然而上述算法却都存在如下三个共同的缺陷：( 1 ) 算法把多个q o s 优化目标加权合并为一个单目标函数加以优化，这就造成所有的解不仅对权值高 度敏感，而且还要求用户必须非常清楚所求解问题中多个q o s 优化目标之间的优 先权、相互影响等信息，以便设定更加合理的权值；( 2 ) 算法最终只能找到唯一 解，而这个解能够同时优化多个q o s 参数的可能性非常小，而从用户的角度来考 虑则更希望在一组同时满足不同q o s 要求的非支配解中选择最适合问题偏好的 解；( 3 ) 算法采用传统的变异和交叉等遗传操作容易造成重要构造块的破坏，存 在早熟收敛或收敛速度慢等问题。 近年来，一些研究者从统计学的观点出发，将构造性模型引入进化算法形成 硕士学位论文 一类基于概率分析的进化算法，称为概率分析进化算法，其主要思想就是为了克 服进化算法因交叉重组和变异等操作导致的连锁问题。p m e a 算法通过从优选的 解集合中提取信息，然后利用这种信息的概率分布产生新的解，由此实现算法的 连锁学习。这种将构造性概率模型引入进化算法的思想形成概率分析进化算法的 理论依据，贝叶斯优化算法是其中较具代表性的算法。在第四章工作的基础上， 本章主要利用上一章所提出的基于决策图贝叶斯的强度p a r c t o 进化算法，提出了 一种能够同时优化带宽、时延、代价等参数的多目标q o s 组播路由算法，该算法 把每个q o s 参数分别作为一个独立的优化目标同时进行优化，在很少的几代运行 后便能找到一组同时满足所有q o s 要求的全局次优解，即非支配p a r e t o 前沿。仿 真实验结果也表明，本章所提出的b m o m r 算法有效可行，具有更快的收敛速度 和更强的搜索能力，能够找到一组较好的q o s 组播路由。 5 2 基于决策图贝叶斯的多目标0 0 s 组播路由算法 5 2 1 多约束0 0 s 组播路由问题的描述 一般的q o s 组播路由问题包含多个约束条件，如带宽、代价、时延、时延差 别、丢包率等。如在设计具体的路由算法是考虑所有因素，算法势必太复杂而不 能实际应用。时延和带宽是实时多媒体传输必需的保证条件，代价是评价网络效 率的重要指标，都应列入约束条件；在保证有效时延的条件下，时延差别可在接 收端通过缓冲技术解决，另外，由于多数网络多媒体应用都附带错误恢复功能， 能容忍一定范围的丢包率，因此这两项可以忽略【6 5 1 。根据以上分析，本章所设计 的算法主要考虑带宽、时延和代价三个约束条件( 为了简化，只考虑链路而不考 虑节点的特性) 。 通信网络可抽象为无向赋权图g = ( v ，e ) ，其中v 代表通信节点集；e 代表 链路集；源节点s v 和所有目的结点m v s ) 构成了网络的基本节点。对每 一条链路e e e 定义了三个参数：链路代价c ( e ) 、链路带宽b ( e ) 和链路时延d ( e ) 。 假设源点s 到所有目的节点m 的组播树为t = ( v t ，e t ) ，其中v t v ，e t g e ，源 节点s 到每个目的节点t e m 的路径为p ( s ，t ) ，则对给定的组播通信任务0 ：( s ，m ， b ，d ) ，多目标q o s 组播路由算法所要寻找一组满足如下约束的组播树，并要求树 必须连通、无环、覆盖所有基本节点以及无非基本节点的叶节点： d ( e ) 5 d f 爿f ，f ) 施雄徊( e ) ，e p ( s ，f ) ) 苫b m i n c ( e ) 老r 、。 其中b ，d 分别为组播树t 的带宽和时延约束。 ( 5 1 ) ，j、l 贝叶斯优化算法及其在q o s 组播路由中的应用研究 5 2 2 问题编码 为满足组播树的带宽限制，编码前先删除图g 中不满足带宽要求的链路，经 过精简的网络图可能不是连通的，而包含几个连通分量，但如果所有基本节点都 位于同一个连通分量g ，表明网络满足带宽限制，否则须应用协商放宽带宽约 束以重新处理。其中g ，中的链路数称为有效链路数，由此减少了问题的编码长 度和求解复杂度。采用二进制编码对g 中的链路编码x - - x l x 2 x m ，其中1 1 1 为g 中的有效链路数，基因位x i 含义为： ， 1图g7 第i 条有效链路被选为组播树的一条边； x ；= j l 0其它； 该编码方法适合要求解的问题，同时也符合编码策略所要求的三个规范：完备性， 健全性和非冗余性。 5 2 3 解码方法 根据上述的编码机制和后面的目标函数定义，本章设计了一种简单有效的解 码方法，该方法能够探测出所构造的组播树是否满足生成条件以及q o s 约束条 件。方法描述如下： ( 1 ) 初始化图g 中的每一个节点为一个组； ( 2 ) 对个体x = x l x 2 x 。，若x i - 1 ，则判断x i 所对应图g 中链路的两个端点所 在的组是否相同；如果相同则合并两个组，否则表明存在环路，因而要给以 惩罚，惩罚度与存在的环数l o o p s 成正比；重复( 2 ) ，直到i = m ： ( 3 ) 删除未被处理过的组，若生存的组中所覆盖的基本结点数p 0 ； 5 2 5 算法描述 b m o m r 算法采用基于源路由选择机制，网络的源节点维护全局的网络拓扑及 其状态信息，并进行网络计算从而确定路由。算法描述如下： ( 1 ) 删除网络图g 中不满足带宽要求的链路，生成新的网络图g ； ( 2 ) 依据图g 对问题进行编码，随机产生初始规则群体辟，构造一个空的外部 群体_ 0 - ，设t = o ，其中l 瓦i - ，i p 0 1 万，t 为最大进化代数； ( 3 ) 执行适应度分配策略，计算出p 和f 中所有个体的适应度，并进行相应的 评估； ( 4 ) 进行环境选择，生成f 。；若f 。中的非支配个体不再发生变化或若f 苫r ， 算法终止； 此时，f + ，中的非支配个体构成p a r e t o 前沿； ( 5 ) 执行锦标赛竞争选择，从i 。中选择个个体，并根据选定的网络评价标准 和约束条件构造相应的贝叶斯网络b ：根据对b 编码后的联合分布信息， 对网络进行学习，从而产生个新个体并替换父代个体，生成只。；设置 t = t + l ，转到( 2 ) 。 5 3 实验结果及分析 ( 1 ) 实验一，采用w a x m a n 方法随机地产生网络，即网络的打个节点从一个 l l 的坐标平面中随机地选取，每对节点n ，v 间存在边的概率为： 贝叶斯优化算法及其在q o s 组播路由中的应用研究 v r ( ) ：卢e x p 掣 ( 5 4 ) z i 儿 其中a ( u ，v ) 为欧氏距离。参数a ，卢从区间( o ，1 】中选取a 越大，距离远的节点之 间边存在的概率就越大：口越大，网络就越稠密。每条链路带宽为0 5 0 m b s 之 间的随机值，链路代价为两节点间的欧拉距离，链路时延= 边的长度1 0 0 0 v ，v 为信息沿链路的传播速度，取为2 3 光速。每次实验的基本节点数为整个网络节 点数的1 3 取整，初始种群为2 0 0 ，共进行2 0 0 次实验。图5 1 给出了两种算法 的平均进化代数随网络节点数变化的比较曲线，可以看出，随着网络规模的增大， b m o m r 算法的进化代数增加趋势明显小于文献 6 3 1 算法，也就是说本章算法收 敛更快，更具实际意义。 ( 2 ) 实验二，为了与文献 6 4 1 1 拘方法进行比较，采用其给出如图5 2 所示的网 络拓扑结构和数据进行2 0 0 实验，其中源节点为1 ，目的节点为f 2 ，9 ，1 0 ，1 3 ， 1 4 。图5 3 给出了时延限制为2 5 时两种算法收敛过程的比较，可以看出，b m o m r 算法有更快的收敛速度。图5 4 为b m o m r 算法运行后最终所获得的p a r e t o 最 优解集，解集中包含单目标情况下所求的最优解，用户可以根据问题的需要在解 集中自主选择最适合的解。 3 0 2 5 2 0 籁 s1 5 翻 霹 睁1 0 0 o 1 0 2 03 0 4 05 0 网络节点数 图5 1 两种算法的平均进化代数随网络节点数变化的比较曲线 堡主兰垡迨苎 4 ( 2 1 ，3 ) 9 1 8 0 1 6 0 1 4 0 1 2 0 $ 1 0 0 蒜8 0 艘 智6 0 4 0 2 0 0 图5 2 实验二的网络拓扑结构 024 681 0 1 21 4 1 61 8 2 0 进化代数 图5 3 两种算法搜索组播树的代价和时延随进化代数变化的比较曲线 4 1 图5 4 两个q o s 参数的p a r e t o 最优解集 ( 3 ) 实验三，利用文献 5 5 】给出的拓扑结构和开销数据分别对本章和文献 5 5 】 的方法进行了2 0 0 次实验。由于用遗传算法解决问题的效率与群体规模和运算代 数有关，因此，本章采用适应度评价次数( 群体规模x 运算代数) 作为评价标准。 表5 1 给出了两种算法收敛于最优解时适应度评价次数的分布情况。当d = 6 时， 文献f 5 5 】算法和b m o m r 算法求得最优解的平均适应度评价次数分别为3 5 6 0 和 2 1 6 0 ；当d = 7 时，文献【5 5 】算法和本章算法求得最优解的平均适应度评价次数分 别为1 7 6 0 0 和6 5 7 0 ，由此可见，b m o m r 算法的收敛速度明显优于文献【5 5 】的方 法，尤其是当时延限制放大，各选路径增多时，其优势更为明显。 表6 1不同算法收敛于最优解时适应度评价次数比较 所占比例( 时延要求所占比例( 时延要求 适应度评估为7 )适应度评估为6 1 次数 文献 5 5 】 b m o m r次数 文献1 5 5 】 b m o m r 算法算法算法算法 0 - 3 2 0 0 06 4 7 9 7 5 0 - 4 0 0 06 6 7 8 4 0 3 2 0 0 0 - 6 4 0 0 02 4 1 2 5 4 0 0 0 1 2 0 0 02 4 5 1 6 o 6 4 0 0 0 - 9 6 0 0 06 0 o1 2 0 0 0 2 0 0 0 07 9 o 9 6 0 0 0 5 2 o2 0 0 0 0 0 9 0 硕士学位论文 5 4 小结 通过算法描述和仿真实验可知，本章提出的b m o m r 算法可以：( 1 ) 把多个 q o s 参数分别作为独立的优化目标同时进行优化；( 2 ) 能够找到一组同时满足不 同q o s 要求的非支配解，给用户提供了选择最适合问题偏好解的机会；( 3 ) 利用决 策图贝叶斯方法，通过对贝叶斯网络的构造和学习替代传统进化算法中的交叉重 组和变异操作，从而实现了自主学习父代群体并产生优秀子代群体，避免因对大 量参数的人工设置和重要构造块的破坏而影响算法的性能；( 4 ) 利用新的编码、解 码方法以及适当的多目标函数，能够快速收敛于一组非支配解( 组播树) ，实现q o s 组播路由。 贝叶斯优化算法及其在q o s 组播路由中的应用研究 结论 目前，随着统计学、信息学、计算机科学等各行各业的快速发展，以遗传算 法为核心的进化算法也有了飞速的发展，由于其思想简单，易于实现以及表现出 来的健壮性，进化算法赢得了许多应用领域，特别是近年在问题求解、优化和搜 索、机器学习、智能控制和人工生命等领域都取得了令人鼓舞的成就。但由于传 统遗传算法一般都是采用固定的遗传操作来生成子代，造成重要构造块的破坏， 影响了算法性能。近年来，一些研究者从统计学的观点出发，将构造性模型引入 进化算法的研究，形成一类基于概率分析的进化算法，称之为概率分析进化算法 ( p m e a ) 。其中，贝叶斯优化算法是一种求解高阶难题较具代表性的p m e a 算法， 其主要思想就是把利用贝叶斯