任务描述

本关任务：利用模拟退火算法解决 TSP 问题。 TSP 问题是在给定的一些城市和这些城市之间的距离中，找出访问每一座城市一次并最终回到起始城市的最短回路。

相关知识

为了完成本关任务，你需要掌握模拟退火算法。

退火

在冶金学中，金属通常要进行原子重排，这是在退火过程中实现的。金属中的原子按照局部能量最小化进行排列。为了以较低的能量重新排列这些原子，首先需将金属加热，直到液化，然后将熔融的金属缓慢冷却，直到凝固。退火后的金属表现出许多人们期望的性能，例如它的韧性和硬度都得到了提升。

模拟退火

如图 2 所示：假设这是一个求最小值的函数图像，如果采用贪心策略，那么从 A 点开始试探，如果函数值继续减少，那么试探过程就会继续。而当到达点 B 时，显然我们的探求过程就结束了（因为无论朝哪个方向努力，结果只会越来越大）。最终我们只能找到一个局部最优解 B 。

模拟退火算法——概率取值

刚刚我们说了，模拟退火算法是以一定的概率来接受比当前解要差的值，那么这个概率是多少呢？由于我们之前说的模拟退火算法是源自于金属退火的原理，所以这个概率的计算也是来源于它。根据 Metropolis 准则，粒子在温度 T 时，趋于平衡的概率为 exp(−ΔE/(kT))，其中 E 为温度 T 时的内能，ΔE 为其改变数，k 为 Boltzmann 常数。Metropolis 准则常表示为：

那么 Metropolis 准则可以转化如下：

模拟退火算法步骤

伪代码如下：

/*
* J(y)：在状态y时的评价函数值
* Y(i)：表示当前状态
* Y(i+1)：表示新的状态
* r： 用于控制降温的快慢
* T： 系统的温度，系统初始应该要处于一个高温的状态
* T_min ：温度的下限，若温度T达到T_min，则停止搜索
*/
while( T > T_min )
{
　　dE = J( Y(i+1) ) - J( Y(i) ) ; 
　　if ( dE >=0 ) //表达移动后得到更优解，则总是接受移动
       Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
　　else
　　{
       // 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也
      if ( exp( -dE/T ) > random( 0 , 1 ) )
      Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
　　}
　　T = r * T ; //降温退火 ，0<r<1 。r越大，降温越慢；r越小，降温越快
　　/*
　　* 若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值
　　*/
　　i ++ ;
}

编程要求

根据提示，本关的编程任务是补全右侧编辑器 Begin 至 End 中间的代码，saa()函数的任务是利用模拟退火算法求出 TSP 问题的最短路径。
注意：saa()函数返回三个参数,分别为 ans 、 result 、 cnt，其中 ans 为最短路径，result 为路径长度，cnt 为降温次数（ TSP 各城市的距离在代码中已给出）。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确，其中路径长度只需低于 50000 并且降温次数为 1448 即可通过实训。

以下是平台的测试样例：

预期输出1：

路径如下：[14, 13, 19, 18, 15, 12, 9, 28, 7, 17, 27, 11, 26, 20, 6, 
16, 30, 2, 21, 25, 22, 8, 0, 10, 29, 4, 5, 23, 3, 1, 24]
路径长度：46860.89447968355
降温次数：1448
路径长度符合要求

预期输出2：

路径如下：[6, 27, 29, 17, 3, 4, 24, 14, 15, 18, 30, 11, 12, 7, 9, 
2, 19, 21, 25, 22, 28, 23, 26, 8, 16, 10, 5, 1, 0, 13, 20]
路径长度：44583.241163416074
降温次数：1448
路径长度符合要求

参考资料

1.模拟退火算法实例
2.大白话解析模拟退火算法
3.模拟退火算法

代码文件

student.py

import math
import time
import random

# 初始温度
T = 50000
# 最低温度
T_end = 1e-8
# 在每个温度下的迭代次数
L = 100
# 退火系数
delta = 0.98

# 31个城市的坐标
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]]
# 存储两个城市之间的距离
d = [[0 for i in range(31)] for j in range(31)]
# 存储一条路径
ans = []

# 计算降温次数
cnt = 0


# 计算两个城市之间的距离
def get_city_distance():
    for i in range(len(citys)):
        for j in range(i, len(citys)):
            d[i][j] = d[j][i] = math.sqrt((citys[i][0] - citys[j][0]) ** 2 + (citys[i][1] - citys[j][1]) ** 2)


# 使用随机交换路径中两个城市的位置来产生一条新路径
def create_new(a):
    #a=list(range(len(a)))
    i = random.randint(0, len(a) - 1)
    j = random.randint(0, len(a) - 1)
    a = list(a)
    a[i], a[j] = a[j], a[i]
    return a


# 获取路径的长度
def get_route_distance(a):
    dist = 0
    for i in range(len(a) - 1):
        dist += d[a[i]][a[i + 1]]
    return dist

#模拟退火
def saa():
    # ********** Begin **********#

    # ********** End **********#
    #函数返回三个参数
    #ans:路径,例如：[14, 13, 19, 18, 15, 12, 9, 28, 7, 17, 27, 11, 26, 20, 6, 16, 30, 2, 21, 25, 22, 8, 0, 10, 29, 4, 5, 23, 3, 1, 24]
    #result:路径长度
    #cnt:降温次数
    #路径长度在50000以内即可，降温次数最终返回值应为1448
    return ans,result,cnt

main.py

from student import *
print("路径如下："+str(saa()[0]))
print("路径长度："+str(saa()[1]))
print("降温次数："+str(saa()[2]))
if (saa()[2]==1448) and (saa()[1]<50000):
    print("路径长度符合要求")
else:
    print("路径长度太长")