一种适用于求解TSP问题的改进的禁忌算法

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (1): 57-59.

一种适用于求解TSP问题的改进的禁忌算法

武妍,周欣

同济大学计算机科学与工程系，上海 200092

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-01-01 发布日期:2008-01-01
通讯作者: 武妍

Meliorative tabu search algorithm for TSP problem

WU Yan,ZHOU Xin

Department of Computer Science and Engineering，Tongji University，Shanghai 200092，China

Received:1900-01-01 Revised:1900-01-01 Online:2008-01-01 Published:2008-01-01
Contact: WU Yan

摘要/Abstract

摘要： 利用传统的禁忌算法的基本思想，针对TSP问题，提出了一种改进的禁忌算法（MTS）。该算法在初始解的生成，邻域结构及禁忌策略方面进行了大的改进，充分地利用了问题本身的启发式信息与禁忌算法的优点。算法首先通过对城市分区，然后对区域连接，生成初始解；同时生成每个城市的k邻居列表，利用k邻居列表和改进的禁忌策略来突破局部最优。通过对CHN144问题及若干TSPLIB中问题的求解，结果表明所提算法能够以较快速度求得较好的满意解。

关键词: 禁忌算法, 启发式算法, 旅行商问题

Abstract: Based on the basic concepts of traditional Tabu search algorithm，a meliorative Tabu search algorithm for solving TSP has been proposed.This algorithm has great improvement in initial solution’s production，neighbor structure and taboo strategy. Furthermore，it makes full use of heuristic information and Tabu search algorithm’s advantages.At first，this algorithm divides the cities into certain areas.Then，it connects these areas into a path，so that，we can get the initial solution.Meanwhile，we produce the cities k-neighbor list and use them with the improved taboo strategies to break through the local optimum.In this paper，we apply the algorithm to solve the CHN144 problem and some problems in TSP library（TSPLIB）.The result shows that the novel algorithm can achieve satisfied solution with satisfied speed.

Key words: Tabu search algorithm, heuristic algorithm, Traveling Salesman Problem

武妍,周欣. 一种适用于求解TSP问题的改进的禁忌算法[J]. 计算机工程与应用, 2008, 44(1): 57-59.

WU Yan,ZHOU Xin. Meliorative tabu search algorithm for TSP problem[J]. Computer Engineering and Applications, 2008, 44(1): 57-59.

[1]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[2]	卜冠南，刘建华，姜磊，张冬阳. 一种自适应分组的蚁群算法[J]. 计算机工程与应用, 2021, 57(6): 67-73.
[3]	张呈玲，李进金，林艺东. 基于OE-概念格的形式背景属性约简[J]. 计算机工程与应用, 2021, 57(15): 82-89.
[4]	瞿拓思，曹海燕，许方敏，方昕，王秀敏. 大规模MIMO系统中优化导频分配方案研究[J]. 计算机工程与应用, 2020, 56(8): 60-65.
[5]	孟鑫，杨琴，郝婷婷，张洁，曹策俊. 不同订单分配和算法下的拣货路径优化组合[J]. 计算机工程与应用, 2020, 56(23): 229-236.
[6]	李雅丽，王淑琴，陈倩茹，王小钢. 若干新型群智能优化算法的对比研究[J]. 计算机工程与应用, 2020, 56(22): 1-12.
[7]	陈思远，林丕源，黄沛杰. 指针网络改进遗传算法求解旅行商问题[J]. 计算机工程与应用, 2020, 56(19): 231-236.
[8]	易成岐，郭鑫，童楠楠，窦悦，陈东，王建冬. 基于启发式社团发现模型的创新态势研判算法[J]. 计算机工程与应用, 2020, 56(15): 74-79.
[9]	周克良，龚达欣，张宇龙. 区域破坏重建的蚁群优化算法[J]. 计算机工程与应用, 2020, 56(14): 62-67.
[10]	胡晓敏，梁天毅，王明丰，李敏. 新型树启发式搜索算法的机器人路径规划[J]. 计算机工程与应用, 2020, 56(11): 164-171.
[11]	葛显龙1，2，薛桂琴1. 不确定环境下多品类共同配送路径优化[J]. 计算机工程与应用, 2019, 55(9): 264-270.
[12]	迟宗正，董绍正，郭童，任志磊，周宽久，郭禾. 求解风力发电机布局问题的超启发式算法研究[J]. 计算机工程与应用, 2019, 55(7): 220-225.
[13]	尚正阳1，顾寄南2，唐仕喜2，孙晓红2. 高效求解三维装箱问题的剩余空间最优化算法[J]. 计算机工程与应用, 2019, 55(5): 44-50.
[14]	刘明霞1，游晓明1，刘升2. 基于聚度的自适应动态混沌蚁群算法[J]. 计算机工程与应用, 2019, 55(3): 15-22.
[15]	侯屿1，2，秦小林2，彭皓月1，2，张力戈1，2. 全局调距和声特征选择算法[J]. 计算机工程与应用, 2019, 55(2): 21-27.