改进的求解TSP问题文化蚁群优化方法

doi:10.3778/j.issn.1002-8331.2010.26.017

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (26): 49-52.DOI: 10.3778/j.issn.1002-8331.2010.26.017

改进的求解TSP问题文化蚁群优化方法

顾军华，范培培，宋庆增，刘恩海

河北工业大学计算机科学与软件学院，天津 300130

收稿日期:2009-12-15 修回日期:2010-03-23 出版日期:2010-09-11 发布日期:2010-09-11
通讯作者: 顾军华

Improved culture ant colony optimization method for solving TSP problem

GU Jun-hua，FAN Pei-pei，SONG Qing-zeng，LIU En-hai

School of Computer Science and Engineering，Hebei University of Technology，Tianjin 300130，China

Received:2009-12-15 Revised:2010-03-23 Online:2010-09-11 Published:2010-09-11
Contact: GU Jun-hua

摘要/Abstract

摘要： 在文化算法基础上提出了一种改进的用于求解TSP问题的蚁群优化算法。改进算法采用新的双层进化机制对文化算法的种群空间与信念空间进行了重新设计，用最大最小蚁群系统（MMAS）构建种群空间，在信念空间中对当前最优解进行改进的3-OPT交叉变换操作，由于采用了这种双层进化机制，种群空间获得了更高的进化效率。通过仿真实验结果表明，改进算法比传统的蚁群算法（ACO）、文化蚁群算法（CACS）效果更好，收敛速度更快，精确度更高。

关键词: 文化算法, 文化蚁群算法, 最大最小蚁群系统, 旅行商问题, 3-OPT算法

Abstract: Based on cultural algorithm，an improved Ant Colony Optimization algorithm（ACO） for Traveling Salesman Problem（TSP） has been proposed.In the improved algorithm，the population space and the belief space of cultural algorithm are redesigned.This algorithm uses double evolutionary mechanisms and the Max-Min Ant System（MMAS） to build the population space，and adopts 3-OPT cross operation for the current optimal solution in the beliefs pace.As the result of this double evolutionary mechanisms，the population space gets higher efficiency of evolution.The simulation results show that the improved algorithm is more effective than Ant Colony Optimization algorithm（ACO） and Cultural Ant Colony Algorithm（CACS），which has faster convergence speed and greater accuracy.

Key words: cultural algorithm, cultural ant colony algorithm, Max-Min Ant System（MMAS）, Traveling Salesman Problem（TSP）, 3-OPT algorithm

中图分类号:

TP18

顾军华，范培培，宋庆增，刘恩海. 改进的求解TSP问题文化蚁群优化方法[J]. 计算机工程与应用, 2010, 46(26): 49-52.

GU Jun-hua，FAN Pei-pei，SONG Qing-zeng，LIU En-hai. Improved culture ant colony optimization method for solving TSP problem[J]. Computer Engineering and Applications, 2010, 46(26): 49-52.

[1]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[2]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[3]	白首华，郭广颂，胡天彤. 交互式多目标文化算法优化多模态混合指标[J]. 计算机工程与应用, 2021, 57(17): 80-87.
[4]	陈思远，林丕源，黄沛杰. 指针网络改进遗传算法求解旅行商问题[J]. 计算机工程与应用, 2020, 56(19): 231-236.
[5]	周克良，龚达欣，张宇龙. 区域破坏重建的蚁群优化算法[J]. 计算机工程与应用, 2020, 56(14): 62-67.
[6]	刘明霞1，游晓明1，刘升2. 基于聚度的自适应动态混沌蚁群算法[J]. 计算机工程与应用, 2019, 55(3): 15-22.
[7]	胡士娟，鲁海燕，黄洋，许凯波. 求解工作量平衡多旅行商问题的改进遗传算法[J]. 计算机工程与应用, 2019, 55(17): 150-155.
[8]	陈佳，游晓明，刘升，李娟. 结合信息熵的多种群博弈蚁群算法[J]. 计算机工程与应用, 2019, 55(16): 170-178.
[9]	李娟，游晓明，刘升，陈佳. 自适应模糊蚁群系统[J]. 计算机工程与应用, 2019, 55(15): 75-81.
[10]	赵亚文，熊瑞平，乔治，梁齐齐，罗勇. 应用捕食搜索策略的改进多态蚁群算法[J]. 计算机工程与应用, 2019, 55(14): 115-121.
[11]	姚书婷，胡志华，魏晨. 多禁止时间窗约束的路径恢复问题研究[J]. 计算机工程与应用, 2019, 55(12): 265-270.
[12]	陈雷，张红梅，张向利. 自适应动态邻域布谷鸟混合算法求解TSP问题[J]. 计算机工程与应用, 2018, 54(23): 42-50.
[13]	白景波，李宏伟，陈亮，冯玉芳，刘建永. 双链量子蚁群系统及应用[J]. 计算机工程与应用, 2018, 54(21): 1-6.
[14]	巫东凯，张凤斌，席亮. 自适应混合变异克隆选择算法研究[J]. 计算机工程与应用, 2018, 54(21): 78-83.
[15]	徐小平，张东洁. 基于猴群算法求解旅行商问题[J]. 计算机工程与应用, 2018, 54(2): 144-148.

改进的求解TSP问题文化蚁群优化方法

Improved culture ant colony optimization method for solving TSP problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics