SA solve TSP

AngelNH

发布于 2020-05-08 00:18:09

8340

发布于 2020-05-08 00:18:09

文章被收录于专栏：AngelNI

本文采用模拟退火算法（SA）来解决TSP问题，如果你之前看过理解了遗传算法（GA）来解决TSP问题，再看到本篇SA算法，会发现模拟退火算法简单了好多，实现起来也很简单。

相对于遗传算法，模拟退火算法解决问题的效率还是比较高的。不得不说，我之前的那篇GA算法还有很多要改进优化的地方。

模拟退火算法是从物理现象受到启发而发明的一种算法。其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是一种通用的优化算法，其物理退火过程由以下三部分组成：加温过程、等温过程、冷却过程。下面用流程图介绍了SA算法基本思想。

最后代码和结果图。

流程图

代码

在这里我没有设置终止条件。感觉设置终止条件为的就是增大迭代次数，所以我只设置了迭代次数5000次。

import numpy as np
import time
import copy
from matplotlib import pyplot as plt
np.random.seed(2131412)
#初始化路线
def init_path(city_num):
    path = [i for i in range(city_num)]
    #随机打乱
    np.random.shuffle(path)
    return path
#计算距离
def compute_distance(path,distance):
    dis = 0.0
    for i in range(len(path)-1):
        dis += distance[path[i]][path[i+1]]
    return dis
#路线更改
def change_path(path):
    new_path = copy.copy(path)
    l = np.random.randint(0,len(path)-2)
    r = np.random.randint(l+1,len(path)-1)
    new_path[l:r+1] = reversed(new_path[l:r+1])
    return new_path
#路线变化图
def show(path,city_position,dis):
    plt.cla()   # 清除键
    #画点
    plt.scatter(city_position[0],city_position[1],color = 'r')
    #划线
    x = [city_position[0][i] for i in path]
    y = [city_position[1][i] for i in path]
    plt.plot(x,y,color = 'b')
    plt.xticks([])
    plt.yticks([])
    plt.text(-5.25, -14.05, "Total distance=%.2f" % dis, fontdict={'size': 20, 'color': 'red'})
    plt.pause(0.01)
    #plt.show()
    pass
#最好的路线图
def best_show(path,city_position,dis):
    plt.scatter(city_position[0],city_position[1],color = 'r')
    x = [city_position[0][i] for i in path]
    y = [city_position[1][i] for i in path]
    plt.plot(x,y,color = 'b')
    plt.xticks([])
    plt.yticks([])
    plt.text(-5.25, -14.05, "Total distance=%.2f" % dis, fontdict={'size': 20, 'color': 'red'})
    plt.show()
    pass
#TSP问题解决
def TSP(city_num,city_position,distance,round = 5000):
    #初始温度
    T = 1e99
    #退火系数
    rate = 0.99
    #初始化路径
    path = init_path(city_num)
    #初始距离
    dis = compute_distance(path,distance)
    for i in range(round):
        #新的路径
        new_path = change_path(path)
        #新的距离
        new_dis = compute_distance(new_path,distance)
        if new_dis < dis:
            path = new_path
            dis = new_dis
        # metropolis 准则 得到新解或执行降温
        elif np.random.rand() > np.exp(-(new_dis-dis)/T):
            #更新解
            path = new_path
            dis = new_dis
            #降温过程
            T*=rate
        print(f'round {i}  ,  distance {dis}')
        show(path,city_position,dis)
    show(path,city_position,dis)

if __name__ == "__main__":
    city_num = 50
    x = [ 178,272,176,171,650,499,267,703,408,437,491,74,532,416,626,42,271,359,163,508,229,576,147,560,35,714,757,517,64,314,675,690,391,628,87,240,705,699,258,428,614,36,360,482,666,597,209,201,492,294]
    y = [ 170,395,198,151,242,556,57,401,305,421,267,105,525,381,244,330,395,169,141,380,153,442,528,329,232,48,498,265,343,120,165,50,433,63,491,275,348,222,288,490,213,524,244,114,104,552,70,425,227,331]
    city_position = np.array([x,y])
    #初始化一个全0矩阵
    distance = np.zeros((len(x),len(x)))
    #计算距离矩阵,distance[i][j]表示 i to j 的距离
    for i in range(len(x)):
        for j in range(len(x)):
            distance[i][j] = np.sqrt(np.square(x[i]-x[j])+np.square(y[i]-y[j]))
    TSP(city_num,city_position,distance)