TS禁忌搜索算法求解TSP问题(Java实现)

<hr style=” border:solid; width:100px; height:1px;” color=#000000 size=1”>

一、TSP问题

TSP问题(Travelling Salesman Problem)即旅行商问题,又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类,一类是对称TSP问题(Symmetric TSP),另一类是非对称问题(Asymmetric TSP)。所有的TSP问题都可以用一个图(Graph)来描述:
在这里插入图片描述

二、禁忌搜索算法

1.算法简介

禁忌(Tabu Search)算法是一种亚启发式(meta-heuristic)随机搜索算法,它从一个初始可行解出发,选择一系列的特定搜索方向(移动)作为试探,选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解,TS搜索中采用了一种灵活的“记忆”技术,对已经进行的优化过程进行记录和选择,指导下一步的搜索方向,这就是Tabu表的建立。

2.算法思路

1、在搜索中,构造一个短期循环记忆表-禁忌表,禁忌表中存放刚刚进行过的 |T|(T称为禁忌表)个邻居的移动,这种移动即解的简单变化。
2、禁忌表中的移动称为禁忌移动。对于进入禁忌表中的移动, 在以后的 |T| 次循环内是禁止的,以避免回到原来的解,从而避免陷入循环。|T| 次循环后禁忌解除。
3、禁忌表是一个循环表,在搜索过程中被循环的修改,使禁忌表始终保持 |T| 个移动。
4、即使引入了禁忌表,禁忌搜索仍可能出现循环。因此,必须给定停止准则以避免出现循环。当迭代内所发现的最好解无法改进或无法离开它时,算法停止。

3.终止条件

1.禁忌对象:可以选取当前的值(cur)作为禁忌对象放进tabu list,也可以把和当前值在同一“等高线”上的都放进tabu list。
2.为了降低计算量,禁忌长度和禁忌表的集合不宜太大,但是禁忌长度太小容易循环搜索,禁忌表太大容易陷入“局部极优解”。
3.上述程序段中对best_so_far的操作是直接赋值为最优的“解禁候选解”,但是有时候会出现没有大于best_so_far的,候选解也全部被禁的“死锁”状态,这个时候,就应该对候选解中最佳的进行解禁,以能够继续下去。
4.终止准则:和模拟退火,遗传算法差不多,常用的有:给定一个迭代步数;设定与估计的最优解的距离小于某个范围时,就终止搜索;当与最优解的距离连续若干步保持不变时,终止搜索;
5.邻域:系统总是在初始点的邻域搜索可能解的,因而必须定义适合的邻域空间,如果解空间存在一个最优解X,初始搜索点为S0,那么如果S0不存在到达X的通路,就会使搜索陷入S0的邻域的局部最优解。可以证明如果邻域满足对称性条件,则在假设禁忌表足够长的情况下必然可搜索到全局最优解。

4.算法图解

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

5.Java代码

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.List;
  4. import java.util.Random;
  5. /*
  6. ** Create by: WSKH
  7. Date:2021-07-26
  8. Time:20:27
  9. */
  10. public class TabuSearchAlgorithm_TSP {
  11. public final int MAX_GEN = 3000;//最大的迭代次数(提高这个值可以稳定地提高解质量,但是会增加求解时间)
  12. public final int N = 100;//每次搜索领域的个数(这个值不要太大,太大的话搜索效率会降低)
  13. public final int len = 20;//禁忌长度
  14. public int cityNum ;//城市数量,手动设置
  15. public int[][] tabooList;//禁忌表
  16. public int[] Ghh;//初始路径编码
  17. public int[] bestGh;//最好的路径编码
  18. public int[] LocalGh;//当前最好路径编码
  19. public int[] tempGh;//存放临时编码
  20. public double[][] dist;//距离矩阵
  21. public int bestT;//最佳的迭代次数
  22. public double bestEvaluation;//最优解
  23. public double LocalEvaluation;//每次领域搜索的最优解(领域最优解)
  24. public double tempEvaluation;//临时解
  25. public List<Integer[]> pointList = new ArrayList<>();//每个城市的坐标
  26. public int t;//当前迭代
  27. public Random random;//随机函数对象
  28. public int l = 0;//当前禁忌表长度
  29. //外部调用接口
  30. public void Run() throws Exception {
  31. long startTime = System.currentTimeMillis();
  32. initVar();
  33. TabuSearch();
  34. long endTime = System.currentTimeMillis();
  35. System.out.println("求解用时:"+(endTime-startTime)/1000.0+"秒");
  36. }
  37. //禁忌搜索主函数
  38. public void TabuSearch(){
  39. //开始迭代,停止条件为达到指定迭代次数
  40. while (t<=MAX_GEN){
  41. //当前领域搜索次数
  42. int n = 0;
  43. LocalEvaluation = Double.MAX_VALUE;
  44. while (n <= N){
  45. //得到当前编码Ghh的邻居编码tempGh
  46. tempGh = generateNewGh(Ghh.clone(),tempGh.clone());
  47. //判断其是否在禁忌表中
  48. if(!judge(tempGh)){
  49. //如果不在
  50. tempEvaluation = evaluate(tempGh);
  51. if(tempEvaluation < LocalEvaluation){
  52. //如果临时解优于本次领域搜索的最优解
  53. //那么就将临时解替换本次领域搜索的最优解
  54. LocalGh = tempGh.clone();
  55. LocalEvaluation = tempEvaluation;
  56. }
  57. n++;
  58. }
  59. }
  60. if(LocalEvaluation < bestEvaluation){
  61. //如果本次搜索的最优解优于全局最优解
  62. //那么领域最优解替换全局最优解
  63. bestT = t;
  64. bestGh = LocalGh.clone();
  65. bestEvaluation = evaluate(bestGh);
  66. }
  67. Ghh = LocalGh.clone();
  68. //加入禁忌表
  69. enterTabooList(LocalGh.clone());
  70. t++;
  71. //System.out.println("第"+t+"代:bestEvaluation = "+bestEvaluation);
  72. }
  73. //求解完毕
  74. System.out.println("最佳迭代次数:"+bestT);
  75. System.out.println("最佳长度为:"+bestEvaluation);
  76. System.out.println("最佳路径为:");
  77. for (int i = 0; i < bestGh.length; i++) {
  78. System.out.print(bestGh[i]+"-->");
  79. }
  80. System.out.println(bestGh[0]);
  81. }
  82. //加入禁忌队列
  83. public void enterTabooList(int[] tempGh){
  84. if(l<len){
  85. //如果当前禁忌表还有空位,则直接加入即可
  86. tabooList[l] = tempGh.clone();
  87. l++;
  88. }else{
  89. //如果禁忌表已经满了,则移除第一个进表的路径,添加新的路径到禁忌表末尾
  90. //后面的禁忌编码全部向前移动一位,覆盖掉当前第一个禁忌编码
  91. for (int i = 0; i < tabooList.length-1; i++) {
  92. tabooList[i] = tabooList[i+1].clone();
  93. }
  94. //将tempGh加入到禁忌队列的最后
  95. tabooList[tabooList.length-1] = tempGh.clone();
  96. }
  97. }
  98. //判断路径编码是否存在于禁忌表中
  99. public boolean judge(int[] tempGh){
  100. int count = 0;
  101. for (int i = 0; i < tabooList.length; i++) {
  102. for (int j = 0; j < tabooList[i].length; j++) {
  103. if(tempGh[j]!=tabooList[i][j]){
  104. count++;
  105. break;
  106. }
  107. }
  108. }
  109. return count!=tabooList.length;
  110. }
  111. //领域交换,生成新解(随机指定数组中的两个数,不包括首尾,然后让这两个数进行位置互换,达到生成一个新路线的作用)
  112. public int[] generateNewGh(int[]Gh,int[]tempGh) {
  113. int temp;
  114. //将Gh复制到tempGh
  115. tempGh = Gh.clone();
  116. int r1 = 0;
  117. int r2 = 0;
  118. ////这段代码(r1==0||r2==0)是为了保证起点不受改变,如果有固定的起点的话,可以使用这几行代码
  119. // while (r1==r2||(r1==0||r2==0)){
  120. // r1 = random.nextInt(cityNum);
  121. // r2 = random.nextInt(cityNum);
  122. // }
  123. while (r1==r2){
  124. r1 = random.nextInt(cityNum);
  125. r2 = random.nextInt(cityNum);
  126. }
  127. //交换
  128. temp=tempGh[r1];
  129. tempGh[r1]=tempGh[r2];
  130. tempGh[r2]=temp;
  131. return tempGh.clone();
  132. }
  133. //生成一个初始解
  134. public int[] getInitGh() throws Exception {
  135. //固定起点为地点数组的第一个元素
  136. Ghh[0] = 0;
  137. //记录已生成的点
  138. List<Integer> indexList = new ArrayList<>();
  139. indexList.add(0);
  140. //随机生成其余点
  141. for (int i = 1; i < Ghh.length; i++) {
  142. while (true){
  143. int r = random.nextInt(cityNum);
  144. if(!indexList.contains(r)){
  145. //只有当地点不重合时才添加进列表,保证初始解中没有重复的地点
  146. indexList.add(r);
  147. Ghh[i] = r;
  148. break;
  149. }
  150. }
  151. }
  152. System.out.println("初始解:"+Arrays.toString(Ghh));
  153. return Ghh.clone();
  154. }
  155. //计算两点之间的距离(使用伪欧氏距离,可以减少计算量)
  156. public double getDistance(Integer[] place1,Integer[] place2){
  157. //伪欧氏距离在根号内除以了一个10
  158. return Math.sqrt((Math.pow(place1[0]-place2[0],2)+Math.pow(place1[1]-place2[1],2))/10.0);
  159. //return Math.sqrt((Math.pow(place1[0]-place2[0],2)+Math.pow(place1[1]-place2[1],2)));
  160. }
  161. //初始化变量
  162. public void initVar() throws Exception {
  163. cityNum = pointList.size();//城市数量为点的数量
  164. tabooList = new int[len][cityNum];//禁忌表
  165. Ghh = new int[cityNum];//初始路径编码
  166. bestGh = new int[cityNum];//最好的路径编码
  167. LocalGh = new int[cityNum];//当前最好路径编码
  168. tempGh = new int[cityNum];//存放临时编码
  169. dist = new double[cityNum][cityNum];//距离矩阵
  170. //初始化距离矩阵
  171. for (int i = 0; i < dist.length; i++) {
  172. for (int j = 0; j < dist[i].length; j++) {
  173. if(i==j){
  174. //对角线为0
  175. dist[i][j] = 0.0;
  176. }else{
  177. //计算i到j的距离
  178. dist[i][j] = getDistance(pointList.get(i),pointList.get(j));
  179. }
  180. }
  181. }
  182. //初始化参数
  183. bestT = 0;
  184. t = 0;
  185. random = new Random(520);
  186. Ghh = getInitGh();
  187. //复制当前路径编码给最优路径编码
  188. tempGh = Ghh.clone();
  189. bestGh = tempGh.clone();
  190. bestEvaluation = evaluate(bestGh);
  191. tempEvaluation = evaluate(tempGh);
  192. LocalEvaluation = Double.MAX_VALUE;
  193. }
  194. //评价函数
  195. public double evaluate(int[] path){
  196. double pathLen = 0.0;
  197. for (int i = 1; i < path.length; i++) {
  198. //起点到终点途径路程累加
  199. pathLen += dist[path[i-1]][path[i]];
  200. }
  201. //然后再加上返回起点的路程
  202. pathLen += dist[path[0]][path[path.length-1]];
  203. return pathLen;
  204. }
  205. }
  206. --------------------------------------------------------------------------
  207. 结果展示:
  208. (一)不固定起点:
  209. 初始解:[0, 21, 33, 13, 46, 36, 14, 40, 12, 6, 34, 44, 2, 35, 43, 38, 26, 15, 23, 42, 17, 25, 39, 32, 22, 19, 29, 20, 45, 7, 31, 4, 11, 47, 1, 8, 28, 37, 10, 3, 18, 30, 5, 24, 27, 41, 16, 9]
  210. 最佳迭代次数:2844
  211. 最佳长度为:12206.89917444571
  212. 最佳路径为:
  213. 40-->15-->21-->2-->33-->28-->4-->47-->41-->9-->34-->44-->23-->31-->38-->20-->12-->46-->19-->32-->45-->35-->5-->36-->18-->16-->26-->42-->29-->27-->6-->17-->43-->30-->37-->8-->7-->0-->39-->14-->11-->10-->22-->13-->24-->25-->3-->1-->40
  214. 求解用时:0.227
  215. (二)固定起点
  216. 初始解:[0, 21, 33, 13, 46, 36, 14, 40, 12, 6, 34, 44, 2, 35, 43, 38, 26, 15, 23, 42, 17, 25, 39, 32, 22, 19, 29, 20, 45, 7, 31, 4, 11, 47, 1, 8, 28, 37, 10, 3, 18, 30, 5, 24, 27, 41, 16, 9]
  217. 最佳迭代次数:2679
  218. 最佳长度为:11883.359590041817
  219. 最佳路径为:
  220. 0-->7-->21-->15-->40-->28-->1-->25-->3-->34-->44-->9-->23-->41-->4-->47-->33-->2-->39-->14-->27-->5-->36-->18-->16-->26-->42-->29-->19-->46-->20-->31-->38-->12-->24-->13-->22-->10-->11-->32-->45-->35-->6-->17-->43-->30-->37-->8-->0
  221. 求解用时:0.193

补充:以上使用的是tsplib上的数据att48,这是一个对称TSP问题,城市规模为48,其最优值为10628。tsplib地址:http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/

总结

1.算法优缺点

优点:

  1. 1、容易理解,容易实现,具有较强的通用性;
  2. 2、局部开发能力强,收敛速度很快。
  3. 3.相比于数学规划,动态规划等精确算法而言,在大规模问题上具有更好的
  4. 效果。

缺点:

  1. 1、全局开发能力弱,只能搜索到局部最优解;
  2. 2、搜索结果完全依赖于初始解和邻域的映射关系。

2.改进建议

禁忌搜索算法是一种随机算法,其求解带有偶然性,可以通过启发式的生成新解规则,来提高算法随机求解的效率,常见的有贪婪规则,精英规则等。

注:参考链接
[1] https://blog.csdn.net/cc098818/article/details/99869166
[2] https://blog.csdn.net/wangqiuyun/article/details/8816463
[3] https://baike.baidu.com/item/%E7%A6%81%E5%BF%8C%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95/6436980?fr=aladdin


文章标签:

原文连接:https://juejin.cn/post/7068627703041097758

相关推荐

翟佳:高可用、强一致、低延迟——BookKeeper的存储实现

管正雄:基于预训练模型、智能运维的QA生成算法落地

814. 二叉树剪枝 : 简单递归运用题

【综合笔试题】难度 3.5\u002F5,多解法热门二叉树笔试题

【java刷算法】牛客—剑指offer3栈、数组、递归、二分法的初步练习

leetcode 2342. Max Sum of a Pair With Equal Sum of Digits (python)

22张图带你深入剖析前缀、中缀、后缀表达式以及表达式求值

随机数索引(一题双解)【Leetcode每日(4.25)一题】C++

1260. 二维网格迁移 : 简单构造模拟题

坚持用C++刷牛客题(剑指offer专题)

日拱一卒,麻省理工教你信息安全和密码学

C语言——三种方式实现学生信息管理

快速排序及优化

萌新也能看懂的KMP算法

简答一波 HashMap 常见八股面试题 —— 算法系列(2)

素数算法(Prime Num Algorithm)

必须收藏!双目立体匹配算法:Patch Match Stereo实用详解教程

有哪些高质量的自学网站?

731. 我的日程安排表 II : 线段树(动态开点)的两种方式

LeetCode周赛302,这也太卷了,20分钟ak也只有300名……