·530 智能系统学报 第4卷 径，即系统不再搜索较好的解，称为停滯现象 如下变异操作规则： 定义2设ra(r,s)、T✉(r,s)分别为与节点r 规则3采用对访问节点序列按排列组合的方 相连的边上最大、最小信息素值，令 法进行编码，即某个巡回路径的染色体是该巡回路 8(r）=Tmm(r,s）-Tn(r,s). 径的节点序列.每完成一次迭代计算，只对当前最优 对某个给定的入(0<入<1)，在所有与节点r相 解进行变异操作 连的边中，信息素量大于A8(r)+Tmi(r,s)的边的 规则4对最优个体重组分区间进行，操作区 数量即为节点r的节点分支数， 间长度取3，变异适度函数取节点连线距离，交换区 定义3设(r)为节点r(r=1,2,…,n)的节点 间内2节点的位置，并比较交换前后区间节点之间 分支数，N为节点总数，则平均节点分支数定义为 的距离和，如果交换后的区间节点之间的距离和小 名职 (2) 于交换前，则交换原节点序列相应2节点位置，否则 保留区间内原节点序列顺序，进行下一个操作区间 由于信息素蒸发的影响，较差解路径上的信息 并重复相同的处理过程. 素量将越来越少，节点上连接边信息素最大值和最 小值的差量将越来越大，根据定义2，节点分支数将 2 VACO算法构造 随之减少.当平均节点分支数趋于2时，意味着所有 1)初始化，设置蚂蚁的初始速度vel=nitVel, 的蚂蚁都选择了同样的路径，即算法出现停滞现象. 用禁忌表abuk记录蚂蚁k当前所走过的节点，a- 如果此时当前解还未达到最优，则说明算法陷入了 lowed.={C-tabu,表示蚂蚁k下一步允许选择的节 局部最优.利用变异算法局部寻优能力强的特点对 点，其中，C为所有节点的集合；其余初始化过程与 当前最优个体进行变异，可加快局部寻优速度，并且 蚁群系统(ACS)算法[3]相同. 有助于算法跳出局部最优， 2)将m只蚂蚁随机分配到n个节点，并将出发 在遗传算法中，变异处理过程一般是先随机地 节点置人禁忌表abuk: 选择2个位置点，然后对区间之间的节点位置按所 3)对处于第i个节点的第k只蚂蚁，依转移概 取适度函数值大小进行重排.为了表现变异过程的 率式(3)[o1选择连接的下一个节点方 随机性，变异操作的区间长度是随机的.然而，区间 长度过大会增加算法搜索的随机性和盲目性，特别 p:(i,j)= 地，对于算法已收敛到局部较优解的情况，变异区间 「arg,ma.r(i)(i》},q≤q(a(t): 较大时很难找到更优解，为此，提出一种效果较为理 ts, 其他 想的连续小区间变异策略：如图2所示，将各节点按 (3) 排列顺序划分为若干个连续子区间，每个区间长度 式中： 取3.以区间i为例，交换b、c2节点的位置显然并 (4) 不影响区间i与外区间节点间的连接关系；现在只 9(A()=(2 n i 需比较交换前后区间内节点距离和大小，即比较 A(t)∈[2，n]表示算法在第t次迭代时的平均节点 D1=D(a,b)+D(c,d)和D2=D(a,c)+D(b,d)的 分支数；n表示节点数；q为[0,1]上分布的随机数； 大小，如果D2<D,说明(acbd)序列组合要优于 (i,)表示节点i与节点j之间的信息素量；n(i,) (abcd),交换原节点序列中b、c的位置，否则保留 表示节点i与节点之间的启发式因子，一般取2节 区间i原节点顺序 点间距离的倒数；B为权重系数. 蚂蚁在选择下一个节点之前先随机生成q,如 果q值小于q(入(t)),则从节点i到所有可行的节 点中找出概率最大的节点，即为下一个要到达的节 图2变异区间划分规则 点；否则按如下概率公式选择下一个节点： Fig.2 Division rules of interval variation P(i,)= 这种局部变异调整后的搜索效率很高，在蚁群 x(i)(i,) 算法迭代前期有助于提高算法的搜索速度；在算法 ,j∈allowed:; r(i,)(i,) 迭代后期，算法陷人局部最优，其宏观表现是蚂蚁的 巡游线路出现局部路径交叉，显然，采取局部调整的 0， 其他 策略对于这一情况的处理是非常有效地.综上，定义 4)修改禁忌表：选择节点后将蚂蚁移动到新的