一种求解最短路径路由的遗传优化算法

A genetic optimization algorithm for shortest path routing

将可变长度染色体——路由串和它的基因——节点应用于编码问题,交叉操作,在交叉点进行部分染色体(路由串)交换,变异操作,以维持种群的多样性。使用该算法进行简单操作,可以维护好所有不可行的染色体;交叉操作和变异操作相结合,能保证最优解的搜索能力和解的全局收敛性。实验结果证明,该算法收敛快,可靠性高。

Variable-length chromosomes--routing strings and their genes--nodes are used for encoding. The crossover operation exchanges partial chromosomes （partial-routes） at positional independ- ent crossing sites, and the mutation operation maintains 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. The simulation shows that the algorithm converges fast and is reliable.