模拟退火算法SAA

模拟退火算法来源于固体退火原理,是一种基于概率的算法,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。

来源

模拟退火算法(Simulated Annealing,SA)最早的思想是由N. Metropolis等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。

源码

%模拟退火算法之旅行商算法
%ij.txt存放的是各点经纬度
clc;clear
load ij.txt;%加载目标数据ij.txt存放25x8矩阵
x=ij(:,1:2:8);%x为25x4矩阵
x=x(:);%x化为10x1矩阵
y=ij(:,2:2:8);%y为25x4矩阵
y=y(:);%y化为100x1矩阵
sj=[x y];%100x2矩阵
d1=[70,40];%起始点
sj=[d1;sj;d1];%首尾添加上出发点和终点
sj=sj*pi/180;%角度化为弧度
%计算距离
d=zeros(102);%先建一个102x102的空的距离矩阵,再把对应距离填进去
%A(R cos x1 cos y1 , R sin x1 cos y1 , R sin y1 )
%B(R cos x2 cos y2 , R sin x2 cos y2 , R sin y2 )
%其中 R = 6370 为地球半径。
%A, B 两点的实际距离:
%d = R arccos[cos(x1 − x2 ) cos y1 cos y2 + sin y1 sin y2 ]
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(j,2)));
    end
end
%上述的d为上三角矩阵,根据对称性,化为对称矩阵,d矩阵包含各点间的距离信息
d=d+d';
S0=[];
Sum=inf;
rand('state',sum(clock));%作用是定义一个随时间变化的初值
%matlab里面的随机生成函数基本都是以rand为基函数通过函数关系式得到,
%比如 normrnd,unidrnd等,你每次重启matlab后运行已编好的含随机数生成的函数你将得到相同的结果,
%比如我的电脑上重启matlab运行unidrnd(100),每次的值都是82,这是因为rand函数的初值都一样,
%所以为了避免上述问题经常在程序前运行或加命令rand('state',sum(clock)),这样重启matlab,运行随机数生成值就不同了。
for i=1:1000%循环1000次,尽可能让所有排序情况都出现一遍
    s=[1,1+randperm(100),102];%s为中间2到101的排列组合
    temp=0;
    for j=1:101
        temp=temp+d(s(j),s(j+1));
    end
    if temp<Sum
       Sum=temp;
       S0=s;%保存当前最小值的排序情况
    end
end
e=0.1^30;%选定的终止温度 e = 10 −30 ,判断退火过程是否结束
at=0.999;%选定的降温系数α进行降温即:T =αT
L=20000;
T=1;
%退火过程
for k=1:L
c=2+floor(100*rand(1,2));%floor函数其功能是“向下取整”,或者说“向下舍入”,即取不大于x的最大整数
%ceil函数向上取整
c=sort(c);% [a,b]=sort(X)是按列从小到大排序,而 [a,b]=sort(X,2)是按行,b为排序情况
c1=c(1);c2=c(2);
%计算代价函数值
df=d(S0(c1-1),S0(c2))+d(S0(c1),S0(c2+1))-d(S0(c1-1),S0(c1))-d(S0(c2),S0(c2+1));
if df<0%接受准则
    S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)];
    Sum=Sum+df;
elseif exp(-df/T)>rand(1)%以概率exp(−df/T)接受新的路径%注意时elseif而不是else if
    S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)];
    Sum=Sum+df;
end;
T=T*at;%退火
if T<e%达到终止温度
    break;
end;
end;
%输出路径和路径长度
S0,Sum
%画出其中一个巡航路径
plot(sj(S0,1)/pi*180,sj(S0,2)/pi*180);
hold on
plot(sj(S0,1)/pi*180,sj(S0,2)/pi*180,'rx');
axis([-5,75,-5,45]);

人已赞赏
编程技术

遗传算法GA

2020-9-17 8:00:00

WordPress教程

WordPress更改文章密码保护显示的提示内容

2020-8-3 18:33:50

⚠️
恩月阁文章由星九进行编写或整理,部分内容来源于互联网,仅供网友学习交流,若您喜欢本文可附上原文链接随意转载。
若无意中侵害到您的权益,请发送邮件至 xingjiu@nuue.cn 或点击右侧 私信:星九 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索