一种最短路由问题的遗传算法研究

A Research of a Genetic Algorithm for Shortest Path Routing Problem

研究最短路由问题的遗传算法.采用可变长度染色体的编码方法,在固定网络和随机网络环境下,用C语言得出的仿真结果及与Dijkstra算法相比表明:大多解与Dijkstra算法的解相同,存在少数的不同解偏离不大;种群越大,路由的失败比率越小,收敛的速率越慢;当种群一定,增大网络规模时,解的质量下降,网络收敛速率急剧提高.

Variable-length chromosomes routing problem of a genetic algorithm. and their genes have been used for solving the shortest path Under random and fixed network, computer simulations with C and comparing with Dijkstra algorithm showed that most of the results are equal to the results of Dijkstra. Meanwhile, the results showed that the larger the population-sizing, the smaller the failure of ratio and the slower the rate of convergence. With population-sizing being fixed, the larger the population-sizing, the poorer the quality of results, and the higher rate of convergence.