（计算机软件与理论专业论文）qos组播路由的模拟退火自适应遗传算法.pdf

鹄埘矢害 面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 摘要 应用自适应遗传算法解决q o s 组播路由是近几年发展起来的一个热门课题。自适应遗 传算法具有高度并行、随机和自适应等特性，但是，该算法具有以下缺陷：( 1 ) 容易陷入局 部最优解，出现早熟现象；( 2 ) 参数缺乏动态性，无法满足遗传进化的动态适应性。结合模 拟退火算法，本文提出一种q o s 组播路由的模拟退火自适应遗传算法s a a g a ，通过对多组 实验结果的分析，验证了s a a g a 算法的有效性。本文的工作如下： l 、引入模拟退火算法到自适应遗传算法的交叉和变异算子中。模拟退火算法具有较强 的局部搜索能力，使搜索过程避免陷入局部最优解，不但可以有效地抑制早熟现象，而且也 缓解了单独利用自适应遗传算法的选择压力； 2 、改进了自适应遗传算法的交叉概率和变异概率。交叉概率和变异概率的选择是影响 算法行为和性能的关键，直接影响算法的收敛性。但自适应遗传算法的概率选择不利于进化 过程的初期，其间搜索效率缓慢。因此，本文在自适应遗传算法的基础上对交叉和变异概率 进行改进，加快本算法在进化初期的搜索效率； 3 、采用基于路径的编码方式，有效解决本算法在编码、译码方面的困难，适应网络规 模的不断增长； 4 、采用基于惩罚算子的适应度评价，保证本算法更加客观衡量个体优劣： ： 5 、采用轮盘赌和最佳个体保留策略相结合的选择算子，保证本算法收敛到全局最优； 6 、设计修补环路算子，有效解决个体在执行交叉和变异算子后可能出现环路的问题。 仿真实验结果表明，本算法收敛速度快，具有良好的稳定性、寻优性和可扩展性，可以 满足不断变化的网络规模。 关键词：组播路由：遗传算法；模拟退火；q o s 约束 鞠囊吁又萼面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 a b s t r a c t q o sm u l t i c a s tr o u t i n gi sah o tt o p i ci nr e c e n ty e a r s a n dt h ea d a p t i v eg e n e t i ca l g o r i t h mi s h i 曲l yp a r a l l e l ，r a n d o ma n da d a p t i v ec h a r a c t e r i s t i c s ，w h i c hi sa l le f f e c t i v ew a y t oq o sm u l t i c a s t r o u t i n g h o w e v e r , t h i sa l g o r i t h mh a st h ef o l l o w i n gd e f e c t s ：( 1 ) v u l n e r a b l et ol o c a lo p t i m i z a t i o n ； ( 2 ) p a r a m e t e r si sl a c ko fd y n a m i c ，u n a b l et os a t i s f yt h ed y n a m i ce v o l u t i o no fg e n e t i ca d a p t a t i o n w i t hs i m u l a t e da n n e a l i n ga l g o r i t h m ，t h i sp a p e rp r o p o s e sas i m u l a t e da n n e a l i n ga d a p t i v eg e n e t i c a l g o r i t h m ( s a a g a ) f o rq o sm u l t i c a s tr o u t i n g w ev e r i f yt h ev a l i d i t yo ft h es a a g a w i t ht h e m u l t i g r o u pa n a l y s i so f t h ee x p e r i m e n tr e s u l t s i nt h i sp a p e r , t h ew o ki s 笛f o l l o w s ： f i r s t l y , i n t r o d u c es i m u l a t e da n n e a l i n ga l g o r i t h mt ot h ec r o s s o v e ra n dm u t a t i o no p e r a t o ro f a d a p t i v eg e n e t i ca l g o r i t h m s i m u l a t e da n n e a l i n ga l g o r i t h mh a ss t r o n g e rl o c a ls e a r c hc a p a b i l i t i e s ， w h i c ha v o i d sap a r t i a lo p t i m u md u r i n gt h es e a r c hp r o c e s s i tn o to n l yi n h i b i t st h ep r e m a t u r eo f a d a p t i v eg e n e t i ca l g o r i t h m , b u ta l s oe a s e st h es e p a r a t eu s eo fa d a p t i v eg e n e t i ca l g o r i t h ms e l e c t i o n p r e s s u r e s e c o n d l y , i m p r o v et h ec r o s s o v e ra n dm u t a t i o np r o b a b i l i t yo fa d a p t i v eg e n e t i ca l g o r i t h m t h e s e l e c t i o no ft h ec r o s s o v e ra n dm u t a t i o np r o b a b i l i t yi st h ek e yt ot h eb e h a v i o ra n dp e r f o r m a n c eo f t h ea l g o r i t h m ，w h i c hh a st h ed i r e c ti m p a c to nt h ec o n v e r g e n c eo ft h ea l g o r i t h m h o w e v e r ，t h e p r o b a b i l i t yc h o i c eo fa d a p t i v eg e n e t i ca l g o r i t h mi sn o tc o n d u c i v et oe v a l u a t i o ne a r l y , a n di t s s e a r c he f f i c i e n c yi ss l o w t h u s ，w ei m p r o v e dt h ec r o s s o v e ra n dm u t a t i o np r o b a b i l i t yb a s e do nt h e a d a p t i v eg e n e t i ca l g o r i t h m ，w h i c hi sa b l et of a s t e nt h es e a r c he f f i c i e n c yo ft h i sa l g o r i t h mi n e v a l u a t i o ne a r l y t h i r d l y , c o d eb a s e do nt h ep a t h , w h i c hi sa ne f f e c t i v es o l u t i o nt ot h ea l g o r i t h mi nt h ec o d i n g a n dd e c o d i n ga n ds a t i s f i e st h eg r o w t ho f t h en e t w o r ks c a l e f o u r t h l y , e v a l u a t et h ef i t n e s sb a s e do np u n i s h m e n to p e r a t o r , w h i c he n s u e st h a tt h i sa l g o r i t h m i sa b l et om e a s u r ei n d i v i d u a lm e r i t so b j e c t i v e l y f i f t h l y , u s ec h o i c eo p e r a t o rw i t ht h ec o m b i n a t i o no ft h er o u l e t t eg a m b l i n ga n dt h eb e s t i n d i v i d u a lt or e t a i n , w h i c he n s u e st h i sa l g o r i t h mi sa b l et oc o n v e r g eg l o b a lo p t i m u m s i x t h l y , d e s i g nt h er e p a i rl o o po p e r a t o r , w h i c hd e a l sw i t ht h ep o s s i b l el o o pp r o b l e ma f t e rt h e i n d i v i d u a lf i n i s h e dc r o s s o v e ra n dm u t a t i o no p e r a t o re f f e c t i v e l y ；i 麓_ 一幺乎 面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 t h es i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h mh a sf a s tc o n v e r g e n c ea n db e t t e rp e r f o r m a n c e i t i sa b l et os a t i s f yt h ec h a n g i n gn e t w o r ks c a l e k e yw o r d s ：m u l t i c a s tr o u t i n g ；g e n e t i ca l g o r i t h m ；s i m u l a t e da n n e a l i n g ；q o sc o n s t r a i n t 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的 成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内 容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对 本文的研究成果做出重要贡献的个人和集体，均已在文中以明确方式 标明。 本声明的法律责任由本人承担。 论文作者签名：毒犯 日期：毯n 盈心 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文储虢嬉翩躲空生帐虫_ 鞠鼍一矢掌 面向q 。s 组播路由优化的模拟退火自适应遗传算法 兰州大学硕士学位论文 1 1 问题提出 第一章绪论 近年来，随着网络通讯技术的快速发展以及i n t e m e t 的普及，q o s 组播路由成为当今发 展的热点之一。它主要为许多新的网络应用提供服务，如视频点播、远程教学、网上拍卖等。 因此，研究适合q o s 组播的路由算法是非常必要的。 当前，许多学者采用遗传算法解决q o s 组播路由问题，现在简要介绍如下：文献【1 】中 提出一种求解时延约束的遗传算法，其交叉策略采用相同链路保留，分类并连接零星予树以 构成组播树的方法；文献【2 】中提出一种通用遗传算法，其采用n x n 的一维二进制编码机制； 文献p 1 提出一种求解带时延约束组播路由问题的启发式遗传算法，其采用树型编码，并运用 d c u r 算法【4 】计算费用最短路径。 以上算法存在以下不足： 1 )编码、解码过程复杂，算法搜索空间随网络规模的增大而急剧增大，算法效率低； 2 )交叉和变异算子相当复杂，算法容易陷入未成熟收敛，并且精度不好： 3 ) 交叉和变异概率采用“事先确定+ 固定不变”的方法，参数无法满足算法的动态性 要求，易出现早熟现象； 4 )不具有较强的局部搜索能力，容易陷入局部最优。 因此，本文针对以上不足，提出了一种q o s 组播路由的模拟退火自适应遗传算法 s a a g a ( s i m u l a t e da n n e a l i n ga d a p t i v eg e n e t i ca l g o r i t h m ) 。 1 2 项目背景 本文的项目背景来源于中科院声学所的“基于i p v 6 的p 2 p 弹性重叠网络智能节点的研 制”项目。该项目主要参考“下一代互联网示范工程2 0 0 5 年研究开发、产业化及应用试验 有关技术参考要求”中的分项c n g i - 0 4 1 2 1 d ，其目标是：研制智能节点设备，在c n g i 上构建基于结构化p 2 p 模型的i p v 6 弹性重叠网络，实现一个分布式资源管理平台；监控链 路状态，屏蔽网络故障和变更，为应用层提供可靠、高效的资源定位和查找服务；利用智能 节点探测网络路径和性能，为应用提供路由优化等网络服务；实现基于智能节点的分布式病 麓擘，矢害 面向q o s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 毒监测架构，并且可为c n g i 提供一种分布式网络管理工具。 作者在此项目中参与了基于网络路径信息的q o s 组播路由优化子项目。通过同步网络 路径信息，采用模拟退火自适应遗传算法，构建q o s 组播路由树，从而优化组播路由。主 要用于加快组播组数据传输。本文结合作者在中科院声学所高性能网络实验室参与的课题， 进行归纳总结，并在此基础上作了进一步的扩展，研究适合于上述应用的组播路由算法。 1 3 论文创新之处 l 、采用按路径编码的方式，生成的个体均代表一棵组播树，有效解决遗传算法在编码、 译码方面的困难；能够使交叉和变异算子更易执行和实现；且码长仅取决于组播节点个数， 不会随着网络规模的增大而变长，本算法能够适应大型网络； 2 、采用基于惩罚算子的适应度评价，保证本算法更加客观衡量个体优劣，确保个体的 性能评价。 3 、采用最佳个体保留策略的选择算子，能够保证群体中较好的个体不被交叉和变异算 子破坏，而直接保留至下一代群体中，保证本算法收敛到全局最优； 4 、引入模拟退火思想到自适应遗传算法的交叉和变异算子中，能有效抑制自适应遗传 算法陷入局部最优解的缺陷； 5 、改进自适应遗传算法，不仅使交叉概率n 和变异概率厶能随适应度自动改变，而 且改进的交叉概率只和变异概率尸肼在种群的最大适应度值、最小适应度值和平均适应度值 之间进行线形调整，加快本算法的搜索效率； 6 、设计修补环路算子，可有效解决本算法中个体在执行交叉和变异操作后可能会出现 环路的问题。 2 ：萄鼍一幺害面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 2 1 组播路由 2 1 1 工作原理 第二章相关技术 组播是一种从一个发送者同时向多个接收者或者多个发送者向多个接收者传送数据包 的通信过程。组播源把数据包发送到特定组播组，而只有属于该组播组的地址才能接收到此 数据包 5 1 。 组播以最佳的方式将数据传输给所有的主机 6 1 。组的成员可以是动态的，即成员可以在 任何时间加入一个组或离开一个组，组的大小和位置没有限制，一个主机可以是多个组的成 员。组播可以大大的节省网络带宽，提高数据传送效率，减少主干网拥塞的可能性。因为无 论有多少个目标地址，在整个网络的任何一条链路上只传送单一的数据包。组播组中的主机 可以是在同一物理网络，也可以来自不同的物理网络。 为了满足多媒体实时应用等的需求，很有必要寻求网络层对组播通信的支持，使组播技 术满足此类应用的要求，为此就有了实现组播的方式，也就是建立组播树【7 1 。组播树是覆盖 源节点和所有目的节点的一棵生成树，建立的组播树优点为：( 1 ) 信息可以沿着树的分支并 行的传到各个目的节点，这可以降低信息传递的时延：( 2 ) 信息只在树的分支处进行复制， 从而使复制的份数尽量少，这样做可以节省大量的带宽资源，提高资源的利用率，并且能减 少拥塞的发生。 2 1 2 组播优势 相较于单播和广播而言，组播虽然实现较为复杂。但在带宽、服务器负载和网络负载等 方面具有明显优势，具体如下： 1 ) 占用带宽少。运用组播技术分发信息可以从本质上减少整个网络带宽的需求。与单 播技术不同，当多个用户要求同一服务器提供同样数据时，采用组播技术，服务器 只需发送一份数据，数据只在交叉处进行复制，这样每条链路中只有一份数据的拷 贝在传输，因此带宽的需求不会随用户数量的增加而增加。 2 )服务器负载小。单播传输方式需要为每一个用户发送一份数据拷贝，因此当用户数 3 ：菊埘矢霉面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 目增加，服务器的负载也将增大。而组播只需要发送一份数据拷贝，服务器负载不 会随着用户数目的增加而增大，这样就有效地降低了服务器负载。 3 )网络资源消耗低。虽然复制组播数据给路由器带来了一定消耗，但是从整体而言， 组播在网络中的传播数据量大大减少，明显降低了带宽要求，减少了网络出现拥塞 的可能性，有效降低了网络的负载。 2 1 3 应用前景 由于组播技术具有“一发多传”和按组接收的特性，因此组播技术在网络环境中有着十 分广泛的应用，具体如下： 1 )数据分发：主要利用组播技术“一发多传”的特性，数据中心利用组播技术，只 需一次就可以将数据发送到多个目的地址，这样就省去了重复传输的工作量。为 保证数据的可靠传输，在传输数据的时候要使用像文件传输协议( f 1 t ) 一样的组播 文件传输协议( m f t p ) 。 2 ) 实时数据传播：采用组播技术，利用按组接收特性，向大量的主机组传输实时数 据。这是当前深受欢迎的一个应用领域。一个典型的例子是将股票信息实时发送 到交易大厅的工作站。 3 )游戏和仿真：组播可以用于有大量参与者的游戏和仿真，参与的p c 机或工作站只 需进入组播组，就可以开始发送和接受游戏及仿真数据，通过不同的组播组可以 将游戏加入者分为不同的游戏空间。 4 )多媒体应用；多媒体是当前组播技术最重要的应用领域，随着宽带网络技术和多 媒体技术的发展，利用网络来传输多媒体数据越来越普遍，例如多媒体会议系统， 视频点播( v o d ) 系统等。 2 2 服务质量q o s 2 2 1q o s 简介 当前的i n t e r a c t 只能提供尽力发送服务，网络层不区分用户业务的种类，而将网络资源 ( 包括链路带宽、交换节点、c p u 资源、队列等) 公平的提供给各类业务，以最大速度尽力转 发数据分组作为单一目标，在分组丢失概率，延迟等方面公平的对待各类业务。这种尽力发 4 鞠埘矢害面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 送的机制使网络层无法提供网络传输参数的保证。然而在实际网络应用环境中，丢失率、带 宽、端到端延时和延时抖动等参数对于网络和应用业务往往是至关重要的。例如，文件传输 业务要求分组的丢失率尽可能低，而传输延时不是关键因素：i p 电话等多媒体业务要求延 时和延时抖动尽可能小，而丢失率可以相对大一些。这就要求网络能够区别对待各种业务， 并提供不同的服务质量。 q o s ( q u a l i t yo fs e r v i c e ) 是应用业务对网络传输服务所提出的一组可度量的要求，主 要包括带宽、端到端延时、分组丢失率、抖动、花费代价等。当在网络上传输相应的数据业 务时，必须满足的度量要求。q o s 需求可以通过一个限制集来描述，其中的限制可以是链路 限制、路径限制或树限制。其中，链路限制定义了从源到目的地的每一条链路的限制，如带 宽限制：路径限制定义了从源到目的地的一条路径上端到端q o s 需求，如延时；树限制定 义了对组播中使用的整个组播树的限制，例如对组播树延时的限制是对树中从源到所有目的 地的路径中最大延时限制。 当前i n t e m e t 的主要路由协议包括域内路由协议( o s p f ，l 啦i ) 和域间路由协议( b g p ) 等。这些都是“尽力发送”的路由协议，选择路由时通常只使用单一优化目标( 如跳数或花 费) ，因此在某种意义上所有的业务都是属于“最短路径”的。即使源节点到目的节点之间 存在“更好的”路径，只要不是最短路径也不会被使用。这样的路由机制会导致某些链路空 闲的情况下而在另外的一些链路上造成拥塞。q o s 路由就是将传统的最短路径变为一条更好 的路径，其主要目标包括以下两点：( 1 ) 为每一个接纳的q o s 业务连接请求，找到满足其 q o s 要求的可行路径；( 2 ) 优化全局资源利用率，平衡网络负载，从而最大化网络接受其他 q o s 请求的能力 8 1 。 2 2 2q o s 度量 根据r f c 2 3 8 6 1 9 1 的定义，q o s 是网络传送一个流时需要保障的一组业务要求。许多服务 对网络提出了更高的要求，这些要求通常都用q o s 参数来表示，主要q o s 参数如下： 1 ) 带宽( b a n d w i d t h ) ：指单位时间内传输的数据包数量； 2 ) 延时( d e l a y ) ：指数据包从发送到接收之间的时间间隔。它包括终端设备的编码解 码时间，数据包在传输介质中的传输时间，数据包在交换机或路由器中被处理的 时间，以及数据包在交换机或路由器的等待队列中的排队时间； 3 ) 延时抖动o i t t e r ) 当数据包到达时，如果等待队列中没有别的数据包，则它将以固 5 萄鲥，乞警面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 定延时被转发出去，但是如果等待队列中有别的数据包，则它可能需要等待，这 时数据包被交换的延时就等于固定延时加上在队列中等待的时间，以上两种情况 下的延时变化程度就是延时抖动； 4 )丢包率( p a c k e tl o s sr a t e ) - 指在特定的时间段内，丢失的数据包占传输的数据包总 数的比例。 不同的应用所要求的q o s 也不相同，例如音频、视频能够容忍一定的丢失率，但它们 对时延和时延抖动有较高的要求，对实时视频信号的传送则必须保证高带宽；数据通信要求 低的丢失率，但时延和时延抖动的要求不严。不同的q o s 参数具有不同的特征，常见的四 种典型特征为：加性、乘性、凸性和凹性【l o l ，定义如下： 定义2 1 ：令c 矗_ ，) 表示链路以歹夕上的某种度量，对于任意的路径p = 一，j ，k ， ，州，称度量c 是： ( 1 ) 加性的，如果c 例= c ，+ c ，砂+ + c ( i ，圳，例如时延、时延抖动、费用； ( 2 ) 乘性的，如果c 纠= c p ，刃c ，矽* c a ，圳，例如可靠性； ( 3 ) 凹性的，如果c 例= m f n c e ，力，c 疗，砂，c m 叫，例如带宽； ( 4 ) 凸性的，如果c 纠= m a x f c ( i ，c ，矽，c 口，m ) l 。 2 2 3q o s 组播 许多网络服务往往在采用组播的同时带有q o s 要求。在这种模式下，其组播过程与没 有q o s 约束条件的组播有所不同，以r s v p 为例，q o s 组播流程如图2 1 所示： 圈2 1 网络组播路由( 带宽、延时) 流程图 1 )组播组成员通过i g m p 协议加入到组播组中； 2 )组播路由器砌r 4 通过某种组播路由算法来构建一棵通往各组播成员的组播生成 6 麓埘矢孽 面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 树。该组播树不仅具有节点连通性保证，而且还需满足q o s 要求。 3 )s e r v e r 发送r s v pp a t h 消息，该消息沿组播树向各组播成员发送。例如在图2 1 的生成树中，s e r v e r 发往h o s t 2 的路径为s e r v e r - + 融_ r 4 一r 3 - h o s t 2 。当组 成员收到r s v pp a t h 消息后，沿逆向发送资源预留请求。例如h o s t 2 收到p a t h 消息后，它将沿h o s t 2 - r 3 _ r 4 - 砌_ + s e r v e r 进行资源预留； 4 )最后，当s e r v e r 收到各组成员发来的资源预留消息后，开始发送组播分组，这些 分组将沿组播树转发。组播树如图2 2 所示： 2 3 遗传算法g a 2 3 1g a 基本思想 图2 2 满足q o s 要求的组播树 遗传算法g a ( g e n e t i ca l g o r i t h m ) 实质上是一种繁衍、监测和评价的迭代算法。它模拟自 然界生物“适者生存，优胜劣汰”的进化理论，每个个体在种群演化过程中都被评价并得到 其适应度值，个体在选择、交叉以及变异算子的作用下向更高的适应度进化以达到寻求问题 最优解的目标【l l 】。 2 3 2g a 基本步骤 编码 遗传算法以决策变量的编码作为搜索对象，实际问题经过编码后称为染色体个体。编 码不但决定了如何将现实问题转换为遗传算法可操作的基因型个体，还决定了如何从搜索空 间的基因型变换到解空间的表现型时的解码方法。编码方式在很大程度上决定了如何进行群 体的遗传进化运算以及遗传进化运算的效率。 对于一个实际问题，编码方式可能有多种，往往需要在编码解码难易程度、时空消耗、 遗传算子执行效率等方面取得平衡。常见的编码方法可分为三大类：二进制编码、浮点数编 7 蔺囊吁又尊 面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 码、符号编码。将实际的问题空间对应的转换到编码空间，是设计遗传算法的基础。 种群初始化 执行遗传算法的第一步，就是要生成一个包含一定数量的个体的初始群体，作为遗传 算法运行的最初群体。可基于两种思想来生成初始群体的个体： 1 )随机由编码组合成解空间的个体。该方法实现简单，但生成的个体可能在问题空间 中没有相对应的解，不具有实际意义。 2 )考虑具体问题与编码的对应关系，将问题空间中具有实际意义的解转换到编码空 间。该方法能保证个体具有实际意义，但实现相对复杂。 所以，应针对具体的编码方案和遗传算子实现方法来确定种群的初始化方法。 适应度函数 在遗传算法中，是以个体适应度的大小来确定该个体被遗传到下一代群体中的概率的。 个体的适应度越大，表明该个体所对应解的质量越高，被遗传到下一代的概率也越大。适应 度函数是用来计算个体适应度，它与实际的问题紧密关联。在实现遗传算法时，需要分析实 际问题的特点，构建适当的适应度函数，以便通过适应度反映个体的优良程度。 选择算子 遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作。选择操作是建立在对个体 的适应度进行评价的基础上。选择操作的主要目的是为了避免基因缺失，提高全局收敛性和 计算效率。常见的选择策略如下： 1 )比例选择方法：各个个体被选中的概率与其适应度大小成正比。该选择策略操作 简单，实现方便，但选择误差比较大，可能存在最好个体未被选择到下一代的情 况。 2 )最优保存策略：群体中适应度最高的个体不参加交叉运算，直接代替本代群体中 经过遗传操作后产生的适应度最低个体。保留了最优个体，但可能导致算法全局 搜索能力不强，容易陷入局部最优。 3 )确定式采样选择：可保证适应度较大的一些个体一定能够被保留在下一代，操作 比较简单。 交叉算子 遗传算法中也使用交叉算子来产生新的个体。所谓交叉运算，是指针对两个相互配对的 染色体按照某种方式相互交换其部分基因，从而形成新的个体【12 1 。交叉运算是遗传算法区 别于其它进化算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法。 交叉算子的设计和实现与所研究的问题密切相关。要求它既不要太多的破坏个体编码串 8 蔺埘虫害面向q 。s 组播路由优化的模拟退火自适应遗传算法 兰州大学硕士学位论文 中表示优良性状的优良模式，又要能够有效地产生出一些较好的新个体模式，即交叉算子需 保证前一代中优秀个体的性能在后一代的新个体中尽可能得到遗传和继承。最常用的交叉策 略是单点交叉，此外，还有多点交叉、正交交叉等。 变异算子 在遗传算法中也引入了变异算子来产生新的个体。所谓变异运算，是指将个体染色体 编码串中的某些基因座上的基因值用其它等位基因来替代，从而形成一个新的个体【1 3 1 。 从遗传算法运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方 法，它决定了遗传算法的全局搜索能力；而变异算法是产生新个体的辅助方法，它决定了遗 传算法的局部搜索能力，同时也维持群体的多样性，防止出现早熟现象。同交叉算子一样， 变异算子的具体设计也往往与研究实际问题密切相关。 交叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使 得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。 2 3 3 自适应遗传算法a g a 2 3 3 1a g a 来源 遗传算法是一种模拟生物进化过程的全局收敛算法。一些理论研究证明传统的简单遗传 算法很难收敛到全局最优解，简单遗传算法在多峰值复杂优化问题的求解过程中容易陷入局 部最优解。 简单遗传算法等算法采用控制参数事先确定和固定不变的方法，在优化过程中的效果较 差，无法满足在遗传进化中对这些参数动态的、变化的要求，尤其是交叉概率和变异概率。 因而无法比较客观地反映种群中个体的个性化要求。从生物迸化的角度看，这种做法虽然考 虑到了种群对环境的适应能力的模拟，但是却忽略了种群跟随环境进化时，个体发育和遗传 行为( 如交配频率、交配范围、变异程度和繁殖数量等) 随之变化的自适应特性这是影 响控制参数不变的算法性能和效率的根本原因f 1 4 ，1 5 】。 为了保证遗传算法的全局收敛性，首先要维持种群中个体的多样性，避免有效基因的丢 失；另一方面，为了加快算法的收敛速度，就要使种群较快地向最优状态转移，这样会减少 种群的多样性，使算法容易陷入局部最优状态。在较快地找到最优解的同时，防止早熟收敛 是遗传算法中一个较难解决的问题。目前对遗传算法的控制参数( 种群大小、交叉概率和变 9 鞠埘文掌 面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 异概率等) 的设置还缺少合理的理论指导。由于参数选择关系到遗传算法的收敛性、稳定性 和计算时间等诸多因素，并且影响到计算结果的质量和系统的性能。因此，对于遗传算法控 制参数的选取成为研究热点。 对于遗传算法控制参数中的交叉概率和变异概率的选择是影响算法行为和性能的关键， 它们的好坏直接影响遗传算法的收敛性。由于简单遗传算法中交叉概率和变异概率取固定 值，交叉概率与变异概率不能反映进化的过程，从而容易出现早熟或随机漫游的现象。对于 交叉概率，若交叉概率太大，新个体产生速度就越快，适应度高的个体被破坏的可能性也就 越高；若交叉概率太小，就不易产生新个体，算法容易陷入停滞状态。对于变异概率，若变 异概率取值太大，遗传算法就变成了纯粹的随机搜索算法；若变异概率太小，也不易产生新 个体1 1 6 , 1 7 1 。 种群中的个体，即基因串中的相似样板被称为“模式”，模式表示基因串中某些特征位 相同的结构。由模式定理知，具有低阶、短定义距及平均适应度高于种群平均适应度的模式 在子代中呈指数增长。遗传算法初期，模式集中在适应度较低的个体上，若采用较小的交叉 概率和变异概率，种群很难产生出优秀新个体。遗传算法后期，模式向适应度较高的个体集 中，倘若仍采用较大的交叉概率和变异概率，容易破坏优良模式，使算法陷入局部收敛。要 为某个特定的优化问题设置好交叉概率和变异概率，算法需要经过反复地试验且难以丰富种 群中优良解的多样性。因此，产生了使交叉概率和变异概率能够随着适应度自动改变的自适 应遗传算法【1 8 1 。 2 3 3 2a g a 概述 1 9 9 4 年s r i n i v a s 等人提出了一种根据适应度动态调整交叉概翠p c 和变异概翠厶的自适 应遗传算法a o a ( a d a p t i v eg e n e t i ca l g o r i t h m ) 【1 9 】。 在s r i n i v a s 等人提出的自适应遗传算法中，交叉概率b 和变异概率按如下公式进行 自适应调整。 f 掣 心厶 p c = t 一名 。州喀 【 k 2 f r a n 接收新解，其中r a n 是【o ，1 ) 区间的随 机数。令t e m = s t e m 。6 为略小于1 0 的系数。 麓埘虫霉 面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 若满足收敛条件，则退火过程结束；否则，转2 ) 。 3 ) 模拟退火算法依据m e t r o p o l i s 准则接收新解，它除接受优化解外，还在一定限度内 接受恶化解，这是模拟退火算法优于其他局部搜索算法的优势所在。 1 2 ：啕斜虫害面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 第三章q o s 组播路由的模拟退火自适应遗 传算法s a a g a 3 1 引言 当前，采用启发式算法来解决q o s 组播路由问题，但是这些算法要么太复杂而难于求 解，要么太费时而不能实际应用。因此，许多学者提出应用模拟退火算法( s i m u l a t e d a n n e a l i n g a l g o r i t h m ，s a ) 2 2 2 3 1 、蚂蚁算法( a n t a l 9 0 r i t l 瑚，a a ) 2 4 , 2 5 】和神经网络( n e u m ln e 似o r kn n ) 【2 6 2 7 】 等智能方法来求解组播路由问题。 而且近年来一些学者采用标准遗传算法解决q o s 组播路由问题，但是这种方法存在以 下缺陷： 1 )采用二进制编码机制，此种编码在精度要求高时，个体编码串很长，算法的搜索 空间急剧扩大，造成算法的效能低下； 2 )交叉概率和变异概率采用“事先确定+ 固定不变”的方法，这使参数缺乏动态性， 无法满足算法的动态性要求，易出现早熟收敛； 3 )局部搜索能力较差，算法容易陷入局部最优解； 4 )选择算子没有采用最佳个体保留策略，无法保证能够收敛到全局最优。 本文针对以上不足，提出q o s 组播路由的模拟退火自适应遗传算法s a a g a ( s i m u l a t e d a n n e a l i n ga d a p t i v eg e n e t i ca l g o r i t h m ) 。首先，本算法采用基于路径的编码方式，既可以避 免编码、译码复杂的问题，又可以适应网络规模的不断增长。其次，将模拟退火算法引入到 本算法中，不仅可以提高本算法的运行效率，而且避免本算法出现早熟现象。最后，对自适 应遗传算法进行改进，根据适应度动态调整交叉概率和变异概率，使其在最大适应度值、平 均适应度值和最小适应度值之间自动做出改变，不但加快算法的收敛速度，而且提高算法的 运行效率。 3 2s a a g a 算法 3 2 1s a a g a 算法基本思路 本文针对q o s 多约束组播路由问题提出模拟退火自适应遗传算法s a a g a ，首先构造候 1 3 蔺_ _ ，乞害 面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 选路径集，寻找从源节点到各目的节点所有满足多约束的路径，然后从每个目的节点的候选 路径集中随机选择一条路径组成组播树。为了提高本算法的性能，引入模拟退火算法的思想， 有效克服了自适应遗传算法收敛速度慢和易陷入局部最优的缺陷。本算法具有以下特点： 1 )采用基于路径编码方式。这种编码方式使生成的个体均代表一棵组播树。有效地解 决自适应遗传算法在编码、译码方面的困难；码长仅取决于组播节点个数，不会随 着网络规模的增大而变长，本算法能够适应大型网络： 2 )采用基于惩罚算子的适应度评价，保证本算法更加客观衡量个体优劣； 3 )采取基于最佳保留策略的选择算子。能够保证群体中较优的个体不被交叉和变异算 子破坏，而直接保留至下一代群体中，保证本算法能收敛到全局最优； 4 )引入模拟退火思想。在自适应遗传算法a g a 的交叉和变异算子中引入模拟退火思 想。虽然a g a 算法有较强的全局搜索性能，但它的局部搜索能力较差，在进化后 期搜索效率较低。而模拟退火算法却具有较强局部搜索能力，并能使搜索过程避免 陷入局部最优解，但它不适合全局搜索。因此，将模拟退火算法和自适应遗传算法 有机结合在一起，取长补短，一方面可以有效抑制a g a 算法的早熟现象，同时也 缓解单独利用a g a 算法的选择压力，另一方面，也可以有效抑制本算法陷入局部 最优解： 5 )改进自适应遗传算法a g a 。本文对a g a 算法进行改进，即b 和厶随适应度的变 化在最大适应度值、平均适应度值和最小适应度值之间自动做出改变。虽然a g a 算法的交叉概率和变异概率随适应度自动改变，但它比较适用于进化的后期，对于 进化的初期很不利，最终出现早熟收敛。为此，我们对交叉概率和变异概率做了进 一步改进，使得群体不会处于一种近似停滞不变的状态； 6 )设计修补环路算子。可有效解决个体在执行交叉和变异算子后可能会出现环路的问 题。 综上，模拟退火自适应遗传算法s a a g a 思想可归纳为：自适应遗传算法是对初始种群 进行优化，模拟退火算法是对进化中的种群进行优化，并将优化后的种群返回给遗传操作进 行下一步操作。温度较高时1 ，s a a g a 算法表现为对种群的“广搜索”，温度较低时，s a a g a 算法表现为对种群的“细搜索”。由此可见，s a a g a 算法结合了模拟退火算法和自适应遗 传算法的优点，弥补各自的缺点，为优化组播路由提供了有效途径。 1 4 ：犄t r e e 虫害面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 3 2 2s a a g a 算法描述 设斟啪为一个无向赋权图，其中y = k 为网络节点集，可表示交换机、路由器或 子网；庐 p ) ，p ： 龟，v k v n 为网络链路。 设从节点f 到节点_ ，的路径尸( 力是一个节点序列，其中对序列中任意的砖，v f 砘和它 的后续节点v j + j ，有链路e = e 晒，其有五个权值函数：端到端时延d e l a y ( e ) ：e 啵+ 、 时延抖动歹娩“p ) ：e 崾+ 、代价c o s t ( e ) e - r + , 丢包率l o s s ( e ) ：e - - r + 和可用带宽b a n d w i d t h ( e ) e 幔+ 。并且链路e 具有如下性质： n - i 1 ) 在时延上：d e l a y ( p ( i , j ) ) = d d a y ( e 3 i = 1 n - i 2 ) 在时延抖动上：j i t t e r ( p ( i ，) ) = j i t t e r ( e i ) n - i 3 ) 在代价上：c o s t ( p ( i ，_ ) ) = c o s t ( e 1 ) n - i 4 ) 在丢包率上：l o s s ( p ( i ，j f ”= 1 一兀( 1 一l o s s ( e , ) ) 5 ) 在可用带宽上：b a n d w i d t h ( p ( i ，歹) ) = m i n ( b a n d w i d t h ( e 1 ) ) 其中q = ，m h ，吃，一l 定义3 1 ：s a a g a 算法求解q o s 组播路由问题可定义为：网络图g = ( 1 f , e ) ，组播源点 s 属于以组播目的节点集d = d l ，盔，盔) ，c j i 属于n j f = 1 ，2 ，疗。寻找一棵最优组播树d ) ， 满足： 1 ) 时延约束：d e l a y ( p ( s ，4 ) ) d 乃 2 )时延抖动约束：j i t t e r ( p ( s ，z ) ) 以 3 ) 丢包率约束：l o s s ( e ( s ，z ) ) ， 4 ) 可用带宽约束：b a n d w i d t h ( p ( s ，z ) ) 骂 5 ) 代价优化：所有满足1 到4 约束的组播树，e o s t ( t ( s ，功) 最小。 其中，p 传，彩为染色体玳功上源节点s 到目的节点函的路径。局是带宽约束，d 乃， 1 5 麓埘虫害 面向q 。s 组播路由优化的模拟退火自适应遗传算法兰州大学硕士学位论文 砒和兕，分别是目的节点谚的时延、时延抖动和丢包率约束。 3 3s a a g a 算法设计 3 3 1 流程 本文提出的模拟退火自适应遗传算法s