1、蚁群算法研究报告题目信息工程学院专业计算机科学与技术姓 名程亮学 号201115068指导教师谭同德2014-6-4目录第一章 蚁群算法概述 21.1 蚁群算法概念 21.2 蚁群算法原理 21.3 蚁群算法的特点 31.3.1 人工蚁群的特点 31.3.2 蚁群的特点 31.4 蚁群算法的应用 41.5 算法模型 4第一章 蚁群算法解决TSP问题 52.1 TSP 问题描述 52.2 基于 TSP 问题的蚁群算法模型52.3蚂蚁系统解决TSP问题实现步骤62.4蚂蚁系统解决TSP问题流程图.62.5 关键代码 7参考文献 . 106第一章蚁群算法概述1.1蚁群算法概念蚁群算法（Ant Clo 。

2、ny Optimization , ACQ是一种群智能算法 ， 它是由一 群无智能或有轻微智能的个体（Age nt）通过相互协作而表现出智能行为 ， 从而 为求解复杂问题提供了一个新的可能性 。
从 1991年意大利学者DorigoM等首次 提出蚁群算法以来 ， 蚁群算法作为一种自然计算方法 ， 由解决tsP（旅行商）问题开始 ， 从一维静态优化问题到多维动态优化问题 ， 从解决离散域围问题到连续域围 ， 发展到今天已经相对成熟了 ， 应用到了众多的领域 ， 比如说数据挖掘、物流、 通信网络、大规模集成电路、网络路由等 。
而且这种仿生算法同遗传算法、粒子 群算法、免疫算法、神经网络等智能算法相结合的新算法 ，更好的提高了效率并 加强了 。

3、其在实际问题中的应用 。
蚁群算法之所以能引起相关领域研究者的注意 ， 是因为这种求解模式能将问 题求解的快速性、全局优化特征以及有限时间答案的合理性结合起来 。
其中 ， 寻优的快速性是通过正反馈式的信息传递和积累来保证的 。
而算法的早熟性收敛又可以通过其分布式计算特征加以避免 ，同时 ， 具有贪婪启发式搜索特征的蚁群系 统又能在搜索过程的早期找到可以接受的问题解答 。
这种优越的问题分布式求解 模式经过相关领域研究者的关注和努力 ， 已经在最初的算法模型基础上得到了很 大的改进和拓展 。
研究蚁群算法的改进方法以及其发展和应用的趋势 ， 为蚁群算法在更多领域有更多的应用价值来说是十分必要的 。
1.2蚁群算法原理蚁群算法是一种仿生 。

4、学算法 ， 是由自然界中蚂蚁觅食的行为而启发的 。
在自 然界中 ， 蚂蚁觅食过程中 ， 蚁群总能够按照寻找到一条从蚁巢和食物源的最优路 径 。
图（1）显示了这样一个觅食的过程 。
ff（b）在图1（ a）中 ， 有一群蚂蚁 ， 假如& aA是蚁巢 ， E是食物源（反之亦然） 。
这 群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶 。
假如在A和E之间突然出现了 一个障碍物(图1 (b),那么 ， 在B点(或D点)的蚂蚁将要做出决策 ， 到底 是向左行驶还是向 右 行驶？ 由 于一开 始路上没有 前面蚂 蚁留下的信 息素 (pheromon ， 蚂蚁朝着两个方向行进的概率是相等的 。
但是当有蚂蚁走过时 ，它将会在它行进的路上释放出信息素 ， 并且这种信息 。

5、素会议一定的速率散发掉 。
信息素是蚂蚁之间交流的工具之一 。
它后面的蚂蚁通过路上信息素的浓度 ，做出 决策 ， 往左还是往右 。
很明显 ， 沿着短边的的路径上信息素将会越来越浓(图 1(c),从而吸引了越来越多的蚂蚁沿着这条路径行驶 。
1.3 蚁群算法的特点1.3.1 人工蚁群的特点. 蚁群算法中所使用的蚂蚁是现实蚂蚁行为特征的一种抽象 ， 称为人工蚂蚁 。
人工蚂蚁的通讯方式、 相互协作机制与现实蚂蚁一样 ，但是如果完全依照现实蚂 蚁行为机制来设计蚁群算法 ，实验表明算法需要很多的时间才会收敛 ，而且可能 会收敛于一些局部优解 。
故人工蚂蚁又有不同于现实蚂蚁的地方 ，以tsP问题为 例：(1) 人工蚂蚁有一定的 。

6、记忆能力 ， 它可以记住已经走过的路径 ， 以保证不会 重复走相同的城市 。
现实的蚂蚁没有记忆 。
(2) 人工蚂蚁不仅仅依据信息素来确定要走的路径 ， 还引入了与问题相关的 启发信息 ， 比如相邻边的长度 。
这个构造的启发信息有利于下一步的搜索 。
(3) 人工蚂蚁处于一个离散的时间环境下 ， 而现实中的蚂蚁是在一个连续的 状态下 。
所以 ，人工蚂蚁可以根据问题的需要比较灵活的加入相应的规则 ，以更 加有效的解决实际问题 。
1.3.2 蚁群的特点蚁群中的蚂蚁具有多元性、相关性 ， 而且相互之间的协作又体现了整体性 ，所以蚁群具有系统性的特点 。
人工蚂蚁在任务中越来越趋向于一种接近最优的结 果 ， 整体来看就是一种从无序到有序的自组织过 。

7、程 ，这种自组织性增加了算法的 鲁棒性 。
在解决问题的过程中 ，当某个解较优时 ，就会使更多的蚂蚁选择这个解 ，解越优 ，蚂蚁选择此解的概率越大 ，直到收敛到最优解 ，这使蚁群有了正反馈的 特性 。
由于在选择的过程种采用了轮转赌 ，这样会增加一些随机的因素 ，增大了 解的搜索围 ， 如此便是一种负反馈的性质 。
由于蚁群中每只蚂蚁都是并行运作 ，所以蚁群还有分布式并发的特点 。
1.4 蚁群算法的应用由前面的论述可知 ，蚁群算法是一种启发式算法 ，它来源于对蚂蚁群体搜索 行为的研究 。
它还充分模拟了实际蚁群寻求最短路径的协作优化特性 。
由于蚂蚁 寻求最短路径的行为类似于旅行商) 问题的解决过程 ，因而蚁群算法 。

8、能在问题实 例中得到最优的结果 。
另外 ， 蚁群算法还被用于作业车间调度问题、 二次分配问 题、多维背包问题、数据的特征聚类过程 ， 并取得了很好的寻优结果 。
蚁群算法在解决组合优化类问题求解方面表现出了突出的适用特征 。
人工蚁 群中的多个智能体通过正反馈确保了最优化过程的快速性 ，而早熟收敛则可以由 蚁群算法的分布式计算特性来加以避免 。
同时 ， 由于它的贪婪式启发搜索特性 ，在搜索过程的早期就可以找到可以接受的解 。
这样 ， 在一种问题求解模式中 ，同 时结合了问题求解的快速性、 全局最优特征以及在优化过程初期解的合理性等特 性 ， 从而引起了相关领域研究者的注意 。
通过相关领域研究者的关注和努力 ，蚁群算法在最初 。

9、模式的基础上得到了许 多改进和扩展 ， 并在大量领域获得了应用 ， 比如机器人系统、图像处理、制造系 统、车辆路径系统、通信系统、工程设计领域及电力系统等 。
它还被用于各类动 态资源分配、行动规划和数据聚类等相关问题的研究中 。
1.5 算法模型经过 研究 者反 复改 进 ，建立 模型的 基 本思想是 ：以正 反馈( Positive Feedback)为基础 ， 通过对较好的潜在解的增强 ， 来实现对最优解的搜索 。
1) 通过设立虚拟信息素( Virtual Pheromone )来实现信息正反馈 ， 为寻找 更优解打基础 。
2) 通过引入信息素挥发机制( Evaporation )实现负反馈 ， 以避免正反馈出 现早熟现象 。

10、 (Stagnation)。
但是需要注意的是信息素按照一定的时间间隔挥发 ， 时间间隔太短会出现早 熟现象 ， 时间间隔太短个体间的协作会受到抑制 ， 所以要合理制定时间间隔 。
Dorigo 经过深入研究 ， 针对信息素的更新策略有给出了三种模型 ， 它们分 别是：蚁量系统( Ant-Quantity )、蚁密系统( Ant-Density )和蚁周系统 ( Ant-Cycle )三种模型的实现大致相同 , 主要区别是在信息素的更新方式上 。
在用蚂蚁系 统解决TSP问题时,蚁量模型和蚁密模型是蚂蚁在构建一条合法路径的过程中进 行信息素的更新的 , 当蚂蚁走过一条边之后 , 就对该边进行信息素的更新 。
而蚁周 模型是 。

11、在所有蚂蚁都构建了一条合法路径之后才对各边进行信息素更新的 , 并 且三者在蚂蚁释放信息素的量上面也不同 。
蚁密模型中 , 蚂蚁在自己所走过的边 上所释放的信息素是一个常量Q,而蚁量模型中 ， 蚂蚁在自己所走过的边上释放的信息素是Q/d,其中Q是一个常量,而dt是蚂蚁走过边的长度 。
第二章蚁群算法解决TSP问题2.1 TSP问题描述TSP问题是给定一个城市的集合以及城市之间的旅行代价 ， 寻找经过每个城 市一次且仅一次而最终回到起始城市旅行代价最小的路径 。
如果构造一个图如下 图中的顶点为城市 ， 顶点间的边表示城市间的交通线 ， 边上的权为沿该交通线旅 行的费用那么,TSP问题就抽象为在这个图中寻找最短哈密尔顿 。

12、回路 。
Ant-Cycle模型在路径上信息素的更新机制利用的是整体信息 ， 这种机制会让段路径上对应的信息量逐渐增大 ， 充分体现了算法中全局围较短路径的生存能 力 ， 加强了信息正反馈性能 ， 提高了系统搜索收敛的速度 。
在解决TSP问题时性 能较好 ， 故通常成Ant-Cycle模型为蚂蚁系统的基本模型 。
2.2基于TSP问题的蚁群算法模型蚁群算法的模型中常用的变量主要有：b i(t)代表t时刻节点i n的蚂蚁个数； t j(t)为t时刻路径(i , j )上的信息浓度；n表示TSP中节点个数；m=i 1表示蚂蚁的总数；r = t j(t)|c i,cj c为t时刻路径I j上信息量的集合 。
蚂蚁下一步选取哪个城市作 。

13、为转移的目标由各路径上的信息浓度决定 。
禁忌表tabu k (k=1,2,m中的元素都是蚂蚁k已经走过且不能再次选择的城市 ，蚂蚁每走过一个城市 ， 就要把该城市加入到tabuk中 ， 所以tabuk是不断变化的1pij (0 = *JU卄伽广时,0集合 。
每个蚂蚁都按照如下公式的计算结果来选择下一个目标:寸 j E allowedkelseAllowed k=C- tabu k中的元素是蚂蚁接下来可以走的城市；信息启发因子a表示信息轨迹的重要性 ， a越大 ， 该蚂蚁选择过的这条路径就越受其它蚂蚁欢 迎 ， 容易被其他蚂蚁选择；期望启发因子 B代表了启发信息在路径选择时的重要性；启发函数n j (t)表示为：|牯) 。

14、=7其中 ， dj为相邻两城市的距离 。
很显然 ， 两城市之间的路径越短 ， 该路径就越 容易吸引蚂蚁 ， 即p k(t)就越大 。
ij为了避免蚂蚁在某些路径上积累的信息素浓度过高 ， 以至于启发信息起不了作用 ， 在每只蚂蚁都搜索到一条哈密尔顿回路（闭合回路）后 ， 各路径上的信息 素浓度根据下面两个公式进行修改：S（於十）=（I P）右（C+尹）=工巧（八4 I0,1）代表信息挥发快慢；T j（t）是t时刻所有蚂蚁在边（i , j ）上累积的信息 ， 而蚂蚁k累积的信息量为 T jk （t）:t=0 时 ，Tij （0）=0 。
当 所有元素都存放到tabu k里面时 ， 蚂蚁k就找到了一条符合要求的 Hamilton回 路 。
2.3 。

15、蚂蚁系统解决TSP问题实现步骤1.初始化 ， 首先设定相关参数：需遍历城市数 n、蚂蚁数m初始时各路径 信息素t j、m只蚂蚁遍历（循环）次数的最大值 Nmax信息素挥发系 数 以及a、B、Q等 。
建立禁忌列表Jk ， 并保证此时列表中没有任何 城市 。
2将m个蚂蚁随机放在各个城市上 ， 每个城市至多分布一个蚂蚁 ， 并将m修改禁忌表Jk O3. 所有蚂蚁根据概率转换公式和选择下一城市 ，并将该元素（城市）移动到该 蚂蚁个体的禁忌表中 。
4. 所有蚂蚁遍历完n个城市后在所经过的路径上根据信息更新公式更新所 有所有信息素 ， 并记录本次迭代过程重点最优路径和最优路径长度 。
5. 清空禁忌列表Jk ， 重复步骤3和4,直到每一个 。

16、蚂蚁都完成 Nmax次遍历 所有城市 ， 最后输出的路径为最优路径 。
2.4蚂蚁系统解决TSP问题流程图I-讥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为启发因 。

17、子 ， 这里设为距离的倒数Tau=o nes(CityNum,CityNum);
%Tau 为信息素矩阵Tabu=zeros(m,CityNum);
%存储并记录路径的生成 NC=1;
%迭代计数器 R_best=zeros(NC_max,CityNum);
% 各代最佳路线L_best=i nf.*o nes(NC_max,1);
%各代最佳路线的长度L_ave=zeros(NC_max,1);
% 各代路线的平均长度 while NC=ran d);
to_visit=J(Select(1);
Tabu(i,j)=to visit;
endendif NC=2Tabu(1,:)=R_best(NC-1,:);
。

18、end%四记录本次迭代最佳路线L=zeros(m,1);
for i=1:mR=Tabu(i,:);
L(i)=CalDist(dislist,R);
endL_best(NC)=mi n( L);
pos=fi nd(L=L_best(NC);
R_best(NC,:)=Tabu(pos(1),:);
L_ave(NC)=mea n(L);
drawTSP(Clist,R_best(NC,:),L_best(NC),NC,0);
NC=NC+1%更新信息素Delta_Tau=zeros(CityNum,CityNum);
for i=1:mfor j=1:(CityNum-1)Delta_Tau(Tabu(i 。

【算法|蚁群算法研究报告】19、,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i);
endDelta_Tau(Tabu(i,CityNum),Tabu(i,1)=Delta_Tau(Tabu(i,CityNum),Tabu(i,1)+Q/L(i);
endTau=(1-Rho).*Tau+Delta_Tau;
%六禁忌表清零Tabu=zeros(m,CityNum);
%pause;
tauji(NC)=Tau(1,2);
end10参考文献1 朱 杰 蚁群算法解决 TSP 问题的浅析 J 电脑知识与技术 Vol.3,No.4,August 2008, pp.724- 725,7462 宏 蚁群算法解决 TSP 问题的研究 J 农业网络信息 ：1672- 625（ 1 2007）03- 0022033郭平 鄢文晋 基于TSP问题的蚁群算法综述J计算机科学2007VOI.34 No.10 。

稿源：(未知)

【傻大方】网址：/a/2021/0801/0023374116.html

标题：算法|蚁群算法研究报告