基于精确罚函数法的遗传算法求解时延约束组播路由问题

摘要

有时延约束的组播问题是通信网络多点路由优化问题中的重要部分，已被证明是NP-complete问题.本文提出了一种基于罚函数法的启发式遗传算法以求解该问题，并讨论了违反时延约束不可行解的罚函数选取问题，进化过程中采用适于此类问题的动态交配概率、变异概率以提高算法的收敛速度.最后分析了算法的复杂度.仿真表明，本文算法是有效的、稳定的.