Abstract: To overcome the problem of easily falling into local optimum solution in the application of genetic algorithm in anycast routing, a new anycast routing algorithm based on an improved genetic algorithm is proposed by introducing the chaos disturbance operator and the dissimilarity method. Simulation results show that the proposed algorithm has a good ability of global search, which can avoid the precocious phenomenon as far as possible. By the presented method, one can efficiently and quickly find the optimal path with low cost from multiple anycast routings that meet the needs of the bandwidth and delay constraints. The analysis of the experimental results further demonstrates the proposed algorithm can accelerate the convergence rate and improve the success rate of finding the optimal solutions.

Key words: chaos genetic algorithm, anycast routing, delay constraint, dissimilarity

摘要： 为解决遗传算法应用于选播路由时存在的易于陷入局部最优问题，结合混沌扰动算子和相异度方法，提出了一种基于改进的遗传算法的选播路由算法。仿真实验结果表明，该算法具有较强的全局搜索能力，较好地解决了“早熟”收敛问题，能够快速、有效地从多个选播成员中找到满足带宽约束和时延限制，且代价最小的最优路径。通过分析仿真实验数据，证明了算法具有较快的收敛速度，且提高了找到最优解的成功率。

关键词: 混沌遗传算法, 选播, 时延限制, 相异度