模拟退火算法解决TSP问题
发布时间
阅读量：
阅读量
1.问题描述
旅行商问题（Travelling Salesman Problem, 简记TSP，亦称货郎担问题)：设有n个城市和距离矩阵D=[dij]，其中dij表示城市i到城市j的距离，i，j=1，2 … n，则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为最短。
2.算法设计
首先计算距离矩阵，假设任意两个城市的距离为其直线距离，并且任意两个城市之间都存在道路。
然后初始化一系列参数，设置概率控制参数T=100，设置每个概率尝试次数L=20000
任意初始化一个序列，从0出发经过所有点回到0即可，对于每个序列都存在一个总的路径长度，这个路径长度为所有路程之和，作为退火算法中的温度状态。
通过二变法随意找到另外一个序列，计算新序列的路径长度，并且计算转移概率，根据此概率决定是否转移。
以此类推。直到发生两次对应控制参数T变化后，均没有发生转移时，算法退出。
3.程序流程
4.核心伪代码
> Procedure TSP_USE_SIMULATED_ANNEALING; begin INITIALIZE; { 初始化i0= π1
> … πn, t0=100, L= 20000 } randomize; { 初始化随机数种子 } Repeat
> bChange:=0;
> for l:=1 to L do
> begin
> GENERATE; { 采用2变换法产生新的路径 }
> CALCULATE(df); { 计算 df = f(j)-f(i) 的值 }
> if ACCEPT(t, df) then { 根据Metropolis准则判断是否接受新的路径 }
> begin
> f: = f + df; { 计算已接受的路径的长度 }
> bChange := 1;
> end;
> end;
> t:=t * 0.9; { 衰减函数 α(t)=0.9 * t }
> if (bChange = 0) then s:=s+1 else s:=0; until s = 2 { 停止准则为连续两个Mapkob链路径无变化 } End;
5.部分代码以及解释
完整代码见git：sunxueliang96/Machine-learning-stuffs/tree/master/计算智能相关算法
citys = [[1304,2312],[3639,1315],[4177,2244],[3712,1399],[3488,1535],[3326,1556],[3238,1229],[4196,1004],[4312,790],[4386,570],[3007,1970],[2562,1756],[2788,1491],[2381,1676],[1332,695],[3715,1678],[3918,2179],[4061,2370],[3780,2212],[3676,2578],[4029,2838],[4263,2931],[3429,1908],[3507,2367],[3394,2643],[3439,3201],[2935,3240],[3140,3550],[2545,2357],[2778,2826],[2370,2975]]
a = pd.DataFrame(citys)#这里是31个城市，理论上多少个都可以
l = len(citys)
#数据从网上找来的
def review():#展示所有点
a.plot(x=0,y=1,kind = 'scatter')
plt.show()
#计算任意两省之间的距离,得到31*31的矩阵
def dist(x1,y1,x2,y2):
return np.sqrt(np.power(x1-x2,2)+np.power(y1-y2,2))
#init
b = []
a.columns = ['x','y']
[b.append(dist(a.loc[i].x,a.loc[i].y,a.loc[j].x,a.loc[j].y)) for i in range(l) for j in range(l)]
c = np.reshape(b,(l,l))
#c为距离矩阵#处理出一个矩阵来，反应着每两个矩阵之间的距离，显然这是一个对称矩阵，（还有优化的空间）
path = list(range(l))
path.append(0)
#初始路径为0-1-2-3-。。。-30-0
#init#
然后计算转移概率
def possibilities(t,fi,fj):#计算转移概率
if fj<fi:
return 1
elif(fj==fi):
return 0
else:
return math.exp((fi-fj)/t)
#用二交换法取一条新路，这里可以更改，也就是说用任何方法来试图获得新的路径都是可行的。
def get_new_path(pa):#用二交换法取一条新路
t = np.random.randint(low=1,high=31,size=2)
u = min(t)
v = max(t)
newpath = list.copy(pa)
swit = newpath[v]
newpath[v] =newpath[u]
newpath[u]=swit
return newpath
绘制路径
def plot(path):##绘制一次路径
plt.scatter(a['x'],a['y'],color='b')
x=[]
y=[]
for i in range(l+1):
x.append(citys[path[i]][0])
y.append(citys[path[i]][1])
plt.plot(x,y,color='r')
主函数比较好写，按照流程图即可。
部分截图
左边是最终结果，右边是优化（退火）过程
全部评论 (0)
还没有任何评论哟~