蚁群算法研究报告

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

i=1:(ceil(m/CityNum))

Randpos=[Randpos,randperm(CityNum)];

end

Tabu(:,1)=(Randpos(1,1:m))';

%三m只蚂蚁按概率函数选择下一座城市，完成各自的周游forj=2:CityNumfori=1:mvisited=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)

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;

endend

if

NC>=2

Tabu(1,:)=R_best(NC-1,:);

end

%四记录本次迭代最正确路线L=zeros(m,1);fori=1:mR=Tabu(i,:);

L(i)=CalDist(dislist,R);

end

L_best(NC)=min(L);

pos=find(L==L_be