改进的遗传算法求解旅行商问题
CSTR:
作者:
作者单位:

大连海事大学交通运输管理学院,辽宁大连116026.

作者简介:

于莹莹

通讯作者:

中图分类号:

TP301.6;TP18

基金项目:

国家自然科学基金项目(71271034);辽宁省教育厅科学研究一般项目(L2012173);中央高校基本科研业务费专项基金项目(3132013319, 2013YB06).


Improved genetic algorithm for solving TSP
Author:
Affiliation:

College of Transportation Management,Dalian Maritime University,Dalian 116026,China.

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    提出一种解决旅行商问题的改进遗传算法. 在传统遗传算法的基础上, 引入贪婪算法进行种群初始化; 从遗传进化代数和个体适应函数值两个方面实现遗传参数自适应调节, 在加快寻优速度的同时防止寻优陷入局部最优; 采用基于贪婪方法的启发式交叉算子优化交叉结果; 对交叉前后的种群分别实施精英个体保留策略, 保证最优基因结构得以延续. 实验结果分析表明, 改进的遗传算法可以在种群规模较小的情况下具有更可靠的寻优能力.

    Abstract:

    An improved genetic algorithm for solving traveling salesman problem(TSP) is proposed. Based on the traditional genetic algorithm, the proposed algorithm introduces the greedy method into species initialization. In order to improve the optimization speed and prevent the local minimum, the improved algorithm updates the crossover probability and mutation probability adaptively according to the evolution stages and the fitness value of individuals. The heuristic crossover operator
    based on greedy method is used to optimize the crossover results. The strategy of keeping the best individuals to propagate the optimal gene structure is introduced. The results of TSP example show that the improved algorithm can find the global optimal solution with high performance.

    参考文献
    相似文献
    引证文献
引用本文

于莹莹 陈燕 李桃迎.改进的遗传算法求解旅行商问题[J].控制与决策,2014,29(8):1483-1488

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2013-05-09
  • 最后修改日期:2013-12-06
  • 录用日期:
  • 在线发布日期: 2014-08-20
  • 出版日期:
文章二维码