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

news/2024/4/24 5:05:13/

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比较小时,得到的一般都是最优解,当规模比较大时,一般只能得到的近似解。这时可以通过增大种群大小和增加最大遗传代数使优化值更接近最优解。

http://www.ppmy.cn/news/280433.html

相关文章

locust的安装和运行的demo

最近开始学习locust&#xff0c;从最初的安装到运行一个简单的demo。 lcoust官网上有介绍安装和使用&#xff1a;https://docs.locust.io/en/stable/installation.html locust 需要的python环境&#xff0c;首先要安装python。 因为本人已经安装了python以及python…

亚马逊美国站 隐形墨水笔CPC认证 儿童玩具

隐形墨水笔 一种采用透明墨水并集成紫外线灯的笔。 隐形笔是指书写后的字迹在正常光线下不能看见&#xff08;隐形&#xff09;的笔&#xff0c;只有在紫外灯的照射下才能看见。一般用来标记物品或写不想轻易让人看见的语句。 市面上的隐形笔分为水性隐形墨水笔、油性隐形墨水…

故障分析 | 一个因 SSL 配置导致的复制异常报错

在构建 MySQL 复制过程中&#xff0c;IO 线程始终连接不上主库&#xff0c;反复确认复制账号的权限、账号密码都没问题&#xff0c;最终定位为 SSL 配置的问题。 作者&#xff1a;木板。某全国性股份制银行 DBA。擅长 DB2&#xff0c;MySQL 和 Oracle 数据库的运行维护和调优、…

【MySQL】JDBC编程 (Java的数据库编程:JDBC 导入驱动包 MySQL Connector Java 编写JDBC代码 插入操作 查询操作)

文章目录 Java的数据库编程&#xff1a;JDBC导入驱动包MySQL Connector Java 编写JDBC代码插入操作查询操作 Java的数据库编程&#xff1a;JDBC 真正在工作中操作数据库,99.9%都是通过代码来操作,很少会手动在客户端里输入sql语句.各种数据库,MySQL,Oracle,SQL Server 在开发的…

U盘工具量产过程

一、确定芯片主控及芯片型号 1、查找主控用U盘检测工具芯片精灵或芯片无忧 芯片精灵下载地址: http://www.upantool.com/test/xinpian/2011/ChipGenius_V4.html 芯片无忧下载地址: http://www.upantool.com/test/ChipEasy.html 2、运行芯片精灵&#xff08;检测更准确&#xf…

一款很好用的网络U盘

http://u.115.com/invite/993aa5be Hi~&#xff0c;我最近使用了115网络U盘&#xff0c;邀请你一起加入体验~ 115网络U盘很好用哦&#xff0c;我的几个好友已经在上面注册了。我们可以相互分享文件、文档、照片、音乐&#xff0c;3G 的永久空间、5G 的临时空间&#xff0c;还可…

自己动手做一个绿色便携版的谷歌浏览器Chrome,可以放入U盘随意带走的

鉴于很多浏览器流氓而且广告又太多,所以无法自拔的用上了谷歌浏览器,但是经常的换电脑又无法保存自己的浏览器使用习惯和收藏数据,这个时候就想到有绿色的版的谷歌浏览器,但是找了很多网上的资源,软件,都不太满意,所以想自己做一个绿色版的谷歌浏览器,那么经过一个下午的努力,成…

U盘数据恢复工具哪个好?

U盘是目前最为常用的数据存储设备之一&#xff0c;用户可以通过U盘将数据随身携带或是在不同设备之间传输数据。存储在U盘中的数据一般都比较重要&#xff0c;如果数据不小心丢失了&#xff0c;会给用户造成很多麻烦和损失。 U盘数据丢失是非常常见的数据问题之一&#xff0c;…

Microsoft SQL Server 2019 详细安装教程

文章目录 系列文章目录前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 一、SqlServer2019安装步骤 双击运行好的setup.exe 选择安装&#xff0c;点击第一个全新独立安装 默认点击下一步 勾选介绍&#xff0c;点击下一步 点击下一步 点击下一步 勾选需要…

【Python入门篇】——Python函数(函数介绍,函数的定义,函数的参数和函数的返回值)

作者简介&#xff1a; 辭七七&#xff0c;目前大一&#xff0c;正在学习C/C&#xff0c;Java&#xff0c;Python等 作者主页&#xff1a; 七七的个人主页 文章收录专栏&#xff1a; Python入门&#xff0c;本专栏主要内容为Python的基础语法&#xff0c;Python中的选择循环语句…

操作系统 第三章 3.1 错题整理

装入时&#xff0c;相应的地址要修改 若存放的位置从150开始 则所有的地址都加150 加完后的地址是物理地址 不能改变 可变分区&#xff1a;产生的外部碎片需要紧凑 C D 都是执行时才进行地址的变换的 该共享段直接在内存中 不用调入调出 供多个进程共享 II 假设该进程很小 页面…

云渲染对学生党有哪些好处和挑战?

云渲染是一种依托于云计算的云端服务&#xff0c;用户将本地任务提交到远程服务器&#xff0c;由远程的计算机集群资源进行运算操作&#xff0c;将上传的任务进行云端渲染后再返回本地。云渲染的优势是可以节省本地设备的性能和时间&#xff0c;提高渲染效率和质量。那么&#…

计算机主机电源是否都一样,一般计算机电源都在多少电压?

01 180-250伏 一般计算机电源都在180至250伏电压范围内工作。计算机电源是安装在计算机内部&#xff0c;负责将普通市电转换为计算机可以使用的电压的一个计算机部件。计算机电源为开关电路&#xff0c;将普通交流电转为直流电&#xff0c;再通过斩波控制电压&#xff0c;将不同…

一般计算机电源都在多少压力,一般计算机电源都在多少电压 计算机电源一般都在多少电压...

1、一般计算机电源都在180至250伏电压范围内工作。 2、计算机电源是安装在计算机内部&#xff0c;负责将普通市电转换为计算机可以使用的电压的一个计算机部件。计算机电源为开关电路&#xff0c;将普通交流电转为直流电&#xff0c;再通过斩波控制电压&#xff0c;将不同的电压…

Intel中支持Intel VT的CPU型号

Intel作为CPU的霸主&#xff0c;有时候做的事情&#xff0c;就不那么厚道。 人家AMD几乎是全线产品都支持CPU Virtualization——AMD-V。 Intel的&#xff0c;却只有高端产品才有&#xff0c;甚至一些早期的高端产品都没有&#xff01;不知道他当初是怎么考虑的。 可能之前&…

【Spring Boot学习】日志文件,Spring Boot也会写日记了,这些事你知道嘛 ? ? ?

前言: 大家好,我是良辰丫,在上一篇文章中我们已经学习了Spring Boot的配置,接下来我们要学习一些日志相关的东西,什么是日志呢?我们慢慢往下看.&#x1f48c;&#x1f48c;&#x1f48c; &#x1f9d1;个人主页&#xff1a;良辰针不戳 &#x1f4d6;所属专栏&#xff1a;javaE…

酷睿i7-i5-i3区别の酷睿-CPU-真伪鉴别

一般来说.分别酷睿-CPU i3-i5-i7肯定不是问题&#xff0c;如果荷包充实的话&#xff0c;可能就直接上i7 980x了。但更多普通用户在攒机或者是选购时还是会有很多疑问&#xff0c;他们只有要选购时才会遇到怎么分辨i3/i5/i7这种问题。 就比如有非常多的普通用户不清楚i7 也有两种…

CPU类型

CPU插座&#xff08;英语&#xff1a;CPU socket&#xff09; 插座名称制造年份停止使用年份支持的CPU封装形式针脚数针脚大小总线速度备注DIP1970s仍然使用Intel 8086 Intel 8088DIP402.54mm5/10MHz PLCC ?仍然使用Intel 80186 Intel 80286 Intel 80386PLCC68, 1321.27mm6-…

最新计算机cpu简介,计算机cpu的类型是什么?计算机CPU分类简介

引言计算机cpu对计算机的重要性与大脑对人类的重要性一样. 它几乎掌握了整个计算机的操作系统. 如果cpu出现问题,则整个计算机将一片混乱. 那么,市场上最常见的计算机CPU类型是什么?我应该怎么买? 如果您想了解计算机cpu的类型,那么您首先必须知道计算机cpu是什么. 我们通…

获奖!!!元年科技荣获信创“大比武”云平台技术支撑赛道单项奖

2022年底&#xff0c;由北京航空航天大学、北京理工大学、中国电子工业标准化技术协会信息技术应用创新工作委员会&#xff08;简称信创工委会&#xff09;共同主办的2022信创“大比武”活动圆满落幕。大赛由云平台技术支撑、操作系统生态建设、通信业务运营技术等七大赛道构成…