蚁群算法理论、应用及其与其它算法的混合

意大利学者Dorigo M．，Maniezzo V．和Colorni A．于1992年通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法—蚁群优化(ACO)。该算法的出现引起了学者们的极大关注，在过去短短十多年的时间里，已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛的应用，并取得了较好的效果。 本论文围绕蚁群算法的理论及其应用，就如何解决非线性整数规划问题、连续性优化问题、聚类问题、与其它算法混合以及收敛性进行了较为深入、系统的研究。本文的主要研究成果包括： (1) 提出了一种新的蚁群算法来求解无约束的整数规划问题。蚂蚁在整数空间内运动，同时在路径上留下激素，以此引导搜索方向。对蚁群算法参数的合理选取进行了实验分析，给出了算法参数选取的基本原则。数值试验计算结果表明该方法比较有效，并具有通用性。对几个典型的整数规划问题，如武器-目标分配、多处理机调度、可靠性优化等问题，根据各问题的特点，采用了不完全相同方法，并与其他方法作了比较，效果比较有效。提出了一种求解旅行商问题的多样信息素的蚁群算法。根据蚁群算法信息素更新的特性，把蚁群的三种不同的信息素更新方式混合在一起，既利用了局部信息，又考虑了整体信息，将局部搜索和全局搜索相结合，使收敛性得到提高。旅行商问题的仿真实验结果表明了该混合算法的有效性。提出一种解决连续优化问题的蚁群算法。把连续解空间分成若干空间网格点，采用蚁群算法找出信息量大的空间网格点，缩小变量范围，继续找出信息量大的空间网格点，直到网格的间距小于预先给定的精度。 (2) 对模式识别中典型问题-聚类问题进行了研究，提出了两种求解聚类问题的蚁群算法。一种方法是模拟蚂蚁寻食过程，蚂蚁在模式样本到聚类中心的路径上留下外激素，外激素引导聚类过程；另一种是与K-均值算法混合，利用K-均值方法的结果作为初值，根据分类结果更新信息素。测试数据显示与K-均值算法混合的算法效果相当好。 (3) 提出了与模拟退火算法混合的两种算法。一种是在模拟退火算法中运用蚁群算法思想找邻域的解，称为蚁群模拟退火算法，并用该算法解决圆排列问题；另一种是由模拟退火算法生成初始信息素分布，然后由蚁群算法根据累计更新的信息素找出若干组解后，再经过模拟退火算法在邻域内找另外一个解的操作，得到更有效的解，称为模拟退火蚁群算法，并用该算法解决旅行商问题。 (4) 根据蚁群算法与遗传算法的特性，提出了与遗传算法混合的蚁群算法。由遗传算法生成初始信息素分布，在蚂蚁算法寻优中，采用遗传算法的交叉和变异的策略，得到更有效的解。