模拟退火算法求解旅行商问题（python实现）

刺骨的言语ヽ痛彻心扉 2022-10-08 15:17 227阅读 0赞

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

--------------------

### 文章目录 ###

*  模拟退火算法求解旅行商问题
 *  一、模拟退火算法原理
 *  二、旅行商问题
 *   *  1.求解思路
     *  2.代码
 *  总结

--------------------

旅行商问题(TSP 问题)。假设有一个旅行商人要拜访全国31个省会城市，他需要选择所要走的路径，路径的限制是每个城市只能拜访-一次， 而且最后要回到原来出发的城市。路径的选择要求是:所选路径的路程为所有路径之中的最小值。

--------------------

# 一、模拟退火算法原理 #

见链接：[万字长文了解模拟退火算法原理及求解复杂约束问题（源码实现）][Link 1]

# 二、旅行商问题 #

## 1.求解思路 ##

旅行商问题是一个十分经典的NP难度问题，如果想找到真正的唯一最优的解复杂度是O(N!)的，所以求解这一类问题的策略就是找一个相对最优的解，也就是最优化问题。模拟退火算法就是一种启发式的组合优算法，通过不断迭代来寻找最优解。  
      旅行商问题的解可以表述为一个循环排列，我们可以把求解旅行商问题当做把n个城市的全排列进行对比，求最短的一条路径，但是这样复杂度太高，这里使用一个叫Mapkob链的东西，也就是城市的最排列次数不能超过Mapkob链长度（L = 20000）。对于当前已有的排列，产生新排列的过程使用2变换法，也就是在当前的队列中任选两个序号u和v（u<v），将u和v及其之间的顺序逆转。在逆转之后需要重新计算新路径长度，若新路径长度小于当前路径，就用新路径代替当前路径，否则使用模拟退火算法根据概率决定是否转移。

## 2.代码 ##

代码如下（示例）：

#!/usr/bin/env python3
    # -*- coding: utf-8 -*-
    # @Author: yudengwu(余登武）
    # @Date  : 2021/6/22
    #@email:1344732766@qq.com
    
    import numpy as np
    import pandas as pd
    from tqdm import tqdm#进度条设置
    import matplotlib.pyplot as plt
    from pylab import *
    import matplotlib; matplotlib.use('TkAgg')
    mpl.rcParams['font.sans-serif'] = ['SimHei']
    mpl.rcParams['axes.unicode_minus'] = False
    
    city_num = 31  # 城市的数量
    #############1.数据集 城市坐标
    C=[1304 ,2312,3639 ,1315,4177 ,2244,3712 ,1399,3488, 1535,3326, 1556,
        3238 ,1229,4196 ,1044,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,2376,
        3394 ,2643,3439,3201,2935,3240,3140,3550,2545,2357,2778,2826,
        2370 ,2975]                 #31个省会城市坐标
    C=np.array(C).reshape(-1,2)#shape=(31, 2)
    
    
    ###############相关函数：距离和亲和度函数（路程） 路径画图函数################
    
    ####.函数：计算城市之间的距离
    def calculate_distance(X, Y):
        """
        计算城市两辆之间的欧式距离，结果用numpy矩阵存储
        :param X: 城市的X坐标，np.array数组
        :param Y: 城市的Y坐标，np.array数组
        """
        distance_matrix = np.zeros((city_num, city_num))
        for i in range(city_num):
            for j in range(city_num):
                if i == j:
                    continue
                dis = np.sqrt((X[i] - X[j]) ** 2 + (Y[i] - Y[j]) ** 2)  # 欧式距离计算
                distance_matrix[i][j] = dis
        return distance_matrix
    
    
    ##适应度函数 计算总距离
    def fitness_func(distance_matrix, xi):
        """
        适应度函数，计算目标函数值.
        :param distance: 城市的距离矩阵
        :param xi: 的一个解
        :return: 目标函数值，即总距离
        """
        total_distance = 0
        for i in range(1, city_num):
            start = xi[i - 1]
            end = xi[i]
            total_distance += distance_matrix[start][end]
        total_distance += distance_matrix[end][xi[0]]  # 从最后一个城市回到出发城市
        return total_distance
    
    
    #路径画图
    def plot_tsp(gbest):
        """绘制最优解的图形"""
        X=D[:,0]#城市坐标的X轴
        Y=D[:,1]#城市坐标的Y轴
        plt.scatter(X, Y, color='r')
        for i in range(1, city_num):
            start_x, start_y = X[gbest[i - 1]], Y[gbest[i - 1]]
            end_x, end_y = X[gbest[i]], Y[gbest[i]]
            plt.plot([start_x, end_x], [start_y, end_y], marker='>',alpha=0.8)
        start_x, start_y = X[gbest[0]], Y[gbest[0]]
        plt.plot([start_x, end_x], [start_y, end_y], color='b', alpha=0.8)
        plt.show()
    
    
    #=======在现有路径上采用2变换法，返回新的路径====
    def getNewPath(cur_path):
        #cur_path=np.random.choice(range(31),31,replace=False)
        path = cur_path.copy()
        u = np.random.randint(0,city_num,1)[0]
        v = np.random.randint(0,city_num,1)[0]
        while u==v:
            v = np.random.randint(0, city_num, 1)[0]
    
        path[u:v] = list(reversed(path[u:v] ))
        return path
    
    #############模拟退火算法开始############
    D=calculate_distance(C[:,0], C[:,1])#任意两个城市距离间隔矩阵 shape=(31, 31)
    # 初始温度，结束温度
    t_init = 50
    t_final = 1e-7
    # 温度衰减系数
    a = 0.98
    # 迭代次数
    markovlen = 100
    
    
    def SA_TSP():
        # 获取初始距离矩阵
        D=calculate_distance(C[:,0], C[:,1])#任意两个城市距离间隔矩阵 shape=(31, 31)
        # 得到初始解
        cur_path = np.random.choice(range(city_num),city_num,replace=False)
        print('初始解\n',cur_path)
        cur_dis=fitness_func(D, cur_path)
        print('初始路径总长度：',cur_dis)
        best_path = cur_path#最优解
        best_dis = cur_dis#最优解对应的路径长度
        t = t_init#当前温度
        while t > t_final:#如果温度小于最小温度
            #print('当前温度t:',t)
            for point in range(markovlen):#当前温度t,进行markovlen次迭代
                new_path = getNewPath(cur_path)#新的解
                new_dis = fitness_func(D, new_path)#新的解 对应的路径长度
    
                delt = new_dis - cur_dis #能量差
    
                if delt <= 0:  # 表示得到优解
                    cur_path = new_path
                    cur_dis = new_dis
                    #==是否是全局最优解==
                    if best_dis > cur_dis:
                        best_dis = cur_dis
                        best_path = cur_path
                else:  # 得到较差解
                    p = np.math.exp(-delt / t)
                    if np.random.random() < p:  # 接受差解
                        cur_path = new_path
                        cur_dis = new_dis
            t *= a  # 退火
    
        print("城市数量：{}, 最优路径：{}, 结果距离为：{:.2f}".format(city_num, best_path, best_dis))
        plot_tsp(best_path)
    
    SA_TSP()

![20210622135302165.png_pic_center][] ![20210622135355242.png_pic_center][]

--------------------

# 总结 #

结果和之前写的其它算法版本差不多。其它算法：粒子群、遗传、差分、免疫、蚁群等 。可以翻翻同专栏的其它文章。

![在这里插入图片描述][20210622135544497.jpg_pic_center]  
作者：电气-余登武  
![20210622135634324.jpg_pic_center][]

[Link 1]: https://blog.csdn.net/kobeyu652453/article/details/118070337
[20210622135302165.png_pic_center]: https://img-blog.csdnimg.cn/20210622135302165.png#pic_center
[20210622135355242.png_pic_center]: /images/20221005/bd8694a7c838402fa56ad4fcc6914ae2.png
[20210622135544497.jpg_pic_center]: /images/20221005/6537d0630a6849cf86970e2e143caed7.png
[20210622135634324.jpg_pic_center]: /images/20221005/01a1e212016d473485858e26cea9633b.png