基于遗传算法的最短路径路由优化算法

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

Shortest Path Routing Optimization Algorithms Based on Genetic Algorithms

This paper presents a heuristic genetic algorithmic solve to shortest path routing optimization problem. Variable- length chromosomes (routing strings) and their genes (nodes) have been used for encoding the problem. The crossover opera- tion that exchanges partial chromosomes (partial- routes) at posi- tional independent crossing sites and the mutation operation maintain the genetic diversity of the population. The proposed 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 veri- fied that this algorithm is efficient and effective.