禁忌搜索算法是TSP问题1. TSP问题概述旅行商访问n城市，最终返回出发城市，要求每个城市只能访问一次，优化目标是最小化行程之和。
2 .示例求解结果20城市坐标： (88，16 )，42，76 )，5，76 )，69，13 )，73，56 )，100，100 )，22，92 )，48，74 )
结果如下。
3 .禁忌搜索算法设计禁忌搜索算法的核心思想是不重复已搜索过的解，以提高搜索效率本算法在求解时主要设置两个禁忌表。 在全局禁忌表和局部禁忌表上，在邻域搜索时随机配对交换两个城市的位置以获得新的路径。 其中，全局禁忌表包含迭代中最近n代的结果，局部禁忌表包含各代域搜索时遍历的新路径，全局禁忌(无全局重复搜索)和局部禁忌)邻居
3.1初始解结构禁忌搜索算法对初始解敏感，表达良好的初始解有利于提高算法的收敛速度和求解质量。 本算法尝试了两种初始化方法。 一种是随机结构法，这是最常用的初始解结构方法。 随机初始解路径图如下。
取而代之的是引入贪婪算法构建初始解。 (1)随机生成出发城市，(2)选择离现在城市最近的城市作为下一个城市，(3)重复步骤(2)直到通过所有的城市。 贪婪算法的结构路线图如下。
贪婪算法结构的初始解很好，可以看出后续的优化过程可以很快收敛到最优解。
3.2禁忌搜索算法# -*- coding: utf-8 -* -“”禁忌搜索算法求解TSP问题随机求解(0 101 )二维平面生成20点距离最小化((importmathimportrandomimportpandaspdimportmatplotlib.pyplotaspltfrommatib.) serif']=['SimHei'] #添加此选项后，可以以图形方式显示中文#计算路径距离，即评估函数defcalfitness(line )。 dis_matrix ) : dis _ sum=0dis=0foriinrange (len (line ) ) : ifilen (line (-1: dis=dis _ matrix.loc lon ) 1 ) deftraversal_search(line，dis_matrix， tabu_list ) : #邻域随机遍历搜索traversal=0#搜索次数traversal_list=[]#用于保存本地搜索的局部禁忌表traversal_value=[]# 局部解对应路径距离while traversal=traversal max : pos 1，pos2=random.randint(0，len(line )-1 ) #当前爸爸通过交换new _ line [ pos2]=new _ line [ new _ line ]生成的dis_matrix(#当前路径距离#新生成的路径不存在于全局禁忌表和本地禁忌表中，而是有效if(new_linenotintraversal_list ) ) new_line not in tabu_list ) : traversal _ list.append (new _ line ) travetrs trave value (，traversal _ list [ traversal _ value.index ] min ) traversal _ value ] dis _ matrix ) : ' '贪婪策略构建初始解' ' '
(CityCoordinates)):dis_matrix.loc[i,i]=math.pow(10,10) line = []#初始化 now_city = random.randint(0,len(CityCoordinates)-1)#随机生成出发城市 line.append(now_city)#添加当前城市到路径 dis_matrix.loc[:,now_city] = math.pow(10,10)#更新距离矩阵，已经过城市不再被取出 for i in range(len(CityCoordinates)-1): next_city = dis_matrix.loc[now_city,:].idxmin()#距离最近的城市 line.append(next_city)#添加进路径 dis_matrix.loc[:,next_city] = math.pow(10,10)#更新距离矩阵 now_city = next_city#更新当前城市 return line #画路径图def draw_path(line,CityCoordinates): x,y= [],[] for i in line: Coordinate = CityCoordinates[i] x.append(Coordinate[0]) y.append(Coordinate[1]) x.append(x[0]) y.append(y[0]) plt.plot(x, y,'r-', color='#4169E1', alpha=0.8, linewidth=0.8) plt.xlabel('x') plt.ylabel('y') plt.show()if __name__ == '__main__': #参数 CityNum = 20#城市数量 MinCoordinate = 0#二维坐标最小值 MaxCoordinate = 101#二维坐标最大值 #TS参数 tabu_limit = 50 #禁忌长度，该值应小于(CityNum*(CityNum-1)/2） iterMax = 200#迭代次数 traversalMax = 100#每一代局部搜索次数 tabu_list = [] #禁忌表 tabu_time = [] #禁忌次数 best_value = math.pow(10,10)#较大的初始值，存储最优解 best_line = []#存储最优路径 #随机生成城市数据,城市序号为0,1，2,3... CityCoordinates = [(random.randint(MinCoordinate,MaxCoordinate),random.randint(MinCoordinate,MaxCoordinate)) for i in range(CityNum)] ＃ CityCoordinates = [(88, 16),(42, 76),(5, 76),(69, 13),(73, 56),(100, 100),(22, 92),(48, 74),(73, 46),(39, 1),(51, 75),(92, 2),(101, 44),(55, 26),(71, 27),(42, 81),(51, 91),(89, 54),(33, 18),(40, 78)] #计算城市之间的距离 dis_matrix = pd.DataFrame(data=None,columns=range(len(CityCoordinates)),index=range(len(CityCoordinates))) for i in range(len(CityCoordinates)): xi,yi = CityCoordinates[i][0],CityCoordinates[i][1] for j in range(len(CityCoordinates)): xj,yj = CityCoordinates[j][0],CityCoordinates[j][1] dis_matrix.iloc[i,j] = round(math.sqrt((xi-xj)**2+(yi-yj)**2),2) # #初始化,随机构造 # line = list(range(len(CityCoordinates)));random.shuffle(line) # value = calFitness(line,dis_matrix)#初始路径距离 # 贪婪构造 line = greedy(CityCoordinates,dis_matrix) value = calFitness(line,dis_matrix)#初始路径距离 #存储当前最优 best_value,best_line = value,line draw_path(best_line,CityCoordinates) best_value_list = [] best_value_list.append(best_value) #更新禁忌表 tabu_list.append(line) tabu_time.append(tabu_limit) itera = 0 while itera <= iterMax: new_value,new_line = traversal_search(line,dis_matrix,tabu_list) if new_value < best_value:#优于最优解 best_value,best_line = new_value,new_line#更新最优解 best_value_list.append(best_value) line,value = new_line,new_value#更新当前解 #更新禁忌表 tabu_time = [x-1 for x in tabu_time] if 0 in tabu_time: tabu_list.remove(tabu_list[tabu_time.index(0)]) tabu_time.remove(0) tabu_list.append(line) tabu_time.append(tabu_limit) itera +=1 #路径顺序 print(best_line) #画路径图 draw_path(best_line,CityCoordinates) TSP系列目录 智能优化算法类别启发式算法求解TSP问题系列博文进化算法遗传算法求解TSP问题仿人智能优化算法禁忌搜索算法求解TSP问题仿自然优化算法模拟退火算法求解TSP问题群智能优化算法蚁群算法求解TSP问题群智能优化算法粒子群算法求解TSP问题总结篇五种常见启发式算法求解TSP问题改进篇遗传-粒子群算法&遗传-禁忌搜索算法求解TSP问题记录学习过程，欢迎指正