模拟退火——算法思想与实例

系列链接

        遗传算法讲解及实例

        差分进化算法讲解及实例

        模拟退火算法讲解及实例

定义

        模拟退火算法以优化问题求解过程与物理退火过程之间的相似性为基础，优化的目标函数相金属的内能，优化问题的自变量合状态空间相金属的内能状态空间，问题的求解过程就是找一个组合状态，使目标函数值最小。利用Metopolis算法并适当地控制温度的下降过程实现模拟退火，从而达到求解全局优化问题的目的

术语

                                  

算法思想

                                          

初始化

        首先是要选定一些参数，这些参数可以再代码注释中看到，数据的初始化常使用随机初始化

产生新解

        给当前某个解加上一部分产生一个新解，通常加上的为步长乘以一个区间内的随机数，需要判断新解是否仍在可行区间内，如果超出了区间，需要重新再计算一个新解，直到满足要求为止

新解保留

        系统从当前状态1到另一种状态2，能力从E1变化到E2，判断如果E2 < E1，则接受新解，反之可以一定概率接受新解：

                                      

        这里也可以反映出，模拟退火算法可以突出局部最优，趋向于全局最优

终止条件

        一般是温度低到阈值，也可以设置其他条件，比如误差低于1e-8则结束

例题

        求函数f(x,y) = 5cos(xy) + xy + y^3 的最小值， x ∈ [ -5, 5 ] y ∈ [-5，5 ]

        函数图像如下，具有多个局部最优点

                     

下边是模拟退火算法的计算结果：最小值 -152.0904

                    

代码

脚本1 —— 画图

%%%%%%%%%f(x，y)=5*cos(x*y)+x*y+y^3%%%%%%%%%
clear all;              %清除所有变量
close all;              %清图
clc;                    %清屏
x=-5:0.02:5;
y=-5:0.02:5;
N=size(x,2);
for i=1:N
    for j=1:N
         z(i,j)=5*cos(x(i)*y(j))+x(i)*y(j)+y(j)^3;
    end
end
mesh(x,y,z)
xlabel('x')
ylabel('y')

脚本2 —— 适应度评价函数

%%%%%%%%%%%%%%%%%%%%%%%%%%%适应度函数%%%%%%%%%%%%%%%%%%%%%%%%%
function value=func2(x,y)
value=5*cos(x*y)+x*y+y*y*y;
 

标本3 —— 模拟退火算法

%%%%%%%%%%%%%%%%%%%%%%模拟退火算法解决函数极值%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;                      %清除所有变量
close all;                      %清图
clc;                            %清屏
XMAX= 5;                        %搜索变量x最大值
XMIN= -5;                       %搜索变量x最小值
YMAX= 5;                        %搜索变量y最大值
YMIN= -5;                       %搜索变量y最小值
%%%%%%%%%%%%%%%%%%%%%%%%%%%冷却表参数%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
L = 100;                        %马可夫链长度
K = 0.99;                       %衰减参数
S = 0.02;                       %步长因子
T=100;                          %初始温度
YZ = 1e-8;                      %容差
P = 0;                          %Metropolis过程中总接受点
%%%%%%%%%%%%%%%%%%%%%%%%%%随机选点 初值设定%%%%%%%%%%%%%%%%%%%%%%%%%
PreX =  rand * (XMAX-XMIN)+XMIN;
PreY =  rand * (YMAX-YMIN)+YMIN; 
PreBestX = PreX;
PreBestY = PreY;
PreX =  rand * (XMAX-XMIN)+XMIN;
PreY =  rand * (YMAX-YMIN)+YMIN; 
BestX = PreX;
BestY = PreY;
%%%%%%%%%%%每迭代一次退火一次(降温), 直到满足迭代条件为止%%%%%%%%%%%%
deta=abs( func2( BestX,BestY)-func2 (PreBestX, PreBestY));
while (deta > YZ) && (T>0.001)
    T=K*T; 
    %%%%%%%%%%%%%%%%%%%%%在当前温度T下迭代次数%%%%%%%%%%%%%%%%%%%%%%
    for i=1:L  
        %%%%%%%%%%%%%%%%%在此点附近随机选下一点%%%%%%%%%%%%%%%%%%%%%
        p=0;
        while p==0
            NextX = PreX + S* (rand * (XMAX-XMIN)+XMIN);
            NextY = PreY + S*( rand * (YMAX-YMIN)+YMIN);
            if (NextX >= XMIN && NextX <= XMAX && NextY >=...
                    YMIN && NextY <= YMAX)
                p=1;
            end
        end
        %%%%%%%%%%%%%%%%%%%%%%%是否全局最优解%%%%%%%%%%%%%%%%%%%%%%
        if (func2(BestX,BestY) > func2(NextX,NextY))
            %%%%%%%%%%%%%%%%%%保留上一个最优解%%%%%%%%%%%%%%%%%%%%%
            PreBestX = BestX;
            PreBestY = BestY;
            %%%%%%%%%%%%%%%%%%%此为新的最优解%%%%%%%%%%%%%%%%%%%%%
            BestX=NextX;
            BestY=NextY;
        end
        %%%%%%%%%%%%%%%%%%%%%%%% Metropolis过程%%%%%%%%%%%%%%%%%%%
        if( func2(PreX,PreY) - func2(NextX,NextY) > 0 )
            %%%%%%%%%%%%%%%%%%%%%%%接受新解%%%%%%%%%%%%%%%%%%%%%%%%
            PreX=NextX;
            PreY=NextY;
            P=P+1;
        else
            changer = -1*(func2(NextX,NextY)-func2(PreX,PreY))/ T ;
            p1=exp(changer);
            %%%%%%%%%%%%%%%%%%%%%%%%接受较差的解%%%%%%%%%%%%%%%%%%%%
            if p1 > rand        
                PreX=NextX;
                PreY=NextY;
                P=P+1;         
            end
        end
        trace(P+1)=func2(BestX, BestY);
    end
    deta=abs( func2( BestX,BestY)-func2 (PreBestX, PreBestY));
end
disp('最小值在点:');
BestX
BestY
disp( '最小值为:');
func2(BestX, BestY)
plot(trace(2:end))
xlabel('迭代次数')
ylabel('目标函数值')
title('适应度进化曲线')