电子学报 ›› 2001, Vol. 29 ›› Issue (4): 506-509.

• 论文 • 上一篇    下一篇

基于精确罚函数法的遗传算法求解时延约束组播路由问题

郭 伟, 席裕庚   

  1. 上海交通大学自动化研究所,上海 200030
  • 收稿日期:1999-11-29 修回日期:2000-10-28 出版日期:2001-04-25 发布日期:2001-04-25

Solving Delay Constrained Multicast Routing Problem with Genetic Algorithm Based on Accuracy Penalty Function

GUO Wei, XI Yu-geng   

  1. Institute of Automation,Shanghai Jiaotong University,Shanghai 200030,China
  • Received:1999-11-29 Revised:2000-10-28 Online:2001-04-25 Published:2001-04-25

摘要: 有时延约束的组播问题是通信网络多点路由优化问题中的重要部分,已被证明是NP-complete问题.本文提出了一种基于罚函数法的启发式遗传算法以求解该问题,并讨论了违反时延约束不可行解的罚函数选取问题,进化过程中采用适于此类问题的动态交配概率、变异概率以提高算法的收敛速度.最后分析了算法的复杂度.仿真表明,本文算法是有效的、稳定的.

关键词: 时延约束, 组播, 遗传算法, 精确罚函数, 计算复杂度

Abstract: Delay constrained multicast problem is an important part of multipoint routing optimization problem and has been proved to be a NP-Complete problem.The paper provides a heuristic genetic algorithm based on penalty function method to solve the problem,and discusses how to select the penalty function for infeasible solutions which violate the constraint.Dynamic cross probability and mute probability suiting for this kind of problems have been adopted to accelerate the convergence speed.And algorithm complexity is analyzed.Simulations show that the algorithm is effective and stable.

Key words: delay constraint, multicast, genetic algorithm, accuracy penalty function, computation complexity

中图分类号: