蚁群优化算法的搜索偏离性研究

蚁群算法对各类问题存在着不同程度的搜索偏离性，这会对蚁群算法的性能产生负面影响，甚至不能收敛到全局最优解。本课题从如下几个方面研究蚁群算法的搜索偏离性: (1) 研究产生蚁群算法搜索偏离的更多的原因和更全面的分类标准，提出反馈性和交互性两种新的搜索偏离，对这些搜索偏离的完全性、分类标准的合理性进行论证。(2)提出并研究用量化的指标来衡量搜索偏离的程度, 提出解分量的质量数、整体选择概率等概念来建立衡量偏离的指标，研究所提出的指标的合理性、有效性。(3) 研究有效地预测及避免搜索偏离的方法，提出通过信息素发展趋势的静态分析来预测偏离性的思想，提出在每个解分量上加上学习因子来避免搜索偏离的思想。本项目的研究有利于我们更全面地识别蚁群算法的搜索偏离, 分析它存在的原因及对算法性能的影响，可以使我们在应用中针对具体问题有效地预测和防止搜索偏离的发生，提高蚁群算法的优化性能、成熟性及实用性。

蚁群优化(ACO)算法是一种元启发式的随机搜索算法，有很强的优化能力，适合于解决传统搜索方法难于解决的复杂问题。蚁群算法对各类问题存在着不同程度的搜索偏离性，这会对蚁群算法的性能产生负面影响，甚至不能收敛到全局最优解。本课题研究蚁群算法的搜索偏离性的产生原因、衡量指标以及有效地预测及避免搜索偏离的方法。在已经发现的蚁群优化算法的两种搜索偏离（即表征性偏离、构建性偏离）之外，我们提出了两种新的偏离，即反馈性偏离和交互性偏离。我们给出了反馈性偏离和交互性偏离的定义，并且举例说明了它们的存在。我们针对各种偏离提出了衡量偏离大小的评价标准，并对该评价标准进行了测试，用实验证明了我们的评价标准的合理性和有效性。我们提出了预测和纠正蚁群算法的搜索偏离的有效方法。我们分别对传统的蚁群算法和我们的方法在不同问题上的收敛性进行了理论证明，我们的实验结果也充分说明了我们改进的蚁群算法可以有效地纠正搜索偏离，最终收敛于全局最优解。为了避免蚁群算法的搜索偏离，加强解群体的多样性，我们提出了三种改进的蚂蚁路径选择策略，以增加解的多样性，使改进的算法能够有效地避免搜索偏离。我们从理论上证明了所提出的各种选择策略比传统的“轮盘赌”方式有更好的性能, 并用实验验证了三种选择策略的有效性。实验结果表明，我们所提出的方法可以有效地增加解的多样性，避免了搜索偏离的产生。我们利用蚂蚁在图中游走的所展示的很强的优化性能，提出复杂网络中的社区检测的蚁群算法，解决复杂度较高的重叠社区挖掘和动态社区挖掘的问题。在多个实际数据集上的实验结果表明，我们的算法不但能较快地识别实际网络的社区结构，而且可以获得比其他方法更好的划分效果。我们还用上述理论成果解决数据挖掘、生物信息学、组合优化等领域的问题，取得了很好的应用效果.