专栏首页拇指笔记【数学建模】模拟退火算法介绍及实现

【数学建模】模拟退火算法介绍及实现

模拟退火算法

模拟退火算法为一种现代优化算法,用来求解全局最小(最优)解

模拟退火法的核心原理:当材料从状态i进入状态j时,若E(j)<=E(i),状态会被转移(E(i)=E(j));若为其他情况,状态会以小概率被转移。也就是说,模拟退火法是一个不断寻找新解和缓慢降温交替的过程。具体实现:

  1. 优化函数 f(x)。
  2. 初始温度,初始解x0。
  3. 根据初始温度,初始解,生成下一个解x2。
  4. 判断f(x2)与f(x0)的关系,并根据核心原理进行判断、取值。
  5. 根据规定的每一个温度结束的标志,判断是否需要降温
  6. 返回第三步

算法流程

具体应用例子

求解TSP问题 例:有100个目标,需要找出巡航最优路径。

代码实现

	clc,clear
	
	%导入数据部分
	
	[~,~,raw] = xlsread('sj.xlsx','Sheet1','A2:H26');
	sj0 = reshape([raw{:}],size(raw)); %将raw{:}重构成原来尺寸的矩阵
	x = sj0(:,[1:2:8]);     %将数据中的经度部分存储在x矩阵中
	x = x(:);               %将x(四列)转为一列
	y = sj0(:,[2:2:8]);     %将数据中的纬度部分存储在y矩阵中
	y = y(:);               %将y(四列)转为一列
	
	%对数据进行处理的部分
	
	sj = [x y];             %将xy矩阵合成,sj中第一列为x;sj中第二列为y
	d1 = [70,40];           %将基地位置存储进去
	sj = [d1;sj;d1];        %将基地存储入数据中,都整合成两列
	sj = sj*pi/180;         %将角度转为弧度制(计算距离时,位置坐标被当作角度计算)
	
	%创建距离公式,距离存储矩阵(用于存储两个点之间的距离)
	
	d = zeros(102);         %创建距离矩阵
	for i = 1:101
	    for j = i+1:102
	        d(i,j) = 6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(i,2))*sin(sj(j,2)));
	    end
	end
	d =d +d';
	
	path = [];              %创建用于存储路径的矩阵
	long = inf;             %初始化距离变量(inf为正无穷)
	rand('state',sum(clock));           %初始化随机数发生器,这种写法的作用:是每一次初始值不同,避免出现相同数字
	
	%蒙特卡洛算法部分,为了得到更好的初始值,先用蒙特卡洛法求解相对较好的解
	
	for j=1:1000            %随机产生一千种解
	    path0 = [1,1+randperm(100),102];%解的情况
	    temp =0;
	    %求解每种情况对应的距离值
	
	    for i=1:101         %通过循环,解得该情况下的距离
	        temp = temp + d(path0(i)+path0(i+1));
	    end
	
	    %对每种情况进行比较,得到最优(小)解
	
	    if temp<long
	        path = path0;
	        long =temp;
	        long
	    end
	end
	
	%模拟退火法部分
	e = 0.1^30;     %结束条件
	L = 20000;      %迭代次数(解空间的大小)
	at = 0.999;     %执行一次的降温比例
	T = 1;          %初始温度
	for k =1:L
	    c = 2+floor(100*rand(1,2));
	    %另c取20000次大于2的值;其中c是一个一行二列的矩阵,rand产生一行二列的元素大于0小于1的随机数矩阵
	    c = sort(c);        %对c的元素进行升序排列
	    c1 = c(1);c2=c(2);
	    df = d(path(c1-1),path(c2))+d(path(c1),path(c2+1)) - d(path(c1-1),path(c1))-d(path(c2),path(c2+1));
	    %判断两组不相邻的两个点的具体是否小于两组相邻两个点之间的距离
	    if df<0
	        path = [path(1:c1-1),path(c2:-1:c1),path(c2+1:102)]; long = long+df;
	        %如果新解距离小于原来解,则进行替换
	    elseif exp(-df/T) >= rand
	        path = [path(1:c1-1),path(c2:-1:c1),path(c2+1:102)]; long = long+df;
	        %以这个极小的概率,进行替换
	    end
	    T = T*at;
	    if T<e
	        break;
	    end
	end
	
	%输出部分
	
	path;
	long;
	xx = sj(path,1);
	yy = sj(path,2);
	figure
	plot(xx,yy,'- *')
	legend('巡航最优路径')
	figure
	plot(xx,yy,'ro')
	legend('巡航点位置')

实现效果

模拟退火法模板

依据上述程序改动

	%模拟退火法部分
	e =   ;     %结束条件(到该温度终止)
	L =   ;     %迭代次数(解空间的大小)
	at =  ;     %执行一次的降温比例
	T =   ;     %初始温度
	for k =1:L
		%{

		计算新解的代价
		
		%}
	    
	    if %取新解的条件(新解的代价需要满足的条件)
	        
	    %{
		满足条件,进行替换
		%}

	    elseif exp(-df/T) >= rand	%不满足条件且被替换的概率
		
		%{
		发生这个概率的事件,进行替换
		}%
	    
	    end

	    T = T*at;	%每次进行降温
	    if T<e		%达到目标温度,结束模拟退火法
	        break;
	    end

本文分享自微信公众号 - 拇指笔记(shuzhi990),作者:拇指笔记

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【动手学深度学习笔记】之对模型参数的访问、初始化和共享

    在创建的过程中,并没有可见的进行参数初始化的过程,因为这里使用了默认的方式进行了初始化参数。

    树枝990
  • 如何查看微信好友已撤回的消息?

    最近逛GitHub时发现了一个半开源的微信PC版的API接口WechatPCAPI,研究了一下,发现还是很好用的,所以就顺便用这个库写了个查看微信已撤回消息的程...

    树枝990
  • 【动手学深度学习】笔记一

    torch.Tensor是存储与变换数据的主要工具。Tensor(张量)是一个多维数组,标量可以看作是0维张量,向量可以看作是1维张量,矩阵可以看作是2维张量。

    树枝990
  • 一场让我持续懵比的面试

    用户2032165
  • 直播报名 | 携程三端通用框架中的CRN-WEB框架,6月28日晚8点

    携程技术
  • 为什么不建议在外包公司长期工作及外包公司的简历怎么写

    image.png 在互联网行业里,外包公司不太受待见。在跳槽去其它公司的时候,如果你上一家公司是外包公司,感觉好像差了点什么似的,整个网络上的舆论环境也对外包...

    web前端教室
  • Javascript快速入门(下篇)

    Javascript, cheer up。 ? ? Ajax:其通过在Web页面与服务器之间建立一个额外的处理层,这个处理层就被称为Ajax引擎,它解释来自用...

    用户1216676
  • 小程序iOS客户端框架——控件事件逻辑框架与控件原生化(上)

    ? 小程序自发布以来,为开发者和用户提供了一种轻量级的App。作为一种不需要下载安装即可使用的应用,它实现了应用“触手可及”的梦想,用户扫一扫或者搜一下即可打...

    腾讯NEXT学位
  • DVWA笔记(三)----Command Injection

    国庆假期一转眼就第四天了,感觉时间过得超快,不知道小伙伴们玩得怎么样呀?哈哈哈,有机会还是要好好玩耍的,天天审代码感觉真的会秃头的。。

    用户5878089
  • DVWA-对Command Injection(命令注入)的简单演示与分析

    上一篇文章中,对命令注入进行了简单的分析,有兴趣的可以去看一看,文章地址 https://www.cnblogs.com/lxfweb/p/12828754.h...

    雪痕@

扫码关注云+社区

领取腾讯云代金券