蚁群算法的改进策略

自蚁群算法提出以来，得到了不断的改进和发展，以下是若干较为有效的改进机制。

1.精英策略

遗传算法中的精英策略（elitist strategy）会保留每一代中适应值最高的个体，而蚁群算法中的精英策略则在每次搜索完成后给最好解以额外的信息素增量以保持最好解的吸引力（Bullnheimer et al.，1997）。在蚁群算法中，找到最好解的蚂蚁被称为精英蚂蚁（elitist ant）。该系统中，最好解上的边会获得额外的信息素增量：

其中，σ是精英蚂蚁的数量，L*是已知最短回路的长度，Q是一只蚂蚁在整个搜索过程中释放的信息素总量。

Bullnheimer等（1997）的计算测试表明，精英策略有助于蚁群在早期就找到更好解，但是精英蚂蚁过多也容易导致早熟收敛。

2.最大最小蚂蚁系统

将蚂蚁的搜索行为集中到最优解附近可以提高解的质量和收敛速度，但这样的搜索方式容易导致早熟收敛现象。Stützle和Hoos（1996）提出了最大最小蚂蚁系统（max-min ant system，MMAS）以防止早熟收敛现象的发生。

与普通蚂蚁系统相比，最大最小蚂蚁系统有以下特点：

（1）在蚂蚁系统中，蚂蚁走过的所有边都进行信息素更新；而在MMAS中，只对当前蚁群中找到最好解的蚂蚁所走过的边进行更新。(www.xing528.com)

（2）在蚂蚁系统中，信息素浓度不受限制，从而使得一些边上的信息素浓度远高于其他边，阻碍了蚂蚁进一步搜寻其他解的可能性；而在MMAS中，每条边的信息素浓度都被限制在[τmin，τmax]区间内，从而防止不同边之间的信息素浓度差距过大。

（3）为使蚂蚁在算法的初始阶段能够更多地搜索新的路径，将各条边的初始信息素浓度设定为τmax；在蚂蚁系统中一般是设定一个较小的初始值τ0。

（4）为了扩展蚁群的搜索空间，MMAS引入了平滑机制，缩小各条边上信息素浓度的差异。

3.混合蚁群算法

蚁群优化算法的守护作业可以引入不同的优化技术，从而提高算法的搜索效率。遗传算法提供了很多可以参考的技术，包括其初始种群，各类遗传算子，都是改进蚁群算法的有效途径。例如，丁建立等（2003）提出将遗传算法融入蚁群算法中，其主要思想是在算法的前期充分利用遗传算法的快速全局搜索能力，产生有关问题的初始信息素分布，从而弥补了蚁群算法在初期由于信息素匮乏导致的算法过慢；在算法后期充分利用蚁群算法的并行性、正反馈性和求精解效率高等特点。

吴庆洪等（1999）受到遗传算法中变异操作的启发，提出了具有变异特征的蚁群算法，在蚁群算法中引入变异机制，采用逆转变异算子，以此增加蚁群搜索时所需的信息量。这种机制充分利用了两元素置换（2-opt）方法简洁高效的特点，使蚁群算法有较快的收敛速度。

Shou（2006）在蚁群算法中引入了遗传算法中的交叉算子，将蚁群算法搜索得到的路径进行交叉运算，产生的子代如果得到较好的解，就相应更新该路径上的信息素，从而加速信息素的更新。Shou（2006）也引入了逆转变异算子，并将其与遗忘策略（Merkle et al.，2002）相结合，以防止算法早熟收敛。