摘要
文章提出的任意两点间k条最优路径问题的遗传算法,采用节点的自然路径作为染色体编码,根据路径节点的连接实施染色体的交叉操作,将节点路径块作为染色体的变异基因块实施变异操作。算法结构简明,收敛速度快,可应用于求解大规模网络中的多条最优路径问题。
A genetic algorithm to search k optimal paths between arbitrary two modes in a graph is presented.The chromosome coding employs natural path representation by connecting nodes.Corresponding crossover method of exchanging part genes of two chromosomes by connectible node,and mutation method of generating a path block between two genes in a chromosome as mutation block gene are designed.Simulation results show the validity of the algorithm.The proposed algorithm can be applied to large-scale network to solve multiple optimal paths.
出处
《计算机工程与应用》
CSCD
北大核心
2006年第12期100-101,113,共3页
Computer Engineering and Applications
基金
陕西省教育厅专项科研基金资助项目(编号:05JK269)
关键词
遗传算法
最短路径
k条最优路径
基因块变异
genetic algorithm,shortest path,multiple optimal paths,block mutation
