文章目录

• 一、TSP问题
• 二、禁忌搜索算法
• • 1.算法简介
  • 2.算法思路
  • 3.终止条件
  • 4.算法图解
  • 5.Java代码
• 总结
• • 1.算法优缺点
  • 2.改进建议

一、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代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/*
**  Create by: WSKH
    Date:2021-07-26
    Time:20:27
*/

public class TabuSearchAlgorithm_TSP {
    public  final int MAX_GEN = 3000;//最大的迭代次数(提高这个值可以稳定地提高解质量，但是会增加求解时间)
    public  final int N = 100;//每次搜索领域的个数(这个值不要太大，太大的话搜索效率会降低)
    public  final int len = 20;//禁忌长度
    public  int cityNum ;//城市数量，手动设置
    public  int[][] tabooList;//禁忌表
    public  int[] Ghh;//初始路径编码
    public  int[] bestGh;//最好的路径编码
    public  int[] LocalGh;//当前最好路径编码
    public  int[] tempGh;//存放临时编码
    public  double[][] dist;//距离矩阵
    public  int bestT;//最佳的迭代次数
    public  double bestEvaluation;//最优解
    public  double LocalEvaluation;//每次领域搜索的最优解（领域最优解）
    public  double tempEvaluation;//临时解
    public  List<Integer[]> pointList = new ArrayList<>();//每个城市的坐标
    public  int t;//当前迭代
    public  Random random;//随机函数对象
    public int l = 0;//当前禁忌表长度

    //外部调用接口
    public void Run() throws Exception {
        long startTime = System.currentTimeMillis();
        initVar();
        TabuSearch();
        long endTime = System.currentTimeMillis();
        System.out.println("求解用时："+(endTime-startTime)/1000.0+"秒");
    }
    //禁忌搜索主函数
    public void TabuSearch(){
        //开始迭代，停止条件为达到指定迭代次数
        while (t<=MAX_GEN){
            //当前领域搜索次数
            int n = 0;
            LocalEvaluation = Double.MAX_VALUE;
            while (n <= N){
                //得到当前编码Ghh的邻居编码tempGh
                tempGh = generateNewGh(Ghh.clone(),tempGh.clone());
                //判断其是否在禁忌表中
                if(!judge(tempGh)){
                    //如果不在
                    tempEvaluation = evaluate(tempGh);
                    if(tempEvaluation < LocalEvaluation){
                        //如果临时解优于本次领域搜索的最优解
                        //那么就将临时解替换本次领域搜索的最优解
                        LocalGh = tempGh.clone();
                        LocalEvaluation = tempEvaluation;
                    }
                    n++;
                }
            }
            if(LocalEvaluation < bestEvaluation){
                //如果本次搜索的最优解优于全局最优解
                //那么领域最优解替换全局最优解
                bestT = t;
                bestGh = LocalGh.clone();
                bestEvaluation = evaluate(bestGh);
            }
            Ghh = LocalGh.clone();
            //加入禁忌表
            enterTabooList(LocalGh.clone());
            t++;
           //System.out.println("第"+t+"代：bestEvaluation = "+bestEvaluation);
        }
        //求解完毕
        System.out.println("最佳迭代次数:"+bestT);
        System.out.println("最佳长度为:"+bestEvaluation);
        System.out.println("最佳路径为:");
        for (int i = 0; i < bestGh.length; i++) {
            System.out.print(bestGh[i]+"-->");
        }
        System.out.println(bestGh[0]);
    }
    //加入禁忌队列
    public void enterTabooList(int[] tempGh){
        if(l<len){
            //如果当前禁忌表还有空位，则直接加入即可
            tabooList[l] = tempGh.clone();
            l++;
        }else{
            //如果禁忌表已经满了，则移除第一个进表的路径，添加新的路径到禁忌表末尾
            //后面的禁忌编码全部向前移动一位，覆盖掉当前第一个禁忌编码
            for (int i = 0; i < tabooList.length-1; i++) {
                tabooList[i] = tabooList[i+1].clone();
            }
            //将tempGh加入到禁忌队列的最后
            tabooList[tabooList.length-1] = tempGh.clone();
        }
    }
    //判断路径编码是否存在于禁忌表中
    public boolean judge(int[] tempGh){
        int count = 0;
        for (int i = 0; i < tabooList.length; i++) {
            for (int j = 0; j < tabooList[i].length; j++) {
                if(tempGh[j]!=tabooList[i][j]){
                    count++;
                    break;
                }
            }
        }
        return count!=tabooList.length;
    }
    //领域交换，生成新解(随机指定数组中的两个数，不包括首尾，然后让这两个数进行位置互换，达到生成一个新路线的作用)
    public int[] generateNewGh(int[]Gh,int[]tempGh) {
        int temp;
        //将Gh复制到tempGh
        tempGh = Gh.clone();

        int r1 = 0;
        int r2 = 0;
        这段代码(r1==0||r2==0)是为了保证起点不受改变，如果有固定的起点的话，可以使用这几行代码
//        while (r1==r2||(r1==0||r2==0)){
//            r1 = random.nextInt(cityNum);
//            r2 = random.nextInt(cityNum);
//        }
        while (r1==r2){
            r1 = random.nextInt(cityNum);
            r2 = random.nextInt(cityNum);
        }
        //交换
        temp=tempGh[r1];
        tempGh[r1]=tempGh[r2];
        tempGh[r2]=temp;
        return tempGh.clone();
    }
    //生成一个初始解
    public int[] getInitGh() throws Exception {
        //固定起点为地点数组的第一个元素
        Ghh[0] = 0;
        //记录已生成的点
        List<Integer> indexList = new ArrayList<>();
        indexList.add(0);
        //随机生成其余点
        for (int i = 1; i < Ghh.length; i++) {
            while (true){
                int r = random.nextInt(cityNum);
                if(!indexList.contains(r)){
                    //只有当地点不重合时才添加进列表，保证初始解中没有重复的地点
                    indexList.add(r);
                    Ghh[i] = r;
                    break;
                }
            }
        }
        System.out.println("初始解："+Arrays.toString(Ghh));
        return Ghh.clone();
    }
    //计算两点之间的距离（使用伪欧氏距离，可以减少计算量）
    public double getDistance(Integer[] place1,Integer[] place2){
        //伪欧氏距离在根号内除以了一个10
        return Math.sqrt((Math.pow(place1[0]-place2[0],2)+Math.pow(place1[1]-place2[1],2))/10.0);
        //return Math.sqrt((Math.pow(place1[0]-place2[0],2)+Math.pow(place1[1]-place2[1],2)));
    }
    //初始化变量
    public void initVar() throws Exception {
        cityNum = pointList.size();//城市数量为点的数量
        tabooList = new int[len][cityNum];//禁忌表
        Ghh = new int[cityNum];//初始路径编码
        bestGh = new int[cityNum];//最好的路径编码
        LocalGh = new int[cityNum];//当前最好路径编码
        tempGh = new int[cityNum];//存放临时编码
        dist = new double[cityNum][cityNum];//距离矩阵
        //初始化距离矩阵
        for (int i = 0; i < dist.length; i++) {
            for (int j = 0; j < dist[i].length; j++) {
                if(i==j){
                    //对角线为0
                    dist[i][j] = 0.0;
                }else{
                    //计算i到j的距离
                    dist[i][j] = getDistance(pointList.get(i),pointList.get(j));
                }
            }
        }
        //初始化参数
        bestT = 0;
        t = 0;
        random = new Random(520);
        Ghh = getInitGh();
        //复制当前路径编码给最优路径编码
        tempGh = Ghh.clone();
        bestGh = tempGh.clone();
        bestEvaluation = evaluate(bestGh);
        tempEvaluation = evaluate(tempGh);
        LocalEvaluation = Double.MAX_VALUE;
    }
    //评价函数
    public double evaluate(int[] path){
        double pathLen = 0.0;
        for (int i = 1; i < path.length; i++) {
            //起点到终点途径路程累加
            pathLen += dist[path[i-1]][path[i]];
        }
        //然后再加上返回起点的路程
        pathLen += dist[path[0]][path[path.length-1]];
        return pathLen;
    }
}
--------------------------------------------------------------------------
结果展示：
（一）不固定起点：
初始解：[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]
最佳迭代次数:2844
最佳长度为:12206.89917444571
最佳路径为:
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
求解用时：0.227秒
（二）固定起点
初始解：[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]
最佳迭代次数:2679
最佳长度为:11883.359590041817
最佳路径为:
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
求解用时：0.193秒

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

总结

1.算法优缺点

优点：

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

缺点：

    1、全局开发能力弱，只能搜索到局部最优解；

    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