摘要： 论述了用启发式遗传算法解决最短路径路由的优化问题,采用可变长度染色体(路由串)和它的基因(节点)应用于编码问题,交叉操作在交叉点进行部分染色体(部分路由)交换,变异操作维持种群的多样性。该算法采用简单维护操作维护好所有的不可行的染色体。交叉操作和变异操作相结合保证了最优解的搜索能力和解的全局收敛性。计算机仿真实验表明该算法快速有效、可靠性高。

关键词: 路由, 最短路径路由, 路由优化, 遗传算法

Abstract: This paper presents a heuristic genetic algorithmic to solve shortest path routing optimization problem. Variable-length chromosomes (routing strings) and their genes (nodes) are used for encoding the problem. The crossover operation exchanges partial chromosomes (partial-routes) at positional independent crossing sites and the mutation operation maintains the genetic diversity of the population. The algorithm can cure all the infeasible chromosomes with a simple repair operation. Crossover and mutation together provide a search capability that results in improved quality of solution and enhanced rate of convergence. Computer simulations have verified that the algorithm is efficient and effective.

中图分类号: 

• TP393