当前位置: 首页 > news >正文

模拟退火算法应用——求解TSP问题

仅作自己学习使用


一、问题

        旅行商问题(TSP) 是要求从一个城市出发,依次访问研究区所有的城市,并且只访问一次不能走回头路,最后回到起点,求一个使得总的周游路径最短的城市访问顺序。
       采用模拟退火算法求解TSP问题,很自然的想到退火的目标函数(优化函数)应该就是总的周游距离。那么在算法中如何体现呢?那就是把城市的坐标放在一个n×2的矩阵中,矩阵中存放城市的顺序就是依次周游城市的路径,所以在求解过程中会不断的产生新的更优解(周游顺序,在算法中体现就是城市坐标的存放顺序),有了这个关键的思路就很好解决了。

二、Matlab代码

clear
clc
T1 = cputime;
C = [% 各个城市坐标39.91, 116.39;   % 北京31.22, 121.48;   % 上海23.13, 113.27;   % 广州22.54, 114.06;   % 深圳30.67, 104.06;   % 成都34.27, 108.93;   % 西安31.98, 118.75;   % 南京39.92, 116.36;   % 天津28.71, 115.83;   % 南昌45.75, 126.63;   % 哈尔滨36.07, 120.38;   % 青岛38.04, 114.48;   % 石家庄29.59, 106.54;   % 重庆26.08, 119.30;   % 福州30.25, 120.16;   % 杭州28.19, 112.97;   % 长沙25.03, 102.73;   % 昆明35.68, 139.76;   % 东京37.56, 126.97;   % 首尔1.35, 103.82;    % 新加坡13.41, 103.86;   % 金边21.03, 105.85;   % 河内3.14, 101.69;    % 吉隆坡39.90, 32.85;    % 安卡拉37.97, 23.73;    % 雅典38.71, -9.14;    % 里斯本41.89, 12.50;    % 罗马52.52, 13.41;    % 柏林55.75, 37.62;    % 莫斯科48.86, 2.35;     % 巴黎
];n = length(C);  % 获取城市的个数
T = 100 * n;    % 初始温度
L = 10;         % 马尔可夫链长度
K = 0.986;      % 降温系数%%  构建城市坐标结构体
city = struct([]);
for i = 1:ncity(i).x = C(i,1);     % 经度city(i).y = C(i,2);     % 纬度
end%% 开始退火
% 统计迭代次数
count = 1;   
% 计算每次迭代后的总距离(第一次就是初始时,按照坐标的顺序计算的距离)
Dist(count) = GetDist(city,n); 
figure(1)
% 当温度无限趋于0度时停止迭代
while T > 0.01 % 每次降温 均进行多次迭代for i = 1:L% 计算原路线周游距离len1 = GetDist(city,n);% 产生随机扰动(随机交换两个城市的坐标)p1 = floor(1 + n * rand()); % rand函数产生一个0,1之间均匀分布的实数,包含0但不包含1p2 = floor(1 + n * rand()); % 因此这个表达式可以产生一个从1到n的随机数while (p1 == p2)p1 = floor(1 + n * rand()); p2 = floor(1 + n * rand());endtemp_city = city;% 交换第P1个城市和第P2个城市的坐标temp = temp_city(p1);temp_city(p1) = temp_city(p2);temp_city(p2) = temp;% 计算新路线的周游距离len2 = GetDist(temp_city,n);% 新、老路线的差值(相当于能量)delta = len2 - len1;if(delta<0)% 新路线的评估函数更小(记住,模拟退火算法相当于是一个求函数极小值的算法)city = temp_city;  % 更新原路线(变量里存放城市的顺序也就是访问城市的顺序)else% Metropolis接受准则(概率选择更差的解)if exp((len1-len2)/T) > rand()% 记住这个概率的公式,指数部分一定是要个负数,概率的值不可能超过1city = temp_city;endendend% 本次迭代结束,统计迭代次数加1count = count + 1; % 将本次迭代的最优解放在len中Dist(count) = GetDist(city,n); %% 本次退火结束,降温T = T * K;% 按照新的城市的顺序,把这些城市画出来for i = 1: n-1plot([city(i).x,city(i+1).x],[city(i).y,city(i+1).y],'bo-');hold on;endplot([city(n).x,city(1).x],[city(n).y,city(1).y],'ro-');title(['优化最短距离:', num2str(Dist(count))]);hold offpause(0.005); % 动态显示出每次的搜索结果
end
T2 = cputime;
figure(2)
plot(Dist,LineWidth=2)
xlabel("迭代次数")
ylabel("目标函数值")
title("适应度进化曲线","搜索时间:"+(T2-T1)+" s")
%% 评估函数
function result = GetDist(city,n)
% 计算总的周游路径长度(评估函数)
% city是各个城市的坐标result = 0;for i = 1:n-1result = result + sqrt((city(i).x - city(i+1).x)^2 + (city(i).y - city(i+1).y)^2);endresult = result + sqrt((city(n).x - city(1).x)^2 + (city(n).y - city(1).y)^2);
end

三、效果

周游图

适应度进化曲线

四、问题

        大家可以试一试更多的城市,当有很多城市的坐标相差不大时,在最后的搜索结果中,会出现一个非常奇怪的问题,就是在周游图中,有些城市消失了,检查存放城市的city结构体,是存放着这些坐标的,这里如果有知道的朋友还请多多批评指教,我将及时改正。

相关文章:

模拟退火算法应用——求解TSP问题

仅作自己学习使用 一、问题 旅行商问题(TSP) 是要求从一个城市出发&#xff0c;依次访问研究区所有的城市&#xff0c;并且只访问一次不能走回头路&#xff0c;最后回到起点&#xff0c;求一个使得总的周游路径最短的城市访问顺序。 采用模拟退火算法求解TSP问题&#x…...

【LeetCode】每日一题 2023_11_28 设计前中后队列(数组/链表/双端队列)

文章目录 刷题前唠嗑题目&#xff1a;设计前中后队列题目描述代码与解题思路偷看大佬题解 结语 刷题前唠嗑 LeetCode&#xff1f;启动&#xff01;&#xff01;&#xff01; 这道题的难度&#xff0c;才是我想象中的中等题的难度好吧&#xff0c;昨天那玩意对我来说还是太难了…...

python基于YOLOv8全系列模型【n/s/m/l/x】开发构建不同参数量级的钢铁产业产品智能自动化检测识别系统

在前文的项目开发实践中&#xff0c;我们已经以钢铁产业产品缺陷检测数据场景为基准&#xff0c;陆续开发构建了多款目标检测模型&#xff0c;感兴趣的话可以自行阅读即可。 《YOLOv3老矣尚能战否&#xff1f;基于YOLOv3开发构建建钢铁产业产品智能自动化检测识别系统&#xf…...

力扣142. 环形链表 II

文章目录 力扣142. 环形链表 II示例代码实现总结收获 力扣142. 环形链表 II 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c…...

【设计模式-2.2】创建型——简单工厂和工厂模式

说明&#xff1a;本文介绍设计模式中&#xff0c;创建型设计模式中的工厂模式&#xff1b; 飞机大战 创建型设计模式&#xff0c;关注于对象的创建&#xff0c;本文介绍的简单工厂和工厂模式同样也是。举一个游戏例子&#xff0c;如飞机大战游戏中&#xff0c;屏幕中敌人类型…...

将文件读入C中的字符数组

当您使用 C 编程语言时&#xff0c;您可能会遇到一些需要将文件读入字符数组的问题&#xff0c;例如分析每个字符的频率&#xff0c;或者将所有句子的每个起始词从小写转换为大写&#xff0c;反之亦然。该解决方案非常简单&#xff0c;但对于不太了解文件读取或写入的人来说可能…...

不小心删除了短信,如何在 Android 上恢复已删除的短信

不小心删除了文字消息在 Android 手机上使用可能会是一种令人痛苦的体验。这些消息可能包含有价值的信息、珍贵的回忆或重要的细节。幸运的是&#xff0c;您可以探索多种方法来恢复这些丢失的消息。在本文中&#xff0c;我们将深入研究可用于检索已删除短信的选项&#xff0c;并…...

Java电子招投标采购系统源码-适合于招标代理、政府采购、企业采购、等业务的企业

项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&#xff0c;以及审…...

springBoot的实现原理;SpringBoot是什么;使用SpringBoot的核心功能;springBoot核心注解以及核心配置文件

文章目录 springBootspringBoot的实现原理什么是 Spring Boot&#xff1f;SpringBoot是什么为什么要使用springBootSpring Boot的核心功能Spring Boot 主要有如下优点&#xff1a; SpringBoot启动过程-流程Spring Boot 的核心注解是哪个&#xff1f;什么是 JavaConfig&#xff…...

logback-spring.xml详解

《springboot使用logback日志框架超详细教程》文中&#xff0c;filter中最重要的两个过滤器LevelFilter&#xff08;日志级别精确匹配&#xff09;、ThresholdFilter&#xff08;阈值过滤&#xff09; 的描述非常准确&#xff1a; springboot使用logback日志框架超详细教程_sp…...

【Python】nn.BCEWithLogitsLoss函数详解

nn.BCEWithLogitsLoss() 是 PyTorch 中一个用于二元分类问题的损失函数&#xff0c;它结合了 Sigmoid 层&#xff08;将输出映射到 [0,1] 范围内&#xff09;和 Binary Cross Entropy&#xff08;BCE&#xff09;损失。这可以避免在正向和反向传播过程中可能出现梯度爆炸或梯度…...

【C++】日期类的实现

在上篇博客中我们已经学习了C中的运算符重载&#xff0c;我们说&#xff0c;操作符只能对于内置类型进行操作&#xff0c;对自定义类型我们需要自己定义函数去实现一系列的操作 那么这篇博客我们就专门把日期这个类单独拿出来写一下它都有哪些有意义的可以重载的运算符&#xf…...

带残差连接的ResNet18

目录 1 模型构建 1.1 残差单元 1.2 残差网络的整体结构 2 没有残差连接的ResNet18 2.1 模型训练 2.2 模型评价 3 带残差连接的ResNet18 3.1 模型训练 3.2 模型评价 4 与高层API实现版本的对比实验 总结 残差网络&#xff08;Residual Network&#xff0c;ResNet&#xff09;…...

【深入解析git和gdb:版本控制与调试利器的终极指南】

【本节目标】 1. 掌握简单gdb使用于调试 2. 学习 git 命令行的简单操作, 能够将代码上传到 Github 上 1.Linux调试器-gdb使用 1.1.背景 程序的发布方式有两种&#xff0c;debug模式和release模式release模式不可被调试&#xff0c;debug模式可被调试Linux gcc/g出来的二进制…...

CGAN原理讲解与源码

1.CGAN原理 生成器&#xff0c;输入的是c和z&#xff0c;z是随机噪声&#xff0c;c是条件&#xff0c;对应MNIST数据集&#xff0c;要求规定生成数字是几。 输出是生成的虚假图片。 生成器生成的图片被判别器认为是真实图片&#xff0c;那么标签就是1 其实判别器模型输出的是…...

C#实体类与XML互转以及List和DataTable转XML的使用

引言 在C#开发中&#xff0c;数据的存储和传输是非常常见的需求。使用XML作为数据格式有很多优点&#xff0c;例如可读性强、易于解析等。而实体类、List和DataTable是表示数据模型的常用方式。本文将介绍如何在C#中实现实体类、List和DataTable与XML之间的相互转换&#xff0c…...

uniapp的vue3的模版的setup函数内使用uniapp内置方法

vue2使用方式直接在method同级使用就行,但是在vue3的setup函数内直接使用会报错,本人找了好久,发现vue3需要导入uniapp模块才能使用,具体如下 使用uniapp上拉加载更多方法 <script>import {onReachBottom} from dcloudio/uni-apponReachBottom(() > {console.log(&qu…...

UI自动化的基本知识

一、UI自动化测试介绍 1、什么是自动化测试 概念&#xff1a;由程序代替人工进行系统校验的过程 1.1自动化测试能解决的问题&#xff1f; 回归测试 (冒烟测试) 针对之前老的功能进行测试 通过自动化的代码来实现。 针对上一个版本的问题的回归 兼容性测试 web实例化不同的浏…...

python实现C++简易自动压行

突发奇想&#xff0c;想要将自己的c压行之后交上去。但是苦于手动压行效率太低&#xff0c;在网上搜索压行网站没有找到&#xff0c;突然发现压行不就是检查检查去个换行符吗。于是心血来潮&#xff0c;用python实现了一个简易压行程序。 首先&#xff0c;宏定义等带#的文件不…...

京东数据分析(京东大数据采集):2023年线上珍珠市场销售数据采集

在珠宝首饰市场&#xff0c;从黄金到钻石&#xff0c;如今年轻人的新风潮又转向了珍珠。珍珠热潮并非刚刚兴起&#xff0c;早在前两年&#xff0c;抖音、快手等短视频台的珍珠开蚌直播内容&#xff0c;就掀起了一波珍珠热潮。 此后&#xff0c;随着珍珠饰品被越来越多社交平台的…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...