禁忌搜索求TSP

• 邻域：将当前解通过某种算子得到新的解的集合就是这个解的邻域，比如通过交换算子将1234->1324，那么1324就是1234的邻域的一部分
• 邻域移动是进行解转移的关键，影响整个算法的搜索速度
• 禁忌表：记录被禁止的对象，防止出现搜索循环和局部最优。一般使用FIFO
• 禁忌步长:多久之后禁忌失效，设计很关键。小了会局部最优，大了会限制搜索，错过好的解
• 候选解（candidate）：从邻域中选择若干个目标值或评价值最佳的邻居作为候选解。候选解集合的生成规则一定程度上决定了搜索的方向和邻域大小，十分关键。候选集过大增加计算内存和计算时间，过小容易过早陷入局部最优。候选集的选择一般由邻域中的邻居组成，可以选择所有邻居，也可以选择表现较好的邻居，还可以随机选择几个邻居。这里我们采用两两交换法则生成候选解集合。
• 选择邻域的策略：最好解优先，即比较所有邻域，耗时久但收敛更好。第一个改进解，即发现对一个改进解就转移，耗时少但收敛差。
• 藐视准则(特赦准则)：当某个被禁忌的移动由优于未被禁忌的移动得到的最优邻域解和历史最优解时，算法接收该移动。
• 停止准则：如最大迭代数、运行时间等

视频：

import matplotlib.pyplot as plt
import numpy as np


def make_data(dim):
    mp = np.ndarray((dim,dim))
    for i in range(dim):
        for j in range(0,i+1):
            if i==j:
                mp[i,j]=0
            else:
                v = np.random.randint(10,500)
                mp[i,j] = v
                mp[j,i] = v
    return mp


class TabuSearch:

    def __init__(self,max_tabu_size=10,candidate_num=11,asp_iter=100):
        self.max_tabu_size = max_tabu_size
        self.candidate_num = candidate_num
        self.asp_iter = asp_iter

    # 获得x通过某种操作(这里是交换)能到达的所有邻域
    def get_neighbor(self,x):
        neighbors = []
        for i in range(len(x)):
            for j in range(i + 1, len(x)):
                neighbor = x.copy()
                neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
                neighbors.append(neighbor)
        return neighbors

    # 取部分邻域作为候选集
    def get_candidates(self,neighbors):
        # 升序，返回新数组
        sorted_neighbors = sorted(neighbors,key=lambda item:self.target_function(item))
        return sorted_neighbors[:self.candidate_num]

    # 如果全部对象都被禁忌、或某对象的解禁能带来很好的影响
    # 此时会让他们重新可选
    # 特赦规则(藐视禁忌准则)
    def aspiration_criterion(self,x,best_x,cur_iter,asp_iter):
        res1,res2 = self.target_function(x) , self.target_function(best_x)
        # 得出的解比当前最优解还好 并且 迭代进行到一定次数
        return res1 < res2 and cur_iter > asp_iter
    # 目标函数
    def target_function(self,x:list):
        path = [self.start] + x + [self.start]
        cur = path[0]
        res = 0
        for nex in path[1:]:
            res += self.mp[cur,nex]
            cur = nex
        return res

    # 传入图、起始点、迭代次数
    def run(self,mp:np.ndarray,start,iter_num=1000):
        # 初始化禁忌空表
        tabu_table = []
        # 获得解维度
        dim = mp.shape[0]
        self.start = start
        self.mp = mp
        # 初始化最初的解,注意起始点是不变的
        x = filter(lambda i:i != start,range(0,dim))
        # 一个是当前解，一个是全历史最优解
        x = list(x)
        best_x = x.copy()
        # 记录过程量
        records = []
        for iter in range(iter_num):
            # 选出neighbors中所有的长度为2的子集，通过按值交换，起到2-opt的效果
            # 获得邻域
            neighbors = self.get_neighbor(x)
            # 可以再选取一部分邻域作为候选集，避免在大规模邻域中搜索
            # 注意和这个
            candidates = self.get_candidates(neighbors)
            # 选最优解
            best_candidate = candidates[0]
            # 不在禁忌表里直接设为当前解
            if best_candidate not in tabu_table:
                # 不需要将他与先前的x进行比较
                # 从而有能力跳出局部最优解
                x = best_candidate
            else:
                # 可赦免就用
                if self.aspiration_criterion(best_candidate,best_x,iter,self.asp_iter):
                    x = best_candidate
                    # 先清除，防止表中同时出现两个
                    tabu_table.remove(best_candidate)
                else:
                    # 这个最优解都不能赦免，只能用没被禁的了
                    # 所以我感觉candidate_num要比max_tabu_size大一点
                    # 不然会死循环？
                    for candidate in candidates:
                        if candidate not in tabu_table:
                            x = candidate
                            break
            # 定长禁忌表的FIFO
            if len(tabu_table) > self.max_tabu_size:
                tabu_table.pop(0)
            # 禁忌
            # 这里存入的是交换后的路径，但其实存交换操作就行(交换的下标x和y)
            tabu_table.append(x)
            # 判断当前最优是否能替代历史最优
            if self.target_function(x) < self.target_function(best_x):
                best_x = x
            records.append(self.target_function(best_x))
        return [start] + best_x +[start] , self.target_function(best_x) , records

np.random.seed(100)
city_num = 10
# mp = make_data(city_num)
mp = np.array([[  0,  18, 290, 333, 369, 353,  89, 442, 404, 360,],
 [ 18,   0, 446, 364,  63,  76, 236,  24, 300, 250,],
 [290, 446,   0, 290, 153, 238, 373, 326,  68, 410,],
 [333, 364, 290,   0, 147, 103,  96, 396, 165, 374,],
 [369,  63, 153, 147,   0, 398, 425, 395, 151, 255,],
 [353,  76, 238, 103, 398,   0, 221, 110,  14, 101,],
 [ 89, 236, 373,  96, 425, 221,   0, 453, 333, 145,],
 [442,  24, 326, 396, 395, 110, 453,   0,  59, 441,],
 [404, 300,  68, 165, 151,  14, 333,  59,   0, 203,],
 [360, 250, 410, 374, 255, 101, 145, 441, 203,   0,]] )
# print(mp)
tbs = TabuSearch()
best_x,best_y,records = tbs.run(mp,0,10)
print(best_x,best_y)
plt.plot(range(len(records)),records)
plt.show()