蚁群算法研究报告
题 目 信息工程学院 专 业 计算机科学与技术 姓 名
程亮 学 号 ********* 指导教师 谭同德
2014-6-4
目 录
第一章 蚁群算法概述 .................................. 2 1.1蚁群算法概念 .................................. 2 1.2蚁群算法原理 .................................. 2 1.3蚁群算法的特点 ................................ 3 1.3.1 人工蚁群的特点 ........................... 3 1.3.2 蚁群的特点 ............................... 3 1.4蚁群算法的应用 ................................ 4 1.5算法模型 ...................................... 4 第二章 蚁群算法解决TSP问题 .......................... 5 2.1 TSP问题描述 .................................. 5 2.2 基于 TSP 问题的蚁群算法模型 ................... 5 2.3蚂蚁系统解决TSP问题实现步骤 ................... 6 2.4蚂蚁系统解决TSP问题流程图 ..................... 6 2.5关键代码 ...................................... 7 参考文献 ............................................ 10
1
第一章 蚁群算法概述
1.1蚁群算法概念
蚁群算法（Ant Clony Optimization， ACO）是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。从1991年意大利学者DorigoM等首次提出蚁群算法以来，蚁群算法作为一种自然计算方法，由解决tsP(旅行商)问题开始，从一维静态优化问题到动态优化问题，从解决离散域围问题到连续域围，发展到今天已经相对成熟了，应用到了众多的领域，比如说数据挖掘、物流、通信网络、大规模集成电路、网络路由等。而且这种仿生算法同遗传算法、粒子群算法、免疫算法、神经网络等智能算法相结合的新算法，更好的提高了效率并加强了其在实际问题中的应用。
蚁群算法之所以能引起相关领域研究者的注意，是因为这种求解模式能将问题求解的快速性、全局优化特征以及有限时间答案的合理性结合起来。其中，寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免，同时，具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答。这种优越的问题分布式求解模式经过相关领域研究者的关注和努力，已经在最初的算法模型基础上得到了很大的改进和拓展。研究蚁群算法的改进方法以及其发展和应用的趋势，为蚁群算法在更多领域有更多的应用价值来说是十分必要的。
1.2蚁群算法原理
蚁群算法是一种仿生学算法，是由自然界中蚂蚁觅食的行为而启发的。在自然界中，蚂蚁觅食过程中，蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。图（1）显示了这样一个觅食的过程。
在图1（a）中，有一群蚂蚁，假如A是蚁巢，E是食物源（反之亦然）。这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶。假如在A和E之间突然出现了
2
一个障碍物（图1（b）），那么，在B点（或D点）的蚂蚁将要做出决策，到底是向左行驶还是向右行驶？由于一开始路上没有前面蚂蚁留下的信息素（pheromone），蚂蚁朝着两个方向行进的概率是相等的。但是当有蚂蚁走过时，它将会在它行进的路上释放出信息素，并且这种信息素会议一定的速率散发掉。信息素是蚂蚁之间交流的工具之一。它后面的蚂蚁通过路上信息素的浓度，做出决策，往左还是往右。很明显，沿着短边的的路径上信息素将会越来越浓（图1（c）），从而吸引了越来越多的蚂蚁沿着这条路径行驶。
1.3蚁群算法的特点
1.3.1 人工蚁群的特点
. 蚁群算法中所使用的蚂蚁是现实蚂蚁行为特征的一种抽象，称为人工蚂蚁。
人工蚂蚁的通讯方式、相互协作机制与现实蚂蚁一样，但是如果完全依照现实蚂蚁行为机制来设计蚁群算法，实验表明算法需要很多的时间才会收敛，而且可能会收敛于一些局部优解。故人工蚂蚁又有不同于现实蚂蚁的地方，以tsP问题为例：
(1)人工蚂蚁有一定的记忆能力，它可以记住已经走过的路径，以保证不会重复走相同的城市。现实的蚂蚁没有记忆。
(2)人工蚂蚁不仅仅依据信息素来确定要走的路径，还引入了与问题相关的启发信息，比如相邻边的长度。这个构造的启发信息有利于下一步的搜索。 (3)人工蚂蚁处于一个离散的时间环境下，而现实中的蚂蚁是在一个连续的状态下。所以，人工蚂蚁可以根据问题的需要比较灵活的加入相应的规则，以更加有效的解决实际问题。
1.3.2蚁群的特点
蚁群中的蚂蚁具有多元性、相关性，而且相互之间的协作又体现了整体性，所以蚁群具有系统性的特点。人工蚂蚁在任务中越来越趋向于一种接近最优的结果，整体来看就是一种从无序到有序的自组织过程，这种自组织性增加了算法的鲁棒性。在解决问题的过程中，当某个解较优时，就会使更多的蚂蚁选择这个解，解越优，蚂蚁选择此解的概率越大，直到收敛到最优解，这使蚁群有了正反馈的特性。由于在选择的过程种采用了轮转赌，这样会增加一些随机的因素，增大了解的搜索围，如此便是一种负反馈的性质。由于蚁群中每只蚂蚁都是并行运作，所以蚁群还有分布式并发的特点。
3
1.4蚁群算法的应用
由前面的论述可知，蚁群算法是一种启发式算法，它来源于对蚂蚁群体搜索行为的研究。它还充分模拟了实际蚁群寻求最短路径的协作优化特性。由于蚂蚁寻求最短路径的行为类似于旅行商）问题的解决过程，因而蚁群算法能在问题实例中得到最优的结果。另外，蚁群算法还被用于作业车间调度问题、二次分配问题、背包问题、数据的特征聚类过程，并取得了很好的寻优结果。
蚁群算法在解决组合优化类问题求解方面表现出了突出的适用特征。人工蚁群中的多个智能体通过正反馈确保了最优化过程的快速性，而早熟收敛则可以由蚁群算法的分布式计算特性来加以避免。同时，由于它的贪婪式启发搜索特性，在搜索过程的早期就可以找到可以接受的解。这样，在一种问题求解模式中，同时结合了问题求解的快速性、全局最优特征以及在优化过程初期解的合理性等特性，从而引起了相关领域研究者的注意。
通过相关领域研究者的关注和努力，蚁群算法在最初模式的基础上得到了许多改进和扩展，并在大量领域获得了应用，比如机器人系统、图像处理、制造系统、车辆路径系统、通信系统、工程设计领域及电力系统等。它还被用于各类动态资源分配、行动规划和数据聚类等相关问题的研究中。
1.5算法模型
经过研究者反复改进，建立模型的基本思想是：以正反馈（Positive Feedback）为基础，通过对较好的潜在解的增强，来实现对最优解的搜索。 1）通过设立虚拟信息素（Virtual Pheromone）来实现信息正反馈，为寻找更优解打基础。
2）通过引入信息素挥发机制（Evaporation）实现负反馈，以避免正反馈出现早熟现象(Stagnation)。
但是需要注意的是信息素按照一定的时间间隔挥发，时间间隔太短会出现早熟现象，时间间隔太短个体间的协作会受到抑制，所以要合理制定时间间隔。
Dorigo经过深入研究，针对信息素的更新策略有给出了三种模型，它们分别是：蚁量系统（Ant-Quantity）、蚁密系统（Ant-Density）和蚁周系统（Ant-Cycle）
三种模型的实现大致相同,主要区别是在信息素的更新方式上。在用蚂蚁系统解决TSP问题时,蚁量模型和蚁密模型是蚂蚁在构建一条合法路径的过程中进行信息素的更新的,当蚂蚁走过一条边之后,就对该边进行信息素的更新。而蚁周模型是在所有蚂蚁都构建了一条合法路径之后才对各边进行信息素更新的 ,并且三者在蚂蚁释放信息素的量上面也不同。蚁密模型中,蚂蚁在自己所走过的边上所释放的信息素是一个常量Q,而蚁量模型中,蚂蚁在自己所走过的边上释放的信息素是Q/dtj,其中Q是一个常量,而dtj是蚂蚁走过边的长度。
4
第二章 蚁群算法解决TSP问题
2.1 TSP问题描述
TSP问题是给定一个城市的集合以及城市之间的旅行代价,寻找经过每个城市一次且仅一次而最终回到起始城市旅行代价最小的路径。如果构造一个图如下:图中的顶点为城市,顶点间的边表示城市间的交通线,边上的权为沿该交通线旅行的费用.那么,TSP问题就抽象为在这个图中寻找最短哈密尔顿回路。
Ant-Cycle模型在路径上信息素的更新机制利用的是整体信息，这种机制会让段路径上对应的信息量逐渐增大，充分体现了算法中全局围较短路径的生存能力，加强了信息正反馈性能，提高了系统搜索收敛的速度。在解决TSP问题时性能较好，故通常成Ant-Cycle模型为蚂蚁系统的基本模型。
2.2 基于 TSP 问题的蚁群算法模型
蚁群算法的模型中常用的变量主要有：b i(t)代表t时刻节点i的蚂蚁个数；τij(t)为 t 时刻路径( i , j )上的信息浓度；n表示 TSP 中节点个数；bi(t)m= 表示蚂蚁的总数； Г={τij(t)|ci,cjC}为 t 时刻路径Iij上信息量的集合。
蚂蚁下一步选取哪个城市作为转移的目标由各路径上的信息浓度决定。禁忌表tabu （kk=1,2,…m）中的元素都是蚂蚁 k 已经走过且不能再次选择的城市，蚂蚁每走过一个城市，就要把该城市加入到tabuk中，所以tabuk 是不断变化的集合。每个蚂蚁都按照如下公式的计算结果来选择下一个目标：
Allowedk=C- tabuk中的元素是蚂蚁接下来可以走的城市；信息启发因子α表示信息轨迹的重要性,α越大，该蚂蚁选择过的这条路径就越受其它蚂蚁欢迎，容易被其他蚂蚁选择；期望启发因子β代表了启发信息在路径选择时的重要性；启发函数 ηij(t)表示为:
其中，dij 为相邻两城市的距离。很显然，两城市之间的路径越短，该路径就越
k容易吸引蚂蚁，即p (t)就越大。
iji1n 5
为了避免蚂蚁在某些路径上积累的信息素浓度过高，以至于启发信息起不了 作用，在每只蚂蚁都搜索到一条哈密尔顿回路（闭合回路）后，各路径上的信息 素浓度根据下面两个公式进行修改：
i , j ) [0,1)代表信息挥发快慢； τij(t)是 t 时刻所有蚂蚁在边 (
上累积的信息，而蚂蚁k 累积的信息量为 τijk (t):t=0时，τij(0)=0。当所有元素都存放到tabu k里面时，蚂蚁 k 就找到了一条符合要求的 Hamilton 回路。
2.3蚂蚁系统解决TSP问题实现步骤
1. 初始化，首先设定相关参数：需遍历城市数n、蚂蚁数m、初始时各路径信息素τij 、m只蚂蚁遍历（循环）次数的最大值Nmax、信息素挥发系数 以及α 、β、Q等。建立禁忌列表Jk，并保证此时列表中没有任何城市。
2. 将m个蚂蚁随机放在各个城市上，每个城市至多分布一个蚂蚁，并将m修改禁忌表Jk 。
3. 所有蚂蚁根据概率转换公式和选择下一城市，并将该元素(城市)移动到该蚂蚁个体的禁忌表中。
4. 所有蚂蚁遍历完n个城市后在所经过的路径上根据信息更新公式更新所有所有信息素，并记录本次迭代过程重点最优路径和最优路径长度。 5. 清空禁忌列表Jk，重复步骤3和4，直到每一个蚂蚁都完成Nmax次遍历所有城市，最后输出的路径为最优路径。
2.4蚂蚁系统解决TSP问题流程图
6
2.5关键代码
%一始化变量 clear;
Alpha=1; %信息素重要程度的参数(对路径选择有很大影响) Beta=5; %启发式因子重要程度的参数(对路径选择有很大影响) Rho=0.95; %信息素蒸发系数
NC_max=200; %最大迭代次数(循环多结果更优适度即可) Q=100; %信息素增加强度系数 (对结果影响小) CityNum=31; %问题的规模（城市个数） [dislist,Clist]=tsp(CityNum); m=CityNum; %蚂蚁个数
Eta=1./dislist;%Eta为启发因子，这里设为距离的倒数 Tau=ones(CityNum,CityNum);%Tau为信息素矩阵
Tabu=zeros(m,CityNum);%存储并记录路径的生成 NC=1;%迭代计数器 R_best=zeros(NC_max,CityNum); %各代最佳路线 L_best=inf.*ones(NC_max,1);%各代最佳路线的长度 L_ave=zeros(NC_max,1);%各代路线的平均长度
while NC<=NC_max %停止条件之一：达到最大迭代次数 %二将m只蚂蚁放到CityNum个城市上 Randpos=[];
for i=1:(ceil(m/CityNum))
Randpos=[Randpos,randperm(CityNum)]; end
Tabu(:,1)=(Randpos(1,1:m))';
%三m只蚂蚁按概率函数选择下一座城市，完成各自的周游 for j=2:CityNum for i=1:m
visited=Tabu(i,1:(j-1)); %已访问的城市 J=zeros(1,(CityNum-j+1));%待访问的城市 P=J;%待访问城市的选择概率分布 Jc=1;
for k=1:CityNum
if isempty(find(visited==k, 1)) J(Jc)=k; Jc=Jc+1; end end
%计算待选城市的概率分布 for k=1:length(J)
7
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta); end
P=P/(sum(P));
%按概率原则选取下一个城市 Pcum=cumsum(P);
Select=find(Pcum>=rand); to_visit=J(Select(1)); Tabu(i,j)=to_visit; end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:); end
%四记录本次迭代最佳路线 L=zeros(m,1); for i=1:m
R=Tabu(i,:);
L(i)=CalDist(dislist,R); end
L_best(NC)=min(L);
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:); L_ave(NC)=mean(L);
drawTSP(Clist,R_best(NC,:), L_best(NC),NC,0); NC=NC+1 %更新信息素
Delta_Tau=zeros(CityNum,CityNum); for i=1:m
for j=1:(CityNum-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i); end
Delta_Tau(Tabu(i,CityNum),Tabu(i,1))=Delta_Tau(Tabu(i,CityNum),Tabu(i,1))+Q/L(i); end
Tau=(1-Rho).*Tau+Delta_Tau; %六禁忌表清零
8
Tabu=zeros(m,CityNum); %pause;
tauji(NC)=Tau(1,2); end
9
参考文献
[1] 朱 杰 蚁群算法解决TSP问题的浅析[J] 电脑知识与技术 Vol.3,No.4,August 2008,
pp.724- 725,746
[2] 宏 蚁群算法解决 TSP 问题的研究[J] 农业网络信息 ：1672- 625（1 2007）03- 0022-
03
[3] 鄢文晋 基于TSP问题的蚁群算法综述[J] 计算机科学 2007Vol.34 No.10
10