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