java网站开发教程流程今天重大新闻头条
传送门（所有的实验都使用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]*mfor i in range(m):vis[i]=0;on= 0while on<m:te = random.randint(0,m-1);if(vis[te]==0):vis[te]=1;g[on]=te;on+=1;
def init(): #初始化函数global bestfor 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); #打印路线，以序列表示