新技术讲座论文

智能控制中蚁群算法的研究及展望

姓名：李妍 学号：040930503 班级：0309102

摘要：蚁群算法是一种新型的模拟进化算法，研究表明该算法具有很好的并行性和鲁棒性等优良性质，在离散的组合优化问题中实验，取得了良好的效果。本文阐述了蚁群算法的原理，对目前蚁群算法的研究进展情况进行了分析，介绍了该算法在理论与实际问题中的应用，对蚁群算法的优缺点进行分析，对其前景进行了展望。

关键词：蚁群算法 原理 研究现状 展望

引言：在当今社会中，随着人工智能和网络和网络技术的飞速发展，科学技术与其他多种学科相互交叉，互相渗透和融合，很多生物方面的研究专家和学者，通过对大自然中很多生物的生活现象和规律进行了大量的研究和探讨，提出了很多基于生物信息系统的只能仿生算法，蚁群算法是这些群体智能算法中的一个重要分支。蚁群算法是由意大利学者M.Dorigo等在20世纪90年代初期研究蚂蚁寻找巢穴到食物源的路径时，从生物进化的机制中受到启发，提出了一种新型的模拟进化算法。该算法不仅具有鲁棒性、正反馈性和分布式计算等优点，还能够智能搜索、全局优化等优势，在求解复杂的组合优化问题上有更强的优势，在分配问题、Job-shop调度和TSP求解等问题上，都有了较好的实验结果，越来越多的研究者对其关注和探讨，算法理论不断地完善。

1、 算法的原理

蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生算法。为了说明蚁群算法的原理，先简单介绍一下蚂蚁搜寻食物的具体过程。

在蚂蚁群找到食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。于此同时释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大。这样就形成了一个正反馈。

最优路径上的激素浓度越来越大，而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。不仅如此，蚂蚁能够适应环境的变化，当蚁群运动路线上突然出现障碍物时，蚂蚁能够很快地重新找到最优路径。整个过程和前面所描述的方式是一致的。在整个寻径过程中，虽然单个蚂蚁的选择能力有限，但是通过激素的作用，整个蚁群之间交换着路径信息，最终找出最优路径。

2、蚁群算法的实现过程

在蚁群算法中，蚂蚁之间相互习作可以较好地解决复杂优化问题。蚂蚁既能共同地行动，又能独立地工作。每只蚂蚁都能够找到一个解，虽然有可能不是较好的解。蚂蚁之间不能直接通讯，但可以通过信息素指引着蚂蚁之间的信息交换。在实现蚁群算法时，实现蚂蚁个体的功能是非常重要的。只要蚂蚁个体的功能完善了，并且拥有了信息素的间接通讯方式，蚁群算法就基本上实现了。

在蚁群算法中，蚂蚁个体需要实现以下四个重要功能：

（1）基于概率的局部搜索策略：实际问题中，蚂蚁经常要从一个状态点移动另一个状态点。经过这样有限步的移动，每只蚂蚁都建立了一个问题的解。在每一步的移动过程，蚂蚁应用基于概率的局部搜索策略选择移动方向。这个策略主要基于蚂蚁的记忆以及信息素浓度，有时还有具体问题的局部信息等。

（2）蚂蚁的记忆：蚂蚁的记忆存储了关于蚂蚁过去的信息。这些记忆的信息可以用于计算所解决方案的价值或每一步移动的贡献。在一些组合优化问题中，利用蚂蚁的记忆可以正确引导蚂蚁构建方案得解。例如在TSP问题中，利用蚂蚁的记忆可以记录蚂蚁已经走过的城市，并将其置于一个禁忌表中。这样就避免蚂蚁重复访问这些城市，使得蚂蚁构造出来的解可以满足TSP问题的约束条件。所以，蚂蚁可以只使用关于局部的信息，就能构造出问题的解。

（3）释放信息素：已经知道蚂蚁之间的协作是通过信息素来完成，信息素给蚁群算法产生正反馈的重要作用。那么，蚂蚁何时释放信息素以及释放信息素的量，由具体问题的特征来决定。蚂蚁可以在构造解的同时逐步释放信息素，也可以构造完一个解后再释放信息素，也可以两者方法结合。而蚂蚁释放的信息素的量与蚂蚁建立解决方案的优劣程度成正比。

（4）蚂蚁决策表：蚂蚁决策表是由信息素函数与启发信息函数共同决定的，

它是一种概率表。蚂蚁使用这个表来指导其搜索最有吸引力的移动方向。在蚂蚁移动时，不仅基于概率的局部搜索策略，还增加了信息素挥发机制。这样就避免了蚂蚁过早收敛，出现早熟。

蚁群算法就是通过蚂蚁个体功能来构造解，并释放信息素来协调，最终找到个较优的解决方案。

3、蚁群算法的研究现状

自从提出基本蚁群算法，并应用其求解TSP问题，许多研究者开始研究如何改进蚁群算法的性能。

A、M．Dorigo等人在蚂蚁系统的基础上做了以下三个方面的改进：（1）提供了一个更好的状态转移选择策略。在蚂蚁系统中，蚂蚁的状态转移策略完全依靠概率进行选择。而在蚁群系统中，蚂蚁使用了不同的选择策略，称为伪随机比例规则，这个规则使用了一个参数来调节蚂蚁探索新路径的程度。（2）全局更新只适用与当前最优的蚂蚁路径上。如果在蚁群系统中对所有蚂蚁构造出来的解都进行更新，那么就会大大降低搜索最优路径的效率，值得蚁群不能很快集中到最优的路径上来。因此，现在只对最优的蚂蚁路径上信息素进行更新。其他路径由于挥发机制信息素会逐渐减少，从而进一步增大了最优路径和最差路径之间的信息素的差异。这样，就会使得蚂蚁选择更倾向于最优路径的选择，从而提高蚁群的搜索效率。（3）在构造解的过程中，应用局部信息更新信息素。在蚁群系统中，蚂蚁在构造路径的同时进行局部更新，而在每次循环后再对路径进行一次全局的更新。

B、最大最小蚂蚁系统 在MMAS中，为了避免早熟收敛，在每个解的元素上的信息素的浓度被限制在一定区域内，这样避免了路径上的信息素被过度增加或过度挥发，使得蚂蚁能更好地搜索新的解决方案。其中应用的一种信息素平滑化机制，其基本思想是，通过增加选择信息素浓度较低路径的概率，以提高探索新解的能力，降低了MMAS对信息素下限的敏感度。

C、多重蚁群算法 引入多重蚁群，几个蚁群群体层的相互作用，能找到更好的解。在某些时间节点上，从各蚁群群体层可以相互交换好的解的相关信息。如果交换的信息量适当，则多重蚁群算法就能在不同的处理器上分配不同的蚁群，从而轻易地实现并行处理，蚁群群体层的交互作用使用了正负两者信息素效

益，更好地交换问题解决过程的规划信息，并保持它们在搜索过程中的多样性。

D、具有变异特征的蚁群算法 蚁群算法虽然有很多优良的性质，但是仍然存在不足之处，如计算时间较长、执行复杂度较高等，因此，提出了具有变异特征的蚁群算法，其中引入变异机制，使得蚁群算法具有较快的收敛速度，提高了算法的运行效率。

E、自适应蚁群算法 蚁群算法加速收敛和早熟停滞现象之间存在矛盾，针对这个问题，有研究者提出一种自适应蚁群算法，可以在加快收敛和避免早熟、停滞现象之间取得很好的平衡。该算法可以根据优化过程中解的分布平衡度，自适应地调整路径选择概率的确定策略和信息量更新策略。自适应蚁群算法，提出了全局更新信息素的规则，并引入蚁群蚂蚁分工与协同学习、协同工作的思想。这些改进，可以大大提高蚁群算法的自适应能力。

F、蚁群算法的典型应用

蚁群算法在解决很多组合问题上都取得比较理想的效果。其中有两个比较著名的组合问题，QAP问题（Quadratic Assignment Problem）和JSP问题（Job-Shop Scheduling Problem）作相应调整的蚁群算法可以比较好地解决这两个组合问题。

另外，将蚁群算法对实际问题的解决也取得一定的进展，如大规模集成电路中的综合布线以及电信网络中的路由等方面的应用。

A、QAP问题

QAP问题的目标函数可以用一个n×n的对称矩阵来描述。蚁群算法基于它和TSP问题这方面的相似性来解决问题，QAP问题的目标函数矩阵S通过距离向量和流向量的组合组成，蚂蚁根据可见度信息来选择下一个节点。

B、JSP问题

JSP问题可以用一个加权图描述。每条边的权值用参数{t,k}信息t和可见度k是通过最长进程时间或者最短完成时间等要求决定。蚂蚁遍历节点的顺序就是相应的解决方案。在解决10×10和10×15的JSP问题中，蚂蚁算法的解与最优解的误差在10%之内。

C、大规模集成电路综合布线

大规模集成电路中的综合布线可以采用蚁群算法的思想来进行。在布线过程

中，各个引脚对蚂蚁的引力可根据引力函数来计算。各个线网根据启发策略，像蚁群一样在开关盒网格上爬行，所经之处便布上一条金属线，历经一个线网的所有引脚之后，线网便布通了。给定一个开关盒布线问题，问题的计算量是固定不变的，主要由算法的迭代次数决定，而迭代次数由开关盒问题本身的性质决定。蚁群算法本身的并行法，使之比较适合于解决布线问题。

D、电信网络路由

电信网络中的路由是通过路由表进行的。在每个节点的路由表中，对每个目的节点都列出了与该节点相连的节点，当有数据包到达时，通过查询路由表可知道下一个将要到达的节点。首先对路由表中的信息素强度进行初始化。然后周期性地释放蚂蚁来进行路由，并修改相应的信息素的值。仿真结果表明，无论呼叫时均匀分布还是集中分布，利用蚁群算法所得呼叫拒绝率和平均路径长度均小于最小负载法结果，在呼叫符合集中分布时，蚁群算法所得呼叫拒绝率低于最短路径法。

4、蚁群算法的优缺点

蚁群算法的优点：

（1）蚁群算法能较好地解决复杂优化问题。蚁群算法是一种结合了分布式计算、正负馈机制和贪婪式搜索的算法。在求解复杂优化问题中，蚁群算法具有很强的搜索较优解的能力。正反馈机制使得蚁群可以很快地发现较优的解。分布式计算避免了蚁群算法出现早熟收敛。而贪婪式搜索有助于在搜索过程中早期就找出可接受的解，提高系统的运行速率。

（2）蚁群算法具有很强的并行性。蚁群算法适用于并行操作，在求解复杂优化问题时，不仅可以从算法自身的改进出发来提高求解效率，也可以从算法的执行模式出发进行优化。

（3）蚁群算法具有很好的扩充性。因为蚁群算法可以不通过蚂蚁个体之间直接通信，而是通过信息素进行间接通信，所以蚁群算法就具有很好的可扩充性。

（4）蚁群算法具有较强的鲁棒性。对于蚁群算法模型稍加改进，就可以应用于其他问题中，在研究蚁群算法的过程中，许多研究者都通过求解TSP问题来研究蚁群算法。

（5）蚁群算法还具有易于与其他方法融合的特性。可以将其余遗传算法和

中，各个引脚对蚂蚁的引力可根据引力函数来计算。各个线网根据启发策略，像蚁群一样在开关盒网格上爬行，所经之处便布上一条金属线，历经一个线网的所有引脚之后，线网便布通了。给定一个开关盒布线问题，问题的计算量是固定不变的，主要由算法的迭代次数决定，而迭代次数由开关盒问题本身的性质决定。蚁群算法本身的并行法，使之比较适合于解决布线问题。

D、电信网络路由

电信网络中的路由是通过路由表进行的。在每个节点的路由表中，对每个目的节点都列出了与该节点相连的节点，当有数据包到达时，通过查询路由表可知道下一个将要到达的节点。首先对路由表中的信息素强度进行初始化。然后周期性地释放蚂蚁来进行路由，并修改相应的信息素的值。仿真结果表明，无论呼叫时均匀分布还是集中分布，利用蚁群算法所得呼叫拒绝率和平均路径长度均小于最小负载法结果，在呼叫符合集中分布时，蚁群算法所得呼叫拒绝率低于最短路径法。

4、蚁群算法的优缺点

蚁群算法的优点：

（1）蚁群算法能较好地解决复杂优化问题。蚁群算法是一种结合了分布式计算、正负馈机制和贪婪式搜索的算法。在求解复杂优化问题中，蚁群算法具有很强的搜索较优解的能力。正反馈机制使得蚁群可以很快地发现较优的解。分布式计算避免了蚁群算法出现早熟收敛。而贪婪式搜索有助于在搜索过程中早期就找出可接受的解，提高系统的运行速率。

（2）蚁群算法具有很强的并行性。蚁群算法适用于并行操作，在求解复杂优化问题时，不仅可以从算法自身的改进出发来提高求解效率，也可以从算法的执行模式出发进行优化。

（3）蚁群算法具有很好的扩充性。因为蚁群算法可以不通过蚂蚁个体之间直接通信，而是通过信息素进行间接通信，所以蚁群算法就具有很好的可扩充性。

（4）蚁群算法具有较强的鲁棒性。对于蚁群算法模型稍加改进，就可以应用于其他问题中，在研究蚁群算法的过程中，许多研究者都通过求解TSP问题来研究蚁群算法。

（5）蚁群算法还具有易于与其他方法融合的特性。可以将其余遗传算法和

模拟退火算法相结合。

蚁群算法的缺点：

（1）对于大规模复杂优化问题，蚁群算法需要较长的搜索时间。蚁群中的蚂蚁个体的运动是随机的，虽然通过信息素的间接协调，能够让蚁群向较优的路径，但是当问题给莫很大时，蚁群很难再较短时间内从大量杂乱无章的路径中找出一条最后的路径。这主要是因为蚁群在搜索早期，各个路径上信息量相差不明显。虽然有正反馈机制，但是需要经过很长一段时间，才能使得较好路径上的信息素浓度明显高于其他路径上的信息素的浓度。所以对于大规模的复杂优化问题，算法的收敛需要较长时间。

（2）蚁群容易出现停滞现象，出现早熟收敛。也就是当搜索进行到一定时间后，所有蚂蚁个体所发现的解完全一致，不能进一步对解进行搜索，所以不利于发现更好的解。因此很多研究者对蚁群算法进行改进，以期望避免算法早熟收敛，以搜索更优的解。

（3）蚁群算法黑没有严格的数学解释。目前还未能提出一个完善的理论分析，对蚁群算法的有效性进行论证。蚁群算法作为一种模拟进化算法，其研究才刚开始，有许多问题仍有待研究。

5、蚁群算法的展望

针对蚁群算法的优缺点，研究者仍然在不断提出各种解决方案，同时，种种实验结果表明，蚁群算法是一种很有发展前景的算法。

目前，蚁群算法主要值得研究的方向：

A）对于蚁群算法，重要的就是开发出求解问题的算法模型，是求解问题更加切实有效。而在工程实际的应用中，算法模型的收敛和算法的复杂程度是值得研究的问题。

B）利用蚁群算法的全局性避开了局部最优，利用局部搜索算法加快了求解过程，寻求两者的完善结合，将成为一个值得探讨的课题。

C）蚁群算法和其他模拟进化算法的结合，形成混合模拟进化算法模型，也会使求解问题变得更加有效。

D）从复杂系统和复杂性科学地角度看，蚁群系统是一个复杂系统。蚁群系统那个寻找从蚁穴从食物源最短路径的过程，是整个蚁群之间相互作用、相互影

响和相互协调的结果。蚁群算法本质上具有概率搜索的特征。因此有研究者提出，可以讲蚂蚁视为微观粒子，利用量子力学波函数的方法研究某时刻粒子坐标的概率振幅。也可以将蚂蚁视为图论中的节点，建立蚁群算法的图论模型，进而分析其在不同问题中约束条件及其之间的关系。对于蚁群算法理论问题的深入研究，可以为推广蚁群算法的应用领域奠定重要的理论基础。

6、结束语

蚁群算法的理论研究和实际应用表明，它是一种很有前景的仿生优化算法。随着人类认识的进步和社会发展的加速，仿生智能及最优化系统理论将越来越成为科学认识和工程实践的有力工具，蚁群算法理论及其应用的研究必将是一个长期的研究课题。蚁群算法这一新兴的仿生优化算法必将展现出更加广阔、更加引人注目的发展前景。

参考文献：

[1]Dorigo, Maniezzo ,Colomi. Ant system:optimization by a colony of coorperating agents[J].IEEE Transactions on SMC,1996.

[2] Dorigo, Cambardella. Ant colony system:a cooperative learning approach to the travelling salesman problem [R].IEEE Transactions on Evolutionary Computing,1997.

[3]吴庆洪，张纪会，徐心和.具有变异特征的蚁群算法[J].计算机研究与发展，1999.

[4]吴启迪，汪镭.只能蚁群算法及应用[M].上海科技教育出版社，2004.

[5]段海滨，王道波，朱家强，等.蚁群算法理论及应用研究的进展[J].2004.

[6]段海滨，王道波，于秀芬.蚁群算法实现的研究进展[J].2006.

[7]李士勇.蚁群算法及应用[M].哈尔滨工业大学出版社，2004.