基因池操作遗传算法的应用层组播路由优化

来源：计算机工程与应用杂志2019年第21期北京时间：

作者：刘庆，王洋，李星，李红叶

单位：1.陕西复杂系统控制与智能信息处理重点实验室，西安 710048；2.西安理工大学 自动化与信息工程学院，西安 710048；3.西安邮电大学 计算机学院，西安 710121

摘要：在应用层组播系统中，负责数据转发的终端节点不具备线速转发能力，较重的转发负载会引起拥塞。以拥塞节点为根的整个子路由树将与源节点失联。为解决由拥塞导致应用层组播稳定性差的问题，将构造最优组播树的过程抽象为有度约束的最小代价Steiner树问题。提出了一种用于构造节点转发能力受限应用层组播树的遗传算法，算法以组播树上各节点的直接前驱对其进行遗传表达，便于节点出度的统计。为使遗传操作适用于直接前驱编码，引入了“基因池”的概念并以此为基础实现了交叉与变异。针对度约束导致产生非可行解的问题，提出将组播树对度约束的超出量作为一个新的优化目标，从而以多目标优化的方式得到Pareto前沿，并从Pareto前沿上截取满足度约束的解作为最终输出，避免了使用惩罚函数法的求得非可行解的风险。仿真实验表明，提出的遗传算法能够构造节点转发能力受限的应用层组播路由树，具有良好的求解可靠性。

关键词：应用层组播,遗传算法,约束松弛,多目标优化