随着Internet的发展,多媒体通信和分布式环境下的协同工作等应用促使了组播通信的发展。组播问题的关键在于组播路由的确定,即寻找简单、高效、健壮的组播路由算法,组播路由算法主要是用来建立一棵性能良好的组播树,并使它能够满足各种业务的服务质量(Quality of Service,QoS)需求,由于QoS组播路由带有多个QoS约束参数,而这种多约束条件下的QoS组播路由问题属于NP完全问题。这使得它与传统的路由过程不同,难以用经典的最短路径优先算法(如Bellman-Ford和Dijkstra算法)求解。对于QoS组播路由问题的研究大多都集中在采用启发式算法求解无约束组播路由问题和时延受限组播路由优化问题,然而由于这些算法都具有较高的时间复杂度而不能满足实际应用的需要。本文利用遗传算法作为求解QoS组播路由优化的算法,主要研究了四类典型的QoS组播路由问题。 首先,根据组播路由问题的特点,建立了候选路由表,采用了等长节点序列串的编码方式,针对标准遗传算法的缺点,引入模拟退火思想,该算法既提高了算法的全局收敛能力也提高了收敛速度。其次,针对目前的单约束(或无约束)组播路由问题的局限性,用遗传算法实现了一种通用的多约束QoS组播路由问题,采用基于路径的树结构编码方式,遗传算子操作过程简单,算法体现了遗传算法较强的搜索能力。再次,通过分析遗传算法和组播路由问题的特点,提出一种双种群遗传算法,通过嫁接种群来指导种群的进化方向,大大提高了算法的收敛速度。最后提出一种双染色体遗传算法来求解时延——带宽约束组播路由问题,同时在产生初始群体时,引入了求解组播路由问题的经典启发式算法思想,设计遗传算子时,采用了双变异率算子,而交叉算子是在两种染色体之间进行的,通过仿真结果验证了该算法的有效性。