当前位置：文档之家 › 蚁群算法及算例

蚁群算法及算例

  • 格式：pptx
  • 大小：635.93 KB
  • 文档页数：54

下载文档原格式

  / 54

合集下载

蚁群算法

蚁群算法

两阶段算法（Two Phase Algorithm）
算法举例
（3）以P0为起点，以P4为终点，求下图最短路径L
Dijkstra算法 动态规划 L为 P0→P6 → P3 → P4. 总长度为97km。
（4）根据最短路进行分组，最短路由三条分支组成，即
P0→P5 → P8 → P7 → P6 → P0. 33km，5.9t
0 0
4 10 17 0
节约法（Saving Method）
算法举例
点对之间连接的距离节约值
连接点 3-4 2-3 7-8 6-7 1-7 节约里程 19 18 17 16 13 连接点 1-2 1-6 6-8 2-4 1-3 节约里程 12 11 10 9 8 连接点 1-8 2-7 5-8 2-6 4-5 节约里程 5 5 4 3 3 连接点 5-7 3-7 5-6 节约里程 3 1 1
Cij P0 P5 P8 P0 0 P5 8 0 P8 22 18 0 P7 33 29 28 P6 33 29 28 P1 ∞ ∞ 37 P2 ∞ ∞ ∞ P3 ∞ ∞ ∞ P4 ∞ ∞ ∞
P7
P6 P1 P2 P3 P4
0
16
0
25
20 0
35
30 22 0
∞
42 34 30 0
∞
∞ ∞ ∞ 22 0
节约法（Saving Method）
算法举例
求初始解
令Ii={i}，i=1，2，· · · ，8；最短路长li=2C0i；载重量ri=Ri；标记 （合并次数）B1=B2=· · · =B8=0.
按节约里程从大到小合并路径 8
P3 P29 10P15 NhomakorabeaP4
11

蚁群算法及案例分析精选全文

蚁群算法及案例分析精选全文
问过的节点;另外,人工蚁
群在选择下一条路径的时
候并不是完全盲目的,而是
按一定的算法规律有意识
地寻找最短路径
自然界蚁群不具有记忆的
能力，它们的选路凭借外
激素，或者道路的残留信
息来选择，更多地体现正
反馈的过程
人工蚁群和自然界蚁群的相似之处在于,两者优先选择的都
是含“外激素”浓度较大的路径; 两者的工作单元(蚂蚁)都
正反馈、较强的鲁棒性、全
局性、普遍性
局部搜索能力较弱，易出现
停滞和局部收敛、收敛速度
慢等问题
优良的分布式并行计算机制
长时间花费在解的构造上，
导致搜索时间过长
Hale Waihona Puke 易于与其他方法相结合算法最先基于离散问题，不
能直接解决连续优化问题
蚁群算法的
特点
蚁群算法的特点及应用领域
由于蚁群算法对图的对称性以
及目标函数无特殊要求，因此
L_ave=zeros(NC_max,1);
%各代路线的平均长度
while NC<=NC_max
%停止条件之一：达到最大迭代次数
% 第二步：将m只蚂蚁放到n个城市上
Randpos=[];
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';
scatter(C(:,1),C(:,2));
L(i)=L(i)+D(R(1),R(n));
hold on
end
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])

蚁群算法附带数据结果

蚁群算法附带数据结果

[代码说明]蚁群算法解决VRP问题[算法说明]首先实现一个ant蚂蚁类，用此蚂蚁类实现搜索。

算法按照tsp问题去解决，但是在最后计算路径的时候有区别。

比如有10个城市,城市1是配送站，蚂蚁搜索的得到的路径是1,3,5,9,4,10,2,6,8,7。

计算路径的时候把城市依次放入派送线路中,每放入一个城市前，检查该城市放入后是否会超过车辆最大载重如果没有超过就放入如果超过，就重新开始一条派送路线……直到最后一个城市放完就会得到多条派送路线这样处理比较简单可以把vrp问题转为tsp问题求解但是实际效果还需要验证。

[作者]Wugsh@2011.12.16wuguangsheng@guangsheng.wu@%}%清除所有变量和类的定义clear;clear classes;%蚁群算法参数(全局变量)global ALPHA; %启发因子global BETA; %期望因子global ANT_COUNT; %蚂蚁数量global CITY_COUNT; %城市数量global RHO; %信息素残留系数!!!global IT_COUNT; %迭代次数global DAry; %两两城市间距离global TAry; %两两城市间信息素global CITYW Ary; %城市货物需求量global VW; %车辆最大载重%===================================================================%设置参数变量值ALPHA=1.0;BETA=2.0;RHO=0.95;IT_COUNT=200;VW=100;%=================================================================== %读取数据并根据读取的数据设置其他参数load data.txt; %从文本文件加载数据city_xy_ary=data(:,2:3); %得到城市的坐标数据CITYW Ary=data(:,4); %得到每个城市的货物需求量CITY_COUNT=length(CITYW Ary); %得到城市数量(包括配送站在内)ANT_COUNT=round(CITY_COUNT*2/3)+1; %根据城市数量设置蚂蚁数量,一般设置为城市数量的2/3%MMAS信息素参数%计算最大信息素和最小信息素之间的比值PBest=0.05; %蚂蚁一次搜索找到最优解的概率temp=PBest^(1/CITY_COUNT);TRate=(1-temp)/((CITY_COUNT/2-1)*temp); %最大信息素和最小信息素之间的比值%信息素的最大最小值开始的时候设置成多大无所谓%第一次搜索完成会生成一个最优解,然后用这个解会重新产生最大最小值Tmax=1; %信息素最大值Tmin=Tmax*TRate; %信息素最小值% 计算两两城市间距离DAry=zeros(CITY_COUNT);for i=1:CITY_COUNTfor j=1:CITY_COUNTDAry(i,j)=sqrt((city_xy_ary(i,1)-city_xy_ary(j,1))^2+(city_xy_ary(i,2)-city_xy_ary(j,2))^2);endend% 初始化城市间信息素TAry=zeros(CITY_COUNT);TAry=TAry+Tmax;%===================================================================%初始化随机种子rand('state', sum(100*clock));%另一种方法%rand('twister',sum(100*clock))%定义蚂蚁mayi=ant();Best_Path_Length=10e9; %最佳路径长度，先设置成一个很大的值tm1=datenum(clock); %记录算法开始执行时的时间FoundBetter=0; %一次搜索是否有更优解产生%开始搜索for i=1:IT_COUNTfprintf('开始第%d次搜索, 剩余%d次',i,IT_COUNT-i);FoundBetter=0; %搜索前先置为没有更优解产生for j=1:ANT_COUNT%蚂蚁搜索一次mayi=Search(mayi);%得到蚂蚁搜索路径长度Length_Ary(j)=get(mayi,'path_length');%得到蚂蚁搜索的路径Path_Ary{j}=get(mayi,'path');%保存最优解if (Length_Ary(j) < Best_Path_Length);Best_Path_Length=Length_Ary(j);Best_Path=Path_Ary{j};%有更优解产生,设置标志FoundBetter=1;endend%有更好解产生,进行2-OPT优化if (FoundBetter == 1)fprintf(' , 本次搜索找到更好解!');Best_Path=opt2(Best_Path);Best_Path_Length=PathLength(Best_Path);end%-------------------------------------------------------------%全部蚂蚁搜索完一次，更新环境信息素TAry=TAry*RHO;%只有全局最优蚂蚁释放信息素dbQ=1/Best_Path_Length;for k=2:CITY_COUNTm=Best_Path(k-1); %上一个城市编号n=Best_Path(k); %下一个城市编号%更新路径上的信息素TAry(m,n)=TAry(m,n)+dbQ;TAry(n,m)=TAry(m,n);end%更新最后城市返回出发城市路径上的信息素TAry(n,1)=TAry(n,1)+dbQ;TAry(1,n)=TAry(n,1);%-------------------------------------------------------------%更新完信息素,进行边界检查Tmax=1/((1-RHO)*Best_Path_Length); %信息素最大值Tmin=Tmax*TRate; %信息素最小值for m=1:CITY_COUNTfor n=1:CITY_COUNTif (TAry(m,n)>Tmax)TAry(m,n)=Tmax;endif (TAry(m,n)<Tmin)TAry(m,n)=Tmin;endendend%-------------------------------------------------------------%换行fprintf('\n');endtm2=datenum(clock); %记录算法结束执行时的时间fprintf('\n搜索完成, 用时%.3f秒, 最佳路径长为%.3f , 派送方案如下:：\n\n[1]',(tm2-tm1)*86400,Best_Path_Length);%=================================================================== %输出结果dbW=0;for i=2:CITY_COUNTm=Best_Path(i-1); %上一个城市n=Best_Path(i); %当前城市if (dbW+CITYW Ary(n)>VW) %运送的货物超过限制fprintf(' (满载率: %.1f%%)\n[1]-%d',dbW*100/VW,n);dbW=CITYW Ary(n); %运输的重量等于该城市的需求量else %没有超过限制fprintf('-%d',n);dbW=dbW+CITYWAry(n); %运输的重量加上该城市的需求量endendfprintf(' (满载率: %.1f%%)',dbW*100/VW);fprintf('\n\n');%====== [程序结束]===================================================== %对结果进行2-OPT优化function f=opt2(Line)%数组长度size=length(Line);NewLine=Line; % 返回结果先设置成原来路径Flag=1;while (Flag == 1)Flag=0;for i=1:size-2a=Line(1,1:i); %路径前段b=fliplr(Line(1,i+1:size)); %路径后段倒置c=cat(2,a,b); %新路径%新路径更好就替换if (PathLength(c)<PathLength(NewLine))NewLine=c;Flag=1;fprintf('\n======================= 2-OPT 优化成功! ===');endendend%返回结果f=NewLine;end1 14.5 13.0 0.02 12.8 8.5 0.13 18.4 3.4 0.44 15.4 16.6 1.25 18.9 15.2 1.56 15.5 11.6 0.87 3.9 10.6 1.38 10.6 7.6 1.79 8.6 8.4 0.610 12.5 2.1 1.211 13.8 5.2 0.412 6.7 16.9 0.913 14.8 2.6 1.314 1.8 8.7 1.315 17.1 11.0 1.916 7.4 1.0 1.717 0.2 2.8 1.118 11.9 19.8 1.519 13.2 15.1 1.620 6.4 5.6 1.721 9.6 14.8 1.51 0 0 02 3639 1315 123 4177 2244 134 3712 1399 145 3488 1535 536 3326 1556 457 3238 1229 228 4196 1004 119 4312 790 1110 4386 570 5611 3007 1970 4312 2562 1756 2413 2788 1491 6514 2381 1676 3215 1332 695 5616 3715 1678 6717 3918 2179 6718 4061 2370 2219 3780 2212 3420 3676 2578 5621 4029 2838 2422 4263 2931 2523 3429 1908 2624 3507 2367 4625 3394 2643 8726 3439 3201 3327 2935 3240 2228 3140 3550 2429 2545 2357 5630 2778 2826 2431 2370 2975 4332 1304 2312 12。

蚁群算法概述

蚁群算法概述

蚁群算法概述一、蚁群算法蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来寻找最优解决方案的机率型技术。

它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。

其选择一条路径的概率与该路径上分泌物的强度成正比。

因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。

蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。

蚁群算法就是根据这一特点，通过模仿蚂蚁的行为，从而实现寻优。

这种算法有别于传统编程模式，其优势在于，避免了冗长的编程和筹划，程序本身是基于一定规则的随机运行来寻找最佳配置。

也就是说，当程序最开始找到目标的时候，路径几乎不可能是最优的，甚至可能是包含了无数错误的选择而极度冗长的。

但是，程序可以通过蚂蚁寻找食物的时候的信息素原理，不断地去修正原来的路线，使整个路线越来越短，也就是说，程序执行的时间越长，所获得的路径就越可能接近最优路径。

这看起来很类似与我们所见的由无数例子进行归纳概括形成最佳路径的过程。

实际上好似是程序的一个自我学习的过程。

3、人工蚂蚁和真实蚂蚁的异同ACO是一种基于群体的、用于求解复杂优化问题的通用搜索技术。

与真实蚂蚁通过外激素的留存/跟随行为进行间接通讯相似，ACO中一群简单的人工蚂蚁（主体）通过信息素（一种分布式的数字信息，与真实蚂蚁释放的外激素相对应）进行间接通讯，并利用该信息和与问题相关的启发式信息逐步构造问题的解。

人工蚂蚁具有双重特性：一方面，他们是真实蚂蚁的抽象，具有真实蚂蚁的特性，另一方面，他们还有一些在真实蚂蚁中找不到的特性，这些新的特性，使人工蚂蚁在解决实际优化问题时，具有更好地搜索较好解的能力。

人工蚂蚁与真实蚂蚁的相同点为：1．都是一群相互协作的个体。

蚁群算法原理介绍

蚁群算法原理介绍
E E
15
15
A
B 30 15 F 15
C 30
D
A
B 30 30 F 30
C 30
D
路径BFC：蚂蚁增加，信息量增加，路径被选择的机率增加； 路径BEC：时间增加，信息量减少，路径被选择的机率减小。
基本蚁群算法的系统学特征
蚁群算法是一个系统
分布式计算
自组织
正反馈
蚁群算法是一个系统
Bertalanffy L V： 系统可以确定为处于一定的相互关系中 并与环境发生关系的各组成部分（要素）的 综合体。
蚁群行为描述
E E
d=1
d=1
15
15
蚁A 穴
B 30 d=0.5
C 30 d=0.5
D
食 物 源
A
B 30 15 F 15
C 30
D
F
释放信息素与路径长度成反比
蚁群行为描述
E E
10
10
A
B 30 20 20
C 30
D
A
B 30 30 30
C 30
D
F
F
信息量大，路径被选概率大
基本蚁群算法的机制原理
2.2.5 初始的蚁群优化算法—基于图的蚁群 系统（GBAS）
假设共4只蚂蚁，所有蚂蚁都从城市A出发，挥发因子 k 1 2 , k 1, 2,3 。此时，观察GBAS的计算过程。 矩阵 共有12条弧，初始信息素记忆矩阵为：
0 1 12 1 12 1 12 1 12 0 1 12 1 12 (0) ( ij (0)) 1 12 1 12 0 1 12 1 12 1 12 1 12 0
TSP的目的

蚁群算法——精选推荐

蚁群算法——精选推荐

蚁群算法⼀、蚁群算法蚁群算法是在20世纪90年代由澳⼤利亚学者Marco Dorigo等⼈通过观察蚁群觅⾷的过程，发现众多蚂蚁在寻找⾷物的过程中，总能找到⼀条从蚂蚁巢⽳到⾷物源之间的最短路径。

随后他们在蚂蚁巢⽳到⾷物源之间设置了⼀个障碍，⼀段时间以后发现蚂蚁⼜重新⾛出了⼀条到⾷物源最短的路径。

通过对这种现象的不断研究，最后提出了蚁群算法。

蚁群算法在解决（即TSP问题）时，取得了⽐较理想的结果。

⼆、基本⼈⼯蚁群算法原理运⽤⼈⼯蚁群算法求解TSP问题时的基本原理是：将m个蚂蚁随机地放在多个城市，让这些蚂蚁从所在的城市出发，n步（⼀个蚂蚁从⼀个城市到另外⼀个城市为1步）之后返回到出发的城市。

如果m个蚂蚁所⾛出的m条路经对应的中最短者不是TSP问题的最短路程，则重复这⼀过程，直⾄寻找到满意的TSP问题的最短路径为⽌。

为了说明这⼀个算法下⾯⽤⼀个算法流程图来表⽰⼀下：三、蚁群算法中涉及到的参数及其符号：：蚂蚁数量，约为城市数量的1.5倍。

如果蚂蚁数量过⼤，则每条路径上的信息素浓度趋于平均，正反馈作⽤减弱，从⽽导致收敛速度减慢；如果过⼩，则可能导致⼀些从未搜索过的路径信息素浓度减⼩为0，导致过早收敛，解的全局最优性降低：信息素因⼦，反映了蚂蚁运动过程中积累的信息量在指导蚁群搜索中的相对重要程度，取值范围通常在[1, 4]之间。

如果信息素因⼦值设置过⼤，则容易使随机搜索性减弱；其值过⼩容易过早陷⼊局部最优：启发函数因⼦，反映了启发式信息在指导蚁群搜索中的相对重要程度，取值范围在[3, 4.5]之间。

如果值设置过⼤，虽然收敛速度加快，但是易陷⼊局部最优；其值过⼩，蚁群易陷⼊纯粹的随机搜索，很难找到最优解：信息素挥发因⼦，反映了信息素的消失⽔平，相反的反映了信息素的保持⽔平，取值范围通常在[0.2, 0.5]之间。

当取值过⼤时，容易影响随机性和全局最优性；反之，收敛速度降低：信息素常数，表⽰蚂蚁遍历⼀次所有城市所释放的信息素总量。

蚁群算法


基本蚁群算法程序流程图
开始 初始化
循环次数Nc← Nc+1
蚂蚁k=1 蚂蚁k=k+1
按式（1）选择下一元素 修改禁忌表 N Y K≥ m
按式（2）和式（3）进行信息量更新 满足结束条件 Y
Байду номын сангаас输出程序计算结果 结束 N
复杂度分析
对于TSP，所有可行的路径共有(n-1)!/2条，以 此路径比较为基本操作，则需要(n-1)!/2-1次基 本操作才能保证得到绝对最优解。 若1M FLOPS，当n=10, 需要0.19秒 n=20, 需要1929年 n=30, 需要1.4X10e17年
{ ij (t ) | ci , c j C}是t时刻集合C中元素
蚂蚁k(k=1,2,…,m)在运动过程中，根据各条路径上的信息 量决定其转移方向。这里用禁忌表tabuk来记录蚂蚁k当前 所走过的城市，集合随着tabuk进化过程做动态调整。在 搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发 信息来计算状态转移概率。在t时刻蚂蚁k由元素（城市）i 转移到元素（城市）j的状态转移概率：
1) 标有距离的路径图 2) 在0时刻，路径上没有信息素累积，蚂蚁选择路径为任意 3) 在1时刻，路径上信息素堆积，短边信息素多与长边，所以蚂蚁更 倾向于选择ABCDE
特
点
（1）其原理是一种正反馈机制或称增强型学习系统；它通过 信息素的不断更新达到最终收敛于最优路径上； （2）它是一种通用型随机优化方法；但人工蚂蚁决不是对实 际蚂蚁的一种简单模拟，它融进了人类的智能； （3）它是一种分布式的优化方法；不仅适合目前的串行计算 机，而且适合未来的并行计算机； （4）它是一种全局优化的方法；不仅可用于求解单目标优化 问题，而且可用于求解多目标优化问题； 2 （5）它是一种启发式算法；计算复杂性为 O( NC m n )，其 中NC 是迭代次数，m 是蚂蚁数目，n 是目的节点数目。

第 6 章 蚁群算法


蚂蚁如何找到最短路径
信息素：信息素多的地方显然经过这里的蚂蚁多， 因而会有更多的蚂蚁聚集过来。 正反馈现象：某一路径上走过的蚂蚁越多，则后来 者选择该路径的概率就越大。
蚁群算法的基本思想
当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂 位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然 会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长 的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最 短的路径就近似找到了。
则，输出目前的最优解。
3 目标值控制规则，给定优化问题（目标最小化）的一个下界和一个 误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法 终止。
TSP应用举例
TSP应用举例
Introduction of Artificial Intelligence
Introduction of Artificial Intelligence
蚁群算法的数学模型
第二步:选择路径路径 在t时刻，蚂蚁k从城市i转移到城市j的概率为：
蚁群算法的数学模型
蚁群算法的数学模型
第四步：输出结果 若未达到终止条件则转步骤二，否 蚁群的规模和停止规则
蚁群大小: 一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。 终止条件: 1 给定一个外循环的最大数目，表明已经有足够的蚂蚁工作； 2 当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算 法已经收敛，不再需要继续；
我国最早研究蚁群算法的是东北大学的张纪会博士 和徐心和教授。
什么是蚁群算法
蚁群算法(ant colony optimization, ACO)，又称蚂 蚁算法，是一种用来在图中寻找优化路径的机率型 算法。它由Marco Dorigo于1991年在他的博士论文 中提出，其灵感来源于蚂蚁在寻找食物过程中发现 路径的行为。

数据分析知识：数据挖掘中的蚁群算法

数据分析知识：数据挖掘中的蚁群算法蚁群算法是一种模拟蚂蚁觅食行为的启发式算法。

它是一种基于群体智能的方法，能够有效地用于数据挖掘和机器学习领域。

本文将介绍蚁群算法的基本原理和应用案例。

一、蚁群算法的基本原理蚁群算法受到了蚂蚁觅食行为的启发。

蚂蚁在觅食过程中会遵循一定的规则，例如在路径上释放信息素，吸引其他蚂蚁前往同一方向；在路径上的信息素浓度较高的路径更容易选择。

蚁群算法利用了这些规则，以一种群体智能的方式搜索解空间。

具体来说，蚁群算法由以下几个步骤组成：1.初始化：定义问题的解空间和初试信息素浓度。

解空间可以是任何基于排列、图形或其他对象的集合，例如TSP问题中的城市序列集合。

信息素浓度矩阵是一个与解空间大小相同的矩阵，用于反映每个解的吸引力。

2.移动规则:蚂蚁在解空间中移动的规则。

通常规则包括根据当前解和信息素浓度选择下一步解以及更新当前解的信息素浓度。

3.信息素更新:蚁群中的蚂蚁经过路径后，更新路径上的信息素浓度。

通常信息素浓度的更新涉及一个挥发系数和一个信息素增量。

4.终止条件:确定蚁群算法的运行时间，例如最大迭代次数或达到特定解的准确度。

蚁群算法是一种群体智能的方法，每只蚂蚁只能看到局部的解。

通过信息素的释放和更新，蚁群最终能够找到全局最优解。

二、蚁群算法的应用案例蚁群算法最常用于解决组合优化问题，例如TSP问题、车辆路径问题和任务分配问题。

下面将介绍蚁群算法在TSP问题和车辆路径问题中的应用。

1. TSP问题TSP问题是一个NP难问题，是指在旅行时，如何有效地走遍所有篮子，使得总的旅行距离最小。

蚁群算法是适用于TSP问题的一种有效的算法。

在每一代，蚂蚁会在城市之间移动，假设当前城市为i，则下一个选择的城市j是基于概率函数计算得到的。

概率函数考虑了当前城市的信息素浓度以及城市之间的距离。

每条路径释放的信息素浓度大小根据路径长度而定。

这样，蚂蚁可以在TSP问题上找到最优解。

2.车辆路径问题车辆路径问题是指在有限时间内如何合理地分配车辆到不同的客户，以最小化送货时间和车辆的旅行距离。

蚁群算法——精选推荐

蚁群算法这算是填3年前的⼀个坑吧，已经懒癌晚期了，想必也还是要挣扎下，那今天先从蚁群算法这个坑说起，如果你是要寻找怎么优化蚁群算法，可以直接跳过本⽂，如果你还不了解什么是蚁群算法，或许本⽂能够提起你的兴趣。

如果你同样对遗传算法和粒⼦群算法感兴趣，请查看3年前我对于这两个算法见解的⽂章。

简单蚁群算法模拟实验：这个模拟实验⽐较简单，并没有对信息素、路径选择等做优化，主要是⽅便⼤家查看简单的蚂蚁系统能够带来⼀个什么样的效果,详细说明见后⽂。

什么是蚁群算法按百度百科的话来说，蚁群算法(ant colony optimization, ACO)，⼜称蚂蚁算法，是⼀种⽤来在图中寻找优化路径的机率型算法。

它由Marco Dorigo于1992年在他的博⼠论⽂中提出，其灵感来源于蚂蚁在寻找⾷物过程中发现路径的⾏为。

蚁群算法是⼀种模拟进化算法，初步的研究表明该算法具有许多优良的性质，并且现在已⽤于我们⽣活的⽅⽅⾯⾯。

基本原理蚂蚁在运动过程中，会留下⼀种称为信息素的东西，并且会随着移动的距离，播散的信息素越来越少，所以往往在家或者⾷物的周围，信息素的浓度是最强的，⽽蚂蚁⾃⾝会根据信息素去选择⽅向，当然信息素越浓，被选择的概率也就越⼤，并且信息素本⾝具有⼀定的挥发作⽤。

蚂蚁的运动过程可以简单归纳如下：1. 当周围没有信息素指引时，蚂蚁的运动具有⼀定的惯性，并有⼀定的概率选择其他⽅向2. 当周围有信息素的指引时，按照信息素的浓度强度概率性的选择运动⽅向3. 找⾷物时，蚂蚁留下家相关的A信息素，找家时，蚂蚁留下⾷物相关的B信息素，并随着移动距离的增加，洒播的信息素越来越少4. 随着时间推移，信息素会⾃⾏挥发⼀个简单的例⼦，如果现在有两条通往⾷物的路径，⼀条较长路径A,⼀条较短路径B,虽然刚开始A,B路径上都有蚂蚁，⼜因为B⽐A短，蚂蚁通过B花费的时间较短，随着时间的推移和信息素的挥发，逐渐的B上的信息素浓度会强于A，这时候因为B的浓度⽐A强，越来越多多蚂蚁会选择B，⽽这时候B上的浓度只会越来越强。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
▲一种新的自适应蚁群算法（AACA） ▲基于混合行为的蚁群算法（HBACA）
（一）带精英策略的蚂蚁系统 ASelite
特点——在信息素更新时给予当前最优解以额 外的信息素量，使最优解得到更好的利用。找 到全局最优解的蚂蚁称为“精英蚂蚁”。
ij t n 1 ij t ij ij
蚁 群 优 化 算 法
（ACO算法）
一、概述 二、蚂蚁系统（AS） 三、算例 四、改进的ACO算法
一、概述
（一）算法背景——蚁群的自组织行为特征
1、高度结构化的组织——虽然蚂蚁的个体行为极其 简单，但由个体组成的蚁群却构成高度结构化的社会 组织，蚂蚁社会的成员有分工，有相互的通信和信息 传递。 2、自然优化——蚁群在觅食过程中，在没有任何提示 下总能找到从蚁巢到食物源之间的最短路径；当经过的 路线上出现障碍物时，还能迅速找到新的最优路径。 3、信息正反馈——蚂蚁在寻找食物时，在其经过的路 径上释放信息素（外激素）。蚂蚁基本没有视觉，但能 在小范围内察觉同类散发的信息素的轨迹，由此来决定 何去何从，并倾向于朝着信息素强度高的方向移动。 4、自催化行为——某条路径上走过的蚂蚁越多，留下 的信息素也越多（随时间蒸发一部分），后来蚂蚁选择 该路径的概率也越高。
Q , 若边 ij 是当前最优解的一部分 Δτ Lgb 0, 否则
ij
Δτ ij ——精英蚂蚁在边 ij ——精英蚂蚁个数；
上增加的信息素量；
Lgb
——当前全局最优解路径长度。
（二）蚁群系统 ACS
１、状态转移规则——伪随机比率规则 设 q0 (0,1) 为常数， q (0,1) 为随机数， 如果 q q0 ，则蚂蚁转移的下一座城市是使 [τ ij (t )]α [ηij (t )]β 取最大值的城市；若 q q0 ， 仍按转移概率确定。 一般， q0 取值较大。 ２、全局更新规则——只有精英蚂蚁才允许释放 信息素，即只有全局最优解所属的边才增加 信息素。 ３、局部更新规则——蚂蚁每次从城市 i 转移到 城市 j 后，边 i, j 上的信息素适当减少。
（二）参数含义及符号
m ——蚂蚁数量；
k ——蚂蚁编号；
t ——时刻； n ——城市数；
d ij ——城市 i, j 之间的距离；
ij ——启发式因子（能见度），反映蚂蚁由
ij ——边 i, j 上的信息素量；
城市 i 转移到城市 j 的启发程度；
ij ——本次迭代边i, j 上的信息素增量；
D 10 E 2
m 参数设置： 5, 1, 1, 0.5, Q 100, ij (0) 2
τ ij t α ηij t β X , 如 果j J k i α β k Y pij t τ is t ηis t sJ k i 0 , 否 则
（三）特点
◆是一种基于多主体的智能算法，不是 单个蚂蚁行动，而是多个蚂蚁同时搜索， 具有分布式的协同优化机制。 ◆本质上属于随机搜索算法（概率算法）， 具有概率搜索的特征。 ◆是一种全局搜索算法，能够有效地避免 局部最优。
（四）优点
◆求解问题的快速性——由正反馈机制 决定； ◆全局优化性——由分布式计算决定， 避免蚁群在寻优空间中过早收敛；
（五）最优最差蚂蚁系统 BWAS
特点：主要是修改了ACS中的全局更新公式，增加 对最差蚂蚁路径信息素的更新，对最差解进 行削弱，使信息素差异进一步增大。
（六）一种新的自适应蚁群算法 AACA
特点：将ACS中的状态转移规则改为自适应伪随机 比率规则，动态调整转移概率，以避免出现 停滞现象。 说明：在ACS的状态转移公式中， q0 是给定的常数； q0 在AACA中， 是随平均节点分支数ANB而变 化的变量。ANB较大，意味着下一步可选的城市较 多，q0 也变大，表示选择信息素和距离最好的边的 可能性增大；反之减小。
mn 1, 1 0.5
ij 0 2
Q 100
四、改进的蚁群优化算法
▲最优解保留策略蚂蚁系统（带精 英策略的蚂蚁系统ASelite） ▲蚁群系统（ACS）
改进的 蚂蚁算法
▲最大-最小蚂蚁系统（MMAS） ▲基于优化排序的蚂蚁系统 （ASrank）
▲最优最差蚂蚁系统（BWAS）
（三）计算公式
k 1、转移概率 pij t 计算公式：
τ ij t α ηij t β , 如 果j J k i α β k pij t τ is t ηis t sJ k i 0 , 否 则



——信息素的相对重要程度；
——启发式因子的相对重要程度；
J k i ——蚂蚁
k 下一步允许选择的城市集合。
1 d ij
2、启发式因子计算公式：ij
3、信息素计算公式
当所有蚂蚁完成1次周游后，各路径上的信息素为：
ij (t n) (1 ) ij (t ) ij
Q ——正常数，
Lk ——蚂蚁 k
在本次周游中所走路径的长度。
开始时， ij 0 C 令
k ij ——第 k 只蚂蚁在本次迭代中留在边 i, j
上的信息素量；
——信息素蒸发（或挥发）系数，
1 ——持久性（或残留）系数， 0 1 ；
Pijk (t ) ——时刻 t 蚂蚁 k 由城市 i 转移到城市 j 的 概率（转移概率）；
tabu ——蚂蚁 k 的禁忌表。 k
（七）基于混合行为的蚁群算法 HBACA
特点：按蚂蚁的行为特征将蚂蚁分成4类，称为4个子蚁 群，各子蚁群按各自的转移规则行动，搜索路径，每迭 代一次，更新当前最优解，按最优路径长度更新各条边 上的信息素，如此直至算法结束。
蚂蚁行为——蚂蚁在前进过程中，用以决定其下一步移 动到哪个状态的规则集合。
1、蚂蚁以随机方式选择下一步要到达的状态。
讨
论
1、对已学过的算法作出某种改进。 2、介绍自学的一种新的算法。 3、查阅文献，介绍某算法在某领域的 一个应用。
4、应用某算法解决一个实际问题。
算 例 A
A
已知资料表
B 2 0 1 4 7 C 10 2 0 3 5 D 8 5 3 0 1 E 3 7 6 2 0 A B C 0 1 9
B
E
C
D
关于 min , max 的取值，没有确定的方法，有的 书例子中取为0.01，10；有的书提出一个在最大 值给定的情况下计算最小值的公式。
（四）基于优化排代完成后，蚂蚁所经路径由小到大排序， 并根据路径长度赋予不同的权重，路径越短权重越大。 k 信息素更新时对 ij 考虑权重的影响。
特点
规则１和２都是为了使搜索过程更具有指导性，即 使蚂蚁的搜索主要集中在当前找出的最好解邻域内。规 则３则是为了使已选的边对后来的蚂蚁具有较小的影响 力，以避免蚂蚁收敛到同一路径。
（三）最大最小蚂蚁系统 MMAS
特点
1、每次迭代后，只对最优解所属路径上的信 息素更新。
2、对每条边的信息素量限制在范围 min , max 内，目的是防止某一条路径上的信息素量远 大于其余路径，避免过早收敛于局部最优解。
（六）AS算法的优点与不足 较强的鲁棒性——稍加修改即可应用 于其他问题。（鲁棒性就是系统的健壮性 ，
优点
用以表征控制系统对特性或参数摄动的不敏 感性。）
分布式计算——本质上具有并行性。
易于与其他启发式算法结合。 不足 一般需要较长的搜索时间。 容易出现停滞现象。
三、算例——5个点的货郎担问题
参数设置：
（二）算法的产生与发展
1、产生——受蚁群觅食行为启发，意大利学者M.Dorigo 于1991年在其博士论文中首次系统地提出一种基于蚂蚁种群 的新型智能优化算法“蚂蚁系统（Ant system,简称AS）”， 并用该法求解旅行商问题，获得了较好的效果。 2、发展——后来，提出者及许多研究者对该算法作了各种 改进，将其应用于更为广泛的领域，如图着色问题、二次分 配问题、工件排序问题、车辆路径问题、车间作业调度问题、 网络路由问题、大规模集成电路设计等。近些年来，M.Dorigo 等人把蚂蚁算法进一步发展成一种通用的优化技术“蚁群优化 （Ant Colony Optimization,简称ACO）”，并将所有符合ACO 框架的算法称为“蚁群优化算法（ACO algorithm）”。 3、展望——初步的研究结果已显示出ACO算法在求解复杂 优化问题，特别是离散优化问题方面的优越性。虽然严格的 理论基础尚未奠定，但从当前的应用效果来看，此算法具有 光明的发展前景。
蚂蚁 2、蚂蚁以贪婪方式选择下一步要到达的状态。 行为 3、蚂蚁按信息素强度选择下一步要到达的状态。
4、蚂蚁按信息素强度和城市间距离选择下一步要 到达的状态 。
五、蚁群算法与遗传、模拟退火算法的比较
实验结果表明：
1、蚁群算法所找出的解的质量最高，遗传 算法次之，模拟退火算法最低。
2、蚁群算法的收敛速度最快，遗传算法次 之，模拟退火算法最慢。蚁群算法之所以 能够快速收敛到全局最优解，是因为该算 法的个体之间不断进行信息交流和传递。 单个个体容易收敛于局部最优，多个个体 通过合作可以很快地收敛于解空间的最优 解的附近。
4、每只蚂蚁只能走合法路线（经过每个城市 1次且仅1次），为此设置禁忌表来控制。 5、所有蚂蚁都搜索完一次就是迭代一次，每 迭代一次就对所有的边做一次信息素更新，原 来的蚂蚁死掉，新的蚂蚁进行新一轮搜索。 6、更新信息素包括原有信息素的蒸发和经过 的路径上信息素的增加。 7、达到预定的迭代步数，或出现停滞现象 （所有蚂蚁都选择同样的路径，解不再变化）， 则算法结束，以当前最优解作为问题的最优解。
◆有限时间内答案的合理性——由贪婪 式搜索模式决定，使能在搜索过程的早期 就找到可以接受的较好解。