蚁群算法，也是优化算法当中的一种。蚁群算法擅长解决组合优化问题。蚁群算法能够有效的解决著名的旅行商问题（TSP），不止如此，在其他的一些领域也取得了一定的成效，例如工序排序问题，图着色问题，网络路由问题等等。接下来便为大家简单介绍蚁群算法的基本思想。

蚁群算法，顾名思义就是根据蚁群觅食行为而得来的一种算法。单只蚂蚁的觅食行为貌似是杂乱无章的，但是据昆虫学家观察，蚁群在觅食时总能够找到离食物最近的路线，这其中的原因是什么呢？其实，蚂蚁的视力并不是很好，但是他们又是凭借什么区寻找到距离食物的最短路径的呢？经过研究发现，每一只蚂蚁在觅食的过程中，会在沿途释放出一种叫做信息素的物质。其他蚂蚁会察觉到这种物质，因此，这种物质会影响到其他蚂蚁的觅食行为。当一些路径上经过的蚂蚁越多时，这条路径上的信息素浓度也就越高，其他蚂蚁选择这条路径的可能性也就越大，从而更增加了这条路径上的信息素浓度。当然，一条路径上的信息素浓度也会随着时间的流逝而降低。这种选择过程被称之为蚂蚁的自催化行为，是一种正反馈机制，也可以将整个蚁群认定为一个增强型学习系统。

为了让大家更好的理解上文中提到的蚁群觅食行为，这里通过一张图片来说明蚁群觅食行为。

如图所示，A点为一个蚁穴，设定其中有两只蚂蚁，蚂蚁1和蚂蚁2。B点为食物所在位置，C点只是路径上的一点。假设ABC形成一个等边三角形，且两只蚂蚁的移动速度均相同。

在t0时刻，两只蚂蚁在蚁穴中，在他们面前有两条路可以选择，即AB或AC。两只蚂蚁随机进行选择，我们假设蚂蚁1选择了路径AC，而蚂蚁2选择了路径AB。

在t1时刻是，蚂蚁1走到了C点，而蚂蚁2走到了B点，即食物所在位置。他们在其经过的路径上释放了信息素，在途中用虚线表示。之后蚂蚁2将食物运往蚁穴，并依然在沿途释放信息素，蚂蚁1则从C点向B点进发。

等到t2时刻时，蚂蚁2到达了蚁穴A点，蚂蚁1到达了食物所在位置B点，此时蚂蚁2再次出发去搬运食物，它发现AB路径上的信息素浓度要高于AC路径上的信息素浓度（AB路径上有两条虚线，AC路径上只有1条虚线）。因此蚂蚁2选择AB路径去搬运食物，而蚂蚁1则在B点获取到了食物，接下来返回蚁穴，但是它也有两种选择，一种是原路返回，另一种便是走线路AB。蚂蚁1发现AB路径上的信息素浓度要高于AC路径上的信息素浓度，因此它将选择AB来返回蚁穴。

如此往复，AC路径的信息素浓度会越来越低，AB路径上的信息素浓度会越来越高，所以AC路径上将没有蚂蚁再次经过，两只蚂蚁都只会选择路径较短的AB线路去搬运食物。

%% 清空环境
clc;clear

%% 障碍物数据
position = load('barrier.txt');
plot([0,200],[0,200],'.');
hold on
B = load('barrier.txt');
xlabel('km','fontsize',12)
ylabel('km','fontsize',12)
title('二维规划空间','fontsize',12)
%% 描述起点和终点
S = [20,180];
T = [160,90];
plot([S(1),T(1)],[S(2),T(2)],'.');

% 图形标注
text(S(1)+2,S(2),'S');
text(T(1)+2,T(2),'T');
 
%% 描绘障碍物图形
fill(position(1:4,1),position(1:4,2),[0,0,0]);
fill(position(5:8,1),position(5:8,2),[0,0,0]);
fill(position(9:12,1),position(9:12,2),[0,0,0]);
fill(position(13:15,1),position(13:15,2),[0,0,0]);

% 下载链路端点数据
L = load('lines.txt');
 
%% 描绘线及中点
v = zeros(size(L));
for i=1:20
    plot([position(L(i,1),1),position(L(i,2),1)],[position(L(i,1),2)...
        ,position(L(i,2),2)],'color','black','LineStyle','--');
    v(i,:) = (position(L(i,1),:)+position(L(i,2),:))/2;
    plot(v(i,1),v(i,2),'*');
    text(v(i,1)+2,v(i,2),strcat('v',num2str(i)));
end
 
%% 描绘可行路径
sign = load('matrix.txt');
[n,m]=size(sign);
 
for i=1:n
    
    if i == 1
        for k=1:m-1
            if sign(i,k) == 1
                plot([S(1),v(k-1,1)],[S(2),v(k-1,2)],'color',...
                    'black','Linewidth',2,'LineStyle','-');
            end
        end
        continue;
    end
    
    for j=2:i
        if i == m
            if sign(i,j) == 1
                plot([T(1),v(j-1,1)],[T(2),v(j-1,2)],'color',...
                    'black','Linewidth',2,'LineStyle','-');
            end
        else
            if sign(i,j) == 1
                plot([v(i-1,1),v(j-1,1)],[v(i-1,2),v(j-1,2)],...
                    'color','black','Linewidth',2,'LineStyle','-');
            end
        end
    end
end
path = DijkstraPlan(position,sign);
j = path(22);
plot([T(1),v(j-1,1)],[T(2),v(j-1,2)],'color','yellow','LineWidth',3,'LineStyle','-.');
i = path(22);
j = path(i);
count = 0;
while true
    plot([v(i-1,1),v(j-1,1)],[v(i-1,2),v(j-1,2)],'color','yellow','LineWidth',3,'LineStyle','-.');
    count = count + 1;
    i = j;
    j = path(i);
    if i == 1 || j==1
        break;
    end
end
plot([S(1),v(i-1,1)],[S(2),v(i-1,2)],'color','yellow','LineWidth',3,'LineStyle','-.');


count = count+3;
pathtemp(count) = 22;
j = 22;
for i=2:count
    pathtemp(count-i+1) = path(j);
    j = path(j);
end
path = pathtemp;
path = [1     9     8     7    13    14    12    22];

%% 蚁群算法参数初始化
pathCount = length(path)-2;          %经过线段数量
pheCacuPara=2;                       %信息素计算参数
pheThres = 0.8;                      %信息素选择阈值
pheUpPara=[0.1 0.0003];              %信息素更新参数
qfz= zeros(pathCount,10);            %启发值

phePara = ones(pathCount,10)*pheUpPara(2);         %信息素
qfzPara1 = ones(10,1)*0.5;           %启发信息参数
qfzPara2 = 1.1;                      %启发信息参数
m=10;                                %种群数量
NC=500;                              %循环次数
pathk = zeros(pathCount,m);          %搜索结果记录
shortestpath = zeros(1,NC);          %进化过程记录
 
%% 初始最短路径
dijpathlen = 0;
vv = zeros(22,2);
vv(1,:) = S;
vv(22,:) = T;
vv(2:21,:) = v;
for i=1:pathCount-1
dijpathlen = dijpathlen + sqrt((vv(path(i),1)-vv(path(i+1),1))^2+(vv(path(i),2)-vv(path(i+1),2))^2);
end
LL = dijpathlen;
 


figure;
plot(1:NC,shortestpath,'color','blue');
hold on
% plot(1:NC,dijpathlen,'color','red');
ylabel('路径总长度');
xlabel('迭代次数');