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

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

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

目錄

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

1.項(xiàng)目介紹? ? ? ?

2.程序代碼

3.運(yùn)行結(jié)果

---

1.項(xiàng)目介紹? ? ? ?

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

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

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

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

在基于TS算法求解TSP問(wèn)題時(shí)，禁忌搜索的核心思想包括以下幾個(gè)方面：

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

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

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

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

---

2.程序代碼

""""
題目：基于禁忌搜索算法的TSP
作者：Rainbook
最終修改時(shí)間：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  # 處理負(fù)號(hào)顯示異常# 計(jì)算路徑距離，即評(píng)價(jià)函數(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]]  # 計(jì)算距離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):# 鄰域隨機(jī)遍歷搜索traversal = 0  # 搜索次數(shù)traversal_list = []  # 存儲(chǔ)局部搜索生成的解,也充當(dāng)局部禁忌表traversal_value = []  # 存儲(chǔ)局部解對(duì)應(yīng)路徑距離while traversal <= traversalMax:pos1, pos2 = random.randint(0, len(line) - 1), random.randint(0, len(line) - 1)  # 交換點(diǎn)# 復(fù)制當(dāng)前路徑，并交換生成新路徑new_line = line.copy()new_line[pos1], new_line[pos2] = new_line[pos2], new_line[pos1]new_value = calFitness(new_line, dis_matrix)  # 當(dāng)前路徑距離# 新生成路徑不在全局禁忌表和局部禁忌表中，為有效搜索，否則繼續(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):'''貪婪策略構(gòu)造初始解'''# 出來(lái)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)  # 隨機(jī)生成出發(fā)城市l(wèi)ine.append(now_city)  # 添加當(dāng)前城市到路徑dis_matrix.loc[:, now_city] = math.pow(10, 10)  # 更新距離矩陣，已經(jīng)過(guò)城市不再被取出for i in range(len(CityCoordinates) - 1):next_city = dis_matrix.loc[now_city, :].idxmin()  # 距離最近的城市l(wèi)ine.append(next_city)  # 添加進(jìn)路徑dis_matrix.loc[:, next_city] = math.pow(10, 10)  # 更新距離矩陣now_city = next_city  # 更新當(dāng)前城市return line# 畫(huà)路徑圖
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__':# 隨機(jī)生成城市信息nCity = 50CityCoordinates = np.random.uniform(0, 2000, [nCity, 2])  # uniform()生成nCity個(gè)二維數(shù)組，數(shù)值范圍是0到2000# 參數(shù)設(shè)置CityNum = nCity  # 城市數(shù)量MinCoordinate = 0  # 二維坐標(biāo)最小值MaxCoordinate = 101  # 二維坐標(biāo)最大值tabu_limit = 50  # 禁忌長(zhǎng)度，該值應(yīng)小于(CityNum*(CityNum-1)/2）iterMax = 200  # 迭代次數(shù)traversalMax = 100  # 每一代局部搜索次數(shù)tabu_list = []  # 禁忌表tabu_time = []  # 禁忌次數(shù)best_value = math.pow(10, 10)  # 較大的初始值，存儲(chǔ)最優(yōu)解best_line = []  # 存儲(chǔ)最優(yōu)路徑# 計(jì)算城市之間的距離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)# 貪婪構(gòu)造line = greedy(CityCoordinates, dis_matrix)value = calFitness(line, dis_matrix)  # 初始路徑距離# 存儲(chǔ)當(dāng)前最優(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次:當(dāng)前優(yōu)解為' % (itera+1))print(best_line)line, value = new_line, new_value  # 更新當(dāng)前解# 更新禁忌表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)# 畫(huà)路徑圖draw_path(best_line, CityCoordinates)

---

3.運(yùn)行結(jié)果

---

????????參考資料來(lái)源：CSDN、百度搜索、維基百科等

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