蚁群算法

背景介绍

ACO(ant colony optimization):研究蚂蚁觅食的过程中，发现单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。蚂蚁会在其经过的路径上释放一种可以称之为信息素的物质，蚁群内的蚂蚁对信息素具有感知能力，它们会沿着信息素浓度较高路径行走，而每只路过的蚂蚁都会在路上留下信息素，形成一种类似正反馈的机制。

核心思想

1. 随机产生一些蚂蚁

2. 判断蚂蚁所在位置的值越小，信息素越多

3. 如果信息素较多，蚂蚁小幅移动，信息素较少，蚂蚁大幅移动

4. 如果蚂蚁移动之后值变小，则说明移动方向正确

5. 回到步骤2，直到满足某个终止条件

6. 此时蚂蚁集群，蚁群位置为极小值，比较可得该算法的最优解

算法流程

ACO

代码实战

代码中所用测试函数可以查看相关文档，测试函数(Test Function)

ACO_main.m

clear;clc;close all;
%自变量取值范围
range_x=[ones(1,1),-ones(1,1)]*500;
%维度
n=size(range_x,1);
%蚂蚁数
m=1000;
%迭代次数
times=100;
%信息素挥发系数
rho=0.8;
%转移概率常数
p0=1;
%转移概率
p=zeros(1,m);
%x为蚁群的初始位置
x=zeros(n,m);
for k=1:n
    x(k,:)=(rand(1,m))*(range_x(k,2)-range_x(k,1))+range_x(k,1);
end
%tau为信息素
tau=-f(x);
%设置当前最优解
best_value=zeros(1,times);
tic;
for i=1:times
    [~,bestindex]=max(tau);
    for j=1:m
        %信息素越大越不容易转移
        p(j)=(tau(bestindex)-tau(j))/tau(bestindex);
        if p(j)<p0
            %如果信息素较多，转移步伐就较小
            temp=x(:,j)+(rand(n,1)*2-1)/i;
        else
            temp=zeros(n,1);
            %如果信息素较少，转移步伐就较大
            for k=1:n
                temp(k)=x(k,j)+(rand(1,1)-0.5)*(range(k,2)-range(k,1));
            end
        end
        %限制边界条件
        for k=1:n
            if temp(k)<range_x(k,1)
                temp(k)=range_x(k,1);
            end
            if temp(k)>range_x(k,2)
                temp(k)=range_x(k,2);
            end
        end
        %如果移动后值变小，则移动
        if f(temp)<f(x(:,j))
            x(:,j)=temp;
        end
        %更新信息素，函数值越小，信息量越大
        tau(j)=(1-rho)*tau(j)-f(x(:,j));
    end
    best_value(i)=min(f(x));
    if i>5&&abs(best_value(i)-best_value(i-5))<1e-5
        break;
    end
end
time=toc;
disp(['用时：',num2str(time),'秒'])
[mini,index]=min(f(x));
disp(['fmin=',num2str(mini)]);
for k=1:n
    disp(['x',num2str(k),'=',num2str(x(k,index))]);
end
if n==1
    hold on;
    plot(x(index),mini,'ro');
    plot_x=range_x(1):(range_x(2)-range_x(1))/1000:range_x(2);
    plot_y=f(plot_x);
    plot(plot_x,plot_y);
    text((range_x(1)+range_x(2))/2,max(plot_y)+0.1*(max(plot_y)-min(plot_y)),['用时：',num2str(time),'秒']);
    hold off;
end
if n==2
    func=@(x1,x2)x1.*sin(sqrt(abs(x1)))+x2.*sin(sqrt(abs(x2)));
    plot_x=range_x(1,1):(range_x(1,2)-range_x(1,1))/1000:range_x(1,2);
    plot_y=range_x(2,1):(range_x(2,2)-range_x(2,1))/1000:range_x(2,2);
    [plot_x,plot_y] =meshgrid(plot_x,plot_y);
    plot_z=func(plot_x,plot_y);
    surf(plot_x,plot_y,plot_z);
    xlabel('x1');
    ylabel('x2');
    zlabel('y');
    hold on;
    plot3(x(1,index),x(2,index),mini,'ko')
    text((range_x(1,1)+range_x(1,2))/2,(range_x(2,1)+range_x(2,2))/2,max(max(plot_z))+0.5*(max(max(plot_z))-min(min(plot_z))),['用时：',num2str(time),'秒']);
    hold off;
end

f.m

function res=f(x)
func=@(x)(x).*sin(sqrt(abs(x)));
res=zeros(1,size(x,2));
for i=1:size(x,1)
    res=res+func(x(i,:));
end

实验结果

ACO
$$f(x)=x \cdot \sin(\sqrt{\lvert x \rvert}) \ , \ x \in [-500,500]$$

$$理论值：f(x)_{min}=f(-420.96874592006)=-418.982887272434$$

$$所求值：f(x)_{min}=f(-420.959294517745)=-418.982875999576$$

性能比较

优点：
- 搜索速度较快
- 受到参数影响较小
- 从群体出发，具有并行性
- 可用于求解复杂的非线性优化问题
- 具有可扩展性，容易与其他算法结合

缺点：

对初始蚂蚁的数量有很高的要求