蚁群算法及其应用研究进展(3)

１４

计算机应用与软件２００８年

其中』Ｂ描述了状态转移时信息素和启发式信息之间的相对重要程度。‰表达了算法在“勘探”和“开采”之间的折衷程度。ｐ和ａ都刻画了信息素随时间的衰减程度。ｒ。则是初始信息素的强度。

Ｓ０ｌ∞ｎｐｌ分析了信息素相关参数对“勘探”和“开采”的影响，提出了在蚁群算法运行之前加入一个预处理阶段，这个阶段先不使用信息素找到一定数量的路径（即回路），再从中选择部分路径在算法开始前初始化信息素，获得了较好的效果。不同的参数组合影响着蚁群算法的性能，Ｐｉｌａｔ以及Ｇａｅｒｔｎｅｒ等哺．９１人将遗传算法与蚁群算法相结合，应用遗传算法优化蚁群算法的参数，获得了较好的效果。Ｍｅｙｅｒ¨驯研究了蚁群算法中参数对“勘探”行为，即保持解的多样性的影响，指出式（２）中的口不仅对协调“勘探”和“开采”行为有决定作用，而且对系统的鲁棒性也有重要影响。

关于蚁群算法参数优化的研究相对较少，然而蚁群算法的参数设置关系到算法最终的性能，因此参数的设置原则值得更深入的研究。

２．２蚁群算法的改进研究

为了提高蚁群算法的性能，获得更快的收敛速度和求解质量，很多研究工作围绕蚁群算法的改进展开。

Ｇ椰ｂａｒｄｅｌｌａ等…’将蚂蚁系统和增强学习中的Ｑ学习算法

融合在一起提出了Ａｎｔ．Ｑ算法。Ｄｏｒｉ９０等¨ｏ采用“精英策略”（Ｅｌｉｔｉｓｔｓｔｍｔｅｇｙ）对蚂蚁系统信息素更新机制进行改进，即增强在每次迭代中找到最优路径的蚂蚁的重要性，对其找到的路径增加额外的信息素，这种策略改善了蚂蚁系统求解大规模问题的能力。

７瞄ｕａｒｄ等¨２１提出了快速蚂蚁系统ＦＡＮＴ（ＦａｓｔＡｎｔ

ｓｙｓｔｅｍ）

的概念，ＦＡＮＴ为了避免算法收敛于局部最优而引入了信息素重置机制。ＳｔｕｔｚｌｅＬＩ副提出了最大一最小蚂蚁系统（ＭＡＸ．ＭＩＮ

Ａｎｔ

ｓｙｓｔｅｍ）的概念，它和第一节中介绍的蚁群系统”ｏ类似，但

最大一最小蚂蚁系统事先限定了路径上信息素的变化范围在ｒ晌和下～之间，＿ｒ耐。和ｒ～是预先设定的参数，这样有效避免了搜索陷入停滞。Ｂｌｕｍ和Ｄｏｒｉｇｏ【１４１提出了超立方框架下的蚁群算法（Ｈｙｐｅｒ－Ｃｕｂｅ

Ｆ姗ｅｗｏｒｋ

ｆｏｒＡｎｔＣｏｌｏｎｙＯｐｃｉｍｉｚａｔｉｏｎ），通过

改进信息素更新规则并且限制信息素在［０，１］之间，使得在这种框架下对蚁群算法的理论分析更容易，而且增加了系统的鲁棒性。

最初的蚁群算法适用于解决组合优化问题，现在也有学者尝试改进蚁群算法求解连续优化问题。Ｐｏｕｎａｋｄｏｕ８ｔ等［１纠提出了只在信息素指导下进行寻优的求解连续优化问题的蚁群算法。Ｄ－６０等¨钊提出了连续交互式蚁群算法（ＣｏｎｔｉｎｕｏｕｓＩｎｔｅｒ∞．

ｔｉｎｇＡｎｔ

ｃｏｌｏｎｙ）求解多目标连续函数优化问题。改进蚁群算法

求解连续优化问题的研究相对较少，这是一个很有潜力的研究方向。

２．３蚁群算法的收敛性及工作机制的研究

蚁群算法问世以来，对蚁群算法的实验研究较多，对算法本身收敛性的分析较少。蚁群算法的收敛性研究对深入理解蚁群算法的工作机理具有重要的理论价值，同时在提高算法收敛速度改善算法性能方面也具有现实意义。因此蚁群算法的收敛性研究是近期蚁群算法理论研究中的一个重要内容。

ＧｕｔｊａＩｌｒ¨７１基于图建立了蚁群算法解决组合优化问题的一般框架，并且证明了在特定的条件下，基于图的蚁群算法

万方数据

（ＧＢＡＳ）可以保证以任意接近于ｌ的概率收敛于给定问题实例的最优解；ｓｔｕｔｚｌｅ和Ｄｏｒｉ９０¨引证明了针对一类蚁群算法，当迭代次数趋向于无穷时，蚁群算法可以保证找到全局最优解；Ｇｕｔ．ｊａｈｒ¨纠后来针对上述两类算法的缺点，对基于图的蚁群算法进行改进并提出了ＧＢＡＳ／Ｉｄｅｖ和ＧＢＡｓ／ｔｄｌｂ，证明了可以选择合适的参数组合使得蚁群算法的动态随机过程收敛到最优解。Ｖｅｒｂｅｅｃｋ等Ⅲｏ基于互联的学习自动机（Ｉｎｔｅｒｃｏｎｎｅｃｔｅｄｋ帅ｉｎｇ

Ａｕｔｏｍａｔａ）对蚁群的行为建模，认为可以把互连的学习自动机作

为理论工具来考察蚁群算法的工作机理。

蚁群算法的理论分析为蚁群算法的改进提供了新的思路和角度，对建立其理论基础有重要意义，目前这方面的研究相对较少，而且这些研究大都针对某一类蚁群算法，并没有在一个共同的理论框架下讨论。

２．４蚁群算法与其它算法的融合

蚁群算法易于与其它算法融合从而互相取长补短，改善算法的性能。目前这个方面的研究成果，包括蚁群算法与遗传算法、神经网络、微粒群算法等等之间的融合研究。

蚁群算法与遗传算法的融合。丁建立等口¨利用遗传算法产生路径上的初始信息素分布，获得了较好的效果。对于蚁群算法与遗传算法的融合，研究主要是用遗传算法优化蚁群算法中的参数和信息素，以及将遗传算法中的选择、交叉变异等操作融人蚁群算法。

蚁群算法与神经网络的融合。Ｂｌｕｍ等ｍｏ用蚁群算法训练前馈神经网络，并将其应用于模式分类。蚁群算法还可以与其它优化算法融合，如免疫算法、粒子群算法。Ｈｏｌｄｅｎ等悼副将蚁群算法和粒子群算法（ＰａＩｔｉｃｌｅＳｗａｍ０ｐｔｉｍｉｚａｔｉｏｎ）集成在一起，

用于处理生物数据集的层次分类（ＨｉｅｒａｒｃｈｉｃａｌＣｌ船ｓｉｆｉｃ“ｏｎ）。Ｂｅｕｏ等Ⅲｏ提出了一个基于蚁群算法和粗糙集方法的模型，并将其用于特征选择。

蚁群算法作为一种较新的仿生优化方法，与其它算法融合和比较的研究仍处于初级阶段，相关的研究文献和报告较少。因此，设计新的融合策略结合其它算法进一步改善蚁群算法的性能，以及探讨蚁群算法与其它算法之间的联系都是非常有意义的研究方向。

３蚁群算法的应用研究

蚁群算法最初被应用到经典的组合优化问题，随着研究的深入，应用范围逐渐扩大到更多的组合优化问题，而且目前已有将蚁群算法应用到连续优化问题的研究。

３．１静态组合优化问题中的应用

蚁群算法目前已经在诸多领域得到应用，如水资源规划、电力系统的优化、物流领域等等。

典型的组合优化问题。从最初用蚁群算法解决旅行商问题¨．３１开始，研究者们陆续将其应用到其它典型的组合优化问题：二次规划问题¨副（Ｑｕ８ｄ饱ｔｉｃＡｓｓｉｇＩｌｍｅｎｔ

Ｐｒｏｂｌｅ瑚）、图着色问

题Ⅲｏ（Ｇｍｐｈ

ｃｏｌｏｒｉｎｇ

Ｐｍｂｌｅ咖）。这些问题具有很强的工程代

表性，蚁群算法在典型的组合优化问题上的出色表现加速了它在工程应用领域的发展。

水利科学方面的应用

蚁群算法在水科学方面的应用

集中在水资源规划设计方面。ｚｅｃｃｈｉｎ等Ⅲｏ用改进的蚁群算法对配水系统的设计进行优化。Ｈｉｌｔｏｎ等拉刊人用蚁群算法对地下

第８期倪庆剑等：蚁群算法及其应用研究进展

１５

水监测网络的设计进行优化。水利科学中的配水系统、灌溉系统、防洪系统的设计等工程应用问题都表现出组合优化问题的特征，因此蚁群算法在水利工程优化领域有广泛的应用前景。

电力系统领域的应用

电力系统的许多优化问题本质

上属于组合优化问题。Ｇｏｍｅｚ等【２驯人将蚁群算法应用于配电网络的规划。Ｖｌａｃｈｏｇｉａｎｎｉｓ旧１提出了用蚁群算法解决约束潮流问题，实验结果表明蚁群算法具有较高的可靠性和优化能力。Ｆｏｏｎｇ等Ⅲ１人将蚁群算法应用到发电厂检修计划的优化。电力系统的这些组合优化问题的有效解决将为电力企业节省大量的资金，因此在电力系统领域的应用具有很高的实际价值。

物流领域的应用

物流领域中的一些问题也具有组合

优化问题的性质。研究较多的是物流配送领域的车辆路径问题，Ｇａｍｂａｒｄｅｌｌａ等ｐｕ人最先将蚁群算法应用于车辆路径问题。Ｍｅｒｋｉｅ等四。人将蚁群算法应用于资源项目约束的排定问题

（Ｒｅｓ叫ｒｃｅ—ＣｏｎｓｔｍｉｎｅｄＰｒｏｊｅｃｔｓｃｈｅｄｕｌｉｎｇＰｍｂｌｅｍｓ），实验表明与

其它启发式算法相比较优势明显。

３．２动态组合优化问题中的应用

在动态组合优化问题中，问题的解随时间而变。蚁群算法在动态组合优化问题的中的应用研究集中在通信领域。ｓｃｈ∞ｎｄｅｒｗｏｅｒｄ等一副人率先将蚁群算法用于通信网络的路由问题，提出了基于蚁群算法的路由算法。Ｄｉ

ｃ啪等Ⅲｏ人基于蚁

群算法设计了自适应路由算法ＡｎｔＮｅｔ，每个节点根据网络的状况动态更新路由表项。Ｈｕｓｓｅｉｎ等’３５１提出了改进的蚁群算法应用于移动自组织网络的路由问题。

通信网络的一些特征，如分布式的信息存储结构、网络的动态特性等与蚁群算法的本质特性非常类似，因此蚁群算法在通信领域中有广泛的应用前景。

目前蚁群算法在连续优化问题中的应用相对较少。ＢｉＩｃｈｅｖ等Ⅲ１最先尝试用蚁群算法解决连续优化问题。Ｈｏ等【３７３通过改进信息素更新策略提出了求解连续优化问题的蚁群算法，算法应用在电磁装置的优化设计上获得了良好的效果。

目前将蚁群算法应用于连续优化问题的研究才刚刚起步，连续优化问题与组合优化问题相比，它们的最终优化目标不同，因此需要在信息素更新策略、蚂蚁的状态转移策略上进行改进以适应连续的连续优化问题的求解。

蚁群算法问世至今已有十多年，其理论和应用都有了很大的进步，蚁群算法从最初求解旅行商问题开始。已经逐步发展为一个优化工具，并且较为成功地应用到科学和工程中的多个领域。蚁群算法具有分布式计算、无中心控制、个体之间异步间接通信的特点，而且易于与其它优化算法相结合。但是同时它也接受的解；算法容易出现停滞现象；蚁群算法作为一个仿生进化用领域也有待进一步的挖掘。

综合本文的分析，蚁群算法在如下几个方面可以作进一步的探讨：

（１）蚁群算法理论基础的挖掘。包括蚁群算法收敛性的分

万方数据

析与证明，蚁群算法适用于一般问题的普遍理论框架的建立，蚁群算法参数设置的原则的进一步研究。

（２）蚁群算法的改进。可以考虑从新的角度对蚁群算法进行改进，比如概率方法，多种群策略，蚁群之间信息共享机制的改进，以及引入其它优化算法中的思想，蚁群算法是一种基于种群的方法（Ｐ０ｐｕｌａｔｉｏｎＢ踮ｅｄＭｅｔｈｏｄ），具有并行性，可以进一步对算法的并行化进行研究。

（３）蚁群算法与其它优化算法比较和融合研究。蚁群算法与其它随机算法之间的比较研究尚处于起步阶段，研究者们已经尝试将蚁群算法与其它优化算法相融合以获得更强的优化能力，但是蚁群算法与其它算法之间融合机制和策略仍有待进一步的探讨。

（４）蚁群算法在实际的工程应用中的问题。当前的应用相当一部分仍是实验和仿真，作为概率算法，它在应用于实际问题时的稳定性也值得研究。

（５）蚁群算法应用领域的拓展。蚁群算法已经被引入很多领域发挥其优化能力。目前应用较多的是静态组合优化问题，如何改进将其应用于动态组合优化问题和连续优化问题是一个值得探索的方向。

参考文献

［１］ｃｏｌｏ巾ｊ

Ａ，Ｄｏｒｉｇｏ

Ｍ，Ｍ肌ｉｅｚ∞Ｖ．Ｄｉｓｔｒｉｂｕｔｅｄｏｐｌ．ｍｉｚａｔｉｏｎｂｙ鲫ｔｃｏｌｏ－

ｎｉｅｓ．Ｐ∞ｃｅｅｄｊｎｇｓ

ｏｆ

ｔｈｅＦｉｒｓｔ

Ｅｕｍｐｅ鲫Ｃｏｎｆｅ他ｎｃｅ

ｏｎ

Ａｒｔｉｆｉｃｉａｌ

Ｉｍ，

Ｐ且ｒｉｓ，ＦｒＭｃｅ。１９９１．

［２］Ｇ０８８ｓ，Ａｒｏｎｓ，ＤｅｎｅｕｂｏｕｒｇＪ

Ｌ，ｅｔ

ａ１．Ｓｅｌ‰瑁“ｚｅｄ

ｓｈｏｎｃｕｔｓｉｎ

ｔｈｅ

Ａｒｇｅｎｔｉ舱明ｔ．Ｎ且ｔｕｒｗｉｓ卵ｎｓｃｈ血ｅｎ，１９８９，７６（１２）：５７９—５８１．［３］Ｄｏｒｉ９０Ｍ，Ｍ帅ｉｅｚ趵Ｖ，ｃｏｌｏｍｉ

Ａ．Ａｎｔ

ｓｙｓｔｅｍ：ａｐｔｉｍｉｚａｌｉｏｎｂｙ

ａ

ｃｏｌｏｎｙ

ｏｆｃ∞ｐｅｒａｔｉｆＩｇａｇｅｎｔ８．ＩＥＥＥ

Ｔｒ粕Ｂａｃｔｊ伽Ｂ∞Ｓｙ８ｔｅ瑚，Ｍ蚰ａｎｄＣｙｂｅｒ．ｎｅｔｉｃｓ．Ｐａｎ

Ｂ，１９９６，２６（１）：２９—４１．

［４］Ｄｏｒｉｇｏ

Ｍ．Ｄｉ

ｃａｍＧ．Ａｎｔ

ｃｏｌｏｎｙ叩ｔｉｍｉｚａｔｉｏｎ：ａ

ｎｅｗ

ｍｅｔａ－ｈｅｕｒｉｓｔｉｃ．

卟ｅＣｏｎ目嘲ｓ

ｏｎ

Ｅｖｏｌｕｔｉｏｎａｒｙ

Ｃｏｍｐ山ｔｉｏｎ，Ｗ∞ｈｉｎｇｔｏｎ，ＤＣ，１９９９．

［５］ＤｏｄｇＤＭ，Ｇａｍｂａｆｄｅｌｌａ

Ｌ

Ｍ．Ａｎｆ∞ｌｏｎｙｓｙｓｏ唧：８ｃｏｏｐｅｍｌｊｖｅｌｅ锄ｊｎｇ

ａｐｐｒｏ扯ｈｔｏ

ｔ量ｌｅｔｍｖｅｌｉｎｇｓａｌ髑眦ｎ

ｐｆｏｂｌｅｍ．ＩＥＥＥ１ｈＩＩｓａｃｔｉｏｎｓ

ｏｎ

Ｅｖｏ．

１ｕｔｉｏｎａｒｙ

ｃｏｍｐｕｔａｔｉ∞，１９９７。ｌ（１）：５３—６６．

［６］

Ｍ

Ｄｏｒｉｇｏ，Ｌ

Ｍ㈨ａｒｄｅｌｌａ．Ａｎｔ

ｃｏＩｏｎｉ髓ｆｏｒｔｈｅｔｒａｖｅｌｌｉｎｇｓａｌｅｓｍ粕

ｐｍｂｌｅｍ．Ｂｊ∞ｙｓｌｅ∞，１９９７，４３（２）：７３—８１．［７］鲥ｎｏｎＣ．Ｂ懈ｔｉｎｇ

ＡｃＯｗｊｌｈ

ａ

ＰｒｅｐｒｏｃｅｓＢｉｎｇｓ‘印．Ｔｌｌｅ

Ａｐｐｌｉｃ砒ｉ哪０ｆ

Ｅｖｏｌｕｔｉｏｎａｒｙ

Ｃ伽ｐｕｔｉｎｇ，ＥｖｏＷｏｒ王【ｓｈ叩８

２００２：ＥｖｏＣＯＰ，ＥｖｏｌＡＳＰ，

ＥｖｏＳＴＩＭｙＥｖｏＰＬＡＮ，Ｋｉｎｓａｌｅ，Ｉ他ｌａｎｄ，２００２．．

［８］ＧａｅｆｔｎｅｒＤ，ｃｌａｒｋＫ．ＯｎＯｐ“ｍａＪ

Ｐａ舢ｅ￡ｅ巧厶”Ａｎｆｃｏｌｏｎｙ

Ｏｐｆｉｍｉ磐

石叩Ａ１９０ｒｉｔｈｍｓ．７ｎｌｅＩｎｔｅｍａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎ

Ａｒｔｍｃｉａｌ

Ｉｎｔｅｌｌｉｇｅｎｃｅ，

ＬｍＶｅｇ∞，ＵＳＡ，２００５．

［９］Ｐｉｌａｔ

Ｍ

Ｌ，ｗｈｉｋＴ．ｕｓｉ“ｇｃｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ

ｔｏ

０ｐｔｉｍｉｚｅＡｃｓ—ＴｓＰ．

ＴｈｅＴｈｉｒｄＩｎｔｅｍａｔｉｏｎａｌＷｏｒｋｓｈｏｐ

ｏｎ

Ａｎｔ

Ａｌｇｏｒｉｔｈ哪，Ｂｎｌ８ｓｅｌＢ，Ｂｅｌ—ｇｉｕｍ，２００２．

［１０］ＭｅｙｅｒＢ．ｃｏｎｖｅｒｇｅｎｃｅＣ∞ｔｒｏｌ

ｉｎ

Ａｃ０．１１１ｅ

Ｇｅｎｅｔｉｃ锄ｄＥｖｏｌｕｔｉ∞ａｒｙ

ＣｏｍＰｕｔ毗ｉｏｎＣｏｎｆｅ他ｎｃｅ，Ｓｅａｔｔｌｅ，ＵＳＡ，２Ｉ）０４．

［１１］Ｇ蛐ｂａｌｄｅｌｋ

ＬＭ。Ｄ０ｄｇｏＭ．Ａｎｆ－Ｑ：ａｆｅｊ小ｒｃｅｍｅｎｃ】ｅ帅ｉｆＩｇ印Ｐｍ卵ｈ

ｔｏ

ｔｈｅｔｎｌｖｅ“ｎｇｓａｌｅｓｍａｎｐｍｂｌｅｍ．Ｔｈｅ１２ｔｈ

Ｉｎｔｅ珊ｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ

ｏｎ

Ｍ扯ｈｉｎｅ

ｋ肌Ｉｉｎｇ，Ｔ曲ｏｅＣｉＩｙ，ＣＡ，ＵＳＡ，１９９５．

［１２］Ｔａｉｌｌａｒｄ

Ｅ

Ｄ，ｃａＩＴＩｂａｒｄｅｌｌａ

Ｌ．Ａｄａｐｔｉｖｅｍｅｍｏｒｉ∞ｆｏｒｔｈｅＱｕａｄｒａｔｉｃ

Ａｓ．

ｓｉｇｎｍｅｎｔ

Ｐｍｂｌｅｍｓ．ＩｓｔｉｔｕｔｏＤａｌｌｅＭｏｌｌｅＤｉＳｔｕｄｉＳｕｌｌＩｎｔｅＩｌｊｇｅｎ丝Ａｎｉｆ；

ｃｉａｌｅ，ＴｅｃｈｎｉｃａｌＲｅｐｏｒｔ：ＩＤＳＩＡ－８７—９７。１９９７．

［１３］Ｔｓｔｕｔｚｌｅ，ＨＨｏ∞．Ｉｍｐｒｏｖｅｍｅｎｔｓｏｎｔｈｅ柚ｔｓｙ咖ｍ：ｉｎｔｍｄｕｃｉｎｇｔｈｅ

ＭＡＸ—ＭＩＮ锄ｔＢｙ８ｔｅｍ．ＴｈｅＩｎｔｅｍａｔｉｏｎａｌＣｏｎｆｅ即ｎｃｅ∞Ａｒｔｉ６ｃ柚Ｎｅｕ—

ｍｌ

Ｎｅ￡ｗｏｒｋｓ鲫ｄＧｅｎｅｔｉｃＡ１９０ｄｃｈ砌，Ｗｊｅｎ。Ｇｅ胂卸ｙ，１９９７．

３．３连续优化问题中的应用

４总结与展望

存在一些缺点：问题规模很大时，需要耗费很长时间才能找到可算法，它在数学上缺少严格的理论基础以及正确性和可靠性的证明。因此，蚁群算法在理论上还有很多问题尚待解决，它的应