下载文档原格式
蚁群算法的原理及其应用1. 蚁群算法的介绍蚁群算法（Ant Colony Optimization, ACO）是一种启发式优化算法，它模拟了蚂蚁在寻找食物路径时的行为。
蚁群算法通过模拟蚂蚁在信息素的引导下进行行为选择，来寻找最优解。
蚁群算法的核心思想是利用分布式的信息交流和反馈机制来完成问题的求解。
2. 蚁群算法的原理蚁群算法的原理可简述为以下几个步骤：1.创建蚁群：随机生成一定数量的蚂蚁，将其放置在问题的初始状态上。
2.信息素初始化：对于每条路径，初始化其上的信息素浓度。
3.蚂蚁的移动：每只蚂蚁根据一定的规则，在解空间中移动，并根据路径上的信息素浓度决定移动的方向。
4.信息素更新：每只蚂蚁在移动到目标位置后，根据路径的质量调整经过路径上的信息素浓度。
5.更新最优路径：记录当前找到的最优路径，并更新全局最优路径。
6.蚂蚁迭代：重复进行2-5步骤，直到满足终止条件。
3. 蚁群算法的应用蚁群算法被广泛应用于许多优化问题的求解，特别是在组合优化、路径规划、图着色等领域。
3.1 组合优化问题蚁群算法在组合优化问题中的应用主要包括旅行商问题（TSP）、背包问题（KP）、调度问题等。
通过模拟蚂蚁的移动和信息素的更新，蚁群算法可以找到全局最优解或接近最优解的解决方案。
3.2 路径规划问题在路径规划问题中，蚁群算法常被用于解决无人车、无人机等的最优路径规划。
蚁群算法能够在搜索空间中寻找最短路径，并考虑到交通拥堵等实际情况，提供合适的路径方案。
3.3 图着色问题蚁群算法可以用于解决图着色问题，即给定一个图，用尽可能少的颜色对其顶点进行着色，使得相邻顶点的颜色不同。
蚁群算法通过模拟蚂蚁的移动和信息素的更新，能够找到一种较好的图着色方案。
4. 蚁群算法的优缺点4.1 优点•收敛性好：蚁群算法能够在相对较短的时间内找到较优解。
•分布式计算：蚂蚁的并行搜索使得蚁群算法能够处理大规模复杂问题。
•鲁棒性强：蚁群算法对问题的可行域和约束条件的适应性较强。
蚂蚁算法求解TSP问题指导教师：李正学系 别：应用数学系班 级：2003级06班姓 名：王源学 号：200312082蚂蚁算法求解TSP问题摘 要蚂蚁算法是通过蚂蚁觅食而发展出的一种新的启发算法，该算法已经成功的解决了诸如TSP问题。
本文简要学习探讨了蚂蚁算法和TSP问题的基本内容，尝试解决一个实例问题并给出C语言算法。
关键词蚂蚁算法；TSP问题。
1 蚂蚁算法与TSP问题1.1 蚂蚁算法蚂蚁算法(Ant Colony Algorithm) 是由意大利学者M.Dorigo ,V. Manierio ,A. Collorni等人于二十世纪九十年代提出的一种新型的模拟进化算法。
受到人们对自然界中真实蚁群集体行为研究成果的启发,考虑到蚁群搜索食物的过程与旅行商问题的相似性,利用蚁群算法求解旅行商问题(Traveling Salesman Problem,TSP ) 、指派问题(AssignmentProblem)和调度问题( Scheduling Problem) ,取得了一些比较满意的实验结果。
蚁群算法是一种适应性好、鲁棒性强,具有正反馈结构的并行算法。
这些初步研究已显示出蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的一些优越性,证明它是一种很有发展前景的方法。
蚂蚁算法在各个领域的应用,说明该算法有着广泛的适应性,但由于该算法出现的较晚,对其研究还处于起步阶段,远不如遗传算法、人工神经网络和模拟退火算法那样成熟。
算法的很多特性,如算法的收敛性,参数的设定都来自于大量实验统计结果,目前对该算法理论研究有待进一步加强。
经过研究发现，蚂蚁在觅食的过程中通过一种称之为信息素（Pheromone）的物质相互传递信息。
更具体地，蚂蚁在运动过程中能够在其所经过的路径上留下信息素，而且在运动过程中能够感受到这种信息素的存在及其强度，并以此指导自己的运动方向。
蚂蚁倾向于朝着信息素浓度高的方向前进，因此，由大量蚂蚁组成的蚁群的行为便表现出一种信息的正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。
用蚁群算法解决TSP 问题一、引言蚁群算法是一种受自然界生物行为启发而产生的“自然”算法，产生于对蚂蚁行为的研究。
蚁群中的蚂蚁以“信息素”为媒介，间接异步的相互联系。
蚂蚁在行动中，会在他们经过的地方留下一些化学物质，称为“信息素”。
这些物质能被同一种群众后来的蚂蚁感受到，并作为一种信号影响后者的行动，具体表现在后到的蚂蚁选择有这些物质的路径的可能性比选择没有这些物质的路径的可能性大的多。
后者留下的信息素会对原有的信息素进行加强，并循环下去。
这样，经过蚂蚁多的路径，后到蚂蚁选择这条路径的可能性就越来越大。
由于在一定的时间内，越短的路径会被越多的蚂蚁访问，因而积累的信息素就越多，在下一个时间内被其他的蚂蚁选中的可能性也越大。
这个过程会持续到所有的蚂蚁都走到最短的那一条路径为止。
二、关键技术（1） 解的表达形式在应用蚁群优化算法时，只需要建立一个虚拟的始终点，相当于蚁群的巢穴和食物所在地，这样一个所经过城市的路径的排列就构成了一个解；（2） 信息素的记忆和更新在算法开始时，由于从来没有蚂蚁去寻找过路径，因此可以认为是没有任何先验信息，即每条路上的信息相等。
客观地将，信息素应该都为0，但是由于在蚁群算法中，信息素决定了蚂蚁选择这条路径的概率，因此可以认为初始信息素矩阵为：1/(*(1))0ij N N p -⎧=⎨⎩i j i j ≠=其中N 为城市数 当算法运行过程中，每次放出m 支蚂蚁，每只蚂蚁按照信息素选择路径，将其中路径最短的记录下来，对这条最短路进行信息素的加强；而对于其他路径，因为信息素的挥发，信息素浓度将会降低，更新后的信息素矩阵为： 11(1)//(1)/k ij k ij k ij p N p p ρρρ--⎧-+⎪=⎨-⎪⎩i j i j →→经过路径不经过路径其中N 为城市数，ρ为挥发系数 （3） 蚁群的规模在一般应用中，蚁群中蚂蚁的个数m 是固定数，不超过TSP 图的节点数。
三、算法实现步骤1 设定蚁群规模m ，计算次数n ，挥发系数ρ，初始化信息素矩阵，设定变量best =+∞记录全局最优解；步骤2 若n =0，推出并输出结果；否则n=n-1，分别放出m 只蚂蚁，按照信息素概率选择路径，并找出m 条路径中的当代最优路径cubest ； 步骤3 根据当代最有路径更新信息素；步骤4 如果cubest<best ，best=cubest ，执行步骤2；否则直接执行步骤2；四、结果及分析通过五个城市节点的TSP 问题的求解，其城市间的距离矩阵为：01015621008139158020156132005291550⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭蚁群算法找到的最优路径为A C B D E →→→→，总路程为43；通过试验结果发现，对于小规模的ＴＳＰ问题，蚁群算法和禁忌搜索、模拟退火算法的计算结果相似，而且耗时很短，因此该算法是合理的。
蚁群算法（ACO）解决TSP问题⼀、蚁群算法1.基本原理蚁群算法（Ant Colony Optimization，ACO）是⼀种基于种群寻优的启发式搜索算法，有意⼤利学者M.Dorigo等⼈于1991年⾸先提出。
该算法受到⾃然界真实蚁群集体在觅⾷过程中⾏为的启发，利⽤真实蚁群通过个体间的信息传递、搜索从蚁⽳到⾷物间的最短路径等集体寻优特征，来解决⼀些离散系统优化中的困难问题。
经过观察发现，蚂蚁在寻找⾷物的过程中，会在它所经过的路径上留下⼀种被称为信息素的化学物质，信息素能够沉积在路径上，并且随着时间逐步挥发。
在蚂蚁的觅⾷过程中，同⼀蚁群中的其他蚂蚁能够感知到这种物质的存在及其强度，后续的蚂蚁会根据信息素浓度的⾼低来选择⾃⼰的⾏动⽅向，蚂蚁总会倾向于向信息素浓度⾼的⽅向⾏进，⽽蚂蚁在⾏进过程中留下的信息素⼜会对原有的信息素浓度予以加强，因此，经过蚂蚁越多的路径上的信息素浓度会越强，⽽后续的蚂蚁选择该路径的可能性就越⼤。
通常在单位时间内，越短的路径会被越多的蚂蚁所访问，该路径上的信息素强度也越来越强，因此，后续的蚂蚁选择该短路径的概率也就越⼤。
经过⼀段时间的搜索后，所有的蚂蚁都将选择这条最短的路径，也就是说，当蚁巢与⾷物之间存在多条路径时，整个蚁群能够通过搜索蚂蚁个体留下的信息素痕迹，寻找到蚁巢和⾷物之间的最短路径。
蚁群算法中，蚂蚁个体作为每⼀个优化问题的可⾏解。
⾸先随机⽣成初始种群，包括确定解的个数、信息素挥发系数、构造解的结构等。
然后构造蚁群算法所特有的信息素矩阵每只妈蚁执⾏蚂蚊移动算⼦后，对整个群体的蚂蚁做⼀评价，记录最优的蚂蚁。
之后算法根据信息素更新算⼦更新信息素矩阵，⾄此种群的⼀次选代过程完成。
整个蚂蚁群体执⾏⼀定次数的选代后退出循环、输出最优解。
2.术语介绍（1）蚂蚁个体。
每只蚂蚁称为⼀个单独的个体，在算法中作为⼀个问题的解。
（2）蚂蚁群体。
⼀定数量的蚂蚁个体组合在⼀起构成⼀个群体，蚂蚁是群体的基本单位。
蚁群算法在TSP问题中的应用研究作者：刘援农来源：《硅谷》2011年第13期摘要：随着计算机技术的发展，各种算法技术也不断在更新，特别是在模仿社会性动物行为领域产生很多智能算法。
主要介绍蚁群算法，阐述其工作原理和特点及使用它求解TSP 问题的具体实现。
关键词：蚁群算法；TSP；群体智能中图分类号：TP273 文献标识码：A 文章编号：1671－7597（2011）0710108－01目前，在大力发展生物启发式计算研究的背景下，社会性动物如蚁群、蜂群、鸟群等的自组织行为引起了人们的广泛关注，许多学者对这种行为进行数学建模并用计算机对其进行仿真，这就产生了所谓的“群集智能”（swarm intelligence，简称SI）。
社会性动物的妙处在于：个体行为简单，但是集体协作工作能体现出一些复杂的智能行为，而在这些行为当中，又以蚁群在觅食过程中总能找到一条从蚁巢到食物源的最短路径最为引人注目。
受其启发，意大利学者M.Dorigo，V.Maniezzo和A.Colorni而于20世纪90年代初提出了一种新型的智能优化算法——蚁群算法。
该算法最初被用于求解著名的旅行商问题（Traveling Salesman Problem，简称TSP）并获得了较好的效果。
1 蚁群算法原理蚂蚁是群体动物，它们没有视觉但是可以通过集体配合劳动找到从巢穴到食物源的最短路径。
仿生学家经过大量研究后发现，蚂蚁在搜索食物时个体之间能通过在路径上留下的气味来进行信息传递，这种气味称作信息素（pheromone）。
在蚂蚁边运动边留下信息素，并且可以根据嗅到的信息素的浓度来进行前进路径的选择。
蚂蚁总是倾向于沿着信息素浓度高的方向来移动，而路径上的信息素会随着时间的推移而逐渐挥发。
信息素强弱指导蚂蚁行进，于是当一条路径上走过的蚂蚁越多，信息素浓度就会越强烈，后来的蚂蚁选择该路径的概率就越大。
这种群体行为构成了一种信息正反馈现象，蚂蚁就是通过这种反馈机制来进行信息交流，最终快速找到食物。
蚁群算法java实现以及TSP问题蚁群算法求解1. 蚁群算法简介蚁群算法（Ant Clony Optimization，ACO）是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。
蚁群算法最早是由意大利学者Colorni A., Dorigo M. 等于1991年提出。
经过20多年的发展，蚁群算法在理论以及应用研究上已经得到巨大的进步。
蚁群算法是一种仿生学算法，是由自然界中蚂蚁觅食的行为而启发的。
在自然界中，蚂蚁觅食过程中，蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。
图（1）显示了这样一个觅食的过程。
图（1）蚂蚁觅食在图1（a）中，有一群蚂蚁，假如A是蚁巢，E是食物源（反之亦然）。
这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶。
假如在A和E之间突然出现了一个障碍物（图1（b）），那么，在B点（或D点）的蚂蚁将要做出决策，到底是向左行驶还是向右行驶？由于一开始路上没有前面蚂蚁留下的信息素（pheromone），蚂蚁朝着两个方向行进的概率是相等的。
但是当有蚂蚁走过时，它将会在它行进的路上释放出信息素，并且这种信息素会议一定的速率散发掉。
信息素是蚂蚁之间交流的工具之一。
它后面的蚂蚁通过路上信息素的浓度，做出决策，往左还是往右。
很明显，沿着短边的的路径上信息素将会越来越浓（图1（c）），从而吸引了越来越多的蚂蚁沿着这条路径行驶。
2. TSP问题描述蚁群算法最早用来求解TSP问题，并且表现出了很大的优越性，因为它分布式特性，鲁棒性强并且容易与其它算法结合，但是同时也存在这收敛速度慢，容易陷入局部最优（local optimal）等缺点。
TSP问题（Travel Salesperson Problem，即旅行商问题或者称为中国邮递员问题），是一种，是一种NP-hard问题，此类问题用一般的算法是很大得到最优解的，所以一般需要借助一些启发式算法求解，例如遗传算法（GA），蚁群算法（ACO），微粒群算法（PSO）等等。
蚁群算法原理及在TSP 中的应用1 蚁群算法（ACA ）原理1.1 基本蚁群算法的数学模型以求解平面上一个n 阶旅行商问题(Traveling Salesman Problem ，TSP)为例来说明蚁群算法ACA （Ant Colony Algorithm ）的基本原理。
对于其他问题，可以对此模型稍作修改便可应用。
TSP 问题就是给定一组城市，求一条遍历所有城市的最短回路问题。
设()i b t 表示t 时刻位于元素i 的蚂蚁数目，()ij t τ为t 时刻路径(,)i j 上的信息量，n 表示TSP 规模，m 为蚁群的总数目，则1()ni i m b t ==∑；{(),}ij i i t c c C τΓ=⊂是t 时刻集合C 中元素(城市)两两连接ij t 上残留信息量的集合。
在初始时刻各条路径上信息量相等，并设 (0)ij const τ=，基本蚁群算法的寻优是通过有向图(,,)g C L =Γ实现的。
蚂蚁(1,2,...,)k k m =在运动过程中，根据各条路径上的信息量决定其转移方向。
这里用禁忌表(1,2,...,)k tabu k m =来记录蚂蚁k 当前所走过的城市，集合随着k tabu 进化过程作动态调整。
在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。
()kij p t 表示在t 时刻蚂蚁k 由元素(城市)i 转移到元素(城市)j 的状态转移概率。
()*()()*()()0k ij ij k kij ij ij s allowed t t j allowed t t p t αβαβτητη⊂⎧⎡⎤⎡⎤⎣⎦⎣⎦⎪∈⎪⎡⎤⎡⎤=⎨⎣⎦⎣⎦⎪⎪⎩∑若否则(1)式中，{}k k allowed C tabuk =-表示蚂蚁k 下一步允许选择的城市；α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间协作性越强；β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的重视程度，其值越大，则该状态转移概率越接近于贪心规则；()ij t η为启发函数，其表达式如下：1()ij ijt d η=(2) 式中，ij d 表示相邻两个城市之间的距离。
对蚂蚁k 而言，ij d 越小，则()ij t η越大，()kij p t 也就越大。
显然，该启发函数表示蚂蚁从元素(城市) i 转移到元素(城市) j 的期望程度。
为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有n 个城市的遍历(也是一个循环结束)后，要对残留信息进行更新处理。
这种更新策略模仿了人类大脑记忆的特点，在新信息不断存入大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。
由此，t n +时刻在路径(,)i j 上的信息量可按如下规则进行调整：()(1)*()()ij ij ij t n t t τρττ+=-+∆ (3)1()()mkij ij k t t ττ=∆=∆∑ (4)式中ρ表示信息挥发系数，则1ρ-表示信息素残留因子，为了防止信息的无限积累，ρ的取值范围为：[0,1)ρ⊂；()ij t τ∆表示本次循环中路径(,)i j 上的信息素增量，初始时刻()0ij t τ∆=，()kij t τ∆表示第k 只蚂蚁在本次循环中留在路径(,)i j 上的信息量。
根据信息素更新策略的不同，Dorigo M 提出了三种不同的基本蚁群算法模型，分别称之为Ant-Cycle 模型、Ant-Quantity 模型及Ant-Density 模型，其差别在于()k ij t τ∆求法的不同。
在Ant-Cycle 模型中,k i j ()0kkij QL t τ⎧⎪∆=⎨⎪⎩若第只蚂蚁在本次循环中经过（，），否则(5)式中，Q 表示信息素强度，它在一定程度上影响算法的收敛速度；k L 表示k 只蚂蚁在本次循环中所走路径的总长度。
在Ant-Quantity 模型中,k i j ()0kijij Q d t τ⎧⎪∆=⎨⎪⎩若第只蚂蚁在t 和t+1之间经过（，），否则(6)在Ant-Density 模型中,k i j ()0kij Q t τ⎧∆=⎨⎩若第只蚂蚁在t 和t+1之间经过（，），否则(7)区别：式(6)和式(7)中利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素；而式(5)中利用的是整体信息，即蚂蚁完成一个循环后更新所有路径上的信息素，在求解TSP 时性能较好，因此通常采用式(5)作为蚁群算法的基本模型。
1.2 基本蚁群算法的实现以下是解决TSP 问题的蚁群算法的基本流程描述，其中的参数设置来自于Dorigo 等人的试验。
基本蚁群算法的具体实现步骤如下：(1) 参数初始化。
令时间t=0和循环次数0c N =，设置最大循环次数max c N ，将m 蚂蚁置于n 个元素(城市)上，另有向图上每条边(,)i j 的初始化信息量()ij t const τ=，其中const 表示常数，且初始时刻(0)0ij τ∆=。
(2) 循环次数1c c N N ←+。
(3) 蚂蚁等禁忌表索引号k=1。
(4) 蚂蚁数目1k k ←+。
(5) 蚂蚁个体根据状态转移概率公式(1)计算的概率选择元素(城市)j 并前进，{}k j C tabu ∈-(6) 修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素(城市)，并把该元素(城市)移动到该蚂蚁个体的禁忌表中。
(7) 若集合C 中元素(城市)未遍历完，即k<m ，则跳转到第(4)步，否则执行第(8)步。
(8) 根据公式(3)和(4)更新每条路径上的信息量。
(9) 若满足结束条件，即如果循环次数max c c N N ≥，则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第(2)步。
2 程序实现（城市为中国各省省会城市）2.1数据列表TSP 问题中的城市选为中国各省省会城市，其实际地理位置的经纬度如表1所示。
表1 中国各省省会城市所在地理位置的经纬度2.2程序实现程序说明：程序是在GreenSim团队编写的程序的基础上进行修改得到，区别在于在程序中加入了更多的说明，便于MATLAB初学者以及对蚁群算法不是很熟悉的读者理解；对程序进行了略微的修改，加入了主程序和真实城市坐标数据。
其中主程序名称为ACAmain_city.m，其是可直接运行的程序。
运行结果如图1-图3所示，结果经过略微调整。
图2为将省会城市改成相应的省（或直辖市、特别行政区）后的图形。
结果均为一次运行所得，但由于算法的随机性，每次运行结果可能会不同。
另外，算法的初始条件对运行结果有很大影响，各种初始条件取值在附录中的程序已给出。
图1 ACA找到的最佳的中国环游路径（省会城市）图2 ACA找到的最佳的中国环游路径（省）图3 ACA迭代收敛曲线附录：（程序）注意：程序是直接从MATLAB中复制过来，拷贝到Word中可能会自动换行，再拷贝到MATLAB中运行时，应作相应调整。
函数文件应放到新的m文件中，并以相应的文件名命名，可运行的只有主程序。
A: 主程序%% 蚁群算法求解最短路径问题：ACAmain_city.mclc; close all; clear all; tic%% 中国各省省会城市23+5(直辖市4，特别行政区2)所在地理位置的经纬度（东经-北纬）C=[ 117.17 31.52; 119.18 26.05; 103.51 36.04; 113.14 23.08; 106.42 26.35; 110.20 20.02; 114.30 38.02; 113.40 34.46; 126.36 45.44; 114.17 30.35; 112.59 28.12; 125.19 43.54; 118.46 32.03; 115.55 28.40; 123.25 41.48; 101.48 36.38; 117.00 36.40; 112.33 37.54; 108.57 34.17; 104.04 30.40; 102.42 25.04; 120.10 30.16; 121.30 25.03; 108.19 22.48; 111.41 40.48; 106.16 38.27;90.08 29.39; 87.36 43.45; 121.29 31.14; 116.24 39.55; 117.12 39.02; 106.33 29.35; 115.07 21.33; 115.12 21.23];T=[ '合肥','福州','兰州','广州','贵阳','海口','石家','郑州','哈尔','武汉','长沙','长春','南京','南昌','沈阳','西宁','济南','太原','西安','成都','昆明','杭州','台北','南宁','呼和','银川','拉萨','乌鲁','上海','北京','天津','重庆','澳门','香港'];%% 参数初始化NC_max=150; m=34; Alpha=1; Beta=5; Rho=0.1; Q=100;%% 绘制找到的最优路径[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho ,Q); %函数调用figure(1); DrawCity(C,T,Shortest_Route); %绘制找到的最优路径toc %计算运行时间%% 绘制收敛曲线figure(2); iter=1:length(L_best);plot(iter,L_best,'-m*',iter,L_ave,':rp','LineWidth',2)xlabel('迭代次数'); legend('各代最佳路线的长度','各代路线的平均长度');grid on; tocB: 函数文件1%% 利用蚁群算法解决TSP问题的函数文件ACA TSP.mfunction[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho ,Q)%% Ant Colony Algorithm for Traveling Salesman Problem%% 主要符号说明%% C n个城市的坐标，n×2的矩阵%% NC_max 最大迭代次数%% m 蚂蚁个数%% Alpha 表征信息素重要程度的参数%% Beta 表征启发式因子重要程度的参数%% Rho 信息素蒸发系数%% Q 信息素增加强度系数%% R_best 各代最佳路线%% L_best 各代最佳路线的长度%% NC_max=150; m=25; Alpha=1; Beta=5; Rho=0.1; Q=100;%% ================================================================ %% 第一步：变量初始化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; % 计算两城市之间的距离elseD(i,j)=eps; % eps = 2.2204e-016，i=j,则距离为0endD(j,i)=D(i,j); % 距离矩阵为对称均值（n*n的矩阵）endendEta=1./D; %Eta为启发因子，这里设为距离的倒数（n*n的矩阵）Tau=ones(n,n); %Tau为信息素矩阵，初始化全为1，Tabu=zeros(m,n); %存储并记录路径的生成tabu:踏步（停止，禁忌表）（m*n的矩阵）NC=1; %迭代计数器R_best=zeros(NC_max,n); %各代最佳路线(行数为最大迭代次数NC_max，列数为城市个数n)L_best=inf.*ones(NC_max,1); %各代最佳路线的长度（inf:无穷大）L_ave=zeros(NC_max,1); %各代路线的平均长度%%while NC<=NC_max %停止条件之一：达到最大迭代次数%% 第二步：将m只蚂蚁放到n个城市上Randpos=[];for i=1:(ceil(m/n)) %ceil表示向无穷方向取整Randpos=[Randpos,randperm(n)]; %randperm(n)：随机产生一个整数排列endTabu(:,1)=(Randpos(1,1:m))'; %每只蚂蚁（m只）都对应有一个位置，Tabu(:,1)为每只蚂蚁的走过的第一个城市%% 第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游for j=2:n %城市从第二个开始for i=1:mvisited=Tabu(i,1:(j-1)); %已访问的城市J=zeros(1,(n-j+1)); %待访问的城市P=J; %待访问城市的选择概率分布（初始化）Jc=1; %循环下标for k=1:n %利用循环求解待访问的城市，如果第k个城市不属于已访问的城市，则其为待访问的城市if isempty(find(visited==k, 1))% if length(find(visited==k))==0J(Jc)=k;Jc=Jc+1; %下标加1，便于下一步存储待访问的城市endend%下面计算待访问城市的概率分布for k=1:length(J) %length(J)表示待访问的城市的个数P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta); %概率计算公式中的分子end %Tau为信息素矩阵,Eta为启发因子矩阵。
