正文

模拟退火算法求解tsp问题(python)(代码片段)

肥猪猪爸  肥猪猪爸  2022-12-05  282

关键词：

👉TSP旅行商问题

旅行商问题大家都应该非常熟悉了，解法也很多，比如贪婪算法、Dijkstra算法等等，本文参考《MATLAB智能算法30个案例分析（第2版）》中第19章的内容，利用模拟退火算法求解TSP问题并给出了python实现版本
TSP问题描述如下：

👉TSP模拟退火算法

关于模拟退火算法的原理，书籍和文章均比较多，这里就不再赘述，大家可以参考其他博文，或阅读《MATLAB智能算法30个案例分析（第2版）》这本书。

👉程序及运行结果（笔者python环境为3.7）

import copy
import math
import random
import matplotlib.pyplot as plt

# 初始温度
T0 = 1000
# 终止温度
Tend = 1e-3
# 个温度下的迭代次数（链长）
L = 200
# 降温速率
q = 0.9

# 各个城市的坐标
X = [(16.4700, 96.1000),
     (16.4700, 94.4400),
     (20.0900, 92.5400),
     (22.3900, 93.3700),
     (25.2300, 97.2400),
     (22.0000, 96.0500),
     (20.4700, 97.0200),
     (17.2000, 96.2900),
     (16.3000, 97.3800),
     (14.0500, 98.1200),
     (16.5300, 97.3800),
     (21.5200, 95.5900),
     (19.4100, 97.1300),
     (20.0900, 92.5500)]


# 构建距离矩阵
def build_distance():
    # 初始化城市距离矩阵
    distance = [[0 for _ in range(len(X))] for _ in range(len(X))]
    # 计算各个城市之间的距离
    for i in range(len(X)):
        pos1 = X[i]
        for j in range(i+1, len(X)):
            pos2 = X[j]
            distance[i][j] = pow((pow(pos1[0] - pos2[0], 2) + pow(pos1[1] - pos2[1], 2)), 0.5)
            distance[j][i] = distance[i][j]
    return distance


# 产生新的路径解
def gen_new_path(path):
    new_path = copy.copy(path)
    # 随机产生两个索引
    idx1 = random.randint(0, len(path) - 1)
    idx2 = random.randint(0, len(path) - 1)
    # 交换路径中的两个城市
    temp = new_path[idx1]
    new_path[idx1] = new_path[idx2]
    new_path[idx2] = temp
    return new_path


# 计算路径总距离
def path_distance(path, distance):
    total_distance = 0.0
    # 循环路径上所有城市进行计算，到最后一个城市返回出发城市
    for i in range(len(path)):
        if i == len(path) - 1:
            total_distance += distance[path[i]][path[0]]
        else:
            total_distance += distance[path[i]][path[i + 1]]
    return total_distance


# Metropolis准则函数
def metropolis(old_path, new_path, distance, t):
    # 路径的能量即路径上各城市距离之和
    # 新路径的能量函数和旧路径的能量函数之差
    delta = path_distance(new_path, distance) - path_distance(old_path, distance)
    # 若新路径能量低于旧路径，则接受新路径解
    if delta < 0:
        return copy.copy(new_path), path_distance(new_path, distance)
    # 若新路径能量高于旧路径，则按exp(-delta/t)概率接受新路径解
    if math.exp(-delta/t) >= random.uniform(0, 1):
        return copy.copy(new_path), path_distance(new_path, distance)
    # 不接受新路径解
    return copy.copy(old_path), path_distance(old_path, distance)


# 绘制结果
def draw_result(best, file_name="tsp_sa"):
    # 各个城市的横纵坐标
    x = [pos[0] for pos in X]
    y = [pos[1] for pos in X]
    # 绘图中文设置
    plt.rcParams['font.sans-serif'] = ['SimHei']  # 显示中文标签
    plt.rcParams['axes.unicode_minus'] = False
    # 清空画布
    plt.clf()
    # 绘制箭头
    for i in range(len(X)):
        # 箭头开始坐标
        start = X[best[i]]
        # 箭头结束坐标
        end = X[best[i + 1]] if i < len(best) - 1 else X[best[0]]
        plt.arrow(start[0], start[1], end[0] - start[0], end[1] - start[1], head_width=0.2, lw=1, length_includes_head=True)
    # 绘制城市编号
    for i in range(len(X)):
        plt.text(x[best[i]], y[best[i]], "".format((best[i] + 1)), size=15, color="r")
    plt.xlabel(u"横坐标")
    plt.ylabel(u"纵坐标")
    plt.savefig(file_name + ".png", dpi=800)


# 绘制进化过程
def draw_evolution(evolution):
    x = [i for i in range(len(evolution))]
    # 清空画布
    plt.clf()
    plt.plot(x, evolution)
    plt.savefig('tsp_sa_evolution.png', dpi=800)


# 模拟退火算法
def simulated_annealing():
    # 城市距离矩阵
    distance = build_distance()
    # 城市个数
    city_cnt = len(distance)
    # 初始化城市路径，这里可以随机生成，也可以跟书中的初始路径保持一致
    # path = random.sample(range(0, city_cnt), city_cnt)
    path = [10, 13, 2, 8, 5, 3, 12, 6, 7, 0, 11, 4, 1, 9]
    # 绘制初始路径
    draw_result(path, "init_path")
    # 初始路线长度
    total_distance = path_distance(path, distance)

    print("初始路线：", [p + 1 for p in path])
    print("初始总距离：", total_distance)
    # 温度
    t = T0
    # 进化过程，每一次迭代的路径总距离
    evolution = []
    # 循环直到冷却后停止
    while t > Tend:
        for _ in range(L):
            # 产生新路径
            new_path = gen_new_path(path)
            # 更新最佳路径及对应的距离
            path, total_distance = metropolis(path, new_path, distance, t)
            # 更新进化过程
            evolution.append(total_distance)
        # 降温
        t = t * q
    # 打印退火后信息
    print("结束温度为：", t)
    print("最佳路线：", [p + 1 for p in path])
    print("最佳距离：", total_distance)
    # 绘制最佳路径
    draw_result(path, "tsp_sa_best")
    # 绘制进化过程
    draw_evolution(evolution)


if __name__ == "__main__":
    simulated_annealing()

程序打印信息如下：

初始路线： [11, 14, 3, 9, 6, 4, 13, 7, 8, 1, 12, 5, 2, 10]
初始总距离： 56.0122140089359
结束温度为： 0.0009120344560464498
最佳路线： [14, 2, 1, 10, 9, 11, 8, 13, 7, 12, 6, 5, 4, 3]
最佳距离： 29.340520066994227

运行结果下图所示：

路径总距离随着迭代的进行逐步稳定，如下图所示：

笔者水平有限，若有不对的地方欢迎评论指正

python数模笔记-模拟退火算法求解旅行商问题的联合算子模拟退火算法(代码片段)

Python数模笔记—求解旅行商问题的联合算子模拟退火算法（完整例程）文章目录Python数模笔记—求解旅行商问题的联合算子模拟退火算法（完整例程）0摘要1引言2模拟退火算法求解旅行商问题2.1模拟退火算法2.2多... 查看详情

tsp基于matlab模拟退火算法求解旅行商问题含matlab源码1129期(代码片段)

一、简介1模拟退火算法原理模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒... 查看详情

tsp基于matlab模拟退火算法求解31城市旅行商问题含matlab源码1148期(代码片段)

模拟退火算法(代码片段)

模拟退火算法是用来求解最优化问题的算法。比如著名的TSP问题，函数最大值最小值问题等等。接下来将以如下几个方面来详细介绍模拟退火算法。 Contents 1.模拟退火算法认识 2.模拟退火算法描述 3.费马点问题求解... 查看详情

python数模笔记-模拟退火算法求解旅行商问题的联合算子模拟退火算法(代码片段)

tsp基于matlabgui模拟退火算法求解旅行商问题含matlab源码1083期

一、TSP简介旅行商问题，即TSP问题（TravelingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次... 查看详情

tsp基于matlabgui模拟退火+蚁群+遗传算法求解旅行商问题含matlab源码1611期(代码片段)

一、TSP简介旅行商问题，即TSP问题（TravelingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是... 查看详情

tsp基于matlab遗传和模拟退火算法求解中国省会城市旅行商问题含matlab源码1254期

模拟退火算法解决旅行商问题（tsp）(代码片段)

本文是使用Matlab实现模拟退火算法解决旅行商问题（TSP）模拟退火是模仿冶金中退火过程的爬山法的改进版本。模拟退火模拟退火是一种用于解决无约束优化问题的优化算法。该方法模拟加热材料然后缓慢降低温度以减... 查看详情

模拟退火算法解决旅行商问题（tsp）(代码片段)

matlab解决tsp问题（货郎担问题，旅行商问题）的模拟退火算法(代码片段)

TSP问题（货郎担问题，旅行商问题）的模拟退火算法function[f,T]=TSPSA(d,t0,tf)%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序%f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度[m,n... 查看详情

毕设题目：matlab智能算法tsp（旅行商）

1案例背景智能优化算法比较常见的有模拟退火算法、遗传算法、人工鱼群算法、神经网络算法等。首先介绍了算法的基本原理,然后总结了各自的优缺点并从原理和参数两个方面对算法进行了对比分析,以经典NP难题——TSP为例进... 查看详情

优化求解基于matlab模拟退火算法求解函数极值问题含matlab源码1203期

一、模拟退火算法简介1引言模拟退火算法(SimulatedAnnealing，SA)的思想最早由Metropolis等人于1953年提出：Kirkpatrick于1983年第一次使用模拟退火算法求解组合最优化问题[1]。模拟退火算法是一种基于MonteCarlo迭代求解策略的随机寻优算... 查看详情

matlab应用实战系列（五十三）-模拟退火算法（附源码）

模拟退火算法模拟退火算法在处理全局优化、离散变量优化等困难问题中，具有传统优化算法无可比拟的优势。这里描述模拟退火算法的原理及其基本框架结构，给出用模拟退火算法求解TSP问题的具体实现方法以下是我为大家准... 查看详情

配送路径规划基于matlab模拟退火算法求解单配送中心多客户多车辆最短路径规划问题含matlab源码1604期(代码片段)

一、模拟退火算法简介1引言模拟退火算法(SimulatedAnnealing，SA)的思想最早由Metropolis等人于1953年提出：Kirkpatrick于1983年第一次使用模拟退火算法求解组合最优化问题[1]。模拟退火算法是一种基于MonteCarlo迭代求解策略的随机... 查看详情

优化求解基于matlabgui模拟退火算法求解全局最大值最小值问题含matlab源码1242期

vrp基于matlab模拟退火算法求解单中心多车辆路径规划问题含matlab源码1072期(代码片段)

一、模拟退火算法简介1模拟退火算法的原理模拟退火算法（SA）是一种适用于大规模组合优化问题的有效近似算法，来源于对固体退火过程的模拟。统计力学表明，在给定初始温度的条件下，通过将温度缓慢... 查看详情

两种改进的模拟退火算法求解大值域约束满足问题2.0

2 两种改进的模拟退火算法模拟退火算法（Simulatedannealingalgorithm）是一种通用的概率算法，其思想源于固体退火过程：当固体物质温度很高时，固体内部粒子运动杂乱无序；而当温度逐渐降低时粒子又渐渐趋于有序运动... 查看详情