基于遗传算法的QoS多播路由优化算法  

QoS Multicast Routing Optimization Algorithm Based on Genetic Algorithms

作　　者：孙宝林[1] 李腊元[1] 

机构地区：[1]武汉理工大学计算机科学与技术学院

出　　处：《计算机工程》2005年第14期70-73,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(60172035;90304018);湖北省自然科学基金资助项目(2004ABA014);湖北省高等学校教学研究基金资助项目(2003A002)

摘　　要：研究了带宽、延时、延时抖动和分组丢失率约束以及费用最小的QoS多播路由优化问题,提出了一种启发式遗传算法。该算法采用可变长度染色体(路由串)和它的基因(节点)应用于编码问题。交叉操作在交叉点进行部分染色体(部分路由)交换,变异操作维持种群的多样性。该算法采用简单维护操作维护好所有的不可行的染色体。交叉操作和变异操作相结合保证了最优解的搜索能力和解的全局收敛性。计算机仿真实验证明该算法快速有效,可靠性高。This paper studies the bandwidth, delay, delay jitter, and packet loss constrained least-cost multicast routing problem which is known to be NP-complete, and presents a heuristic genetic algorithmic to solve the problem. Variable-length chromosomes (routing strings) and their genes (nodes) have been used for encoding the problem. The crossover operation that exchanges partial chromosomes (partial-routes) at positional independent crossing sites and the mutation operation maintain the genetic diversity of the population. The proposed algorithm can cure all the infeasible chromosomes with a simple repair operation. Crossover and mutation together provide a search capability that results in improved quality of solution and enhanced rate of convergence. Computer simulations have verified that this algorithm is efficient and effective.

关 键 词：多播路由 QOS 路由优化 遗传算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]