改进蚁群优化方法求解立体表面TSP问题

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (19): 46-48.

改进蚁群优化方法求解立体表面TSP问题

徐华丽，苏守宝

皖西学院信息工程学院，安徽六安 237012

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-07-01 发布日期:2011-07-01

Improved ant optimization method for travelling salesman problems on cuboid

XU Huali，SU Shoubao

School of Information Engineering，West Anhui University，Liu’an 237012，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-07-01 Published:2011-07-01

摘要/Abstract

摘要： 给出立体表面TSP问题的数学模型，提出一种改进的蚁群优化算法，用于解决立体表面TSP问题。该算法能快速找到最优路径或近似最优路径，得到的解质量较高且计算时间短。实验方法表明，改进后的蚁群算法在TSP的求解中，收敛速度和全局寻优能力均得到较大的提高。

关键词: 全局优化, 改进蚁群算法, 路径规划, 立方体, 旅行商问题

Abstract: This paper gives a mathematical model for solving travelling salesman problems on a cuboid and proposes an improved Ant Colony Optimization algorithom（ACO） to solve the travelling salesman problems on a cuboid.The improved algorithm can obtain the global optimal solution or an approximate solution which is greatly close to the optimal solution，and propose the high-quality solutions within shortest time.The experimental results demonstrate that this improved method has much higher convergence speed than that of the basic ant colony algorithm，and can jump over the region of the local minimum，and escape from the trap of a local minimum successfully.

Key words: global optimization, improved ant colony algorithm, path planning, cuboid, traveling salesman problem

徐华丽，苏守宝. 改进蚁群优化方法求解立体表面TSP问题[J]. 计算机工程与应用, 2011, 47(19): 46-48.

XU Huali，SU Shoubao. Improved ant optimization method for travelling salesman problems on cuboid[J]. Computer Engineering and Applications, 2011, 47(19): 46-48.

[1]	槐创锋，郭龙，贾雪艳，张子昊. 改进A*算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(8): 244-248.
[2]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[3]	廖列法，李浩瀚，李帅，朱合隆，李志军. 结合Winner-Take-All的足球机器人控制策略研究[J]. 计算机工程与应用, 2021, 57(7): 136-143.
[4]	朱佳莹，高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273.
[5]	刘建宇，范平清. 基于改进的RRT*-connect算法机械臂路径规划[J]. 计算机工程与应用, 2021, 57(6): 274-278.
[6]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[7]	王迪，李彩虹，郭娜，刘国名，高腾腾. 基于模糊势场法的移动机器人局部路径规划[J]. 计算机工程与应用, 2021, 57(6): 212-218.
[8]	蒋林，方东君，雷斌，李维刚. 单目视觉移动机器人导航算法研究现状及趋势[J]. 计算机工程与应用, 2021, 57(5): 1-9.
[9]	马向华，张谦. 改进蚁群算法在机器人路径规划上的研究[J]. 计算机工程与应用, 2021, 57(5): 210-215.
[10]	杨凌耀，张爱华，张洁，宋季强. 栅格地图环境下机器人速度势实时路径规划[J]. 计算机工程与应用, 2021, 57(24): 290-295.
[11]	王琛，茅健. 基于时间窗模型的双向机器人路径规划方法[J]. 计算机工程与应用, 2021, 57(23): 287-294.
[12]	赵伟，吴子英. 双层优化A*算法与动态窗口法的动态路径规划[J]. 计算机工程与应用, 2021, 57(22): 295-303.
[13]	成怡，郝密密. 改进深度强化学习的室内移动机器人路径规划[J]. 计算机工程与应用, 2021, 57(21): 256-262.
[14]	张子然，黄卫华，陈阳，章政，李梓远. 基于双向搜索的改进蚁群路径规划算法[J]. 计算机工程与应用, 2021, 57(21): 270-277.
[15]	涂睿，王文格，卢成阳. 移动机器人实时采样路径重规划[J]. 计算机工程与应用, 2021, 57(20): 157-163.