求解k最短路径问题的混合遗传算法  

A Hybrid Genetic Algorithm for Solving k Shortest Path Problem

作　　者：赵礼峰[1] 于汶雨 

机构地区：[1]南京邮电大学理学院,江苏南京210023

出　　处：《计算机技术与发展》2016年第10期32-35,40,共5页Computer Technology and Development

基　　金：国家自然科学基金资助项目(61070234;61071167)

摘　　要：遗传算法求解问题的关键在于对问题的解进行编码,同时需要构造出适应度函数。结合k最短路径实际问题,重新定义了一种染色体编码方式,并且新构造了符合该问题的适应度函数。标准遗传算法采用固定的交叉率和变异率,在应用过程中存在收敛过慢、早熟及稳定性差的缺点。因此,提出了一种改进的自适应遗传算法,对交叉率和变异率采用自适应方式,构造了确定交叉率和变异率的公式,加快了算法收敛速度。同时结合模拟退火的Metropolis准则对子代个体的接收做出选择,克服了算法容易早熟的问题。仿真结果表明,改进后的混合遗传算法可以求解k最短路问题,并且在寻优精确度、时间效率、稳定性上均优于标准遗传算法。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 adaptive 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 efficiency and stability.

关 键 词：混合遗传算法 染色体编码 METROPOLIS准则 k最短路径 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]