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

• 作者: 于汶雨 赵礼峰
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 混合遗传算法 染色体编码 Metropolis准则 k最短路径
• 年，卷（期）: 2016,（10）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 32-35,40
• 页数: 5页
• 分类号: TP301.6
• 字数: 3529字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2016.10.007

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	于汶雨	南京邮电大学理学院	2	19	2.0	2.0