启发式算法模拟退火

模拟退火的计算过程分为：

1. 对于模型求解最小值或者最大值，首先得建立一个函数关系式，然后在定义域范围内随机生成一个初始解x0
2. 在初始解附近生成另外一个解x_new，并保证新解也要在定义域内部
3. 确定什么情况下新解可以替代旧解
4. 重复上述过程N次，得到最优解

其中第三点是算法的关键，一般情况下都会用大值取代小值，即“爬山法”。这种情况带来的坏处就是视野狭窄，可能爬到一个小山坡上，无法达到最高峰。而模拟退化、遗传算法和蚁群算法就相当于给定一些不确定因素，来保证避免找到极值点的情况

模拟退火借助的是退火过程中势能下降原理抽象出来的 𝑚𝑒𝑡𝑟𝑜𝑝𝑜𝑙𝑖𝑠 原理，详见百度百科，来得到一下函数

𝑓𝑛𝑒𝑤>𝑓0 𝑝=1

𝑓𝑛𝑒𝑤<𝑓0 𝑝=𝑒−|(𝑓𝑛𝑒𝑤−𝑓0)|/𝑇

从上面式子可以看出来，温度是会影响概率的，不同温度下，相同的函数差值接受概率 𝑝 不一样，所以在同一温度下需要迭代 𝑛 ，而不同温度之间需要设置一个下降系数 𝛼 ，不同温度应有 𝑁 ，初始温度 𝑇0 不妨设置100.

下面利用算法求解 𝑦=11∗𝑠𝑖𝑛(𝑥)+7∗𝑐𝑜𝑠(5∗𝑥)−𝑒𝑥𝑝(𝑥)+2𝑥2 在【-3，3】上的最大值

%准备1，画出函数图像
x=-3:0.01:3;
y = 11*sin(x) + 7*cos(5*x)-exp(x)+2*x.^2;
figure(1)
plot(x,y,'b');
hold on

%准备2，设置一些基本参数
%定义域
k=1;      %变量个数
x_min=-3;
x_max=3;
N=400;    %外循环次数
n=100;    %内循环次数
T=1000;    %初始温度
a=0.95;   %温度下降


function y = f(x)
  y = 11*sin(x) + 7*cos(5*x)-exp(x)+2*x.^2;
end

·第一步，生成随机解

%正式算法过程
%第一步，随机生成可行解
x0=x_min+(x_max-x_min)*rand(1,k);
y0=f(x0);
h=scatter(x0,y0,'*r');
x_m=x0;
y_m=y0;

• 第二部，生成新的解

for i=1:N
    for j=1:n
        y = randn(1,k);
        z = y / sqrt(sum(y.^2));
        y0=f(x0);
        new = x0+z*sqrt(T);
         for d= 1: k
            if new(d)<x_min(d)
                r = rand(1);
                new(d) = r*x_min(d)+(1-r)*x0(d);
            elseif new(d) > x_max(d)
                r = rand(1);
                new(d) = (1-r)*x_max(d)+r*x0(d);
            end
           x1=new;
           y1=f(x1);

对于不同的问题生成随机解的方法不同，对于函数求极值主要是👆代码所示的方法，而对于 𝑇𝑆𝑃 问题来说，主要需要考虑如何改变地点的位置，主要有移位法、交换法等。遵循的准则是确保新解是随机的，并且在定义域内部。

• 第三步，确定交换

 %第三步，判断是否可以更换
           if y1>=y0
               x0=x1;
               x_m=[x_m;x0];
               y_m=[y_m;y0];
           else 
               p= exp(-abs(y0 - y1)/T);
               if rand(1)<p
                   x0=x1;
               end
           end
         end
        %注意上面是温度相同时候的循环，这时候可以画出来一次的结果和改变温度
    end
         h.XData=x0;  
         h.YData=f(x0);
         T=a*T;  
        pause(0.01)  % 暂停一段时间(单位：秒)后再接着画图 
end

• 第四步，显示结果

[max_y,index]=max(y_m);
max_x=x_m(index);
pause(1);
title('最终结果');
scatter(max_x,max_y,'^r')

最后运行的结果是：

添加图片注释，不超过 140 字（可选）