第二章蚁群算法

第二章蚁群算法

智能优化计算2.1群智能

智能优化计算群智能（SwarmIntelligence,SI）人们把群居昆虫的集体行为称作“群智能”（“群体智能”、“群集智能”、“集群智能”等）

特点

个体的行为很简单，但当它们一起协同工作时，却能够突现出非常复杂（智能）的行为特征。2.1.1群智能的概念2.1群智能

智能优化计算描述群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。特性指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。2.1.2群智能算法2.1群智能

智能优化计算优点灵活性：群体可以适应随时变化的环境；

稳健性：即使个体失败，整个群体仍能完成任务；自我组织：活动既不受中央控制，也不受局部监管。典型算法蚁群算法（蚂蚁觅食）粒子群算法（鸟群捕食）2.1.2群智能算法2.2蚁群优化算法原理

智能优化计算蚁群的自组织行为“双桥实验”通过遗留在来往路径上的信息素（Pheromone）的挥发性化学物质来进行通信和协调。2.2.1蚁群算法的起源2.2蚁群优化算法原理

智能优化计算蚁群的自组织行为“双桥实验”2.2.1蚁群算法的起源2.2蚁群优化算法原理

智能优化计算提出蚁群系统

1992年，意大利学者M.Dorigo在其博士论文中提出蚂蚁系统（AntSystem）。近年来，M.Dorigo等人进一步将蚂蚁算法发展为一种通用的优化技术——蚁群优化（antcolonyoptimization,ACO）。

2.2.1蚁群算法的起源

蚂蚁从A点出发，随机选择路线ABD或ACD。经过9个时间单位时：走ABD的蚂蚁到达终点，走ACD的蚂蚁刚好走到C点。2.2蚁群优化算法原理

智能优化计算2.2.2蚁群算法的原理分析蚁巢食物2.2蚁群优化算法原理

智能优化计算

经过18个时间单位时：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。2.2.2蚁群算法的原理分析蚁巢食物

最后的极限是所有的蚂蚁只选择ABD路线。（正反馈过程）2.2蚁群优化算法原理

智能优化计算2.2.2蚁群算法的原理分析蚁巢食物假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。2.2蚁群优化算法原理

智能优化计算2.2.2蚁群算法的原理分析基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。2.2蚁群优化算法原理

智能优化计算2.2.2蚁群算法的原理分析TSP问题表示为一个N个城市的有向图G=（N，A），其中 城市之间距离目标函数为其中为城市1,2，…n的一个排列，。2.2.2蚁群算法与TSP问题2.2.2蚁群算法与TSP问题

TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1信息素值也称信息素痕迹。2可见度，即先验值。信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。2.2.2蚁群算法与TSP问题蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。2.2.3初始的蚁群优化算法—基于图的蚁群系统（GBAS）初始的蚁群算法是基于图的蚁群算法，graph-basedantsystem,简称为GBAS，是由GutjahrWJ在2000年的FutureGenerationComputingSystems提出的.算法步骤如下：STEP0

对n个城市的TSP问题，城市间的距离矩阵为，给TSP图中的每一条弧赋信息素初值，假设m只蚂蚁在工作，所有蚂蚁都从同一城市出发。当前最好解是 。2.2.3初始的蚁群优化算法—基于图的蚁群系统（GBAS）STEP1

（外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁s从起点出发，用表示蚂蚁s行走的城市集合，初始为空集，。STEP2(内循环)按蚂蚁的顺序分别计算。当蚂蚁在城市i，若 完成第s只蚂蚁的计算。否则，若，则以概率 ， 到达j， ；若则到达 重复STEP2。2.2.3初始的蚁群优化算法—基于图的蚁群系统（GBAS）STRP3

对 ，若，按中城市的顺序计算路径程度；若，路径长度置为一个无穷大值（即不可达）。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t。若，则。用如下公式对W路径上的信息素痕迹加强，对其他路径上的信息素进行挥发。得到新的，重复步骤STEP1。2.2.3初始的蚁群优化算法—基于图的蚁群系统（GBAS）在STEP3

中，挥发因子对于一个固定的，满足并且

经过k次挥发，非最优路径的信息素逐渐减少至消失。2.2.3初始的蚁群优化算法—基于图的蚁群系统（GBAS）以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市i到城市j的转移。算法中包括信息素更新的过程

1信息素挥发（evaporation）信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，由表示，这个挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。

2信息素增强（reinforcement）增强过程是蚁群优化算法中可选的部分，称为离线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂蚁无法实现的集中行动。也就是说，增强过程体现在观察蚁群（m只蚂蚁）中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强，挥发过程是所有弧都进行的，不于蚂蚁数量相关。这种增强过程中进行的信息素更新称为离线的信息素更新。在STEP3中，蚁群永远记忆到目前为止的最优解。图的蚁群系统（GBAS）可以验证，下式满足：即是一个随机矩阵。四个城市的非对称TSP问题，距离矩阵和城市图示如下：2023/2/2222.2.3初始的蚁群优化算法—基于图的蚁群系统（GBAS）假设共4只蚂蚁，所有蚂蚁都从城市A出发，挥发因子。此时，观察GBAS的计算过程。矩阵共有12条弧，初始信息素记忆矩阵为：2023/2/2232.2.3初始的蚁群优化算法—基于图的蚁群系统（GBAS）执行GBAS算法的步骤2，假设蚂蚁的行走路线分别为：当前最优解为，这个解是截止到当前的最优解，碰巧是实际最优解2.2.3初始的蚁群优化算法—基于图的蚁群系统（GBAS）按算法步骤3的信息素更新规则，得到更新矩阵这是第一次外循环结束的状态。2.2.3初始的蚁群优化算法—基于图的蚁群系统（GBAS）重复外循环，由于上一次得到的W2已经是全局最优解，因此按算法步骤3的信息素更新规则，无论蚂蚁如何行走，都只是对W2路线上的城市信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵这是第一次外循环结束的状态。2.2.3初始的蚁群优化算法—基于图的蚁群系统（GBAS）重复外循环，由于W2全局最优解，GBAS只记录第一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优路线的信息素，同时进行挥发。第三次外循环后得到的信息素矩阵为：2.2.3初始的蚁群优化算法—基于图的蚁群系统（GBAS）蚂蚁以一定的概率从城市i到城市j进行转移，信息素的更新在STEP3完成，并随K而变化。假设第K次外循环后得到信息素矩阵，得到当前最优解。第K次循环前的信息素和最优解为，经过第K次外循环后，得到。由于蚂蚁的一步转移概率是随机的，从到也是随机的，是一个马尔可夫过程。2.2.3一般蚁群算法的框架一般蚁群算法的框架和GBAS基本相同，有三个组成部分：蚁群的活动；信息素的挥发；信息素的增强；主要体现在前面的算法中步骤2和步骤3中的转移概率公式和信息素更新公式。2.3基本蚁群优化算法

智能优化计算解决TSP问题

在算法的初始时刻，将m只蚂蚁随机放到n座城市;

将每只蚂蚁k的禁忌表tabuk(s)的第一个元素tabuk(1)设置为它当前所在城市;

设各路径上的信息素τij(0)=C（C为一较小的常数）;2.3.1蚂蚁系统的模型与实现2.3基本蚁群优化算法

智能优化计算解决TSP问题

每只蚂蚁根据路径上的信息素和启发式信息（两城市间距离）独立地选择下一座城市：在时刻t，蚂蚁k从城市i转移到城市j的概率为

α、β分别表示信息素和启发式因子的相对重要程度。2.3.1蚂蚁系统的模型与实现下一步允许的城市的集合2.3基本蚁群优化算法

智能优化计算解决TSP问题

当所有蚂蚁完成一次周游后，各路径上的信息素将进行更新：其中，ρ（0<ρ<1）表示路径上信息素的蒸发系数，Q为正常数，Lk表示第k只蚂蚁在本次周游中所走过路径的长度。

2.3.1蚂蚁系统的模型与实现2.3基本蚁群优化算法

智能优化计算算法流程2.3.1蚂蚁系统的模型与实现2.3基本蚁群优化算法

智能优化计算初始参数城市数30;

蚂蚁数30；

α=1;

β=5;

ρ=0.1;

最大迭代代数200;

Q=1;2.3.1蚂蚁系统的模型与实现2.3基本蚁群优化算法

智能优化计算%%清空环境变量clearallclc

%%导入数据loadcitys_data.mat%%计算城市间相互距离n=size(citys,1);D=zeros(n,n);fori=1:nforj=1:nifi~=jD(i,j)=sqrt(sum((citys(i,:)-citys(j,:)).^2));elseD(i,j)=1e-4;endendend

程序分析2.3基本蚁群优化算法

智能优化计算

%%初始化参数m=30;%蚂蚁数量alpha=1;%信息素重要程度因子beta=5;%启发函数重要程度因子rho=0.1;%信息素挥发因子Q=1;%常系数Eta=1./D;%启发函数Tau=ones(n,n);%信息素矩阵Table=zeros(m,n);%路径记录表iter=1;%迭代次数初值iter_max=200;%最大迭代次数Route_best=zeros(iter_max,n);%各代最佳路径Length_best=zeros(iter_max,1);%各代最佳路径的长度Length_ave=zeros(iter_max,1);%各代路径的平均长度2.3基本蚁群优化算法

智能优化计算%%迭代寻找最佳路径whileiter<=iter_max

%随机产生各个蚂蚁的起点城市start=zeros(m,1);fori=1:mtemp=randperm(n);start(i)=temp(1);endTable(:,1)=start;

%构建解空间citys_index=1:n;

%在iter循环中还有以下三个重要步骤：%1、逐个蚂蚁路径选择%2、计算各个蚂蚁路径距离及最短距离%3、更新信息素end2.3基本蚁群优化算法

智能优化计算

%逐个蚂蚁路径选择fori=1:m

%逐个城市路径选择forj=2:ntabu=Table(i,1:(j-1));%已访问的城市集合(禁忌表)allow_index=~ismember(citys_index,tabu);allow=citys_index(allow_index);%待访问的城市集合P=allow;

%计算城市间转移概率fork=1:length(allow)P(k)=Tau(tabu(end),allow(k))^alpha*Eta(tabu(end),allow(k))^beta;endP=P/sum(P);

%轮盘赌法选择下一个访问城市Pc=cumsum(P);target_index=find(Pc>=rand);target=allow(target_index(1));Table(i,j)=target;endend2.3基本蚁群优化算法

智能优化计算

%计算各个蚂蚁的路径距离Length=zeros(m,1);fori=1:mRoute=Table(i,:);forj=1:(n-1)Length(i)=Length(i)+D(Route(j),Route(j+1));endLength(i)=Length(i)+D(Route(n),Route(1));end2.3基本蚁群优化算法

智能优化计算

%计算最短路径距离及平均距离ifiter==1[min_Length,min_index]=min(Length);Length_best(iter)=min_Length;Length_ave(iter)=mean(Length);Route_best(iter,:)=Table(min_index,:);else[min_Length,min_index]=min(Length);Length_best(iter)=min(Length_best(iter-1),min_Length);Length_ave(iter)=mean(Length);ifLength_best(iter)==min_LengthRoute_best(iter,:)=Table(min_index,:);elseRoute_best(iter,:)=Route_best((iter-1),:);endend2.3基本蚁群优化算法

智能优化计算

%更新信息素Delta_Tau=zeros(n,n);

%逐个蚂蚁计算fori=1:m

%逐个城市计算forj=1:(n-1)Delta_Tau(Table(i,j),Table(i,j+1))=Delta_Tau(Table(i,j),Table(i,j+1))+Q/Length(i);endDelta_Tau(Table(i,n),Table(i,1))=Delta_Tau(Table(i,n),Table(i,1))+Q/Length(i);endTau=(1-rho)*Tau+Delta_Tau;2.3基本蚁群优化算法

智能优化计算运行结果

2.3.1蚂蚁系统的模型与实现2.3基本蚁群优化算法

智能优化计算运行结果

2.3.1蚂蚁系统的模型与实现2.3基本蚁群优化算法

智能优化计算运行结果

2.3.1蚂蚁系统的模型与实现2.3基本蚁群优化算法

智能优化计算运行结果

2.3.1蚂蚁系统的模型与实现2.3基本蚁群优化算法

智能优化计算运行结果

2.3.1蚂蚁系统的模型与实现2.3基本蚁群优化算法

智能优化计算运行结果

2.3.1蚂蚁系统的模型与实现智能优化计算三种模型

ant-cycle：（蚁周）

ant-quantity：（蚁量）

ant-density:

（蚁密）

2.3基本蚁群优化算法2.3.1蚂蚁系统的模型与实现智能优化计算三种模型在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素（局部信息），而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后（全局信息）才对信息素进行更新。2.3基本蚁群优化算法2.3.1蚂蚁系统的模型与实现智能优化计算三种模型的比较模型ant-density,ant-quantity,ant-cycle的比较(M.Dorigo,1996)2.3基本蚁群优化算法2.3.1蚂蚁系统的模型与实现模型参数集最好参数集平均结果最好结果ant-densityα＝1,β=5,ρ=0.01426.740424.635ant-quantityα＝1,β=5,ρ=0.01427.315426.255☻ant-cycleα＝1,β=5,ρ=0.5424.250423.741智能优化计算信息素的分布

2.3基本蚁群优化算法2.3.2蚂蚁系统的参数设置和基本属性智能优化计算信息素的分布

蒸发系数的影响：

2.3基本蚁群优化算法2.3.2蚂蚁系统的参数设置和基本属性ρ＝0.05ρ＝0.95智能优化计算参数α、β对算法性能的影响

停滞现象（Stagnationbehavior）：所有蚂蚁都选择相同的路径，即系统不再搜索更好的解。原因在于较好路径上的信息素远大于其他边上的，从而使所有蚂蚁都选择该路径。

2.3基本蚁群优化算法2.3.2蚂蚁系统的参数设置和基本属性智能优化计算参数α、β对算法性能的影响

α取较大值时，意味着在选择路径时，路径上的信息素非常重要；当α取较小值时，变成随机的贪婪算法。2.3基本蚁群优化算法2.3.2蚂蚁系统的参数设置和基本属性智能优化计算参数α、β对算法性能的影响

α＝0，蚂蚁之间无协同作用；α＝1，有协同作用2.3基本蚁群优化算法2.3.2蚂蚁系统的参数设置和基本属性α＝0α＝1智能优化计算蚂蚁数m对算法的影响

m≈n时，ant-cycle可以在最少迭代次数内找到最优解。

2.3基本蚁群优化算法2.3.2蚂蚁系统的参数设置和基本属性m＝15m＝150m＝30智能优化计算蚂蚁的初始分布

两种情况实验：（1）所有蚂蚁初始时刻放在同一城市；（2）蚂蚁分布在不同城市中。第（2）中情况可获得较高性能。（3）在不同城市分布时，随机分布与统一分布的差别不大。

2.3基本蚁群优化算法2.3.2蚂蚁系统的参数设置和基本属性智能优化计算优点

较强的鲁棒性；分布式计算；易于与其他方法结合。缺点

搜索时间较长；容易出现停滞现象。2.4改进的蚁群优化算法2.4.1蚂蚁系统的优点与不足智能优化计算最优解保留策略（AntSystemwithElitist,ASelite）

每次迭代完成后，对全局最优解更进一步地进行利用；信息素更新策略

σ为最优蚂蚁数，Lgb为全局最优解。2.4改进的蚁群优化算法2.4.2最优解保留策略蚂蚁系统智能优化计算最优解保留策略（AntSystemwithElitist,ASelite）

该策略能够以更快的速度获得最好解，但是如果选择的精英过多则算法会由于较早收敛于局部次优解而导致搜索的过早停滞。2.4改进的蚁群优化算法2.4.2最优解保留策略蚂蚁系统智能优化计算蚁群系统（AntColonySystem,ACS）的改进之处

（1）在选择下一城市时，更多地利用了当前最好解；（2）只在全局最优解所属边上增加信息素；（3）每次蚂蚁从城市i转移到城市j时，边ij

上的信息素将会适当减少，从而实现一种信息素的局部调整以减少已选择过的路径再次被选择的概率。2.4改进的蚁群优化算法2.4.3蚁群系统智能优化计算可行解的构造

伪随机比率选择规则：蚂蚁以概率q0（0～1间的常数）移动到最大可能的城市

q为0～1的随机数，S为一随机变量，当q>q0时，S以以下概率来选择：2.4改进的蚁群优化算法2.4.3蚁群系统智能优化计算局部信息素更新

使已选的边对后来的蚂蚁具有较小的影响力，从而使蚂蚁对没有选中的边有更强的探索能力。当蚂蚁从城市i转移到城市j后，边ij上的信息素更新为：其中，τ0为常数，ξ∈(0,1)为可调参数。2.4改进的蚁群优化算法2.4.3蚁群系统智能优化计算全局信息素更新

只针对全局最优解进行更新：

2.4改进的蚁群优化算法2.4.3蚁群系统智能优化计算最大－最小蚂蚁系统（max-minantsystem,MMAS）的改进之处

（1）每次迭代后，只有最优解（最优蚂蚁）所属路径上的信息被更新；（2）为了避免过早收敛，将各条路径可能的信息素限制于[τmin

,τmax]；（3）初始时刻，各路径上信息素设置为τmax

，在算法初始时刻，ρ取较小值时算法有更好的发现较好解的能力。2.4改进的蚁群优化算法2.4.4最大－最小蚂蚁系统智能优化计算信息素的全局更新

使所有蚂蚁完成一次迭代后，进行信息素更新：

2.4改进的蚁群优化算法2.4.4最大－最小蚂蚁系统智能优化计算基于排序的蚂蚁系统（rank-basedversionofantsystem,ASrank）

每次迭代完成后，蚂蚁所经路径按从小到大的顺序排列，并对它们赋予不同权值，路径越短权值越大。全局最优解权值为w，第r个最优解的权值为max{0,w-r}。2.4改进的蚁群优化算法2.4.5基于排序的蚂蚁系统智能优化计算基于排序的蚂蚁系统（rank-basedversionofantsystem,ASrank）

信息素更新：2.4改进的蚁群优化算法2.4.5基于排序的蚂蚁系统智能优化计算优化结果比较

对对称TSP各迭代10000次，对非对称TSP各迭代20000次：2.4改进的蚁群优化算法2.4.6各种蚁群优化算法的比较TSP实例MMASACSASeliteASEil51.tsp427.6428.1428.3437.3kroA100.tsp21320.321420.021522.8322471.4D198.tsp15972.516054.016205.016705.6Lin31842220.242570.043422.845535.2Ry48p.atsp14553.214565.414685.215296.4Ft70.atsp39040.239099.039261.839596.3Kro124p.atsp36773.536857.037510.238733.1Ftv170.atsp2828.82826.52952.43154.5智能优化计算典型应用列表

2.5蚁群优化算法的应用2.5.1典型应用智能优化计算如何应用

用蚁群算法解决数据分类（数据挖掘任务中的一种）的问题：预先定义一组类，然后把数据系中的每一个数据根据该数据的属性，归入这些类中的一个。当数据量很大时，难以人为判别分类。

2.5蚁群优化算法的应用2.5.2医学诊断的数据挖掘智能优化计算如何应用分类的规则：

IF<term1ANDterm2AND…>THEN<class>

每个term是一个三元组（属性、关系符、属性取值）希望在一个规则中使用最少的判别语句，采用蚁群优化算法达到最优的选择。2.5蚁群优化算法的应用2.5.2医学诊断的数据挖掘智能优化计算例：非典型肺炎考虑如下因素：

2.5蚁群优化算法的应用2.5.2医学诊断的数据挖掘属性发热职业胸部阴影流行病学史值（0,1,2,3）（0,1,2）（0,1,2）（0,1,2）说明0：不考虑该属性1：37.5℃以下2：37.5℃～38.5℃3：38.5℃以上0：不考虑该属性1：医务人员2：其他人员0：不考虑该属性1：无2：有0：不考虑该属性1：无2：有智能优化计算例：非典型肺炎结构图：

一个蚂蚁从始点行走至终点，得到一条路径{0,2,1,0}，其对应的规则为

IF（职业＝其他人员）