傳送門（所有的實驗都使用python實作）
實驗1 BP神經網絡實驗
實驗2 som網實驗
實驗3 hopfield實作八皇後問題
實驗4 模糊搜尋算法預測薄冰厚度
實驗5 遺傳算法求解tsp問題
實驗6 蟻群算法求解tsp問題
實驗7 粒子群優化算法求解tsp問題
實驗8 分布估計算法求解背包問題
實驗9 模拟退火算法求解背包問題
實驗10 禁忌搜尋算法求解tsp問題
一、實驗目的
了解并使用禁忌搜尋算法
二、實驗内容
實作基于禁忌搜尋算法的TSP問題求解
三、實驗環境
使用Python3.0 在 eclipse進行編輯
四、實驗步驟
1、輸入介紹：
城市總數目為14，采用以下城市坐标，坐标取整數。
參數說明： tl初始禁忌長度 time 疊代次數, spe 特赦值
2、産生初始解：
随機産生一個合法的初始解，第一個城市固定，後面的兩個城市交換。
3、目标函數：
巡回路徑的城市間距離之和作為目标函數，函數值最小即為最優解。
4、禁忌對象與規則：
禁忌對象為兩個城市的交換，同時設定特赦值，當出現最優解且禁忌長度小于特赦值時，則特赦該對象，接受新解。否則被禁忌的對象無法産生新解。
5、鄰域搜尋：
除起點外，枚舉交換任意兩個城市交換後的解，選取領域中合法的最優解更新目前解。
6、更新全局最優解。
7、終止條件
達到目标疊代次數則終止并輸出結果，否則繼續在目前解的鄰域搜尋。
運作截圖：
随機産生路線 距離99.503
初始禁忌長度10 特赦值 5 疊代次數20 距離：58.349
初始禁忌長度10 特赦值 5 疊代次數40 距離：48.191
初始禁忌長度10 特赦值 5 疊代次數80 距離：45.472
五、總結
禁忌長度的設定會直接影響到算法的時間，禁忌長度設定過大雖然鄰域搜尋時間變短但是最終結果并非最優，禁忌長度設定過短雖然結果較優，但是耗費了較多時間，本次實驗中初始禁忌長度設定10為最佳。
此外特赦值的大小也會影響算法結果，若特赦值過大，會導緻結果陷入局部最優，一直在某個局部最優解附近循環，若特赦值過小，會導緻失去接受最優解的機會。本次實驗中特赦值取5為最佳。
python源碼
#coding:gbk
import random
import math
import matplotlib.pyplot as plt
global m,best,tl; #m 城市個數 best全局最優 tl初始禁忌長度
global time,spe ; # time 疊代次數, spe特赦值
best = 10000.0;
m=14; tl = 8; spe= 5; time=100
tabu = [[0]*(m) for i in range(m)] #禁忌表
best_way=[0]*m; now_way=[0]*m; #best_way 最優解 now_way目前解
dis = [[0]*(m) for i in range(m)] # 兩點距離
class no: #該類表示每個點的坐标
def __init__(self,x,y):
self.x=x;
self.y=y;
p=[];
def draw(t): #該函數用于描繪路線圖
x=[0]*(m+1);y=[0]*(m+1);
for i in range(m):
x[i] =p[t[i]].x;
y[i] =p[t[i]].y;
x[m] =p[t[0]].x;
y[m] =p[t[0]].y;
plt.plot(x,y,color='r',marker='*' );
plt.show();
def mycol(): #城市坐标輸入
p.append(no( 16 , 96 ));
p.append(no( 16 , 94 )); p.append(no( 20 , 92 )); p.append(no( 22 , 93 )); p.append(no( 25 , 97 )); p.append(no( 22 , 96 )); p.append(no( 20 , 97 ));
p.append(no( 17 , 96 )); p.append(no( 16 , 97 )); p.append(no( 14 , 98 )); p.append(no( 17, 97 )); p.append(no( 21 , 95 )); p.append(no( 19 , 97 ));
p.append(no( 20 , 94 ));
def get_dis(a,b): #傳回a，b兩城市的距離
return math.sqrt((p[a].x-p[b].x) *(p[a].x-p[b].x) +(p[a].y-p[b].y) *(p[a].y-p[b].y));
def get_value(t): #計算解t的路線長度
ans = 0.0;
for i in range(1,m):
ans += dis[t[i]][t[i-1]]
ans += dis[t[0]][t[m-1]]
return ans;
def cop(a,b): #把b數組的值指派a數組
for i in range(m):
a[i]=b[i]
def rand(g): # 随機生成初始解
vis = [0]*m
for i in range(m):
vis[i]=0;
on= 0
while on<m:
te = random.randint(0,m-1);
if(vis[te]==0):
vis[te]=1;
g[on]=te;
on+=1;
def init(): #初始化函數
global best
for i in range(m):
for j in range(m):
tabu[i][j] = 0; #初始化禁忌表
dis[i][j]=get_dis(i,j); #計算兩點距離
rand(now_way) #生成初始解作為目前解
now = get_value(now_way);
cop(best_way,now_way); best = now;
def slove(): #疊代函數
global best,now;
temp = [0]*m; #中間變量記錄交換結果
a = 0;b=0; # 記錄交換城市下标
ob_way =[0]*m; cop(ob_way,now_way);ob_value= get_value(now_way); #暫存鄰域最優解
for i in range(1,m): #搜尋所有鄰域
for j in range(1,m):
if(i+j >= m): break;
if(i==j): continue;
cop(temp,now_way)
temp[i],temp[i+j]=temp[i+j],temp[i]; #交換
value = get_value(temp)
if(value <= best and tabu[i][i+j] < spe): #如果優于全局最優且禁忌長度小于特赦值
cop(best_way,temp); best = value; a = i;b=i+j; #更新全局最優且接受新解
cop(ob_way,temp); ob_value = value;
elif(tabu[i][i+j]==0 and value < ob_value): #如果優于鄰域中的最優解則
cop(ob_way,temp); ob_value = value; a = i;b=i+j; #接受新解
cop(now_way,ob_way); #更新目前解
for i in range(m): # 更新禁忌表
for j in range(m):
if(tabu[i][j] > 0): tabu[i][j]-=1;
tabu[a][b]=tl; #重置a，b兩個交換城市的禁忌值
#*************************主函數*************************
mycol(); #資料輸入
init(); #資料初始化
for i in range(time): #控制疊代次數
slove();
print("路線總長度：",round(best,3)); #列印最優解距離保留三位小數
draw(best_way); #畫圖描繪路線
print("具體路線：",best_way); #列印路線，以序清單示