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

(转载)基于模拟退火算法的TSP问题求解(matlab实现)

1 理论基础

1.1 模拟退火算法基本原理

        模拟退火(simulated annealing,SA)算法的思想最早是由Metropolis等提出的。其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。模拟退火法是一种通用的优化算法,其物理退火过程由以下三部分组成:
        (1)加温过程。其目的是增强粒子的热运动,使其偏离平衡位置。当温度足够高时,固体将熔为液体,从而消除系统原先存在的非均匀状态。
        (2)等温过程。对于与周围环境交换热量而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行的,当自由能达到最小时,系统达到平衡状态。
        (3)冷却过程。使粒子热运动减弱,系统能量下降,得到晶体结构。
        其中,加温过程对应算法的设定初温,等温过程对应算法的Metropolis抽样过程,冷却过程对应控制参数的下降。这里能量的变化就是目标函数,要得到的最优解就是能量最低态。Metropolis准则是SA算法收敛于全局最优解的关键所在,Metropolis准则以一定的概率接受恶化解,这样就使算法跳离局部最优的陷阱。
        模拟退火算法为求解传统方法难处理的TSP问题提供了一个有效的途径和通用框架,并逐渐发展成一种迭代自适应启发式概率性搜索算法。模拟退火算法可以用以求解不同的非线性问题,对不可微甚至不连续的函数优化,能以较大概率求得全局优化解,该算法还具有较强的鲁棒性、全局收敛性、隐含并行性及广泛的适应性,并且能处理不同类型的优化设计变量(离散的、连续的和混合型的),不需要任何的辅助信息,对目标函数和约束函数没有任何要求。利用Metropolis算法并适当地控制温度下降过程,在优化问题中具有很强的竞争力,本章研究基于模拟退火算法的TSP算法。
        SA算法实现过程如下(以最小化问题为例):

 1.2 TSP问题介绍

2 案例背景

2.1 问题描述

        本案例以14个城市为例,假定14个城市的位置坐标如表1所列。寻找出一条最短的遍历14个城市的路径。
表1 各个城市的坐标

2.2 解题思路及步骤

        1.算法流程
        模拟退火算法求解TSP问题流程图如图1所示。
        2.模拟退火算法实现
        (1)控制参数的设置
        需要设置的主要控制参数有降温速率q、初始温度T0、结束温度Tend以及链长L。
        (2)初始解
        对于n个城市的TSP问题,得到的解就是对1~n的一个排序,其中每个数字为对应城市的编号,如对10个城市的TSP问题{1,2,3,4,5,6,7,8,9,10},则|1|10|2|4|5|6|8|7|9|3就是一个合法的解,采用产生随机排列的方法产生一个初始解S。
        (3)解变换生成新解
        通过对当前解S1进行变换,产生新的路径数组即新解,这里采用的变换是产生随机数的方法来产生将要交换的两个城市,用二邻域变换法产生新的路径,即新的可行解S2。例如n=10时,产生两个[1,10]范围内的随机整数r1和r2,确定两个位置,将其对换位置,如r1=4,r2=7
        (4)Metropolis准则
        若路径长度函数为f(S),则当前解的路径为f(S1),新解的路径为f(S2),路径差为df=f(S2)-f(S1),则Metropolis准则为

        (5)降 温
        利用降温速率q进行降温,即T=qT,若T小于结束温度,则停止迭代输出当前状态,否则继续迭代。

3 MATLAB程序实现

3.1 计算距离矩阵

        利用给出的N个城市的坐标,算出N个城市的两两之间的距离,得到距离矩阵(N×N)。计算函数为Distance,得到初始种群。
function D=Distanse(a)
%% 计算两两城市之间的距离
%输入 a  各城市的位置坐标
%输出 D  两两城市之间的距离
row=size(a,1);
D=zeros(row,row);
for i=1:rowfor j=i+1:rowD(i,j)=((a(i,1)-a(j,1))^2+(a(i,2)-a(j,2))^2)^0.5;D(j,i)=D(i,j);end
end

3.2 画路线轨迹图

        画出给的路线的轨迹图函数为DrawPath,程序代码如下:
function DrawPath(Chrom,X)
%% 画路径函数
%输入
% Chrom  待画路径   
% X      各城市坐标位置
R=[Chrom(1,:) Chrom(1,1)]; %一个随机解(个体)
figure;
hold on
plot(X(:,1),X(:,2),'o','color',[0.5,0.5,0.5])
plot(X(Chrom(1,1),1),X(Chrom(1,1),2),'rv','MarkerSize',20)
for i=1:size(X,1)text(X(i,1)+0.05,X(i,2)+0.05,num2str(i),'color',[1,0,0]);
end
A=X(R,:);
row=size(A,1);
for i=2:row[arrowx,arrowy] = dsxy2figxy(gca,A(i-1:i,1),A(i-1:i,2));%坐标转换annotation('textarrow',arrowx,arrowy,'HeadWidth',8,'color',[0,0,1]);
end
hold off
xlabel('横坐标')
ylabel('纵坐标')
title('轨迹图')
box on

3.3 输出路径函数

        将得到的路径输出显示在Command Window中,函数名为OutputPath。
function p=OutputPath(R)
%% 输出路径函数
%输入:R 路径
R=[R,R(1)];
N=length(R);
p=num2str(R(1));
for i=2:Np=[p,'—>',num2str(R(i))];
end
disp(p)

3.4 可行解路线长度函数

        计算可行解的路线长度函数为PathLength,程序代码如下:
function len=PathLength(D,Chrom)
%% 计算各个体的路径长度
% 输入:
% D     两两城市之间的距离
% Chrom 个体的轨迹
[row,col]=size(D);
NIND=size(Chrom,1);
len=zeros(NIND,1);
for i=1:NINDp=[Chrom(i,:) Chrom(i,1)];i1=p(1:end-1);i2=p(2:end);len(i,1)=sum(D((i1-1)*col+i2));
end

3.5 生成新解

        解变换生成新解函数为NewAnswer,程序代码如下:
function S2=NewAnswer(S1)
%% 输入
% S1:当前解
%% 输出
% S2:新解
N=length(S1);
S2=S1;                
a=round(rand(1,2)*(N-1)+1); %产生两个随机位置 用来交换
W=S2(a(1));
S2(a(1))=S2(a(2));
S2(a(2))=W;         %得到一个新路线

3.6Metropolis准则函数

        Metropolis准则函数为Metropolis,程序代码如下:
function [S,R]=Metropolis(S1,S2,D,T)
%% 输入
% S1:  当前解
% S2:   新解
% D:    距离矩阵(两两城市的之间的距离)
% T:    当前温度
%% 输出
% S:   下一个当前解
% R:   下一个当前解的路线距离
%%
R1=PathLength(D,S1);  %计算路线长度
N=length(S1);         %得到城市的个数R2=PathLength(D,S2);  %计算路线长度
dC=R2-R1;   %计算能力之差
if dC<0       %如果能力降低 接受新路线S=S2;R=R2;
elseif exp(-dC/T)>=rand   %以exp(-dC/T)概率接受新路线S=S2;R=R2;
else        %不接受新路线S=S1;R=R1;
end

3.7 主函数

        模拟退火算法参数设置如表1所列。         

        主函数代码如下:

clc;
clear;
close all;
%%
tic
T0=1000;   % 初始温度
Tend=1e-3;  % 终止温度
L=500;    % 各温度下的迭代次数(链长)
q=0.9;    %降温速率%% 加载数据
load CityPosition1;
%%
D=Distanse(X);  %计算距离矩阵
N=size(D,1);    %城市的个数
%% 初始解
S1=randperm(N);  %随机产生一个初始路线%% 画出随机解的路径图
DrawPath(S1,X)
pause(0.0001)
%% 输出随机解的路径和总距离
disp('初始种群中的一个随机值:')
OutputPath(S1);
Rlength=PathLength(D,S1);
disp(['总距离:',num2str(Rlength)]);%% 计算迭代的次数Time
Time=ceil(double(solve(['1000*(0.9)^x=',num2str(Tend)])));
count=0;        %迭代计数
Obj=zeros(Time,1);         %目标值矩阵初始化
track=zeros(Time,N);       %每代的最优路线矩阵初始化
%% 迭代
while T0>Tendcount=count+1;     %更新迭代次数temp=zeros(L,N+1);for k=1:L%% 产生新解S2=NewAnswer(S1);%% Metropolis法则判断是否接受新解[S1,R]=Metropolis(S1,S2,D,T0);  %Metropolis 抽样算法temp(k,:)=[S1 R];          %记录下一路线的及其路程end%% 记录每次迭代过程的最优路线[d0,index]=min(temp(:,end)); %找出当前温度下最优路线if count==1 || d0<Obj(count-1)Obj(count)=d0;           %如果当前温度下最优路程小于上一路程则记录当前路程elseObj(count)=Obj(count-1);%如果当前温度下最优路程大于上一路程则记录上一路程endtrack(count,:)=temp(index,1:end-1);  %记录当前温度的最优路线T0=q*T0;     %降温fprintf(1,'%d\n',count)  %输出当前迭代次数
end
%% 优化过程迭代图
figure
plot(1:count,Obj)
xlabel('迭代次数')
ylabel('距离')
title('优化过程')%% 最优解的路径图
DrawPath(track(end,:),X)%% 输出最优解的路线和总距离
disp('最优解:')
S=track(end,:);
p=OutputPath(S);
disp(['总距离:',num2str(PathLength(D,S))]);
disp('-------------------------------------------------------------')
toc

4 结果分析

        优化前的一个随机路线轨迹图如图2所示。
        随机路线为6—>3—>2—>11—>14—>7—>4—>8—>13—>12—>10—>5—>9—>1—>6。
        总距离为71.4209.
 
        优化后的路线如图3所示。

        最优解为:
        9—>11—>1—>8—>13—>7—>12—>6—>5—>4—>3—>14—>2—>10—>9
        总距离:29.6889 

        优化迭代过程如图4所示。
        由图4可以看出,优化前后路径长度得到很大改进,80代以后路径长度已经保持不变了,可以认为已经是最优 解了。 上面的程序中城市数只有14个,对于更多的城市,坐标随意的城市也是可以计算的,例如N=50,坐标X使用随机数产生:
X=rand(N,2)*10;
这时调整对应的参数,如表2所列。

        即可得到如下结果:优化前的轨迹如图5所示,优化后的轨迹如图6所示,优化迭代过程如图7所示。

初始种群中的个随机解:
22—>31—>50—>37—>11—>3—>23—>46—>19—>28—>48—>1—>47—>12—>45—>42—>40—>39—>33—>34—>18—>41—>25—>13—>49—>27—>36—>29—>16—>6—>2—>14—>21—>5—>24—>32—>38—>43—>7—>4—>26—>8—>9—>20—>44—>35—>15—>30—>17—>10—>22
总距离:271.7719

最优解:
33—>45—>13—>50—>20—>26—>25—>15—>2—>17—>18—>8—>41—>3—>6—>34—>38—>47—>14—>42—>44—>7—>36—>22—>39—>4—>37—>46—>1—>5—>30—>43—>27—>31—>32—>21—>9—>11—>29—>23—>40—>49—>28—>19—>48—>12—>35—>16—>24—>10—>33
总距离:71.3071

5 延伸阅读

5.1 模拟退火算法的改进

        上述程序是比较经典的模拟退火解决TSP问题的算法,程序可以做进一步的改进,在解变换产生新解的过程中只使用了交换两个城市的方法,可以采用下面的方法进行改进,例如:
        (1)使用逆转操作,即选择两个城市后,逆转这两个城市之间的所有城市。
        (2)选择3个城市,将两个城市之间的城市插入到第3个城市的后面(这两个城市之间不包括第3个城市),

5.2 算法的局限性

        问题规模n比较小时,得到的一般都是最优解,当规模比较大时,一般只能得到的近似解。这时可以通过增大种群大小和增加最大遗传代数使优化值更接近最优解。

相关文章:

(转载)基于模拟退火算法的TSP问题求解(matlab实现)

1 理论基础 1.1 模拟退火算法基本原理 模拟退火(simulated annealing,SA)算法的思想最早是由Metropolis等提出的。其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性。模拟退火法是一种通用的优化算法&#xff0c;其物理退火过程由以下三部分组成&am…...

splitpcap 使用说明

背景 当PCAP原始文件特别巨大的时候&#xff0c;整个文件直接载入内存是相当耗时的&#xff0c;于是一个简单的想法是将大的PCAP切分成若干小PCAP。对于这个任务&#xff0c;现有工具splitcap是可以完成的。无论是按照主机对、还是按照五元组信息切分&#xff0c;splitcap都会…...

配置docker阿里云镜像加速

默认情况下docker安装镜像文件是从docker官方的镜像中心下载&#xff1a;https://hub.docker.com/ &#xff0c; 有时速度慢&#xff0c;可以通过配置docker阿里云镜像来加速&#xff0c;配置后&#xff0c;就从国内阿里云下载。 注册阿里云用户&#xff0c;登录->工作台-&g…...

《消息队列高手课》课程学习笔记(八)

如何实现高性能的异步网络传输&#xff1f; **异步与同步模型最大的区别是&#xff0c;同步模型会阻塞线程等待资源&#xff0c;而异步模型不会阻塞线程&#xff0c;它是等资源准备好后&#xff0c;再通知业务代码来完成后续的资源处理逻辑。**这种异步设计的方法&#xff0c;…...

DC电源模块在工业自动化的应用

BOSHIDA DC电源模块在工业自动化的应用 随着自动化技术的不断发展&#xff0c;DC电源模块已成为工业控制系统中不可或缺的一个组成部分。在许多自动化系统中&#xff0c;如机器人、控制器、PLC等&#xff0c;都需要使用到直流电源模块来提供稳定可靠的电源&#xff0c;以确保系…...

Java容器-集合

目录 1.Java容器概述 2.集合框架 3.Collection接口中的方法使用 4.iterator() 5.List接口 2.ArrayList、LinkedList、Vector相同点 3.不同点 1.ArrayList 2.LinkedList 3.Vector 4.Vector源码分析 5.ArrayList源码分析 6.LinkedList源码分析 6.List中的常用方法 …...

总结890

学习目标&#xff1a; 月目标&#xff1a;6月&#xff08;线性代数强化9讲2遍&#xff0c;背诵15篇短文&#xff0c;考研核心词过三遍&#xff09; 周目标&#xff1a;线性代数强化3讲&#xff0c;英语背3篇文章并回诵&#xff0c;检测 每日必复习&#xff08;5分钟&#xff…...

2023年5月青少年机器人技术等级考试理论综合试卷(二级)

青少年机器人技术等级考试理论综合试卷&#xff08;二级&#xff09;2023.6 分数&#xff1a; 100 题数&#xff1a; 45 一、 单选题(共 30 题&#xff0c; 共 60 分) 1.下图中的凸轮机构使用了摆动型从动件的是&#xff1f; &#xff08; &#xff09; A.a B.b C.c D.d 试题类…...

2023CCPC河南省赛 VP记录

感觉现在的xcpc&#xff0c;风格越来越像CF&#xff0c;不是很喜欢&#xff0c;还是更喜欢多点算法题的比赛 VP银了&#xff0c;VP银也是银 感觉省赛都是思维题&#xff0c;几乎没有算法题&#xff0c;感觉像打了场大型的CF B题很简单没开出来&#xff0c;一直搞到最后&…...

【ECCV2022】DaViT: Dual Attention Vision Transformers

DaViT: Dual Attention Vision Transformers, ECCV2022 解读&#xff1a;【ECCV2022】DaViT: Dual Attention Vision Transformers - 高峰OUC - 博客园 (cnblogs.com) DaViT&#xff1a;双注意力Vision Transformer - 知乎 (zhihu.com) DaViT: Dual Attention Vision Trans…...

Apache 配置与应用

Apache 配置与应用 一、构建虚拟 Web 主机httpd服务支持的虚拟主机类型包括以下三种: 二、基于域名的虚拟主机1&#xff0e;为虚拟主机提供域名解析方法一&#xff1a;部署DNS域名解析服务器 来提供域名解析方法二&#xff1a;在/etc/hosts 文件中临时配置域名与IP地址的映射关…...

OpenGL 纹理

1.简介 纹理是一个2D图片&#xff08;甚至也有1D和3D的纹理&#xff09;&#xff0c;它可以用来添加物体的细节&#xff1b;你可以想象纹理是一张绘有砖块的纸&#xff0c;无缝折叠贴合到你的3D的房子上&#xff0c;这样你的房子看起来就像有砖墙外表了。 为了能够把纹理映射(M…...

Jeston Orin Nnao 安装pytorch与torchvision环境

大家好&#xff0c;我是虎哥&#xff0c;Jeston Orin nano 8G模块&#xff0c;提供高达 40 TOPS 的 AI 算力&#xff0c;安装好了Jetpack5.1之后&#xff0c;我们需要配置一些支持环境&#xff0c;来为我们后续的深度学习开发提供支持。本章内容&#xff0c;我将主要围绕安装对…...

ROS:常用可视化工具的使用

目录 一、日志输出工具——rqt_console二、绘制数据曲线——rqt_plot三、图像渲染工具——rqt_image_view四、图形界面总接口——rqt五、Rviz六、Gazebo 一、日志输出工具——rqt_console 启动海龟键盘控制节点&#xff0c;打开日志输出工具 roscorerosrun turtlesim turtles…...

智能应用搭建平台——LCHub低代码表单 vs 流程表单 vs 仪表盘

1. LCHub低代码如何选择 「流程表单」:填报数据,并带有流程审批功能,适合报销、请假申请或其他工作流; 「表单」:填报数据,并带有数据协作功能,如修改、删除、导入、导出,并可以给不同的人不同的管理权限; 「仪表盘」:数据分析处理、结果展示功能,如数据汇总、趋…...

Mac下通过Docker安装ElasticSearch集群

1、安装ElasticSearch 使用docker直接获取es镜像&#xff0c;执行命令docker pull elasticsearch:7.7.0 执行完成后&#xff0c;执行docker images即可看到上一步拉取的镜像。 2、创建数据挂在目录&#xff0c;以及配置ElasticSearch集群配置文件 创建数据文件挂载目录 mkdir -…...

MySQL redo log、undo log、binlog

MySQL是一个广泛使用的关系型数据库管理系统&#xff0c;它通过一系列的日志来保证数据的一致性和持久性。在MySQL中&#xff0c;有三个重要的日志组件&#xff0c;它们分别是redo log&#xff08;重做日志&#xff09;、undo log&#xff08;回滚日志&#xff09;和binlog&…...

文件包含漏洞

一、原理解析。 开发人员通常会把可重复使用的函数写到单个文件中&#xff0c;在使用到某些函数时&#xff0c;可直接调用此文件&#xff0c;而无须再次编写&#xff0c;这种调用文件的过程被称为包含。 注意&#xff1a;对于开发人员来讲&#xff0c;文件包含很有用&#xf…...

Python 中的 F-Test

文章目录 F 统计量和 P 值方差(ANOVA) 分析中的 F 值 本篇文章介绍 F 统计、F 分布以及如何使用 Python 对数据执行 F-Test 测试。 F 统计量是在方差分析检验或回归分析后获得的数字&#xff0c;以确定两个总体的平均值是否存在显着差异。 它类似于 T 检验的 T 统计量&#xf…...

Docker网络模式

一、docker网络概述 1、docker网络实现的原理 Docker使用Linux桥接&#xff0c;在宿主机虚拟一个Docker容器网桥(docker0)&#xff0c;Docker启动一个容器时会根据Docker网桥的网段分配给容器一个IP地址&#xff0c;称为Container-IP&#xff0c; 同时Docker网桥是 每个容器的…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...