基于改进萤火虫算法求解旅行商问题
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然基金项目(61772416)


Solving Traveling Salesman Problem Based on Improved Firefly Algorithm
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 增强出版
  • |
  • 文章评论
    摘要:

    鉴于TSP问题是古老的组合优化难题,而萤火虫算法在求解函数优化问题中表现出优良的性能,因此,本文利用改进的萤火虫算法求解TSP问题.首先,在分析了旅行商问题的特点后,采用整数编码的方式来表示萤火虫的位置.然后,在标准萤火虫算法的位置更新过程中引入了对数递减的惯性权重来影响萤火虫的迭代过程,同时结合了遗传算法中的选择,交叉,变异以及进化逆转操作来提高每一次迭代中种群的多样性及种群的搜索能力,并将改进的算法解决TSP问题.最后,通过Matlab仿真实验表明改进的算法在求解TSP问题时具有更好收敛速度和优化效果.

    Abstract:

    Traveling Salesman Problem (TSP) is an oldest combinatorial optimization problem, and Firefly Algorithm (FA) shows excellent performance to complicated function optimization. Hence, in this study, we used improved FA to solve TSP. Firstly, after the characteristics of TSP are analyzed, and the method of integer encoding is adopted to set the position of fireflies. Then, the logarithmic adjustment factor is introduced in the standard FA. Meanwhile, we combine the crossover, mutation, and reverse operation in Genetic Algorithm (GA) to improve the population diversity and search ability of each iteration, and it is applied to solve TSP. Finally, the numerical experiments show that the proposed algorithm has faster convergence speed and optimization effect.

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

王艳,王秋萍,王晓峰.基于改进萤火虫算法求解旅行商问题.计算机系统应用,2018,27(8):219-225

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2018-01-04
  • 最后修改日期:2018-01-23
  • 录用日期:
  • 在线发布日期: 2018-08-04
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号