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

１４

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

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

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

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

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

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

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

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

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

ｓｙｓｔｅｍ）

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

Ａｎｔ

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

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

Ｆ姗ｅｗｏｒｋ

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

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

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

ｔｉｎｇＡｎｔ

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

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

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

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

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

万方数据

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

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

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

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

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

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

蚁群算法与遗传算法的融合。丁建立等口¨利用遗传算法产生路径上的初始信息素分布，获得了较好的效果。对于蚁群算法与遗传算法的融合，研究主要是用遗传算法优化蚁群算法中的参数和信息素，以 …… 此处隐藏：4225字，全部文档内容请下载后查看。喜欢就下载吧 ……