蚁群算法的原理与应用

1、蚁群算法的原理与运用摘要：意大利学者通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法蚁群算法。该算法已经 在组合优化、函数优化、系统辨识、网络路由、机器人路径规划等领域获得了广泛应用，并取得了较好结 果。本文围绕蚁群算法的原理、理论及其应用，就TSP（旅行商问题X以及OPP（最优路径问题）在matlab 中进行仿真并分析其结果。关键词：蚁群算法；旅行商问题；最短路径问题；仿真Abstract:A population-based simulated evolutionary algorithm called ant colony algorithm（ACA for short）was pr

2、oposed by Italian researchers. The algorithm has been widely applied to the fields of combinatorial optimization , function optimization, system identification, network routing, path planning of robot, good effects of application are gained. This paper focuses on the principles, theory, and applicat

3、ion of ACA, trying to solve the the traveling salesman problem and the optimal path problems by simulating in matlab to analyze the result.Keywords: ant colony algorithm; traveling salesman problem; shortest path problem ; simulation1绪论1.1引言各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物 以后，它会向环境释放一种挥发性分泌物ph

4、eromone （称为信息素，该物质随着时间的推移 会逐渐挥发消失，信息素浓度的大小表征路径的远近）来实现的，吸引其他的蚂蚁过来，这 样越来越多的蚂蚁会找到食物。有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另 辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这 条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复 着。蚂蚁究竟是怎么找到食物的呢？在没有蚂蚁找到食物的时候，环境没有有用的信息素， 那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息 素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得

5、蚂蚁尽量向前方移动（开始， 这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定 的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的 干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试 探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境 的障碍物让蚂蚁的某个方向正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的 诸如迷宫的地图中仍然能找到隐蔽得很好的食物。当然，在有一只蚂蚁找到了食物的时候，大部分蚂蚁会沿着信息素很快找到食物的。但 不排除会出现这样的情况：在最初的时候，一

6、部分蚂蚁通过随机选择了同一条路径，随着这 条路径上蚂蚁释放的信息素越来越多，更多的蚂蚁也选择这条路径，但这条路径并不是最优 （即最短）的，所以，导致了迭代次数完成后，蚂蚁找到的不是最优解，而是次优解，这种 情况下的结果可能对实际应用的意义就不大了。蚂蚁如何找到最短路径的？这一是要归功于信息素，另外要归功于环境，具体说是计算 机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有 两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多(或者较长的路上蚂蚁多， 这也无关紧要)。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一 次的时间就短，这也意味着重

7、复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下 的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素；而长 的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。也 许有人会问局部最短路径和全局最短路的问题，实际上蚂蚁逐渐接近全局最短路的，为什么 呢？这源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径， 这可以理解为一种创新，这种创新如果能缩短路途，那么根据刚才叙述的原理，更多的蚂蚁 会被吸引过来。1.2蚁群算法的基本原理蚁群算法是受自然界中真实蚁群算法的集体觅食行为的启发而发展起来的一种基于群 体的模拟进化算法，属于随

8、机搜索算法，所以它更恰当的名字应该叫人工蚁群算法，我们一般 简称为蚁群算法，至于人工蚁群和真实蚁群的区别,双桥实验里面所显示的那样，蚂蚁这种社 会性动物,虽然个体行为及其简单，但是由这些简单个体所组成的群体却表现出及其复杂的 行为特征。这是因为蚂蚁在寻找食物时，能在其经过的路径上释放一种叫做信息素的物质， 使得一定范围内的其他蚂蚁能够感觉到这种物质，且倾向于朝着该物质强度高的方向移动。 蚁群的集体行为表现为一种正反馈现象，蚁群这种选择路径的行为过程称之为自催化行为， 由于其原理是一种正反馈机制，因此也可以把蚁群的行为理解成所谓的增强型学习系统 (Reinforcement Learning s

9、ystem)下面引用M.Dorigo所举的例子来说明蚁群发现最短路径的 原理和机制，见图1所示。假设D和H之间、B和H之间以及B和D之间通过C的距离为 1, C位于D和B的中央(见图1(a)现在我们考虑在等间隔等离散世界时间点(t=0,1,2.)的 蚁群系统情况。假设每单位时间有30只蚂蚁从A到B,另三十只蚂蚁从E到D,其行走速度 都为1 (一个单位时间所走距离为l),在行走时，一只蚂蚁可在时刻t留下浓度为1的信息素为 简单起见,设信息素在时间区间(t十1,t+2)的中点(t+0.5)时刻瞬时完全挥发。在t=0时刻无 任何信息素，但分别有30只蚂蚁在B、30只蚂蚁在D等待出发。它们选择走哪一条

10、路径是完 全随机的，因此在两个节点上蚁群可各自一分为二，走两个方向。但在t=1时刻，从A到B的 30只蚂蚁在通向H的路径上(见图1 (b)发现一条浓度为巧的信息素，这是由巧只从B走向H 的先行蚂蚁留下来的;而在通向C的路径上它们可以发现一条浓度为30的信息素路径，这是 由巧只走向BC的路径的蚂蚁所留下的气息与15只从D经C到达B留下的气息之和(图 1(C)。这时，选择路径的概率就有了偏差，向C走的蚂蚁数将是向H走的蚂蚁数的2倍。对 于从E到D来的蚂蚁也是如此。这个过程一直会持续到所有的蚂蚁最终都选择了最短的路径为止。这样，我们就可以理 解蚁群算法的基本思想：如果在给定点，一只蚂蚁要在不同的路径

11、中选择，那么，那些被先行 蚂蚁大量选择的路径(也就是信息素留存较浓的路径)被选中的概率就更大，较多的信息素意 味着较短的路径，也就意味着较好的问题回答。(a)Et=0蚁数30蚁数15蚁数15蚁数J5蚁数15蚁数30蚁数10蚁数20蚁数30A(b)蚁群路径搜索实例1.3蚁群算法的算法描述蚁群算法可以看作为一种基于解空间参数化概率分布模型(c)(Parameterized ProbabilisticModel）的搜索算法框架Model 一 based search algorithms）。在蚁算法中，解空间参数化概率, 模型的参数就是信息素，因而这种参数化概率分布模型就是信息素模型。在基于模型的搜

12、索 算法框架中，可行解通过在一个解空间参数化概率分布模型上的搜索产生，此模型的参数用 以前产生的解来更新，使得在新模型上的搜索能够集中在高质量的解搜索空间内这种方法 的有效性建立在高质量的解总是包含好的解构成元素的假设前提下，通过学习这种解构成元 素对解的质量的影响有助于找到一种机制，并通过解构成元素的最佳组合来构造出高质量的 解。一般来说，一个记忆模型的搜索算法通常使用以下两步迭代来解决优化问题：1）可行解通过在解空间参数化概率分布模型上的搜索产生。2）用搜索产生的解来更新参数化概率模型，即更新解空间参数化概率分布的参数，使得 在新模型上的参数搜索能够集中在高质量的解搜索空间内。在蚁群算法中

13、，基于信息素的解 空间参数化概率模型（信息素模型）以解构造图的形式给出。在解构造图上，定义了一种作为 随机搜索机制的人工蚁群，蚂蚁通过一种分布在解构造图上被称为信息素的局部信息的指引, 在解构造图上移动，从而逐步的构造出问题的可行。信息素与解构造图上的节点或弧相关联， 作为解空间参数化概率分布模型的参数。由于TSP问题可以直接的映射为解构造图（城市为 节点，城市间的路径为弧，信息素分布在弧上），加之TSP问题也是个NP难题，所以，蚁群算 法的大部分应用都集中在TSP问题上。一般而言用于求解TSP问题、生产调度问题等优化 问题的蚁群算法都遵循下面的统一算法框架。1.4蚁群算法的特点从蚁群算法的原

14、理不难看出，蚁群的觅食行为实际上是一种分布式的协同优化机制。单 只蚂蚁虽然能够找到从蚁穴到食物源的一条路径，但是找到最短路径的可能性极小，只有当 多只蚂蚁组成蚁群时，其集体行为才突现出蚂蚁的智能发现最短路径的能力。在寻找最短路 径的过程中，蚁群使用了一种间接的通信方式，即通过向所经过的路径上释放一定的信息素， 其他蚂蚁通过感知这种物质的强弱来选择下一步要走的路。总的来说，人工蚁群算法的主要 特点可以概括为以下几点：1）采用分布式控制，不存在中心控制；2）每个个体只能感知局部的信息，不能直接使用全局信息；3）个体可以改变环境，并通过环境来进行间接通讯；4）具有自组织性，即群体的复杂行为是通过个体

15、的交互过程中突现出来的智能；5）是一类概率型的全局搜索方法，这种非确定性是算法能够有更多的机会求得全局最优 解；6）其优化过程不依赖于优化问题本身的严格数学性质，比如连续性、可导性以及目标函 数和约束函数的精确数学描述；7）是一种基于多主体（Multi Agent）的智能算法，各主体之间通过相互协作来更好的适应 环境；8）具有潜在的并行性，其搜索过程不是从一点出发，而是同时从多个点同时进行。这种 分布式多智能体的协作过程是异步并发进行的，分布并行模式将大大提高整个算法的运行效 率和快速反应能力。1.5蚁群算法的研究现状1991年,意大利学者M.Dorigo等提出了第一个蚁群算法一蚂蚁系统（AS

16、）并成功的应用 于求解TSP问题。实验结果证明AS算法具有较强的鲁棒性和发现较好的解的能力,但与此 同时也存在着一些缺陷,如收敛速度慢、易出现停滞现象等。该算法的问世引起了学者们的 普遍关注，并且针对AS算法的缺点，提出了一些改进的蚁群算法。L.M.Gambardella,M.Dorig 提出了 Ant 一 Q算法,该算法用伪随机比例状态转移规则(Pseudo random proportional state transition rule)替换 AS 算法中的随机比例转移规则(Stochastic proportional choice rule),从而 使Ant 一 Q算法在构造解的过程

17、中能够更好的保持知识探索(Exploration)与知识利用 (Exploitation)之间的平衡。除此之外，该算法中还引用了局部信息素更新机制和全局信息素 更新中的精英策略。国内对蚁群算法的研究直到上世纪末才拉开序幕，目前国内学者对蚁群算法的研究主要 是集中在算法的改进和应用上。吴庆洪和张纪会等通过向基本蚁群算法中引入变异机制，充 分利用2交换法简洁高效的特点，提出了具有变异特征的蚁群算法。吴斌和史忠植首先在蚁 群算法的基础上提出了相遇算法,提高了蚂蚁一次周游的质量，然后将相遇算法与采用并行 策略的分段算法相结合，提出一种基于蚁群算法的TSP问题分段求解算法。王颖和谢剑英通 过自适应的改变

18、算法的挥发度等系数,提出一种自适应的蚁群算法以克服陷于局部最小的缺 点。覃刚力和杨家本根据人工蚂蚁所获得的解的情况动态地调整路径上的信息素，提出了自 适应调整信息素的蚁群算法。蚁群算法的应用研究一直非常活跃。继 M.Dorig首先将AS算法用于TSP问题之 后,V.Maniezz等人首先将 AS算法应用于指派问题(Quadratic Assignment Problem,简称 QAP).最近几年,Gambardella, Thailard和Stutzle等也发表了 一些用蚁群算法求解QAP问题 的文章。目前，蚁群算法是求解QAP问题最有效的算法之一。2对蚁群算法的改进与应用范围2.1对蚁群算法

19、的改进虽然传统的蚁群算法具有很强的全局寻优解的能力。但也存在一些缺陷，例如:该算法 的搜索时间过长,大部分计算时间被用于解的构造;在执行过程中容易出现停滞现象,当问题 规模较大时存在陷人局部最优的可能性等。因此，研究者对传统的蚁群算法进行了很多改进 研究。下面介绍两种有代表性的改进方法。最大最小蚁群系统 最大最小蚁群系统(Max 一 Min Ant System,MMAS)是德国学者 T.Stuetzle和H.Hoos提出的，是最具有贪婪式寻优特征的改进蚁群算法，目的在于防止过早 的算法停滞现象。如果信息素过度集中到几条较好的路径上，而其他路径由于长时间没有 蚂蚁经过,信息素逐渐挥发并趋近于零

20、，那么这些路径就最终不再有蚂蚁经过。这种情况下, 有可能丧失寻求最佳路径的机会，此时就出现停滞的现象。MMAS就是针对这种现象,对算法中信息素的浓度引人最大值和最小值限制:当某条路径 上的信息素浓度大于所设定的上限，则强制其为上限值相反，则令其为下限值。通过设定信息 素的上下限，一方面避免了某条路径上的信息素浓度远大于其它路径的信息素浓度从而有 效降低了过早停滞的可能。另一方面，不会因为某些路径的信息素浓度过低而丧失发现新路 径的可能。有研究实验表明,对于要求迭代次数较多的问题求解过程,MMAS算法与传统的蚁 群算法相比，在寻找解的有效性方面和防止算法的过早停滞方面具有更好的效果。但是，需要

21、说明的是，仅采用最大最小信息素浓度的限制还不足以在较长的时间里持久消除停滞现象 因此，可以对其进行进一步改进，例如，在该算法中引人信息素的平滑机制等。动态蚁群算法与传统的蚁群算法相比，动态蚁群算法的改进主要如下：在应用于求解旅行商问题时，传统的蚁群算法是据信息素和启发函数来选择目标城市的, 这两个因子对路径选择的影响力度是固定的。而动态蚁群算法在迭代过程中，选择目标城市 时引人动态因子。在传统的蚁群算法中，对信息素的强度没有限制，其挥发因子是一个常数,因而有陷人局 部最优的可能。而动态蚁群算法中设置动态变化的挥发因子，信息素浓度越高,则挥发因子越 大;浓度越低,挥发因子越小。通过限制，信息素的

22、浓度不可能无限增大，也不可能为零。这样，由于目标城市的动态选择和信息素挥发因子的动态性，动态蚁群算法有力地减少 进化停滞现象。2.2蚁群算法的应用蚁群算法能够将问题求解的快速性、全 优化特性和有限时间内答案的合理性结合起来， 因此对于能够直接转化为路径优化问题的组合类寻优问题能取得比较理想的效果。大规模集成电路的线网布局在大规模集成电路的线网布局中，需要根据电路和工艺 的要求完成芯片上单元或功能模块的布局，然后实现它们之间的互连。此问题可看作是寻找 一个网格平面上两端点之间绕过障碍的最短路径问题。线网上的每个Agent根据启发策略， 像蚂蚁一样在开关盒网格上爬行，所经之处便设置一条金属线,历经

23、一个线网的所有引脚之 后，线网便布通了。应用蚁群算法，可以找到成本最低、最合理的线网布局，而且由于其本身 的并行性,比较适合于解决此类问题。通信网络路由 近年来，许多学者将蚁群算法应用于通讯领域,特别是通信网络中的 路由问题。通网络的路由是通过路由表进行的,在每个节点的由表中，对每个目的节点都列 出了与该节点相连的节点，当有数据包到达时，通过查询路由表可知下一个将要到达的节 点。网络信息的分布性、动态性、随机性和异步性与蚁群算法非常相似，都是利用局部信息 发现解，间接通讯方式和随机状态的转换。Dorigo.Di Caro和Gambardella首先将蚁群算 法应用于网络路由问题，并称这种算法为

24、Ant Net。蚁群算法在电力系统中的应用 电力系统优化是一个复杂的系统工程，它包括无功优 化、经济负荷分配、电网优化及机组最优投人等一系列问题其中很多是高维、非凸、非线 性的优化问题。其中，机组最优投人问题是寻求一个周期内各个负荷水平下机组的最优组合 方式及开停机计划，使运行费用最小。利用状态、决策及路径概念。将机组最优投人问题设 计成类似旅行商问题的模式，从而可方便地利用蚁群算法来求解。还有人将蚁群算法编人水 力发电规划能源管理软件，可很好地节约能源。此外，对于电力系统中的故障检测，蚁群算 法也表现出较好的应用前景。由于故障地点的估计信息来自保护继电器和电路断路器，那么 对所有故障部分的估

25、计可以看作是一个组合优化问题。3蚁群算法在RPP问题中的应用3.1什么是RPP问题路径规划问题(Routing Planning Problems, RPP)在航线设计、管道铺设和改善城市交 通等现实应用中有着十分重要的作用。根据不同的限制条件和求解要求，RPP问题又可以细 分为最优路径问题(Optimal Path Problems，OPP)、旅行商问题(Travelling Salesman Problem， TSP)以及带时间窗的旅行商问题(Travelling Salesman Problem with Time Windows TSPTW) 等多个子问题。分类如图2所示：路径规划问题

26、(RPP)单目怀点务目标点单车辆求解 多车辆求衅炒仇 典旅行商问题带时间窗-限制的车辆路径问题带时间窗限制的(OPP)(TSP)旅行商问袈(VRP)车辆路径问题 (TSPTW) (VRPTW)图2路径规划问题分类3.2 TSP问题3.2.1 TSP问题的描述给定n个城市的集合0，1，2,，n-1及城市之间环游的花费Cij (0WiWn-1, 0WjWn-1, i尹j)。TSP问题是指找到一条经过每个城市一次且回到起点的 最小花费的环游。若将每个顶点看成是图上的节点，花费Cij为连接顶点Vi、Vj边上的权， 则TSP问题就是在一个具有n个节点的完全图上找到一条花费最小的Hamilton回路。蚁群

27、算法求解TSP问题的流程 步骤1:nc=0(nc为迭代步数或搜索次数)；每条边上 的Tj(0)=c(常数)，并且ATj=0 ；放置m个蚂蚁到n个城市上。步骤2:将各蚂蚁的初始出 发点置于当前解集TABUk(s)中;对每个蚂蚁k(k=1,.,m)，按概率Pij(t)移至下一城市j；将 城市j置于TABUk(s)中。步骤3:经过n个时刻，蚂蚁k可走完所有的城市，完成一次循 环。计算每个蚂蚁走过的总路径长度Lk，更新找到的最短路径。步骤4:更新每条边上的 信息量Tij(t+n)。步骤5:对每一条边置ATijuO； nc=nc+1。步骤6:若nc预定的迭代次数 Ncmax，则转步骤2；否则，打印出最短

28、路径，终止整个程序。蚁群算法求解TSP问题的源代码clear all close allclc%初始化蚁群m=31;%蚁群中蚂蚁的数量，当m接近或等于城市个数n时，本算法可以在最少的迭代次数 内找到最优解C=1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;4196 1004; 4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;1332 695;3715 1678; 3918 2179;4061 2370;3780 2212;3676 25

29、78;4029 2838;4263 2931;3429 1908;3507 2367; 3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975;% 城市的坐标矩阵Nc_max=200;%最大循环次数，即算法迭代的次数，亦即蚂蚁出动的拨数(每拨蚂蚁的数量 当然都是m)alpha=1;%蚂蚁在运动过程中所积累信息(即信息素)在蚂蚁选择路径时的相对重要程度， alpha过大时，算法迭代到一定代数后将出现停滞现象beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度rho=0.5;%0rho1,表示路径上信息素的衰减

30、系数(亦称挥发系数、蒸发系数)，1-rho表示信 息素的持久性系数Q=100;%蚂蚁释放的信息素量，对本算法的性能影响不大%变量初始化n=size(C,1);%表示TSP问题的规模，亦即城市的数量D=ones(n,n);%表示城市完全地图的赋权邻接矩阵，记录城市之间的距离for i=1:nfor j=1:nif ijD(i,j)=sqrt(C(i,1)-C(j,1)A2+(C(i,2)-C(j,2)A2);endD(j,i)=D(i,j);endendeta=1./D;%启发式因子，这里设为城市之间距离的倒数pheromone=ones(n,n);%信息素矩阵，这里假设任何两个城市之间路径上的

31、初始信息素都为1 tabu_list=zeros(m,n);%禁忌表，记录蚂蚁已经走过的城市，蚂蚁在本次循环中不能再经过这 些城市。当本次循环结束后，禁忌表被用来计算蚂蚁当前所建立的解决方案，即经过的路径 和路径的长度Nc=0;%循环次数计数器routh_best=zeros(Nc_max,n);% 各次循环的最短路径length_best=ones(Nc_max,1);%各次循环最短路径的长度length_average=ones(Nc_max,1);%各次循环所有路径的平均长度while Ncq0for k=1:length(city_remained)probability(k)=(ph

32、eromone(city_visited(end),city_remained(k)Aalpha*(eta(city_visited(end),city _remained(k)Abeta;position=find(probability=max(probability);to_visit=city_remained(position(1);endelsefor k=1:length(city_remained)probability(k)=(pheromone(city_visited(end),city_remained(k)Aalpha*(eta(city_visited(end),c

33、ity _remained(k)Abeta;endprobability=probability/sum(probability);pcum=cumsum(probability);select=find(pcum=rand);to_visit=city_remained(select(1);end tabu_list(i,j)=to_visit;rvf “%*endendif Nc0tabu_list(1,:)=routh_best(Nc,:);%将上一代的最优路径(最优解)保留下来，保证上 一代中的最适应个体的信息不会丢失end%记录本次循环的最佳路线total_length=zeros(

34、m,1);%m只蚂蚁在本次循环中分别所走过的路径长度for i=1:mr=tabu_list(i,:);%取出第i只蚂蚁在本次循环中所走的路径for j=1:(n-1)total_length(i)=total_length(i)+D(r(j),r(j+1);%第 i 只蚂蚁本次循环中从起点城市 到终点城市所走过的路径长度endtotal_length(i)=total_length(i)+D(r(1),r(n);%最终得到第 i 只蚂蚁在本次循环中所走 过的路径长度endlength_best(Nc+1)=min(total_length);%把m只蚂蚁在本次循环中所走路径长度的最小值 作为

35、本次循环中最短路径的长度position=find(total_length=length_best(Nc+1);%找 到最短路径的位置，即最短路径是第 几只蚂蚁或哪几只蚂蚁走出来的routh_best(Nc+1,:)=tabu_list(position (1),:);%把第一个走出最短路径的蚂蚁在本次循环中 所走的路径作为本次循环中的最优路径length_average(Nc+1)=mean(total_length);%计算本次循环中m只蚂蚁所走路径的平均长 度Nc=Nc+1%更新信息素delta_pheromone=zeros(n,n);for i=1:mfor j=1:(n-1)de

36、lta_pheromone(tabu_list(i,j),tabu_list(i,j+1)=delta_pheromone(tabu_list(i,j),tabu_list(i,j+1)+Q /total_length(i);%total_length(i)为第i只蚂蚁在本次循环中所走过的路径长度(蚁周系统区别 于蚁密系统和蚁量系统的地方)enddelta_pheromone(tabu_list(i,n),tabu_list(i,1)=delta_pheromone(tabu_list(i,n),tabu_list(i,1)+Q/tot al_length(i);%至此把第i只蚂蚁在本次循环中

37、在所有路径上释放的信息素已经累加上去end%至此把m只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去pheromone=(1-rho).*pheromone+delta_pheromone;%本 次循环后所有路径上的信息素%禁忌表清零，准备下一次循环，蚂蚁在下一次循环中又可以自由地进行选择 tabu_list=zeros(m,n);end%输出结果，绘制图形position=find(length_best=min(length_best);shortest_path=routh_best(position(1),:)shortest_length=length_best(positio

38、n(1)%绘制最短路径figure(1)set(gcf,Name,Ant Colony OptimizationFigure of shortest_path,Color,r)N=length(shortest_path);scatter(C(:,1),C(:,2),50,filled);hold onplot(C(shortest_path(1),1),C(shortest_path(N),1),C(shortest_path(1),2),C(shortest_path(N),2)set(gca,Color,g)hold onfor i=2:Nplot(C(shortest_path(i-1

39、),1),C(shortest_path(i),1),C(shortest_path(i-1),2),C(shortest_path(i),2)hold onend%绘制每次循环最短路径长度和平均路径长度figure(2)set(gcf,Name,Ant Colony OptimizationFigure of length_best and length_average,Color,r)plot(length_best,r)set(gca,Color,g)hold onplot(length_average,k)运行结果(a)(b)(c)图3运行结果图3 （a）显示31个城市最短路径的走法；

40、图3 （b）显示每次搜索时的单次路径长度的平 均值（上面的曲线）以及全局最短路径（下面的曲线）；图3（c）显示最短路径为15772。3.3 OPP问题3.3.1 OPP问题的描述 OPP问题是以一个事先指定好的节点为目标，蚂蚁只需要到达该目 标即算一次搜索完成（如图4所示）。但是蚂蚁又无法忽略掉全部的“无用”节点，它必然要 途径一些节点作为过渡才能到达目标节点。因此在OPP问题的路网中，对蚂蚁而言存在着目 标节点（黑色节点）、过渡节点（灰色节点）以及“无用”节点（白色节点）而如何让蚂蚁 能够清楚地分辨出三种节点之间的区别，是提高算法效率，提升最终解质量的关键所在。图4最优路径问题示意图蚁群算法

41、求解OPP问题的流程 当以用时最少，即最快到达目的地点为求解目标 时，OPP问题可描述为：设有N个节点C=C1,C2,C3Cn，现任意选取一个出发点Co 和一个目标点Cd，(Co, CdC)，求一条以Co为起点，Cd为终点的通路 Co, C1,C2, Cd，使得该通路的刃tR,匕2)为最小，其中d为该通路所包含的节点个数，t(Ck-1,Ck)为从节 k-1点Ck-1至节点Ck所花费的时间。蚁群算法求解OPP问题的源代码function varargout = antinface(varargin)% ANTINFACE M-file for antinface.fig% ANTINFACE,

42、by itself, creates a new ANTINFACE or raises the existing% singleton*.% H = ANTINFACE returns the handle to a new ANTINFACE or the handle to %the existing singleton*.%ANTINFACE(CALLBACK,hObject,eventData,handles,.) calls the local% function named CALLBACK in ANTINFACE.M with the given input argument

43、s.% ANTINFACE(Property,Value,.) creates a new ANTINFACE or raises the% existing singleton*. Starting from the left, property value pairs are% applied to the GUI before antinface_OpeningFcn gets called. An% unrecognized property name or invalid value makes property application% stop. All inputs are p

44、assed to antinface_OpeningFcn via varargin.% *See GUI Options on GUIDEs Tools menu. Choose GUI allows only one% instance to run (singleton).% See also: GUIDE, GUIDATA, GUIHANDLES% Edit the above text to modify the response to help antinface% Last Modified by GUIDE v2.5 02-Jun-2008 10:29:35% Begin in

45、itialization code - DO NOT EDITgui_Singleton = 1;gui_State = struct(gui_Name, mfilename, .gui_Singleton, gui_Singleton, .gui_OpeningFcn, antinface_OpeningFcn, .gui_OutputFcn, antinface_OutputFcn, .gui_LayoutFcn,.gui_Callback, );if nargin & ischar(varargin1)gui_State.gui_Callback = str2func(varargin1

46、);endif nargoutvarargout1:nargout = gui_mainfcn(gui_State, varargin:);elsegui_mainfcn(gui_State, varargin:);end% End initialization code - DO NOT EDIT% - Executes just before antinface is made visible.function antinface_OpeningFcn(hObject, eventdata, handles, varargin)% This function has no output a

47、rgs, see OutputFcn.% hObject handle to figure% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user state (see GUIDATA)% varargin command line arguments to antinface (see VARARGIN)% Choose default command line output for antinface handles.output =

48、 hObject;% Update handles structureguidata(hObject, handles);h=waitbar(0,请等待.);for i=1:100waitbar(i/100);enddelete(h);% UIWAIT makes antinface wait for user response (see UIRESUME) % uiwait(handles.handles);% - Outputs from this function are returned to the command line. function varargout = antinfa

49、ce_OutputFcn(hObject, eventdata, handles) % varargout cell array for returning output args (see VARARGOUT);% hObject handle to figure% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user state (see GUIDATA)% Get default command line output from h

50、andles structure varargout1 = handles.output;function edit_initao_Callback(hObject, eventdata, handles)% hObject handle to edit_initao (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user state (see GUIDATA)% Hints: get(hObject,String)

51、 returns contents of edit_initao as text%str2double(get(hObject,String) returns contents of edit_initao as a double% - Executes during object creation, after setting all properties.function edit_initao_CreateFcn(hObject, eventdata, handles)% hObject handle to edit_initao (see GCBO)% eventdata reserv

52、ed - to be defined in a future version of MATLAB% handles empty - handles not created until after all CreateFcns called% Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc & isequal(get(hObject,BackgroundColor), get(0,defaultUicontrolBackgroundColor) set(h

53、Object,BackgroundColor,white);end function edit_q_Callback(hObject, eventdata, handles)% hObject handle to edit_q (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user state (see GUIDATA)% Hints: get(hObject,String) returns contents of

54、edit_q as text%str2double(get(hObject,String) returns contents of edit_q as a double% - Executes during object creation, after setting all properties.function edit_q_CreateFcn(hObject, eventdata, handles)% hObject handle to edit_q (see GCBO)% eventdata reserved - to be defined in a future version of

55、 MATLAB% handles empty - handles not created until after all CreateFcns called% Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc & isequal(get(hObject,BackgroundColor), get(0,defaultUicontrolBackgroundColor) set(hObject,BackgroundColor,white);end functio

56、n edit_alpha_Callback(hObject, eventdata, handles)% hObject handle to edit_alpha (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user state (see GUIDATA)% Hints: get(hObject,String) returns contents of edit_alpha as text%str2double(get

57、(hObject,String) returns contents of edit_alpha as a double% - Executes during object creation, after setting all properties.function edit_alpha_CreateFcn(hObject, eventdata, handles)% hObject handle to edit_alpha (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles

58、empty - handles not created until after all CreateFcns called% Hint: edit controls usually have a white background on Windows.% See ISPC and COMPUTER.if ispc & isequal(get(hObject,BackgroundColor), get(0,defaultUicontrolBackgroundColor) set(hObject,BackgroundColor,white);end function edit_rou_Callba

59、ck(hObject, eventdata, handles)% hObject handle to edit_rou (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles structure with handles and user state (see GUIDATA)% Hints: get(hObject,String) returns contents of edit_rou as text%str2double(get(hObject,String) return

60、s contents of edit_rou as a double% - Executes during object creation, after setting all properties.function edit_rou_CreateFcn(hObject, eventdata, handles)% hObject handle to edit_rou (see GCBO)% eventdata reserved - to be defined in a future version of MATLAB% handles empty - handles not created u