北京Ｔ业大学工学硕十学位论文

础之上ＤｏｒｉｇｏＭ等提出了蚁群系统（ＡｎｔＣｏｌｏｎｙＳｙｓｔｅｍ，简称ＡＣＳ）ｎ训，ＡＣＳ算法作为Ａｎｔ—Ｑ算法的特例实现起来更为简单而且表现出很好的性能。Ｓｔｕｔｚｌｅ和Ｈｏｏｓ提出了最大一最小蚂蚁（Ｍａｘ－ＭｉｎＡｎｔＳｙｓｔｅｍ，简称ＭＭＡＳ）ｎ¨，ＭＭＡＳ的特点是将信息素的大小限制在一定的范围内并使用信息素平滑机制以避免算法运行时陷入停滞状态。随着人们对蚁群算法研究的不断深入，近年来Ｄｏｒｉｇｏ等提出了蚁群优化元启发（ＡｎｔＭＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎＭｅｔａＨｅｕｒｉｓｔｉｃ，简称ＡＣＯ－ＭＨ）ｎ副，把它作为用蚁群算法求解复杂问题的通用框架，并将所有符合ＡＣＯ框架的蚂蚁算法称为蚁群优化算法（ＡＣＯａｌｇｏｒｉｔｈｍ）。ＡＣＯ—ＭＨ为蚁群优化的理

Ｗ论研究和算法设计提供了技术上的保障。ＧｕｔｊａｈｒＪ在蚁群算法的收敛性方面

做出了开创性的研究，他将蚁群算法的行为简化为在一幅代表所求问题的有向图上的行走过程，进而从有向图论的角度对一种改进蚁群算法一图搜索蚂蚁系统（Ｇｒａｐｈ－ｂａｓｅｄＡｎｔＳｙｓｔｅｍ，ＧＢＡＳ）的收敛性进行了理论分析，证明了在一些合理的假设条件下，ＧＢＡＳ能以一定的概率收敛到所求问题的最优解ｎ３。１耵。ＢｌｕｍＣ和ＤｏｒｉｇｏＭ于２００４年提出了蚁群优化的超立方体框架ｎ町。

国内的学者直到上个世纪末才开始关注蚁群算法，主要研究集中于对算法的改进和应用方面。吴庆洪和张纪会等ｎ７１从遗传算法中变异算子的作用得到启发，把逆转变异机制引入到基本的蚁群算法，利用２一交换法简洁高效的特点，提出了具有变异特征的蚁群算法。覃刚力和杨家本ｎ阳提出了一种基于自适应调整信息素的改进蚁群算法，该算法根据蚂蚁所获得的解的情况，动态地调整路径上的信息素，使算法跳离局部最优。王颖和谢剑英ｎ钔通过自适应地改变算法的挥发系数以克服蚁群算法陷入局部最优的缺陷，并能够在保证收敛速度的前提下提高算法的解全局最佳性。吴斌和史忠植啪１在蚂蚁算法的基础上提出了相遇算法，提高了蚁群算法中蚂蚁周游一次的解的质量，然后将相遇算法与采用并行策略的分段算法相结合，提出了一种基于蚁群算法的ＴＳＰ问题分段求解算法。陈岐、沈洁、秦岭等乜¨提出了基于分布均匀度的自适应蚁群算法，该算法根据优化过程中解的分布均匀度，自适应地调整路径选择概率的确定策略和信息素更新策略，使算法具有更好的收敛速度和稳定性。朱庆保和杨志军啪７提出基于变异和动态信息素更新的蚁群优化算法，该算法针对ＴＳＰ问题提出了三种策略：最近节点选择策略、信息素动态更新策略和最优个体变异策略，大大提高了求解问题的速度。黄国锐、曹先彬、王煦法提出了基于信息素扩散的蚁群算法，该算法建立了更加客观真实的蚁群系统的信息素扩散模型，使相近的蚂蚁之间能更好地进行协作。

正是由于蚁群算法具有不同于传统算法的诸多优点，近年来蚁群算法已经被成功应用到许多离散及连续优化问题口３１２钔的求解中。ＤｏｒｉｇｏＭ等首先将ＡＳ算法应用于ＴＳＰ问题中胁一。随后Ｖ．Ｍａｎｉｅｚｚｏ等将ＡＳ算法应用于指派问题（ＱｕａｄｒａｔｉｃＡｓｓｉｇｎｍｅｎｔＰｒｏｂｌｅｍ，简称ＱＡＰ）田瑚１。Ａ．Ｃｏｌｏｒｎｉ等将ＡＳ算法应用于车间作业