从Matlab实例学习蚁群算法(2)

前言

在从Matlab实例学习蚁群算法 中我们介绍了用蚁群算法求解TSP问题的实例。 进一步的，本文介绍一个通过蚁群算法求解连续问题的实例。

问题

求解 $f(x,y)=20(x^2-y^2{)}^2-(1-y{)}^2-3(1+y{)}^2+0.3$ 的最小值。其中$x\in [-5,5],y\in [-5,5]$。 这是一个简单的数学问题，用以阐释蚁群算法的求解过程。

求解流程

1. 随机生成$m$个蚂蚁， 对应于可行域中的$m$个可行解 $(x_m,y_m)$，并求出对应的$f(x_m,y_m)$值，得到其中最优的一个解， 记为$f_{min}$。
2. 遍历所有蚂蚁， 计算$p_m=(f(x_m,y_m)-f_{min})/f_{min}$。 预设常数值$p_0$, 也称为转移概率常数。 判断：

• $p_m<p_0$, 进行局部搜索： $x_m=x_m+\lambda s_x$, $y_m=y_m+\lambda s_y$。 $\lambda$是一个常系数，随着搜索代数的提升而减少， 即$\lambda =1/N_c$。 $s_x$和$s_y$则是可正可负的随机步长值，来进行一个局部的随机搜索。
• $p_m\ge p_0$, 进行全局搜索： 重新生成一个可行解$(x_m,y_m)$。
  可以看到，在这一步中， 主要通过$p_0$来控制探索的解， 若蚂蚁当前所在的解的质量较好，则进行局部搜索寻求更好。 若解的质量较差，则进行全局的重新探索。在重新生成解的过程中， 如果有数值越界导致的解非可行的情况， 则强制归回可行范围内。

3. 判断蚂蚁是否移动： 若新的解对应函数值小于原先解，则进行移动。 否则不动。
4. 更新信息素： $f_m=(1-\rho )f_m+f(x_m,y_m)$， 后续根据$f_m$值来评估最优的解。
5. 判断是否到达迭代代数。 若未到达， 跳转到步骤2。

思考

通过这个实例，我们看到对于求解相较于TSP更为一般的优化问题时，蚁群算法主要就变成了， 多组可行解的智能并行搜索。 此时，根据当前蚂蚁所对应的解的优劣， 好的解则令蚂蚁在解的邻域中进行搜索，而差的解则让蚂蚁跳出这一解进行一个全局的搜索。

总之，感觉智能启发算法的核心思路正如强化学习中的exploration-exploitation 策略相似：以一定的概率保持着对未知的探索，其余遵循经验中最优的方向。

代码

%%%%%%%%%%%%%%%%%%%%蚁群算法求函数极值%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;               %清除所有变量
close all;               %清图
clc;                     %清屏
m=20;                    %蚂蚁个数
G_max=200;               %最大迭代次数
Rho=0.9;                 %信息素蒸发系数
P0=0.2;                  %转移概率常数
XMAX= 5;                 %搜索变量x最大值
XMIN= -5;                %搜索变量x最小值
YMAX= 5;                 %搜索变量y最大值
YMIN= -5;                %搜索变量y最小值
%%%%%%%%%%%%%%%%%随机设置蚂蚁初始位置%%%%%%%%%%%%%%%%%%%%%%
for i=1:m
    X(i,1)=(XMIN+(XMAX-XMIN)*rand);
    X(i,2)=(YMIN+(YMAX-YMIN)*rand);
    Tau(i)=func(X(i,1),X(i,2));
end
step=0.1;                %局部搜索步长
for NC=1:G_max
    lamda=1/NC;
    [Tau_best,BestIndex]=min(Tau);
    %%%%%%%%%%%%%%%%%%计算状态转移概率%%%%%%%%%%%%%%%%%%%%
    for i=1:m
        P(NC,i)=(Tau(BestIndex)-Tau(i))/Tau(BestIndex);
    end
    %%%%%%%%%%%%%%%%%%%%%%位置更新%%%%%%%%%%%%%%%%%%%%%%%%
    for i=1:m
           %%%%%%%%%%%%%%%%%局部搜索%%%%%%%%%%%%%%%%%%%%%%
        if P(NC,i)XMAX
            temp1=XMAX;
        end
        if temp2YMAX
            temp2=YMAX;
        end
        %%%%%%%%%%%%%%%%%%蚂蚁判断是否移动%%%%%%%%%%%%%%%%%%
        if func(temp1,temp2)