Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (6): 71-73.

• 学术探讨 • Previous Articles     Next Articles

Improved genetic algorithm solving QoS multicast routing problem

SUN Ling-ling1,JIA Zhi-ping1,CHEN Ya-nan2,LU Xin3   

  1. 1.Department of Computer Science and Technology,Shandong University,Ji’nan 250061,China
    2.Department of Computer,Shandong Jianzhu University,Ji’nan 250014,China
    3.Department of Economics Management,Beijing Institute of Petrochimical Technology,Beijing 102600,China
  • Received:2007-06-14 Revised:2007-08-13 Online:2008-02-21 Published:2008-02-21
  • Contact: SUN Ling-ling

求解QoS组播路由问题的改进遗传算法

孙玲玲1,贾智平1,陈亚南2,卢 昕3   

  1. 1.山东大学 计算机科学与技术学院,济南 250061
    2.山东建筑大学 计算机学院,济南 250014
    3.北京石油化工学院 经济管理学院,北京 102600
  • 通讯作者: 孙玲玲

Abstract: In this paper,QoS multicast routing problem in embedded network digital video monitoring system is studied,and an improved genetic algorithm is presented to solve the problem.Genetic algorithm is a new global optimal algorithm simulating evolution and widely used to solve all kinds of NP-hard problems.It is suitable to solve multicast routing problem,but the standard genetic algorithm is easy to get into prematurity,and at the end of the algorithm,it runs slowly.In order to overcome the phenomenon,the author adopts initial population uniform building method and self-adaptive mutation to restrain prematurity and introduce ordering to scale fitness to improve convergence speed.Simulation shows that the improved algorithm is efficient and effective,and can find the best solution quickly.It can satisfy limited resource and real-time the system requests.

摘要: 遗传算法是一种非常适合求解QoS组播路由问题的全局优化算法。针对算法运行初期易陷入早熟现象,运行后期收敛速度慢的不足,进行了改进,采用初始群体均衡生成法和自适应变异操作可以很好地抑制早熟现象,引入排序对适应度进行拉伸,从而加快了算法的收敛速度。在嵌入式视频监控系统上进行仿真实验,结果表明改进后的遗传算法收敛速度快,性能好,可以满足系统资源有限和实时性的要求。