????????本篇文章是博主在最化優(yōu)學習、人工智能等領域?qū)W習時，用于個人學習、研究或者欣賞使用，并基于博主對相關等領域的一些理解而記錄的學習摘錄和筆記，若有不當和侵權之處，指出后將會立即改正，還望諒解。文章分類在最優(yōu)化算法：

???????最優(yōu)化算法（1）---《基于禁忌搜索算法（TS）的TSP（Python實現(xiàn)）》

基于禁忌搜索算法（TS）的TSP（Python實現(xiàn)）

目錄

基于禁忌搜索算法（TS）的TSP（Python實現(xiàn)）

1.項目介紹? ? ? ?

2.程序代碼

3.運行結果

---

1.項目介紹? ? ? ?

????????基于禁忌搜索算法（TS）的TSP（Traveling Salesman Problem，旅行商問題），涉及一種用于解決TSP的優(yōu)化方法。TSP是一個經(jīng)典的組合優(yōu)化問題，目標是尋找一條最短路徑，使得旅行商可以訪問每個城市恰好一次并返回起點城市。

????????TS算法作為一種啟發(fā)式優(yōu)化算法，在TSP求解中具有廣泛的應用。相較于傳統(tǒng)的窮舉或貪婪算法，TS算法通過引入禁忌列表和鄰域結構來更全面地探索解空間，從而更有可能找到較為優(yōu)秀的近似最優(yōu)解。

????????禁忌搜索算法從一個初始解開始，在每次迭代中根據(jù)鄰域結構生成新的解，并根據(jù)目標函數(shù)對其質(zhì)量進行評估。若新解優(yōu)于當前最優(yōu)解且未出現(xiàn)在禁忌列表中，則接受該解作為當前最優(yōu)解；否則，尋找下一個最佳候選解。同時，禁忌列表會記錄一段時間內(nèi)禁止選擇的解，以避免陷入循環(huán)或重復訪問相似解的情況。

????????在TSP問題上，鄰域結構通常包括交換兩個城市的位置、翻轉子路徑等操作，而目標函數(shù)則是路徑長度。禁忌搜索通過不斷迭代搜索和更新禁忌列表，逐步改進當前路徑，直至滿足結束條件為止。

在基于TS算法求解TSP問題時，禁忌搜索的核心思想包括以下幾個方面：

1. 禁忌列表：記錄已經(jīng)探索過的路徑或解，以避免下一步重復探索相同的路徑或解。
2. 鄰域結構：定義了TSP解空間中可行解之間的相鄰關系，如通過交換、插入等操作生成新的解。
3. 目標函數(shù)：通常是TSP問題中路徑長度的計算，用于評估每個解的質(zhì)量。

TS算法求解TSP的基本步驟包括：

• 初始化：隨機生成初始路徑
• 迭代搜索：根據(jù)鄰域結構和目標函數(shù)，通過禁忌搜索不斷調(diào)整路徑，并更新禁忌列表，記錄當前最優(yōu)路徑
• 終止條件：達到預設的迭代次數(shù)或滿足特定條件時結束搜索，返回最優(yōu)路徑

????????通過利用TS算法求解TSP問題，可以有效地尋找到較為優(yōu)秀的旅行路線，雖不能保證找到全局最優(yōu)解，但通常能獲得接近最優(yōu)解的結果。

---

2.程序代碼

""""
題目：基于禁忌搜索算法的TSP
作者：Rainbook
最終修改時間：2023.12.30
"""
import math
import random
import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.pylab import mpl
import numpy as npplt.rcParams['font.sans-serif'] = ['Microsoft YaHei']  # 使用微軟雅黑字體
plt.rcParams['axes.unicode_minus'] = False  # 處理負號顯示異常# 計算路徑距離，即評價函數(shù)
def calFitness(line, dis_matrix):dis_sum = 0dis = 0for i in range(len(line)):if i < len(line) - 1:dis = dis_matrix.loc[line[i], line[i + 1]]  # 計算距離dis_sum = dis_sum + diselse:dis = dis_matrix.loc[line[i], line[0]]dis_sum = dis_sum + disreturn round(dis_sum, 1)def traversal_search(line, dis_matrix, tabu_list):# 鄰域隨機遍歷搜索traversal = 0  # 搜索次數(shù)traversal_list = []  # 存儲局部搜索生成的解,也充當局部禁忌表traversal_value = []  # 存儲局部解對應路徑距離while traversal <= traversalMax:pos1, pos2 = random.randint(0, len(line) - 1), random.randint(0, len(line) - 1)  # 交換點# 復制當前路徑，并交換生成新路徑new_line = line.copy()new_line[pos1], new_line[pos2] = new_line[pos2], new_line[pos1]new_value = calFitness(new_line, dis_matrix)  # 當前路徑距離# 新生成路徑不在全局禁忌表和局部禁忌表中，為有效搜索，否則繼續(xù)搜索if (new_line not in traversal_list) & (new_line not in tabu_list):traversal_list.append(new_line)traversal_value.append(new_value)traversal += 1return min(traversal_value), traversal_list[traversal_value.index(min(traversal_value))]def greedy(CityCoordinates, dis_matrix):'''貪婪策略構造初始解'''# 出來dis_matrixdis_matrix = dis_matrix.astype('float64')for i in range(len(CityCoordinates)): dis_matrix.loc[i, i] = math.pow(10, 10)line = []  # 初始化now_city = random.randint(0, len(CityCoordinates) - 1)  # 隨機生成出發(fā)城市l(wèi)ine.append(now_city)  # 添加當前城市到路徑dis_matrix.loc[:, now_city] = math.pow(10, 10)  # 更新距離矩陣，已經(jīng)過城市不再被取出for i in range(len(CityCoordinates) - 1):next_city = dis_matrix.loc[now_city, :].idxmin()  # 距離最近的城市l(wèi)ine.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])for j in range(len(line) - 1):plt.quiver(x[j], y[j], x[j + 1] - x[j], y[j + 1] - y[j], color='r', width=0.005, angles='xy', scale=1,scale_units='xy')plt.quiver(x[-1], y[-1], x[0] - x[-1], y[0] - y[-1], color='r', width=0.005, angles='xy', scale=1,scale_units='xy')plt.title('基于禁忌搜索算法的TSP')# plt.figure()# plt.plot(x, y,color='r', alpha=0.8, linewidth=0.8)# plt.xlabel('x')# plt.ylabel('y')plt.show()if __name__ == '__main__':# 隨機生成城市信息nCity = 50CityCoordinates = np.random.uniform(0, 2000, [nCity, 2])  # uniform()生成nCity個二維數(shù)組，數(shù)值范圍是0到2000# 參數(shù)設置CityNum = nCity  # 城市數(shù)量MinCoordinate = 0  # 二維坐標最小值MaxCoordinate = 101  # 二維坐標最大值tabu_limit = 50  # 禁忌長度，該值應小于(CityNum*(CityNum-1)/2）iterMax = 200  # 迭代次數(shù)traversalMax = 100  # 每一代局部搜索次數(shù)tabu_list = []  # 禁忌表tabu_time = []  # 禁忌次數(shù)best_value = math.pow(10, 10)  # 較大的初始值，存儲最優(yōu)解best_line = []  # 存儲最優(yōu)路徑# 計算城市之間的距離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 = greedy(CityCoordinates, dis_matrix)value = calFitness(line, dis_matrix)  # 初始路徑距離# 存儲當前最優(yōu)best_value, best_line = value, linebest_value_list = []best_value_list.append(best_value)# 更新禁忌表tabu_list.append(line)tabu_time.append(tabu_limit)itera = 0while itera <= iterMax:new_value, new_line = traversal_search(line, dis_matrix, tabu_list)if new_value < best_value:  # 優(yōu)于最優(yōu)解best_value, best_line = new_value, new_line  # 更新最優(yōu)解best_value_list.append(best_value)print('第%d次:當前優(yōu)解為' % (itera+1))print(best_line)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("-------最優(yōu)解為：")print(best_line)# 畫路徑圖draw_path(best_line, CityCoordinates)

---

3.運行結果

---

????????參考資料來源：CSDN、百度搜索、維基百科等

????????文章若有不當和不正確之處，還望理解與指出。由于部分文字、圖片等來源于互聯(lián)網(wǎng)，無法核實真實出處，如涉及相關爭議，請聯(lián)系博主刪除。如有錯誤、疑問和侵權，歡迎評論留言聯(lián)系作者，或者關注VX公眾號：Rain21321，聯(lián)系作者。