TSP问题--禁忌搜索算法

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

禁忌搜索算法的步骤如下：
1.选定一个初始解X，给定一个禁忌表H。
2.若满足停止条件，则停止计算；否则，在X的邻域中选出满足禁忌要求(当某个解足够好的时候，可以打破这个禁忌准则)的候选集CANX，在CANX中选择一个评价最佳的解Xbest，令X=Xbest，更新禁忌表H，重复步骤2。

用TS解TSP问题的代码如下：

#禁忌搜索算法解TSP问题
import numpy as np
import random as rd
import copy

def disCal(path):
    dis = 0
    for i in range(len(path)-1):
        dis += distmat[path[i]][path[i+1]]
    dis += distmat[path[0]][path[-1]]
    return dis

def swap2(sol):
    neighbor = []
    for i in range(len(sol)):
        for j in range(i + 1, len(sol)):
            s = copy.deepcopy(sol)
            x = s[j]
            s[j] = s[i]
            s[i] = x
            neighbor.append(s)
    return neighbor

distmat = np.array([[0,350,290,670,600,500,660,440,720,410,480,970],
                 [350,0,340,360,280,375,555,490,785,760,700,1100],
                 [290,340,0,580,410,630,795,680,1030,695,780,1300],
                 [670,360,580,0,260,380,610,805,870,1100,1000,1100],
                 [600,280,410,260,0,610,780,735,1030,1000,960,1300],
                 [500,375,630,380,610,0,160,645,500,950,815,950],
                 [660,555,795,610,780,160,0,495,345,820,680,830],
                 [440,490,680,805,735,645,495,0,350,435,300,625],
                 [720,785,1030,870,1030,500,345,350,0,475,320,485],
                 [410,760,695,1100,1000,950,820,435,475,0,265,745],
                 [480,700,780,1000,960,815,680,300,320,265,0,585],
                 [970,1100,1300,1100,1300,950,830,625,485,745,585,0]])

if __name__ == '__main__':
    solution = [i for i in range(distmat.shape[0])]
    rd.shuffle(solution)                #随机产生初始解
    shortestDistance = disCal(solution)
    tabuList = []                       #禁忌表
    iterx, iterxMax = 0, 50
    while iterx < iterxMax:
        canSolution = swap2(solution)
        k = []
        shorterDistance = float("inf")
        for i in range(len(canSolution)):
            if disCal(canSolution[i]) < shorterDistance:
                shorterDistance = disCal(canSolution[i])
                k.append(i)
        for i in range(len(k)):
            if disCal(canSolution[k[len(k)-i-1]]) < shortestDistance:
                shortestDistance = disCal(canSolution[k[len(k)-i-1]])
                solution = canSolution[k[len(k)-i-1]]
                break
            else:
                if canSolution[k[len(k)-i-1]] not in tabuList:
                    solution = canSolution[k[len(k)-i-1]]
                    break
        if len(tabuList) < 6:
            tabuList.append(solution)
        else:
            tabuList.pop(0)
            tabuList.append(solution)
        iterx += 1
    print(solution)
    print(disCal(solution))