第6期 印峰，等：个体速度差异的蚁群算法设计及仿真 ·531· 节点，并把该节点移动到该蚂蚁个体的禁忌表中， 速度进行初始化，跳转到2)进行下一次迭代计算； 5)当第k只蚂蚁从节点i转移到节点j后，更新 否则，停止计算。 第k只蚂蚁的速度.根据规则1构造速度增量计算 整个算法流程图如图3所示. 公式： 初始化 el(k)=el(k)+,a,r(i） (5) b,r(ij)+c 随机选择蚂蚁出发点 将初始位置写入禁忌表 式中：a,。和c。为与速度更新相关的常数，可用实 验方法确定其值的最优组合；参数α表示路径信息 根据转移概*选择下一个节点 素对蚂蚁速度的影响权重.由式(5)可知，蚂蚁速度 增量与路径残余信息素成正比，并且每只蚂蚁的一 更新禁忌表 次巡游速度是递增的，但选择较短路径的蚂蚁移动 更新蚂蚁速度 速度要快于选择较长路径的蚂蚁移动速度， 计算信总素稀放量 6)计算动态路径信息素释放量： 信息素局部更新 a, Ar(ij)+etime(d(,vel(k))' (6) N 式中：a,、b,和c,为与信息素释放量相关的常数；参 所有蚂蚁 禁忌表清0 次巡游完毕？ 初始化蚂蚁速度 数Y表示移动时间对路径信息素释放量的影响权 Y 重.时间函数根据前述的规则2构造如下： 对全局最优解进行变异处理 ia6,u()= (7) 全局信息素更新 根据上式可知，蚂蚁移动速度越快，选择的路径 越短，则移动所花的时间越短，在相应路径上释放的 计算平均节点分支数 信息素越多. N 7)信息素局部更新.第k只蚂蚁从节点i转移 达到最大迭代次数 到节点j后，按下式更新路径上的信息素： Y r(i,)=(1-p)r(i,j)+p·△r(i).(8) 结束 式中：p(0<p<1)表示路径信息素的蒸发系数，1- 图3VAC0算法流程图 p表示信息素的持久性系数，△r(i,)表示本次迭代 Fig.3 The process of VACO algorithm 路径上信息素的增量，根据式(6)计算. 8)跳转到3)重新执行上述过程，直至所有的蚂 3仿真实例 蚁巡游一次完毕. 为了检测提出的改进算法的性能，采用经典旅 9)计算当前最优路径T的巡游距离L,记录 行商(TSP)问题进行了不同的实验，并将改进算法 当前最优路径节点编号. 与几种有代表性的改进蚁群算法作了性能上的对比 10)根据规则3、规则4对最优个体进行变异操 分析.本文算法中各参数经初步优化后的取值见表 作，如果经变异产生新的更优解，则用该更优解取代 1,蚁群初始速度nit Vel取200. 当前最优解。 表1VACO算法的参数设置 11)信息素全局更新.对全局最优解所属的边 Table 1 VACO parameter setting 进行信息素更新： Ba,b。c。aa,b,c,yp x(i)=1-p·r(i》+p·(La)l, 410.011110.01110.01 H(i,j》eT. (9) 首先分别采用提出的VACO算法和蚁群优化 12)根据定义1、定义2计算当前的平均节点分 (AC0)算法对Oliver30问题进行求解.迭代次数取 支数 100,计算结果见图4，其中，曲线1和曲线3分别为 13)判断是否已达到最大迭代步长NC_max.如 VACO和AC0计算中每一代所有解取平均值的进 果未达到最大迭代次数，则对禁忌表清零，并对蚂蚁 化曲线，曲线2和曲线4分别为VAC0和AC0