图1 模拟退火搜索演示图
由于前段时间较繁忙,好些时日没有更新公众号了,感谢大家一如既往地支持!!!
之前给大家介绍了爬山算法,虽它有其便利之处,但只对近邻点的感兴趣,难免在寻优过程中陷入局部最优。今天要介绍的模拟退火相当于爬山算法的升级版,它以一定的概率来接受一个比当前解要差的解,因为引入随机过程使得算法能够以“蛙跳式”寻优,就有可能在寻优过程中跳出局部最优从而最终找到全局最优。
以上图为例,模拟退火算法以A点作为初始值,在搜索到局部最优解B点后,会以一定的概率接受往C点方向的移动,可能通过反复地移动搜索就能找到最终的全局最优解D点。
模拟退火算法描述:
1、在指定区间随机产生一定数量的初始解,计算初始目标函数值;
2、结合温度系数更新初始解,计算更新后的目标函数值并计算其与初始目标函数值的差值;
3、根据需要来做判断,这里假设取最大值:若差值大于等于0,则总是接受该移动;若差值小于0,根据Metropolis接受准则来确定取值,根据Metropolis准则,粒子在温度T时趋于平衡的概率为exp(-ΔE/(kT)),其中E为温度T时的内能,ΔE为其改变数,k为玻尔兹曼常数。Metropolis准则可表示为:
由于能量差dE小于0,温度越高,降温的概率就越大;温度越低,则出现降温的概率就越小。
4、重复2,3直至降温结束或达到规定精度要求。
%% 模拟退火演示程序
clear;clc;close all;
% 求解区间
minx = -4;maxx = 2;
% 目标函数
fun = @(x) 3*exp(sin(x.^3))-9*cos(x.^2)-5.6*sin(x);
% 初始解数量
num = 12;
% 初始位置
loc = minx + (maxx-minx)*rand(1,num);
% 根据区间生成模拟温度
T = maxx-minx;
% 迭代次数
Iter = 200;
% 温度位移系数
kd = 0.5;
% 温度概率系数,相当于波尔兹曼常数
k = 0.01;
% 温度降低速率
vt = 0.97;
% 当前解
vP = fun(loc);
x = minx:0.01:maxx;
y = fun(x);
% 存储每个迭代步的最优解
Re = zeros(1,Iter);
% 外层循环用于温度迭代,内层循环用于多初始值求解
for t = 1:Iter
% 当前温度下的平均移动距离
dx_av = kd*T;
% 更新后的温度
T = T*vt;
for p = 1:num
% 以平均移动距离为中心正态分布
dx = dx_av*normrnd(0,1) + dx_av;
if rand <= 0.5 % 左移右移各占50%
dx = - dx;
end
locV = loc(p) + dx;
if (locV<maxx) && (locV>minx) %判断是否越界
local_value = fun(locV);
if local_value > vP(p)
loc(p) = locV;
vP(p)=local_value;
else
dltE = local_value-vP(p);
P = exp(dltE/(k*T));
if rand < P
loc(p) = locV;
vP(p) = local_value;
end
end
end
end
Re(t) = max(vP);
if mod(t,5) == 0
subplot(2,1,1);
plot(x,y);
ylim([min(y)-1 max(y)+1]);
hold on;
plot(loc, vP,'r.','MarkerSize',10);
title('搜寻过程动态演示');
ylabel('函数值 Y');
xlabel('自变量 X');
hold off;
subplot(2,1,2);
plot(1:t,Re(1:t));
hold on;
plot(1:t,ones(1,t)*Re(t),'r--');
ylim([min(Re(1:t))-1 max(Re(1:t))+1]);
[v,c] = max(vP);
title(['当前最优解: ',num2str([loc(c) v])]);
ylabel('当前最优解');
xlabel('迭代步数');
hold off;
pause(0.05);
end
end
运行效果:
当前最优解: -1.69001 22.2977