蚁群算法（ACO）MATLAB实现

baqiao

（一）蚁群算法的由来
蚁群算法(ant colony optimization)最早是由Marco Dorigo等人在1991年提出，他们在研究新型算法的过程中，发现蚁群在寻找食物时，通过分泌一种称为信息素的生物激素交流觅食信息从而能快速的找到目标，据此提出了基于信息正反馈原理的蚁群算法。
7 B+ u/ P9 C' o# a
蚁群算法的基本思想来源于自然界蚂蚁觅食的最短路径原理，根据昆虫科学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它们可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并在周围环境发生变化后，自适应地搜索新的最佳路径。

蚂蚁在寻找食物源的时候，能在其走过的路径上释放一种叫信息素的激素，使一定范围内的其他蚂蚁能够察觉到。当一些路径上通过的蚂蚁越来越多时，信息素也就越来越多，蚂蚁们选择这条路径的概率也就越高，结果导致这条路径上的信息素又增多，蚂蚁走这条路的概率又增加，生生不息。这种选择过程被称为蚂蚁的自催化行为。对于单个蚂蚁来说，它并没有要寻找最短路径，只是根据概率选择；对于整个蚁群系统来说，它们却达到了寻找到最优路径的客观上的效果。这就是群体智能。

（二）蚁群算法能做什么
, l; [. r; U  I5 N蚁群算法根据模拟蚂蚁寻找食物的最短路径行为来设计的仿生算法，因此一般而言，蚁群算法用来解决最短路径问题，并真的在旅行商问题（TSP，一个寻找最短路径的问题）上取得了比较好的成效。目前，也已渐渐应用到其他领域中去，在图着色问题、车辆调度问题、集成电路设计、通讯网络、数据聚类分析等方面都有所应用。

0 X7 r- _1 m0 Y" k/ t- y: _1 t（三）蚁群算法实现
优化的 函数为F（x,y）= -(x.^2+3*y.^4-0.2*cos(3*pi*x)-0.4*cos(4*pi*y)+0.6)
. ^, Z% f. O3 j
( @* O  L# ?) F: i0 k6 Z- y) ZMATLAB

clear
clc
Ant = 300;%蚂蚁数量
Times = 80;%移动次数
Rou = 0.9;%荷尔蒙发挥系数
+ O7 R; q: a9 ?, u- n6 j3 B; dP0 = 0.2;%转移概率
Lower_1 = -1;%搜索范围
) c5 G$ L! L( u; C; Y5 JUpper_1 = 1;
Lower_2 = -1;
Upper_2 = 1;

1 n; w6 _; ?. m% }, v  m, `for i=1:Ant
7 k- o4 U! L9 z    X(i,1)=(Lower_1+(Upper_1-Lower_1)*rand);
    X(i,2)=(Lower_1+(Upper_2-Lower_2)*rand);
    Tau(i)=F(X(i,1),X(i,2));
. D  j2 ^' D: b1 send

step=0.05;
0 {8 c4 N# ?! E: Kf='-(x.^2+3*y.^4-0.2*cos(3*pi*x)-0.4*cos(4*pi*y)+0.6)';

* K8 n# a, S% W4 I8 G7 |" ~1 ?[x,y]=meshgrid(Lower_1:step:Upper_1,Lower_2:step:Upper_2);
z=eval(f);
figure(1);
3 v+ v: R$ H* B" i* V7 Gsubplot(1,2,1);
) {1 l: N* E) u6 C( V+ b& ]4 K0 amesh(x,y,z);
; c8 y9 v- W& e- ?1 j9 ohold on;
# h! X6 I1 @6 {& x* m& F+ N% v9 y- pplot3(X(:,1),X(:,2),Tau,'k*')
! F/ P! j" V; |  T) ^, u) T1 w' bhold on;
text(0.1,0.8,-0.1,'蚂蚁的初始位置分布');
xlabel('x');ylabel('y');zlabel('f(x,y)');

for T=1:Times
    lamda=1/T;
    [Tau_Best(T),BestIndex]=max(Tau);
    for i=1:Ant
        P(T,i)=(Tau(BestIndex)-Tau(i))/Tau(BestIndex);%计算转移状态概率
    end
' s9 |- K% R0 B    for i=1:Ant
/ V- W& x# {3 _* X        if P(T,i)< P0%局部搜索
            temp1=X(i,1)+(2*rand-1)*lamda;
            temp2=X(i,2)+(2*rand-1)*lamda;
        else%全局搜索
) h/ a1 D$ l2 j4 W( m. B            temp1=X(i,1)+(Upper_1-Lower_1)*(rand-0.5);
            temp2=X(i,2)+(Upper_2-Lower_2)*(rand-0.5);
$ s7 n4 _  f7 j6 v  t* ]; Y        end
        if temp1<Lower_1%越界处理
            temp1=Lower_1;
        end
' k$ z+ n$ ?8 `. i+ I9 r. j6 q$ Y        if temp1>Upper_1
" g$ ^$ F2 e. n# }& |            temp1=Upper_1;
3 I  X% k$ ?9 M- {2 ~        end
        if temp2<Lower_2
            temp2=Lower_2;
        end
        if temp2>Upper_2
0 e. k0 I0 T/ H# K9 e$ {6 W0 A% m            temp2=Upper_2;
        end
/ Z2 Q( T  Y9 K3 Z' ^" z2 ^3 b        
* ^; g- O2 v5 M/ n& H        if F(temp1,temp2)>F(X(i,1),X(i,2))%更新位置
            X(i,1)=temp1;
: D9 n  P* T1 a2 ^* e            X(i,2)=temp2;
6 R; V* F! Q" o0 r        end
    end
    for i=1:Ant
        Tau(i)=(1-Rou)*Tau(i)+F(X(i,1),X(i,2));%更新荷尔蒙
! f5 w1 q/ a2 }1 ^    end
end

subplot(1,2,2);
mesh(x,y,z);
hold on;
x=X(:,1);
y=X(:,2);
plot3(x,y,eval(f),'k*');
% ?' Q  M0 ~  R! vhold on;
- M, D. r1 o* A6 M6 `text(0.1,0.8,-0.1,'蚂蚁的最终位置分布');
xlabel('x');ylabel('y');zlabel('f(x,y)');   
! G3 M9 e7 r" K$ L7 B1 J
[max_value,max_index]=max(Tau);
) Q- w# U$ M0 ?  FmaxX=X(max_index,1);
* s; x  `+ f& _) h% R: cmaxY=X(max_index,2);
5 q# l% b/ E3 Z4 {9 G: D* R7 NmaxValue=F(X(max_index,1),X(max_index,2));


4 V7 t, c) R/ Q% m# u1 T8 n优化函数：
$ A% V/ T7 F: {) \
5 [2 D) |: [) ]2 F: _+ u9 @) z  OMATLAB
9 t/ {  v' ~7 t  }4 n
function f = F(x,y)
f = -(x.^2+3*y.^4-0.2*cos(3*pi*x)-0.4*cos(4*pi*y)+0.6);
- \9 A4 E  `3 a  ]; N' ^: {7 R0 _end
* D- @/ ]- f; w% p7 ~, B

效果：


. _3 f: z( t0 ~7 f9 \

SsaaM7

蚁群算法（ACO）MATLAB实现