禁忌搜索理解与c++实现解决旅行商问题

忘是亡心i 2023-05-21 08:58 9阅读 0赞

## 禁忌搜索 理解与c++实现 解决旅行商问题 ##

首先介绍一下旅行商问题本身，

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

和最小生成树有点类似，不同的是，每个地点只能走一次，并且需要返回开始的地点。

TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。

旅行推销员问题是图论中最著名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。

迄今为止，这类问题中没有一个找到有效算法。倾向于接受NP完全问题（NP-Complete或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。

所以考虑用禁忌搜索尝试解决，禁忌搜索的资料好像也比较少。

## 禁忌搜索 ##

禁忌搜索（Tabu Search，TS，又称禁忌搜寻法）是一种现代启发式算法，由美国科罗拉多大学教授Fred Glover在1986年左右提出的，是一个用来跳脱局部最优解的搜索方法。其先创立一个初始化的方案；基于此，算法“移动”到一相邻的方案。经过许多连续的移动过程，提高解的质量。

**先介绍最核心的思路：**

通过改进局部搜索，以跳脱局部最优解。

在一定时间里不找以前选择过的解，在一定情况下可以特赦。

原理听起来很简单，但是实现起来其实细节很多，这里以前选择过的解是广义上的，不一定是解本身，可以是类似的转移动作。

**介绍一下几个名词**

**邻域**:  
下一步所有可能的解的集合。

**领域动作**：  
产生领域的方法，在tsp问题中，为交换两个地方的位置。

**候选集**：  
有的时候领域数量比较多，不把所有领域都做为候选集。可以采取一定的选取方式，或是随机，或是最优的前k个，亦或是别的方式。选择出候选集。

**禁忌表**  
存储已经走过的解，当时间超过禁忌长度的时候，就可以释放。

**禁忌长度**:  
禁忌表生效的时间，禁忌长度越短，内存占用越少，解禁范围越大(搜索范围上限越大)，容易造成循环搜索，过早陷入局部最优。反之相反。

**特赦规则**：  
当有的解存在于禁忌表中时，不能一味的全部舍弃，当满足一定的规则时，就可以将他特赦，也就是参与选择，一般有以下几种特赦规则。  
（1）基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特赦；  
（2）基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；  
（3）基于影响力的规则，可以特赦对目标值影响大的对象。

**候选集**：  
候选集的大小，过大增加计算内存和计算时间，过小过早陷入局部最优。候选集的选择一般由邻域中的邻居组成，可以选择所有邻居，也可以选择表现较好的邻居，还可以随机选择几个邻居。

**评价函数**：  
评价函数分为直接评价函数和间接评价函数。  
直接评价函数：上述例子，均直接使用目标值作为评价函数。  
间接评价函数：反映目标函数特性的函数（会比目标函数的计算更为简便，用以减少计算时间等）。

**终止规则**  
禁忌搜索是一个启发式算法，我们不可能让搜索过程无穷进行，所以一些直观的终止规则就出现了  
（1）确定步数终止，无法保证解的效果，应记录当前最优解；  
（2）频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；  
（3）目标控制原则，如果在一个给定步数内，当前最优值没有变化，可终止计算。

## 由此可见 ##

我认为禁忌搜索是一种思想，上面的参数多到出奇，禁忌的方法也不限于狭义的解，例如在tsp问题中，将所有领域进行编号，禁忌的是领域的编号，在状态转换后，领域编号所对应的解已经不同，但是仍然放在禁忌表中。所以我认为禁忌搜索灵活且可拓展性大。具体到自己实现的时候，也确实遇到很多困难。

网上分析了一位大佬的代码，照着分析了一下。并自己划分了一下功能。

我将一次禁忌搜索分为进行K次小搜索

初始化全局最优解，禁忌表
    循环K次小型搜索
    	初始化搜索相关解(小型搜索最优解，特赦最优解，迭代过程中最优解)
    	迭代N次
    		1.遍历邻域
    			if 在禁忌表中，更新特赦最优解
    			else 不在表中,更新迭代最优解
    		2.判断特设最优解是否满足特赦条件（常见为两种）
    		3.选择迭代最优解进行转移，并更新禁忌表//可用优先队列 但是禁忌表往往规模不大
    	检查全局最优解和搜索最优解

按照这个思路写了代码，相关注意点也写在了注释里

#include<bits/stdc++.h>
    using namespace std;
    #define rand(a,b) ((rand()%(b-a))+a)
    const int INF=INT_MAX;
    const int K=25;//小型搜索的次数
    const int ITERATIONS=100 ;//小型搜索中的迭代次数
    const int TABU_SIZE=10;//禁忌长度
    const int SWAPSIZE=5;//交换数目 ，理解为候选集，此代码中没有用到
    
    int city[60][2];//记录城市坐标
    double adj[60][60];//记录城市之间的距离
    int nowPath[60];//当前路径
    int finalBestPath[60];//最优路径
    int TabuList[2000][3];//第一维度 邻域id 第二维度 0:start 1:end 2.tabu
    //原文件里还有个dis但是个人觉得没有必要 因为没有复用到
    //在最大规模为60的问题中 邻域数量最大为60*59/2 给到2000是足够的
    
    
    
    void readAndInit(int n);
    void getRandomOrder(int path[],int n);//将path初始化为随机序列 值域[0,n)
    int TabuSearch(int n);//禁忌搜索主体
    int smallSearch(int n);//小型搜索
    double getPathValue(int path[],int n);//获取给定路径的数值
    
    
    int main(){
        
        int n=17;
         readAndInit(n);//读入数据以及举例 数据初始化
         TabuSearch(n);
    
    
    
    }
    
    void readAndInit(int n){
        
        for(int i=0;i<n;i++)
            for(int j=0;j<=i;j++){
        
                scanf("%lf",&adj[i][j]);
                adj[j][i]=adj[i][j];
            }
    /*
     * for(int i=0;i<n*2;i++)
                scanf("%d",&city[i/2][i%2]);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                adj[i][j]=sqrt((city[i][0]-city[j][0])*(city[i][0]-city[j][0])+(city[i][1]-city[j][1])*(city[i][1]-city[j][1]));
    
     */
    }
    
    
    
    int TabuSearch(int n){
        
        int finalDis=INF;
        //初始化禁忌表
        int now=0;
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++){
        
                TabuList[now][0]=i;
                TabuList[now][1]=j;
                TabuList[now][2]=0;
                now++;
            }
        //
        for(int i=0;i<K;i++){
        //值得注意 每次搜索禁忌表是共享的 也就是新的小搜索不会重置禁忌表
            int smallSearchDis=smallSearch(n);
            if(finalDis>smallSearchDis){
        //如果此次小型搜索的最优解优于finalDis,则更新
                finalDis=smallSearchDis;
                memcpy(finalBestPath,nowPath,sizeof (nowPath));//路径复制
            }
    
        }
    
    
        //show
        cout<<finalDis<<'\n';
        for(int i=0;i<n;i++)
            printf("->%d",finalBestPath[i]);
    
    
    }
    
    int smallSearch(int n){
        
        getRandomOrder(nowPath,n);
        double bestDis=getPathValue(nowPath,n);//初始化小型搜索最优解
    
        int pardon[2], curBest[2];//特赦最优解和搜索最优解
        pardon[0]=pardon[1]=curBest[0]=curBest[1]=INF;//初始化
        int LNum=n*(n-1)/2;//邻域数量
        for(int i=0;i<ITERATIONS;i++){
        //迭代
    
            for(int j=0;j<LNum;j++){
        //领域搜索
                swap(nowPath[TabuList[j][0]],nowPath[TabuList[j][1]]);
                double tmpDis=getPathValue(nowPath,n);
                if(TabuList[j][2]==0){
        //没有被禁忌
                    if(tmpDis<curBest[1]){
        
                        curBest[0]=j;
                        curBest[1]=tmpDis;
                    }
                }
                else{
        //被禁忌
                    if(tmpDis<pardon[1]){
        
                        pardon[0]=j;
                        pardon[1]=tmpDis;
                    }
                }
                swap(nowPath[TabuList[j][0]],nowPath[TabuList[j][1]]);
            }
            //邻域搜索结束
            //判断特设最优解是否满足特赦条件
            //第一个条件对应领域全被禁忌，在邻域数量大于禁忌长度时不可能出现
            //第二个条件似乎存疑，此刻curBest并没有更新到bestDis上，
            //如果此时curBest比pardon更优，则curBest无法被更新，可能这样是增加搜索前面的可能性？
            //另一方面如果第二个条件成立 必然出现在另一次小型搜索过程中
            //因为重新搜索并没有重置禁忌表，但bestDis被重置，在同一次小型搜索中不可能满足第二个条件
            if(curBest[1] == INF || pardon[1] < bestDis){
        
                curBest[0]=pardon[0];
                curBest[1]=pardon[1];
            }
            //尝试更新 小型搜索的最优解bestDis
            if(curBest[1]<bestDis){
        
                bestDis=curBest[1];
                //交换位置
                swap(nowPath[TabuList[curBest[0]][0]],nowPath[TabuList[curBest[0]][1]]);
                //更新禁忌表 可考虑用其他数据结构维护 例如链表、优先队列维护禁忌表，在禁忌表更新上不是一个数量级
                TabuList[curBest[0]][2]=TABU_SIZE;
                for(int j=0;j<LNum;j++)
                    if(TabuList[j][2]>0)
                        TabuList[j][2]--;
            }
            //随机性可能导致某一次搜索永远在某一个较高点，附近邻域都没有比他大的，即便是禁忌表特赦也没有用
    
        }
        return bestDis;
    
    
    
    
    }
    
    void getRandomOrder(int path[],int n){
        
        //srand(time(0));//保证结果可复现 注释此句
        for(int i=0;i<n;i++)
            path[i]=i;
        for(int i=0;i<n;i++)
            swap(path[i],path[rand(i,n)]);
    }
    
    double getPathValue(int path[],int n){
        
        double value=adj[path[n-1]][path[0]];
        for(int i=0;i<n-1;i++)
            value+=adj[path[i]][path[i+1]];
         return value;
    }

用tsp的数据集测试了一下，效果确实拔群。  
我是用的是gr17，大部分都能找到最优解，偶尔几次为近似解。  
数据集提供在百度网盘，有兴趣可以自己去测试。  
[链接][Link 1] 提取码: wtan

[Link 1]: https://pan.baidu.com/s/1u3NCoU7aPX3VuYqIAxHJlA