[1]赵礼峰,于汶雨.求解k最短路径问题的混合遗传算法[J].计算机技术与发展,2016,26(10):32-35.
　ZHAO Li-feng,YU Wen-yu. A Hybrid Genetic Algorithm for Solving k Shortest Path Problem[J].,2016,26(10):32-35.
点击复制

求解k最短路径问题的混合遗传算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
26
期数:
2016年10期
页码:
32-35
栏目:
智能、算法、系统工程
出版日期:
2016-10-10

文章信息/Info

Title:
 A Hybrid Genetic Algorithm for Solving k Shortest Path Problem
文章编号:
1673-629X（2016)10-0032-04
作者:
 赵礼峰; 于汶雨
 南京邮电大学 理学院
Author(s):
 ZHAO Li-feng; YU Wen-yu
关键词:
 ; 混合遗传算法; 染色体编码; Metropolis准则; k最短路径
Keywords:
 ; hybrid genetic algorithm; chromosome code; Metropolis principle; k shortest path
分类号:
TP301.6
文献标志码:
A
摘要:
 遗传算法求解问题的关键在于对问题的解进行编码，同时需要构造出适应度函数。结合k最短路径实际问题，重新定义了一种染色体编码方式，并且新构造了符合该问题的适应度函数。标准遗传算法采用固定的交叉率和变异率，在应用过程中存在收敛过慢、早熟及稳定性差的缺点。因此，提出了一种改进的自适应遗传算法，对交叉率和变异率采用自适应方式，构造了确定交叉率和变异率的公式，加快了算法收敛速度。同时结合模拟退火的Metropolis准则对子代个体的接收做出选择，克服了算法容易早熟的问题。仿真结果表明，改进后的混合遗传算法可以求解k最短路问题，并且在寻优精确度、时间效率、稳定性上均优于标准遗传算法。
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.

相似文献/References:

[1]曾文飞 王志兵.多目标设备经费分配的混合遗传优化方法[J].计算机技术与发展,2006,(01):55.
　ZENG Wen-fei,WANG Zhi-bing.Research on Optimization of Equipment Fund＇s Assignment Model Based on HGA[J].,2006,(10):55.
[2]田巧玉 古钟璧 周新志.基于混合遗传算法求解非线性方程组[J].计算机技术与发展,2007,(03):10.
　TIAN Qiao-yu,GU Zhong-bi,ZHOU Xin-zhi.Solving Systems of Nonlinear Equations with Hybrid Genetic Algorithm[J].,2007,(10):10.
[3]路致远 严洪森 沈境.基于HGA的冲压车间生产计划与调度的集成优化[J].计算机技术与发展,2007,(03):179.
　LU Zhi-yuan,YAN Hong-sen,SHEN Jing.Integrated Optimization of Production Planning and Scheduling Based on Hybrid Genetic Algorithm[J].,2007,(10):179.
[4]张志宏,吴庆波,邵立松,等.基于飞腾平台TOE协议栈的设计与实现[J].计算机技术与发展,2014,24(07):1.
　ZHANG Zhi-hong,WU Qing-bo,SHAO Li-song,et al. Design and Implementation of TCP/IP Offload Engine Protocol Stack Based on FT Platform[J].,2014,24(10):1.
[5]梁文快,李毅. 改进的基因表达算法对航班优化排序问题研究[J].计算机技术与发展,2014,24(07):5.
　LIANG Wen-kuai,LI Yi. Research on Optimization of Flight Scheduling Problem Based on Improved Gene Expression Algorithm[J].,2014,24(10):5.
[6]黄静,王枫,谢志新,等. EAST文档管理系统的设计与实现[J].计算机技术与发展,2014,24(07):13.
　HUANG Jing,WANG Feng,XIE Zhi-xin,et al. Design and Implementation of EAST Document Management System[J].,2014,24(10):13.
[7]侯善江[],张代远[][][]. 基于样条权函数神经网络P2P流量识别方法[J].计算机技术与发展,2014,24(07):21.
　HOU Shan-jiang[],ZHANG Dai-yuan[][][]. P2P Traffic Identification Based on Spline Weight Function Neural Network[J].,2014,24(10):21.
[8]李璨,耿国华,李康,等. 一种基于三维模型的文物碎片线图生成方法[J].计算机技术与发展,2014,24(07):25.
　LI Can,GENG Guo-hua,LI Kang,et al. A Method of Obtaining Cultural Debris’ s Line Chart Based on Three-dimensional Model[J].,2014,24(10):25.
[9]翁鹤,皮德常. 混沌RBF神经网络异常检测算法[J].计算机技术与发展,2014,24(07):29.
　WENG He,PI De-chang. Chaotic RBF Neural Network Anomaly Detection Algorithm[J].,2014,24(10):29.
[10]刘茜[],荆晓远[],李文倩[],等. 基于流形学习的正交稀疏保留投影[J].计算机技术与发展,2014,24(07):34.
　LIU Qian[],JING Xiao-yuan[,LI Wen-qian[],et al. Orthogonal Sparsity Preserving Projections Based on Manifold Learning[J].,2014,24(10):34.
[11]赵礼峰,王小龙. 图的Steiner最小树问题的混合遗传算法[J].计算机技术与发展,2014,24(10):110.
　ZHAO Li-feng,WANG Xiao-long. Hybrid Genetic Algorithm of Graphical Steiner Tree Problem[J].,2014,24(10):110.

更新日期/Last Update: 2016-11-25