计算机技术与发展2016，Vol.26Issue(10)：32-35,40,5.DOI:10.3969/j.issn.1673-629X.2016.10.007
求解k最短路径问题的混合遗传算法
A Hybrid Genetic Algorithm for Solving k Shortest Path Problem
摘要
Abstract
The key for the genetic algorithm is coding and the need to construct the fitness function. Combined with actual k shortest path problem,a new chromosome coding method is redefined and a new fitness function is constructed. The standard genetic algorithm adopts fixed crossover rate and mutation rate,and exists the defects of low convergence,prematurity and poor stability. Therefore,an improved a-daptive genetic algorithm is proposed,using the adaptive way for the crossover rate and mutation rate,the formula for determining them is construct to accelerate the convergence speed. At the same time,combined with the Metropolis principle of simulated annealing to choose the receiver of the offspring,the algorithm overcomes the problem of premature. The simulation shows that the improved hybrid genetic algorithm can solve the k shortest path problem,and it is superior to the standard genetic algorithm in optimization accuracy,time efficien-cy and stability.关键词
混合遗传算法/染色体编码/Metropolis准则/k最短路径Key words
hybrid genetic algorithm/chromosome code/Metropolis principle/k shortest path分类
信息技术与安全科学引用本文复制引用
赵礼峰,于汶雨..求解k最短路径问题的混合遗传算法[J].计算机技术与发展,2016,26(10):32-35,40,5.基金项目
国家自然科学基金资助项目(61070234,61071167) （61070234,61071167）
