第6期 印峰，等：个体速度差异的蚁群算法设计及仿真 ·529· 调整过程.上述研究结果表明，增加全局最优解的使 过程要快于蚁群2. 用频率，可以使算法获得较好的性能.对较优解的强 2)同一蚁群中蚂蚁个体路径寻优比较. 化有助于加快算法的收敛速度，同时也容易引起停滞 对于以相同速度移动的同一蚁群中的不同个 现象，使算法陷入局部最优.针对该问题，目前提出的 体，选择较短路径ABD移动的个体完成一次巡游的 有效的解决策略可归结于：1)人为限制信息素的总 时间要快于选择较长路径ACD的个体；因此，在相 量，避免路径之间信息素差量过大：2)引入判决因 同时间间隔内，较短路线ABD上积累的信息素更 子，根据定性的分析判断蚁群当前的内部状态，进而 多，其被选择的机会相应更大，随着该过程的继续，2 通过对相关参数的动态调整避免停滞现象⑧，10,3)将 条道路上的信息素数量的差距将越来越大，直至绝 蚁群算法与其他智能方法相结合，在加快局部搜索的 大多数蚂蚁都选择了最短路径 同时提高解的多样性山 通过对于真实蚂蚁路径寻优过程的观察可知， 针对上述问题，本文做了两方面的工作：1)提 其寻优过程的快慢不仅与选择的移动路径有关，而 出一种改进的蚁群算法VACO(AC0 algorithm based 且与其移动速度相关.即有如下关系成立： on ant velocity),通过构造与路径和蚂蚁个体速度相 Search_.time d(i》 vel() (1) 关的时间函数，并建立与时间函数相关的动态信息 素释放机制，使得搜索过程兼顾局部和全局信息，加 式中：d(ii)为2节点连线距离，vel(k)表示第k只 快了在较优路径上信息素正反馈的过程，提高了算 蚂蚁的移动速度.根据式(1)，蚂蚁移动速度越快， 法的收敛速度；2)采取一种连续变异策略，在加快 选择的路径越短，搜索时间就越快.不同于真实蚂蚁 局部搜索过程的同时可有效防止算法陷入局部最 在连续时间内的路径寻优过程，人工蚂蚁采取离散 优.实验结果表明，改进后的算法在收敛性和对较好 的搜索机制，因此不能用蚂蚁速度直接衡量算法寻 解的探索方面得到一定程度的改善， 优的快慢。 1 VACO算法原理分析 由前面分析可知，从整体上观察，完成一次搜索 时间较快的真实蚂蚁个体在移动路径上释放的信息 1.1考虑蚂蚊个体速度的信息素释放机制 素相对较多.如果给人工蚁群设置一个初始“速 以自然界真实蚂蚁路径寻优过程为对象，考虑 度”，并建立某种激励机制使得较优个体“移动速 如下2种情况： 度”呈更快的增长趋势，同时根据式(1)关系构造蚁 1)2组不同速度的蚁群路径寻优比较， 群的路径信息素更新方式，此时可以采用信息素释 日标点 日标点 放量间接描述蚂蚁的寻优速度，据此定义如下的算 法构造规则： d=2 d= d=2. 规则1假设蚁群具有一定的初始速度nitVel, 并且每移动一个步长，第k只蚂蚁的速度增加 △vel(k),其中，蚂蚁速度的增量△vel(k)与路径残 d=2 d d=2 余信息素量成正比.每完成一次迭代计算，对蚂蚁的 ● 速度进行初始化. 起始点 起始点 规则2路径信息素释放量为一个与搜索时间 (a）蚁群1 (h)蚊群2 相关的函数，该函数值由移动路径和蚂蚁速度决定， 图1不同蚁群寻优速度比较 路径长度越短，蚂蚁速度越快，则在该路径上释放的 Fig.1 Comparison of the path optimization speed between 信息素数量越多. different colonies 引入蚂蚁个体运动速度递增的机制，可以加快 如图1所示，在起始点和目标点之间有2条道 信息素在较优路径上信息素正反馈的过程，从而可 路：ABD和ACD,其长度分别为4和6.蚁群1和蚁 以提高蚂蚁的搜索效率， 群2分别以速度1和2匀速移动，并且1>2，假 1.2带变异机制的防停滞策略 设这2种群采取完全相同的路径寻优机制.显然，蚁 根据文献[10,13]，对蚁群算法停滯及相关概 群1完成一次巡游的时间要快于蚁群2，在相同时 念定义如下： 间间隔内，蚁群1在较优路径ABD上信息素的积累 定义1在蚂蚁搜索过程中，由于较好路径上的信 量要大于蚁群2，随着该过程的继续，蚁群1的寻优 息素远大于其他边时，造成所有蚂蚁都选择同样的路