随着Internet的迅速普及发展,传统的Internet所能提供的“尽力而为”的服务已经不能满足不断涌现的新应用对Qos(服务质量)的要求。虽然已提出一些为这些应用提供Qos保障的模型和机制,但它们的运行基础是已知满足Qos约束的分组转发路径。传统的、基于单一度量的路由算法对求解满足Qos约束的路径的问题无能为力。必须提出新的、考虑网络Qos特性的路由选择策略,即Qos路由。已经证明Qos路由是NP完全问题,遗传算法对求解该类问题比较有效。本文采用遗传算法,对Qos单播路由、Qos多播路由两个问题作了一些探索性研究。文中针对这两个问题,分别提出了有效的编码方案,并以编码方案为基础,完成了求解Qos路由的遗传算法的构建工作。本文在以下方面有所创新:(1)为求解Qos单播路由问题的遗传算法提出一种一维二进制编码方案,并针对该编码方案提出了两种可行的个体解码思想。采用该编码方案编码的个体可有效避免路由环;遗传算法的交叉、变异算子实现简单。(2)在求解Qos多播路由问题时,考虑了路由器转发能力的限制。文中为求解Qos多播路由的遗传算法提出了二维矩阵编码方案,采用该编码方案的个体在包含连接信息的同时,还直观显示了组播树中结点度的信息,非常便于判断路由器是否满足转发能力限制。(3)求解多播路由的遗传算法采用了保持父代个体相同链路的交叉策略。在交叉运算过程中,本文提出的编码方案便于寻找相同链路。在研究过程中,以VC6为开发工具,实现了网络拓扑生成算法和求解两类Qos路由问题的遗传算法。经试算比较,算法性能良好,收敛速度较快。最后,对全文进行总结,提出了研究中的不足和对将来进一步研究的若干建议。