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

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (6): 71-73.

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

孙玲玲¹,贾智平¹,陈亚南²,卢昕³

1.山东大学计算机科学与技术学院，济南 250061
2.山东建筑大学计算机学院，济南 250014
3.北京石油化工学院经济管理学院，北京 102600

收稿日期:2007-06-14 修回日期:2007-08-13 出版日期:2008-02-21 发布日期:2008-02-21
通讯作者: 孙玲玲

Improved genetic algorithm solving QoS multicast routing problem

SUN Ling-ling¹,JIA Zhi-ping¹,CHEN Ya-nan²,LU Xin³

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

摘要/Abstract

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

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组播路由问题的改进遗传算法[J]. 计算机工程与应用, 2008, 44(6): 71-73.

SUN Ling-ling¹,JIA Zhi-ping¹,CHEN Ya-nan²,LU Xin³. Improved genetic algorithm solving QoS multicast routing problem[J]. Computer Engineering and Applications, 2008, 44(6): 71-73.