模拟退火算法(SA算法)求解实例---旅行商问题 (TSP)

目录

  • 一、采用SA求解 TSP
  • 二、 旅行商问题
    • 2.1 实际例子:求解 6 个城市的 TSP
    • 2.2 ==**求解该问题的代码**==
    • 2.3 代码运行过程截屏
    • 2.4 代码运行结果截屏(后续和其他算法进行对比)
  • 三、 ==如何修改代码?==
    • 3.1 减少城市坐标,如下:
    • 3.2 增加城市坐标,如下:
  • 四、 模拟退火算法 (Simulated Annealing, SA) 原理
    • 4.1 模拟退火算法定义
    • 4.2 SA算法的基本思想
    • 4.3 SA算法的工作原理
    • 4.4 SA算法的参数
    • 4.5 SA算法的优缺点
      • 4.5.1 优点
      • 4.5.2 缺点
    • 4.6 SA算法的应用场景
    • 4.7 SA算法求解TSP步骤

一、采用SA求解 TSP

求解代码在文中,后续会出其他算法求解TSP问题,你们参加数学建模竞赛只需要会改代码即可。

用来对比此专栏的
遗传算法(GA算法)求解实例—旅行商问题 (TSP)
粒子群算法(PSO算法)求解实例—旅行商问题 (TSP)
注意每次运行SA算法得到的结果可能不太一样。

我知道大家对原理性的东西不感兴趣,我把原理性的东西放在后面,大家如果需要写数模论文可以拿去,但是记得需要改一改,要不然查重过不去。

二、 旅行商问题

2.1 实际例子:求解 6 个城市的 TSP

假设有 6 个城市,其坐标如下:

城市X 坐标Y 坐标
01020
13040
22010
34030
41010
55020

目标是找到一个经过所有城市且总距离最短的路径。

2.2 求解该问题的代码

import numpy as np
import random
import math# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[10, 10],[50, 20]
])# 计算两城市之间的欧几里得距离
def calculate_distance(city1, city2):return np.sqrt(np.sum((city1 - city2) ** 2))# 计算总旅行距离
def total_distance(path):distance = 0for i in range(len(path) - 1):distance += calculate_distance(cities[path[i]], cities[path[i + 1]])distance += calculate_distance(cities[path[-1]], cities[path[0]])  # 回到起点return distance# 模拟退火算法主函数
def simulated_annealing(cities, initial_temp=1000, cooling_rate=0.995, max_iter=1000):num_cities = len(cities)# 初始化解和温度current_path = list(np.random.permutation(num_cities))current_distance = total_distance(current_path)best_path = current_path.copy()best_distance = current_distancetemperature = initial_tempfor iteration in range(max_iter):# 生成新解:随机交换路径中的两个城市new_path = current_path.copy()i, j = np.random.choice(num_cities, 2, replace=False)new_path[i], new_path[j] = new_path[j], new_path[i]# 计算新解的距离new_distance = total_distance(new_path)# 接受新解的条件if new_distance < current_distance or random.random() < math.exp((current_distance - new_distance) / temperature):current_path = new_pathcurrent_distance = new_distance# 更新最佳解if current_distance < best_distance:best_path = current_pathbest_distance = current_distance# 降温temperature *= cooling_rate# 输出当前迭代的信息print(f"Iteration {iteration}: Best distance = {best_distance:.2f}, Temperature = {temperature:.2f}")# 如果温度低到一定程度,停止搜索if temperature < 1e-8:breakreturn best_path, best_distance# 运行模拟退火算法
best_path, best_distance = simulated_annealing(cities)
print("Best path:", best_path)
print("Best distance:", best_distance)

2.3 代码运行过程截屏

在这里插入图片描述

2.4 代码运行结果截屏(后续和其他算法进行对比)

在这里插入图片描述

三、 如何修改代码?

这一部分是重中之重,大家参加数学建模肯定是想跑出自己的结果,所以大家只需要把自己遇到的数学问题,抽象成TSP问题,然后修改代码的城市坐标,然后运行即可。

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[10, 10],[50, 20]
])

3.1 减少城市坐标,如下:

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30]
])

3.2 增加城市坐标,如下:

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[30, 40],[20, 10],[10, 10],[50, 20]
])

四、 模拟退火算法 (Simulated Annealing, SA) 原理

4.1 模拟退火算法定义

模拟退火算法 (Simulated Annealing, SA) 是一种基于概率的随机搜索优化算法,由 S. Kirkpatrick 等人在 1983 年提出。模拟退火算法借鉴了固体退火过程的物理原理,通过在解空间中随机搜索和逐步降低“温度”,找到全局最优解或近似最优解。该算法常用于求解组合优化问题,如旅行商问题 (TSP)、生产调度、资源分配等。

4.2 SA算法的基本思想

模拟退火算法的核心思想是模拟物理退火过程中固体的冷却过程。在退火过程中,固体被加热到一个足够高的温度,然后逐渐冷却,使得固体内部的原子能量状态逐渐达到最小值(即晶格结构最稳定)。在优化问题中,这一过程对应于在解空间中随机搜索,并通过概率准则接受劣解,以避免陷入局部最优解。

4.3 SA算法的工作原理

  1. 初始化

    • 随机生成一个初始解,并设定初始温度 T 和降温速率 α(通常为小于 1 的常数)。
    • 计算初始解的目标函数值(或称“能量”)。
  2. 迭代过程

    • 在当前解的邻域内随机生成一个新解。
    • 计算新解的目标函数值。如果新解更优,则接受该解作为当前解。
    • 如果新解不优,以一定概率接受该解:
      [
      P = \exp\left(-\frac{\Delta E}{T}\right)
      ]
      其中,ΔE 是新解和当前解的目标函数值之差,T 是当前温度。
    • 根据冷却速率 α 更新温度:
      [
      T \leftarrow \alpha \cdot T
      ]
  3. 终止条件

    • 当达到最大迭代次数或温度低于某一阈值时,停止搜索,输出当前最优解。

4.4 SA算法的参数

  • 初始温度 (T):初始的高温状态,控制初期的搜索范围和探索能力。温度越高,算法越容易接受劣解,从而有更好的全局探索能力。
  • 降温速率 (α):控制温度的降低速度,通常设为接近 1 的数值(如 0.99)。降温速率过快可能导致过早收敛到局部最优解。
  • 迭代次数:算法运行的最大迭代次数。迭代次数越多,算法有更大的机会找到全局最优解。

4.5 SA算法的优缺点

4.5.1 优点

  • 跳出局部最优:通过接受劣解的概率机制,SA 算法能够有效跳出局部最优解,逼近全局最优解。
  • 简单易实现:算法结构简单,易于实现和应用于多种优化问题。
  • 适应性强:SA 算法可以处理非线性、非连续和多峰值的复杂优化问题。

4.5.2 缺点

  • 收敛速度较慢:SA 算法在初期的高温阶段具有较强的探索能力,但温度降低后搜索步长缩小,收敛速度较慢。
  • 参数敏感:算法性能对初始温度、降温速率等参数较为敏感,需要根据问题特点进行调节。
  • 计算开销大:在温度较高和迭代次数较多的情况下,计算开销较大。

4.6 SA算法的应用场景

  • 组合优化问题:如旅行商问题 (TSP)、背包问题、图着色问题等。
  • 工程设计优化:如集成电路布局优化、结构设计优化等。
  • 机器学习:如神经网络训练、特征选择、参数优化等。
  • 生产调度与资源分配:如车间调度、任务分配、物流配送等。

4.7 SA算法求解TSP步骤

  1. 初始化:随机生成一个初始路径,并计算路径的总旅行距离。
  2. 迭代过程:在当前路径的邻域内(如交换两个城市的位置)随机生成一个新路径,计算新路径的总旅行距离。
    • 如果新路径更短,则接受该路径作为当前解。
    • 如果新路径更长,以一定概率接受该解,以避免陷入局部最优。
  3. 降温:逐步降低温度,减少接受劣解的概率。
  4. 终止条件:当达到最大迭代次数或温度低到一定程度时,停止搜索,输出当前最优路径。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/424867.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

文件格式转换:EXCEL和CSV文件格式互相转换

目录 1.EXCEl和CSV文件格式互相转换1.1首先安装所需的Python包1.2excel转换为csv代码如下&#xff1a;1.3csv转换为excel代码如下&#xff1a; 由于excel文件在数学建模数据处理当中的局限性&#xff0c;我们通常把excel文件转换为csv文件来处理&#xff0c;下面是相关的代码&a…

用网卡的ap模式抓嵌入式设备的网络包

嵌入式设备不像pc上&#xff0c;有一些专门的工具比如wareshark来抓包&#xff0c;嵌入式设备中&#xff0c;有的可能集成了tcpdump&#xff0c;可以用来进行简单的抓包&#xff0c;但是不方便分析&#xff0c;况且有的嵌入式设备不一定就集成了tcpdump工具。 关于tcpdump工具…

Hibernate基础

Hibernate基础总结 有利的条件和主动的恢复产生于再坚持一下的努力之中&#xff01; 好久没更新了&#xff0c;今天入门了Hibernate&#xff0c;由于之前学习了MyBatis&#xff0c;初步感觉二者的底层实现思想有很多相似之处&#xff0c;下面让我们以一个入门Demo的形式感受一…

AIGC实战——多模态模型Flamingo

AIGC实战——多模态模型Flamingo 0. 前言1. Flamingo 架构2. 视觉编码器3. Perceiver 重采样器4. 语言模型5. FIamingo 应用小结系列链接 0. 前言 我们已经学习了文本生成图像模型 DALL.E 2&#xff0c;在本节中&#xff0c;我们将探索另一种多模态模型 Flamingo&#xff0c;它…

Docker上安装mysql

获取 MySQL 镜像 获取镜像。使用以下命令来拉取镜像&#xff1a; 1docker pull mysql:latest 这里拉取的是最新版本的 MySQL 镜像。你也可以指定特定版本&#xff0c;例如&#xff1a; 1docker pull mysql:8.0 运行 MySQL 容器 运行 MySQL 容器时&#xff0c;你需要指定一些…

redis基本数据结构-hash

这里写自定义目录标题 1. redis的数据结构hash1.1 Hash 数据结构的特点1.2 常见命令1.3 适用示例 2. 常见业务场景2.1 用户信息存储2.1.1 场景2.1.2 优势2.1.3 解决方案2.1.4 代码实现 2.2 购物车管理2.2.1 背景2.2.2 优势2.2.3 解决方案2.2.4 代码实现 3. 注意事项&#xff1a…

USB的电气特性

文章目录 一、USB的三种速率及状态切换图1. **附加&#xff08;Attached&#xff09;**2. **供电&#xff08;Powered&#xff09;**3. **复位&#xff08;Reset&#xff09;**4. **地址设置&#xff08;Addressed&#xff09;**5. **配置&#xff08;Configured&#xff09;**…

llama网络结构及源码

目录 模型初始化 config lm_head transformer wte h rms_1/rms_2 attn c_attn c_proj 线性层mlp ln_f rope_cache mask_cache kv_caches tokenizer tokenizer初始化 tokennizer.encoder 位置编码和mask 确定最大文本长度 建立rope_cache 建立mask_cache …

C#/.NET/.NET Core技术前沿周刊 | 第 5 期(2024年9.9-9.15)

前言 C#/.NET/.NET Core技术前沿周刊&#xff0c;你的每周技术指南针&#xff01;记录、追踪C#/.NET/.NET Core领域、生态的每周最新、最实用、最有价值的技术文章、社区动态、优质项目和学习资源等。让你时刻站在技术前沿&#xff0c;助力技术成长与视野拓宽。 欢迎投稿&…

ICM20948 DMP代码详解(23)

接前一篇文章&#xff1a;ICM20948 DMP代码详解&#xff08;22&#xff09; 上一回解析完了inv_icm20948_wakeup_mems函数&#xff0c;本回回到inv_icm20948_initialize_lower_driver函数中&#xff0c;继续往下解析。为了便于理解和回顾&#xff0c;再次贴出inv_icm20948_init…

闯关leetcode——26. Remove Duplicates from Sorted Array

大纲 题目地址内容 解题代码地址 题目 地址 https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/ 内容 Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appear…

Framebuffer应用编程

目录 前言 LCD操作原理 涉及的 API 函数 open函数 ioctl 函数 mmap 函数 Framebuffer程序分析 源码 1.打开设备 2.获取LCD参数 3.映射Framebuffer 4.描点函数 5.随便画几个点 上机实验 前言 本文介绍LCD的操作原理和涉及到的API函数&#xff0c;分析Framebuffer…

Python青少年简明教程:tkinter库入门

Python青少年简明教程&#xff1a;tkinter库入门 tkinter是Python的标准GUI&#xff08;图形用户界面&#xff09;库。它提供了一种快速而简单的方法来创建GUI应用程序。tkinter是Python自带的&#xff0c;无需额外安装&#xff0c;随 Python 安装包一起提供。 在Python 3.x中…

rtems 5.3 qemu realview_pbx_a9 环境搭建:生成 rtems arm 工具链

前言 rtems 是一款比较优秀的 RTOS&#xff0c;官方网址 https://www.rtems.org/ 当前 rtems 最新发布的版本&#xff1a;rtems-5.3 版本&#xff0c; 下载地址 https://ftp.rtems.org/pub/rtems/releases/5/5.3/ rtems 支持的 平台也是比较多的&#xff0c;当前支持 STM32F4…

调制是什么,为什么

一、什么是调制、解调&#xff1f; 调制&#xff1a;将信息承载到满足信道要求的高频信号上的过程就是调制。 解调&#xff1a;解调是调制的逆过程&#xff0c;将有用的信息从高频信号中恢复出来的过程就是解调。 二、为什么需要调制&#xff1f; 通信是为了实现“信息”的传…

【自然语言处理】实验三:新冠病毒的FAQ问答系统

目录 前言 1.新建data_process.py 1.1导入包并定义功能模块1用来读取问题和答案FAQ的文件 1.2功能模块2&#xff1a;进行问题/问题列表处理&#xff08;正则化&#xff0c;分词&#xff09; 1.3功能模块3&#xff1a;处理输入的问题 1.4功能模块4&#xff1a;计算输入问题与问题…

基于双向RRT算法的三维空间最优路线规划matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1 单向RRT算法 4.2 双向RRT算法 5.完整程序 1.程序功能描述 基于双向RRT&#xff08;Randomly Exploring Random Trees, 随机探索随机树&#xff09;算法的三维空间最优路径规划是一种解…

Java | Leetcode Java题解之第406题根据身高重建队列

题目&#xff1a; 题解&#xff1a; class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, new Comparator<int[]>() {public int compare(int[] person1, int[] person2) {if (person1[0] ! person2[0]) {return person2[0] - perso…

【目标检测数据集】锯子数据集1107张VOC+YOLO格式

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;1107 标注数量(xml文件个数)&#xff1a;1107 标注数量(txt文件个数)&#xff1a;1107 标注…

什么是java的spi?

Java SPI&#xff08;Service Provider Interface&#xff09;是一种提供服务发现机制的设计模式&#xff0c;允许在运行时动态地发现、加载和替换服务的实现。SPI机制的核心思想是&#xff1a;通过接口定义服务&#xff0c;并且使用外部的实现类来提供该服务的具体功能。 目录…