# Tabu Search (TS)，禁忌算法

作者: 肥了个大西瓜 | 来源:发表于2018-07-04 15:12 被阅读0次

# Tabu Search (TS)，禁忌算法
awesome 禁忌搜索
【算法】禁忌搜索算法(Tabu Search，TS)超详细通俗解
2019-01-28
好码分享：开源算法框架Open Tabu Search求解VRP
Tabu
DFS（深度优先搜索）和BFS(广度优先搜索)
[观影记·禁忌]
字符串查找 js实现kmp算法
ORID35 binary search/sliding win

1 Tabu Search 介绍

TS是Local Search（LS）的扩展，是一种全局逐步寻优的全局性邻域搜索算法。

传统的LS通过迭代，不断搜寻邻域中更优的解来替换当前解，实现优化，该方式容易陷入局部最优。

TS模仿人类的记忆功能，在搜索过程中标记已经找到的局部最优解及求解过程，并于之后的搜索中避开它们。

算法通过禁忌策略实现记忆功能，通过破禁准则继承LS的强局部搜索能力。种种机制的配合，使得TS一方面具备高局部搜索能力，同时又能防止算法在优化中陷入局部最优。

2 Tabu Search 主要构成要素

（1）评价函数（Evaluation Function）：评价函数是用来评价邻域中的邻居、判断其优劣的衡量指标。大多数情况下，评价函数为目标函数。但自定义的形式也可存在，算法也可使用多个评价函数，以提高解的分散性（区分度）。

（2）邻域移动（Move Operator）：邻域移动是进行解转移的关键，又称“算子”，影响整个算法的搜索速度。邻域移动需要根据不同的问题特点来自定义，而整个邻近解空间是由当前解通过定义的移动操作构筑的所有邻域解构成的集合。

（3）禁忌表（Tabu Table, Tabu List）：禁忌表记录被禁止的变化，以防出现搜索循环、陷入局部最优。对其的设计中最关键的因素是禁忌对象（禁忌表限定的对象）和禁忌步长（对象的禁忌在多少次迭代后失效）。

禁忌表是禁忌搜索算法的核心，禁忌表的对象、步长及更新策略在很大程度上影响着搜索速度和解的质量。若禁忌对象不准确或者步长过小，算法避免陷入局部最优的能力会大打折扣；若禁忌表步长过大，搜索区域将会限制，好的解就可能被跳过。

（4）邻居选择策略（Neighbor Selection Strategy）：选择最佳邻域移动的规则。目前最广泛采用的是“最好解优先策略”及“第一个改进解优先策略”。前者需比较所有邻域，耗时较久，但解的收敛更有效；后者在发现第一个改进解就进行转移，耗时较少，但收敛效率弱于前者，对于邻域解空间较大的问题往往比较适合。

（5）破禁准则（Aspiration Criterion）：破禁准则是对于禁忌表的适度放松。当某个被禁忌的移动可得到优于未被禁忌的移动得到的最优邻域解和历史所得到的最优解时，算法应接受该移动，不受禁忌表的限制。

（6）停止规则（Stop Criterion）：禁忌搜索中停止规则的设计多种多样，如最大迭代数、算法运行时间、给定数目的迭代内不能改进解或组合策略等等。

3 Tabu Search 算法内容

3.1 Tabu Search 流程

Tabu Search流程

4 Tabu Seach Coding

4.1 Coding

/*
language: C++ 11
Author: Xing He
School: HuaZhong University of science and technology
compilier: g++.exe ACS.cpp -o ACS.exe -Ofast -std=c++11 

*/

#include<bits/stdc++.h>
using namespace std;
int type;// type == 1 全矩阵, type == 2 二维欧拉距离 
// const
const int INF = 0x3f3f3f3f;
#define sqr(x) ((x)*(x))
#define eps 1e-8
#define percent 0.9
#define MAX_ITERATION 1000
//variables
string file_name;
int N;//城市数量 
double **dis;//城市间距离 
int **TabuList;// 禁忌表
double **Delta;//邻域变化评价函数值 
bool *vis; // 标记是否被访问 
int TabuLength;
struct vertex{
    double x, y;// 城市坐标 
    int id;// 城市编号 
    
    int input(FILE *fp){
        return fscanf(fp, "%d %lf %lf", &id, &x, &y);
    }
    
}*node;


struct Path{
    int *path;//解结构 
    double L;//目标值 
    int n;//数据规模 
    void initlization(int x){
        path = new int[x];
        n = x;
        L = INF;
        return;
    }//初始化 
    
    double calc(){
        double ans = 0;
        for (int i = 0; i < n - 1; i ++)
            ans += dis[path[i]][path[i + 1]];
        L = ans + dis[path[n - 1]][path[0]];
        return ans;
    }//计算结果 
    
    double get_edge(int i, int j){
        if (i == n) i = 0;
        if (j == n) j = 0;
        if (i == -1) i = n - 1;
        if (j == -1) j = n - 1;
        return dis[path[i]][path[j]];
    }
    
    double swap_operator(int index_i, int index_j){
        double delta = 0;
        if(index_i == index_j - 1 || index_i == index_j + n - 1){ 
            delta += get_edge(index_i, index_j + 1) + get_edge(index_i - 1,index_j);
            delta -= get_edge(index_i - 1, index_i) + get_edge(index_j, index_j + 1);
        } 
        else if(index_i == index_j + 1 || index_j == index_i + n -1){
           delta += get_edge(index_j, index_i + 1) + get_edge(index_j - 1,index_i);
           delta -= get_edge(index_j - 1, index_j) + get_edge(index_i,index_i + 1);
        }
        else{
           delta += get_edge(index_j, index_i - 1) + get_edge(index_j,index_i + 1);
           delta += get_edge(index_i, index_j - 1) + get_edge(index_i,index_j + 1);
           delta -= get_edge(index_i, index_i - 1) + get_edge(index_i,index_i + 1);
           delta -= get_edge(index_j, index_j - 1) + get_edge(index_j,index_j + 1);
        }
       return delta;
    }//swap邻域计算 
    
    void print(FILE *fp){
        fprintf(fp, "Best_solution:%.0lf\n", L);
        for (int i = 0; i < n; i ++)
            fprintf(fp, "%d->", path[i] + 1);
        fprintf(fp, "%d\n", path[0] + 1);
        return;
    }//输出结果 
    
}solution, best;//当前解，最优解 

bool operator <(const Path &a, const Path &b){
        return a.L < b.L;
}

double EUC_2D(const vertex &a, const vertex &b){
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
} 

void io(){//输入
    printf("input file_name and data type\n");
    cin >> file_name >> type;
    FILE *fp = fopen(file_name.c_str(), "r");
    fscanf(fp, "%d", &N);
    node = new vertex[N + 5];
    dis = new double*[N + 5];
    double tmp = 0;
    int cnt = 0;
    if (type == 1){
        for (int i = 0; i < N; i ++){
            dis[i] = new double[N];
            for (int j = 0; j < N; j ++){
                fscanf(fp, "%lf", &dis[i][j]);
            }
        }
    }else{
        for (int i = 0; i < N; i ++)
            node[i].input(fp);      
        for (int i = 0; i < N; i ++){
            dis[i] = new double[N];
            for (int j = 0; j < N; j ++){
                dis[i][j] = EUC_2D(node[i], node[j]);// 计算距离        
            }
        }
    }
    fclose(fp);
    return;
}

int get_next(int x){
    double MIN = INF;
    int ans = 0;
    for (int i = 0; i < N; i ++){
        if (dis[x][i] < MIN && !vis[i]){
            MIN = dis[x][i];
            ans = i;
        }
    }
    return ans;
}//贪心选择下一个

void construction_init_solution(){
    int now = 0;
    vis[now] = 1;
    for (int i = 1; i < N; i ++){
        int s = get_next(now);
        solution.path[i] = s;
        now = s;
        vis[now] = 1;
    }
    solution.calc();
    best = solution;
    Delta = new double*[N];
    for (int i = 0; i < N; i ++){
        Delta[i] = new double[N];
        for (int j = 0; j < N; j ++){
            Delta[i][j] = solution.swap_operator(i, j);
        }
    }
    best.print(stdout);
}//贪心构造初始解 

void init(){
    solution.initlization(N);
    best.initlization(N);
    solution.path[0] = 0;
    TabuList = new int*[N];
    vis = new bool[N];
    TabuLength = (int)(N * percent);//设置禁忌步长 
    for (int i = 0; i < N; i ++){
        TabuList[i] = new int[N];
        vis[i] = 0;
        for (int j = 0; j < N; j ++){
            TabuList[i][j] = -TabuLength;
        }
    }//初始化禁忌表 
    
}
int r, s;
double neighbour(int round, Path sol){
    double delta = 0, MIN = 0;
    r = 0, s = 0;
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++){
            if (TabuList[i][j] + TabuLength > round) continue;
            if (Delta[i][j] < MIN){
                MIN = Delta[i][j];
                r = i;
                s = j;
            }
        }
    return MIN;
}//邻域选择操作 

void update(int i){
    if (i == -1) i = N - 1;
    if (i == N) i = 0;
    for (int j = 0; j < N; j ++){
        if (i != j){
            Delta[i][j] = solution.swap_operator(i, j);
            Delta[j][i] = solution.swap_operator(j, i);
        }
            
    }
    return;
}// 更新Delta值 

void Delta_update(){
    int index_i = r, index_j = s;
    if(index_i == index_j - 1 || index_i == index_j + N - 1){ 
        update(index_i); update(index_j); 
        update(index_i - 1); update(index_j + 1);
    }else if(index_i == index_j + 1 || index_j == index_i + N - 1){
        update(index_i); update(index_j); 
        update(index_i + 1); update(index_j - 1);
    }else{
        update(index_i); update(index_j); 
        update(index_i + 1); update(index_j - 1);
        update(index_i - 1); update(index_j + 1);
    }
}// 更新有关的变化值，当r,s交换，只有与r,s相邻的城市在进行交换的时候会受到影响，避免重复计算 

void TabuSearch(){
    for (int round = 0; round < MAX_ITERATION; round ++){
        double delta = neighbour(round, solution);
        TabuList[r][s] = round;//更新禁忌表 
        if (delta <= 0){
            swap(solution.path[r], solution.path[s]);
            Delta_update();
            solution.calc();    
        }//更新当前解 
        if (solution < best) best = solution;//更新最优解 
        printf("round:%d: best_so_far:%.0lf\n", round, best.L);
    }
}

int main(){
    srand((unsigned) time(0));//初始化随机种子 
    io();//输入 
    init();//初始化 
    construction_init_solution();//贪心构造初始解 
    TabuSearch();//禁忌搜索 
    best.print(stdout);//输出 
}

4.2 算例

满秩矩阵式 ( type = 1 )

输入文件格式为：

File_name File_type

salesman.in 1

0 1 2 2 3

2 0 3 4 2

3 2 0 4 1

3 4 5 0 5

2 4 1 4 0

输出结果为：

opt_solution:

2.例二二维坐标式 ( type = 2 )

输入文件格式为：

File_name File_type

KroA100.tsp 2

100

1 1380 939

2 2848 96

3 3510 1671

4 457 334

5 3888 666

6 984 965

7 2721 1482

8 1286 525

9 2716 1432

10 738 1325

11 1251 1832

12 2728 1698

13 3815 169

14 3683 1533

15 1247 1945

16 123 862

17 1234 1946

18 252 1240

19 611 673

20 2576 1676

21 928 1700

22 53 857

23 1807 1711

24 274 1420

25 2574 946

26 178 24

27 2678 1825

28 1795 962

29 3384 1498

30 3520 1079

31 1256 61

32 1424 1728

33 3913 192

34 3085 1528

35 2573 1969

36 463 1670

37 3875 598

38 298 1513

39 3479 821

40 2542 236

41 3955 1743

42 1323 280

43 3447 1830

44 2936 337

45 1621 1830

46 3373 1646

47 1393 1368

48 3874 1318

49 938 955

50 3022 474

51 2482 1183

52 3854 923

53 376 825

54 2519 135

55 2945 1622

56 953 268

57 2628 1479

58 2097 981

59 890 1846

60 2139 1806

61 2421 1007

62 2290 1810

63 1115 1052

64 2588 302

65 327 265

66 241 341

67 1917 687

68 2991 792

69 2573 599

70 19 674

71 3911 1673

72 872 1559

73 2863 558

74 929 1766

75 839 620

76 3893 102

77 2178 1619

78 3822 899

79 378 1048

80 1178 100

81 2599 901

82 3416 143

83 2961 1605

84 611 1384

85 3113 885

86 2597 1830

87 2586 1286

88 161 906

89 1429 134

90 742 1025

91 1625 1651

92 1187 706

93 1787 1009

94 22 987

95 3640 43

96 3756 882

97 776 392

98 1724 1642

99 198 1810

100 3950 1558

输出结果为：

best_known_solution: 21282

Reference:

# Tabu Search (TS)，禁忌算法
1 Tabu Search 介绍 TS是Local Search（LS）的扩展，是一种全局逐步寻优的全局性邻域...
awesome 禁忌搜索
禁忌搜索(Tabu Search)算法及python实现实验10 禁忌搜索算法求解tsp问题
【算法】禁忌搜索算法(Tabu Search，TS)超详细通俗解
01 什么是禁忌搜索算法？ 1.1 先从爬山算法说起爬山算法从当前的节点开始，和周围的邻居节点的值进行比较。如...
2019-01-28
Local Search 常用的local search 算法有爬山算法, 模拟退火算法, 遗传算法和禁忌查找等...
好码分享：开源算法框架Open Tabu Search求解VRP
一、前言很早之前就想写这篇文章了，由于各种不可描述的原因拖延到了现在，今儿就把坑给填上吧~ 前排提示：小伙伴们可...
Tabu
背景：Tabu来自于电影Félicité。这里扯的只是Félicité和Tabu的关系中Tabu的感受。（为了锻炼...
DFS（深度优先搜索）和BFS(广度优先搜索)
深度优先搜索算法（Depth-First-Search）深度优先搜索算法（Depth-First-Search），...
[观影记·禁忌]
因为上课的作业要求，要求去看一部葡萄牙电影，电影的名字叫禁忌（Tabu），无论是在电影内，还是电影外，这名字都是多...
字符串查找 js实现kmp算法
github地址: https://github.com/Tiger-eat-cat/search.ts[http...
ORID35 binary search/sliding win
[658] Find K closest elements 解题报告算法用什么算法Binary search ...