蚁群算法的理论与性能研究

来源：互联网   发布日期：2011-09-26 13:13:13   浏览：8527次  

蚁群优化算法是一种新型的求解复杂优化问题的元启发式算法，它是由意大利学者m.dorigo等人受到自然界中真实蚁群集体行为的灵感而首先提出来的，并用来解决离散优化问题。由于蚁群算法具有稳健性、全局性、普遍性、分布式计算等优点，其理论研究不断深入，应用领域不断扩大。大量实验结果表明，它在解决许多组合优化问题时都能表现出较好的求解能力，经过了众多国内外学者不断地对其进行扩展和改进，蚁群算法正经历着一个不断发展和完善的过程。 虽然通过对大量应用问题的求解，已经显示出蚁群优化算法的高效性，但它的成功主要在实验层次上，很少有理论来解释利用蚁群算法为什么能够成功地解决这些问题。它能否保证所得到的解一定是全局最优解，还有什么问题利用蚁群算法不能解决，对于能够解决的问题，它的时间复杂性到底有多大。因此有必要研究蚁群优化算法的欺骗性问题。由于蚁群算法具有本质上的并行特性，我们需要研究如何高效率地对它进行并行化，如何平衡通信开销与加速比之间的关系。蚁群算法的一个主要缺点是不能直接解决连续优化问题。以往解决此类问题的方案，大部分改变了蚁群优化算法的基本结构，不能充分发挥蚁群优化算法的正反馈机制的优势。因此有必要研究在解决连续优化问题时该如何保持本质模型的不变，如何充分利用信息素和启发式信息，保证解的精确性的同时能加速收敛速度。 本文针对蚁群算法的上述问题，作了下面的研究。 (1)研究蚁群算法求解欺骗性问题时的收敛性和时间复杂度。以n-bit陷阱问题为例，证明了蚁群算法一阶欺骗性问题在一定的信息素初始值条件下，不满足解的收敛性，但满足值的收敛性。我们证明了，使用信息素带限的蚁群算法mmas求解n-bit陷阱问题达到最优解的时间复杂度为o(n2m.logn)，这里n为问题的规模，m为蚂蚁的个数。同时，我们的实验结果也验证了上述结论的正确性。 (2)提出了一种mpp上的自适应的并行蚁群算法paco。该算法在两个方面进行了重要改进来加强算法的性能。一方面，我们提出一种处理机之间的信息交流策略，使得每个处理机可自适应地选择另外一个处理机来交流信息并更新信息素。另一方面，我们还提出一种根据解的多样性来自适应地调节信息交流周期的方法，以在加强优化能力的同时避免早熟收敛，以增加解的多样性。我们对并行蚁群算法paco值的收敛性进行了分析与证明。我们用标准的旅行商问题在大规模并行机上做了测试，实验结果表明，我们算法在收敛速度，加速比，稳定性和准确性各方面都要优于别的并行蚁群算法。 (3)提出了一种用蚁群算法求解连续空间优化问题的方法。该方法保持了基本蚁群算法的基本框架，将传统蚁群算法中蚂蚁由解分量的信息素和启发式的乘积值按比例来决定取值概率的方式，改为根据连续的概率分布函数来取值。我们还将函数在各个维上的极值点方向作为蚂蚁搜索的启发式信息。在标准测试函数上的试验结果显示，我们的算法与其他类似的算法相比，不但具有较快的收敛速度，而且能够有效地提高解的精确性，增强了算法的稳定性。

赞助本站