文档介绍：166 微 电 子 学 与 计 算 机 2003 年第 23 卷第 5 期
一种基于改进遗传算法的多播路由选择方长，效率降低;文献【2]针对延时约束提出一种 节点‘出发的图‘(V,E)的子树，它包括D 的所有
算法，但该算法易过早收敛。文献[3]也提出了一种 节点(以k 来表示节点个数)和(V-D)的任意子集，
遗传算法的解决方案，但该算法采用单点交叉算 将其定义为T=(�r�Er)，其中，V,C V ,E,C E。令p(di)
法，收敛速度不如人意。一个好的算法应该简单、快 表示从源节点试ED 到目的节点的路径，则该多播
捷、全局性好，本文提出一种在改进遗传算法基础 树 的时延 为由源节点 。到各 目的节 点路径时延 的最
上的考虑多种约束的多播路由算法，在保证全局收 大值 即:
敛的基础上，大大提高了收敛速度。本算法属于源 ����d(T)=max(E�E,g)d(e)�d�ED)
路由算法，即每个节点都要拥有整个网络的状态信 ��该 多播树 的费用定义为 :
息。路由计算只在源点进行 。 ������e(7)=7-..,,c(e)
��该 多播树 的带 宽定义为:
2 多播路由 问题 的网络模 型 �����6(乃=m in{b(e)���ET
��将 通信网络用有向图G (V,E)表示，V 表示每 ��假 定多播树的最大时延限制为0 ，带宽限制为
收稿 日期:2005-07-28 。，本文多播路由优化问题的目标就是寻求满足上
基金项 目: 国家 863 计划重大专项资助项 目(20 02A A 10 30 61) 述两个 约束的多播路 由树 . 同时使得总 费用最小 。20 0 6 年 第 23 卷 第 5 期 微 电 子 学 与 计 算 机 167
用公 式 表 示 为 ��( 5)交叉操作: