蚁群算法及案例分析.pptx
蚁群算法及案例分析蚁群算法及案例分析目 录目 录l蚁群算法原理蚁群算法原理l蚁蚁群算法计算步骤群算法计算步骤lTSPTSP算算例分析例分析l蚁群算法的特点及应用领域蚁群算法的特点及应用领域l 蚁群算法原理蚁群算法原理1、蚂蚁在路径上释放信息素信息素。2、碰到还没走过的路口，就随机挑选一条路走。同时，释放与路径长度有关的信息素。3、信息素浓度与路径长度成反比反比。后来的蚂蚁再次碰到该路口时，就选择信息素浓度较高路径。4、最优路径上的信息素浓度越来越大5、最终蚁群找到最优寻食路径最优寻食路径。自然界中,蚁群的这种寻找路径的过程表现为一种正反馈正反馈的过程,与人工蚁群的寻优算法极为一致。如我们把只具备了简单功能的工作单元视为”蚂蚁”,那么上述寻找路径的过程可以用于解释人工蚁群的寻优过程。人工蚁群人工蚁群具有一定的记忆能力。它能够记忆已经访问过的节点;另外,人工蚁群在选择下一条路径的时候并不是完全盲目的,而是按一定的算法规律有意识地寻找最短路径自然界蚁群自然界蚁群不具有记忆的能力，它们的选路凭借外激素，或者道路的残留信息来选择，更多地体现正反馈的过程人工蚁群和自然界蚁群的相似之处在于,两者优先选择的都是含“外激素”浓度较大的路径; 两者的工作单元(蚂蚁)都是通过在其所经过的路径上留下一定信息的方法进行间接的信息传递。l 蚁群算法原理蚁群算法原理开始初始化迭代次数Nc=Nc+1蚂蚁k=1蚂蚁k=k+1按照状态转移概率公式选择下一个元素修改禁忌表K=蚂蚁总数m？按照公式进行信息量更新满足结束条件？输出程序计算结果结束YYNNl 蚁群算法计算步骤蚁群算法计算步骤l TSPTSP算例分析算例分析给定n个城市和两个两个城市之间的距离，要求确定一条经过各个城市一次当且仅当一次的最短路径。旅行商问题（旅行商问题（TSPTSP）第一第一步步: :初始化初始化将m只蚂蚁随机放到n个城市，每只蚂蚁的禁忌表为蚂蚁当前所在城市，各边信息初始化为c。禁忌表体现了人工蚂蚁的记忆性，使得蚂蚁不会走重复道路，提高了效率。l TSPTSP算例分析算例分析l TSPTSP算例分析算例分析l TSPTSP算例分析算例分析第四步：输出结果第四步：输出结果若迭代次数小于预定的迭代次数且无退化行为（找到的都是相同的解）则转步骤二，否则，输出目前的最优解。参参 数数选选 取取l TSPTSP算例分析算例分析% 第一步：变量初始化n=size(C,1); %n表示问题的规模（城市个数）D=zeros(n,n); %D表示完全图的赋权邻接矩阵for i=1:nfor j=1:nif i=jD(i,j)=(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2)0.5; %点i,j之间的距离elseD(i,j)=eps;endD(j,i)=D(i,j);endendEta=1./D; %Eta为启发因子，这里设为距离的倒数Tau=ones(n,n); %Tau为信息素矩阵Tabu=zeros(m,n); %存储并记录路径的生成NC=1; %迭代计数器R_best=zeros(NC_max,n); %各代最佳路线L_best=inf.*ones(NC_max,1);%各代最佳路线的长度L_ave=zeros(NC_max,1); %各代路线的平均长度 while NC=rand);to_visit=J(Select(1);Tabu(i,j)=to_visit;endendif NC=2Tabu(1,:)=R_best(NC-1,:);end%第四步：记录本次迭代最佳路线L=zeros(m,1);for i=1:mR=Tabu(i,:);for j=1:(n-1)L(i)=L(i)+D(R(j),R(j+1);endL(i)=L(i)+D(R(1),R(n);endL_best(NC)=min(L);pos=find(L=L_best(NC);R_best(NC,:)=Tabu(pos(1),:);L_ave(NC)=mean(L);NC=NC+1;%第五步：更新信息素Delta_Tau=zeros(n,n);for i=1:mfor j=1:(n-1)Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i);endDelta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);endTau=(1-Rho).*Tau+Delta_Tau;%第六步：禁忌表清零Tabu=zeros(m,n);end %第七步：输出结果Pos=find(L_best=min(L_best);Shortest_Route=R_best(Pos(1),:);Shortest_Length=L_best(Pos(1);subplot(1,2,1)DrawRoute(C,Shortest_Route)subplot(1,2,2);plot(L_best)hold onplot(L_ave)hold offend子函数：子函数：function DrawRoute(C,R)% 画路线图的子函数% C: 节点坐标，由一个N2的矩阵存储% R: Rout路线N=length(R);scatter(C(:,1),C(:,2);hold onplot(C(R(1),1),C(R(N),1),C(R(1),2),C(R(N),2)hold onfor ii=2:Nplot(C(R(ii-1),1),C(R(ii),1),C(R(ii-1),2),C(R(ii),2)hold onend endl TSPTSP算例分析算例分析100015002000250030003500400045005001000150020002500300035004000 xy最 短 路 线0204060801001201401601802001.51.61.71.81.922.1x 104迭 代 次 数长度最 优 路 线 的 长 度 及 平 均 值Shortest_Length =1.5602e+04l 蚁群算法的特点及应用领域蚁群算法的特点及应用领域蚁群算法的特点优点优点缺点缺点不依赖于所求问题的具体数学表达式描述，具有很强的找到全局最优解的优化能力模型普适性不强，不能直接应用于实际优化问题正反馈、较强的鲁棒性、全局性、普遍性局部搜索能力较弱，易出现停滞和局部收敛、收敛速度慢等问题优良的分布式并行计算机制长时间花费在解的构造上，导致搜索时间过长易于与其他方法相结合算法最先基于离散问题，不能直接解决连续优化问题l 蚁群算法的特点及应用领域蚁群算法的特点及应用领域蚁群算法的应用领域由于蚁群算法对图的对称性以及目标函数无特殊要求，因此可以解决各种对称、非对称问题，线性、非线性问题。旅行商（TSP）问题电力调度问题通信图形着色化工路径优化交通数据挖掘机器人聚类分析冶金网络配置其他领域序列求序其他组合优化问题谢 谢 观 看 ！谢 谢 观 看 ！
