模拟退火算法解决旅行商问题

import numpy as np
import matplotlib.pyplot as plt
import matplotlib
import math
import random

#为了调整格式，测试数据
matplotlib.rcParams['font.family'] = 'STSong'
np.set_printoptions(linewidth=400)
np.set_printoptions(threshold=np.inf)

"""
载入数据
----------------------
重庆,106.54,29.59
拉萨,91.11,29.97
乌鲁木齐,87.68,43.77
银川,106.27,38.47
呼和浩特,111.65,40.82
南宁,108.33,22.84
哈尔滨,126.63,45.75
长春,125.35,43.88
沈阳,123.38,41.8
石家庄,114.48,38.03
太原,112.53,37.87
西宁,101.74,36.56
济南,117,36.65
郑州,113.6,34.76
南京,118.78,32.04
合肥,117.27,31.86
杭州,120.19,30.26
福州,119.3,26.08
南昌,115.89,28.68
长沙,113,28.21
武汉,114.31,30.52
广州,113.23,23.16
台北,121.5,25.05
海口,110.35,20.02
兰州,103.73,36.03
西安,108.95,34.27
成都,104.06,30.67
贵阳,106.71,26.57
昆明,102.73,25.04
香港,114.1,22.2
澳门,113.33,22.13
"""
city_name = []
city_condition = []
with open('data.txt','r',encoding='UTF-8') as f:
    lines = f.readlines()
    for line in lines:
        line = line.split('\n')[0]
        line = line.split(',')
        city_name.append(line[0])
        city_condition.append([float(line[1]), float(line[2])])
city_condition = np.array(city_condition)

"""
地图展示
"""
def map_show():
    fig = plt.figure()
    ax1 = fig.add_subplot()
    ax1.set_title('城市分布图')
    plt.scatter(city_condition[:,0],city_condition[:,1])
    plt.xlabel('经度')
    plt.ylabel('纬度')
    plt.show()

#距离矩阵
city_count = len(city_name)
Distance = np.zeros([city_count+1, city_count+1])
for i in range(1,city_count+1):
    for j in range(1,city_count+1):
        Distance[i][j] = math.sqrt((city_condition[i-1][0] - city_condition[j-1][0]) ** 2 + (city_condition[i-1][1] - city_condition[j-1][1]) ** 2)

"""
全局参数设计
"""
#path_new 代表着新的路径，distance代表着路径的和，即适应度。
#起始温度和最终温度
t2 = (1,100)
#马尔可夫的长度
alpha = 0.98
markovlen = 200
#存放路径的组合
# path_new = np.array([i for i in np.arange(1,city_count+1)])
path_new = np.array([1,  3,7, 2,18, 9, 29,  19, 20, 10, 21, 14, 15, 8, 25, 26, 11,  23,28, 27, 16, 17, 22, 30, 24,5, 12, 13, 4, 6,31])
# path_new = np.array([1,  3,7, 2,18, 9, 11,  19, 20, 10, 21, 14, 15, 8, 25, 26, 29, 28, 27, 16, 17, 22, 23, 30, 5, 12, 13, 4, 6, 24,31])
path_current = path_new.copy()
#赋予初始值
value_current = 99000
#最优路径
path_best = path_new.copy()
#最优解
value_best = 99000
t = t2[1]
"""
总距离,适应度计算
"""
def get_total_distance(path_new):
    distance = 0
    for i in range(city_count-1):
        #count为30，意味着回到了开始的点，此时的值应该为0.
        distance += Distance[path_new[i]][path_new[i+1]]
    distance += Distance[path_new[-1]][path_new[0]]
    return distance
"""
外循环的终止条件是最终温度
内循环的终止条件是马尔科夫的长度，种群数量。
"""
"""
交叉变异，迭代，降温
"""
result = []#记录过程中最优的值
while t > t2[0]:
    j = 1
    for i in np.arange(markovlen):
        j += 1
        if np.random.rand() > 0.5:
            while True:
                #双交换
                loc1 = np.int(np.ceil(np.random.rand()*(city_count-1)))
                loc2 = np.int(np.ceil(np.random.rand()*(city_count-1)))
                if loc1 != loc2:
                    break
            path_new[loc1],path_new[loc2] = path_new[loc2],path_new[loc1]
        else:
            while True:
                #三交换
                loc1 = np.int(np.ceil(np.random.rand() * (city_count - 1)))
                loc2 = np.int(np.ceil(np.random.rand() * (city_count - 1)))
                loc3 = np.int(np.ceil(np.random.rand() * (city_count - 1)))
                if ((loc1 != loc2) & (loc2!=loc3) & (loc1 != loc3)) :
                    break
            if loc1 > loc2:
                loc1,loc2 = loc2,loc1
            if loc2 > loc3:
                loc2,loc3 = loc3,loc2
            if loc1 >loc2:
                loc1,loc2 = loc2,loc1
         #思想参考l1>l2,借用的t,片段互换，注意换片段的位置。这里可以讲讲思想
            path_list = path_new[loc1:loc2].copy()
            path_new[loc1:loc3-loc2+loc1] = path_new[loc2:loc3].copy()
            path_new[loc3-loc2+loc1:loc3] = path_list.copy()
        distance = get_total_distance(path_new)
        if distance < value_current:
            value_current = distance
            #路径也复制
            path_current = path_new.copy()
            if distance < value_best:
                value_best = distance
                path_best = path_new.copy()
        else:
            if np.random.rand() < np.exp(-(distance-value_current)/t):
                #一定概率接受
                value_current = distance
                path_current = path_new.copy()
            else:
                path_new = path_current.copy()
    t = alpha * t  # 降温
    j = j +1

    result.append(value_best)#记录过程中最优的值。即每次迭代的最优值，最短路径也是从这里面产生的。
"""
主函数
"""
def main():
    # 输出部分
    print("模拟退火算法解决tsp问题")
    print("最优值是：", value_best)
    print("最优路径：", path_best)
    map_show()
    # 距离迭代图
    fig = plt.figure()
    ax3 = fig.add_subplot()
    ax3.set_title('距离迭代图')
    plt.plot(np.array(result))
    plt.xlabel('迭代次数')
    plt.ylabel('距离值')
    plt.show()

    # 路线图绘制
    fig = plt.figure()
    ax2 = fig.add_subplot()
    ax2.set_title('最佳路线图')
    x = []
    y = []
    path = []
    for i in range(len(city_name)):
        x.append(city_condition[path_best[i] - 1][0])
        y.append(city_condition[path_best[i] - 1][1])
        path.append(path_best[i])
    x.append(x[0])
    y.append(y[0])
    path.append(path[0])
    for i in range(len(x)):
        plt.annotate(path[i], xy=(x[i], y[i]), xytext=(x[i] + 0.3, y[i] + 0.3))
    plt.plot(x, y, '-o')
    plt.show()

if __name__ =="__main__":
    main()