·544· 智能系统学报 第14卷 初始4 初始信息素相依矩阵 2)构建区块 4624市选择 形成 1 矩阵 To To.. 区块是简短的染色体片段，本研究通过学习 4最优 ☐2455 to-to to To To 链接关系构建区块。首先确定区块的最小长 4.024E56 度，然后随机选择起始位置，最后为各位置选择 Jto ToTo 工序。在区块最小长度内，起始位置采用位置信 图3初始相依信息素矩阵 息素矩阵中的信息选择工序，如图7，假设P> Fig.3 Initially dependent pheromone matrix P>…>P,选择工件放入起始位置S1。其他 初始4 初始信息素相依矩阵 位置采用位置信息素矩阵和相依信息素矩阵的合 4624阝选择 形成S 并信息，以轮盘赌选择法(roulette wheel section, 4246d53: 最优 矩阵国 6666 25西一6-6 RWS)对工序进行筛选，已经人选的工件不再进 4.24356: …… 行筛选，如图8，假设CP2最大，选择工件2放入 6.06 位置S2 图4初始位置信息素矩阵 起始位置 Fig.4 The initial position pheromone matrix t f1 ②更新信息素矩阵 由遗传算法产生的最新一代的前30%适应 To Ta 度较高的染色体更新信息素矩阵，更新过程如图5， 更新公式如式(2)： 图7起始位置工序挑选 Fig.7 Starting position process selection Tij(t+1)=(1-p)xTi(t)+pATg(t+1) △rt+1)= ∫1/L,若蚂蚁经过路径(i,) (2) 位置信息素矩阵 相依信息素矩阵 0,其他 S S2 S3--Sm JJ2J…J 式中：表示每对相邻工件（伍，）间的信息素浓 fn-- tn …t 度；Tt+l)表示更新的t;p表示信息素的蒸发 t t到 速率。 初始4 前30%条染色体 新相依信息素矩阵 4,回6245D降序4,45362 CP=W(tnltz+tx+...+t))+W"(ta/(ta+ta+..+t)) 兴9 CP=W(il+is+...+i))+W(tl(+i+...+)) 4,②46卫53 CP=W(ta/(a+t+..+r2)+W(《2+i+..tt)》 4.24356 4243▣ JTa Ta Ta..Ty 假设CP>CP>A>Cp, 选择J 图5更新相依信息素矩阵 Fig.5 Update dependent pheromone matrix 图8区块最小长度内其他位置工件选择 同理，得到更新的位置信息素矩阵如图6。 Fig.8 Workpiece selection at other positions within the 更新公式如式(3)： block's minimum length T(t+1)=(1-p)xT()+pAT(+1) 当出现两个或多个较大值时随机选择。位置信 ∫1/L,若蚂蚁经过的第m个节点为节点i △rt+1)=0,其他 息素浓度概率计算公式为 (3) m=1,2,…,n ∑tm (4) 式中：t为蚂蚁经过的第m个节点为节点i时在 ieun 节点i处释放的信息素。 相依信息素浓度概率计算公式为 T Pu-T i,j=1,2,…,n (5) S S S 合并概率计算公式 T. CP,=(W×P)+(W'×Pm,ijm=1,2,…n(6) 式中：i表示工件号；j表示i所连接的上一个工 T 件号；m表示染色体上的工件的位置；n表示染色 图6更新的位置信息素矩阵 体长度；Pm表示工件i与位置m在位置矩阵的概 Fig.6 Updated positional information matrix 率；P表示相依矩阵中工件j相连于工件i之后1 6 2 4 5 3 2 4 6 1 5 3 1 2 4 3 5 6 选择 最优 初始 μ μ最优 1 2 4 3 5 6 形成 矩阵 初始信息素相依矩阵 … J1 J2 J3 … Jj J1 - … J2 - … J3 - … … … … … … Ji … - μ1 μ2 μn τ0 τ0 τ0 τ0 τ0 τ0 τ0 τ0 τ0 τ0 τ0 τ0 … 图 3 初始相依信息素矩阵 Fig. 3 Initially dependent pheromone matrix 1 6 2 4 5 3 2 4 6 1 5 3 1 2 4 3 5 6 选择 最优 初始 μ μ最优 1 2 4 3 5 6 形成 矩阵 初始信息素相依矩阵 … S1 S2 S3 Sj J1 J2 J3 Ji μ1 μ2 μn τ ′ 0 τ ′ 0 τ ′ 0 τ ′ 0 τ ′ 0 τ ′ τ 0 ′ 0 τ ′ 0 τ ′ 0 τ ′ 0 τ ′ 0 τ ′ 0 τ ′ τ 0 ′ 0 τ ′ 0 τ ′ 0 τ ′ 0 … … … … … … … … … … 图 4 初始位置信息素矩阵 Fig. 4 The initial position pheromone matrix ②更新信息素矩阵 由遗传算法产生的最新一代的前 30% 适应 度较高的染色体更新信息素矩阵，更新过程如图 5， 更新公式如式 (2)： τi j(t+1) = (1−ρ)×τi j(t)+ρ∆τi j(t+1) ∆τi j(t+1) = { 1/L, 若蚂蚁经过路径(i, j) 0, 其他 (2) τi j i, j τi j(t+1) τi j ρ 式中： 表示每对相邻工件 ( ) 间的信息素浓 度； 表示更新的 ； 表示信息素的蒸发 速率[12]。 12 τ 新相依信息素矩阵 J1 J2 J3 … Jj J1 - … J2 - … J3 - … … … … … - … Ji … 4 5 3 1 6 2 2 4 6 1 5 3 6 2 4 5 3 1 降序 排列 更新 前 30% 条染色体 1 6 2 4 5 3 2 4 6 1 5 3 1 2 4 3 5 6 初始 μ … … μ1 μ2 μn μ1 μ2 μj τi1 τ31 τ32 τ23 τ13 τ12 τ21 τ3j τ2j τ1j τi2 τi3 τij 图 5 更新相依信息素矩阵 Fig. 5 Update dependent pheromone matrix 同理，得到更新的位置信息素矩阵如图 6。 更新公式如式 (3)： τ ′ mi(t+1) = (1−ρ)×τ ′ mi(t)+ρ∆τ ′ mi(t+1) ∆τ ′ mi(t+1) = { 1/L, 若蚂蚁经过的第m个节点为节点i 0, 其他 (3) τ ′ mi m i i 式中： 为蚂蚁经过的第 个节点为节点 时在 节点 处释放的信息素。 S1 S2 S3 … Sm J1 … J2 … J3 … … … … … … … Ji … τ ′ 11 τ ′ 21 τ ′ 12 τ ′ 13 τ ′ 22 τ ′ 23 τ ′ 31 τ ′ 32 τ ′ 33 τ ′ i1 τ ′ i2 τ ′ i3 τ ′ im τ ′ 3m τ ′ 2m τ ′ 1m 图 6 更新的位置信息素矩阵 Fig. 6 Updated positional information matrix 2) 构建区块 P ′ 11 > P ′ 21 > ··· > P ′ i1 J1 S 1 CP2 J2 S 2 区块是简短的染色体片段，本研究通过学习 链接关系[13]构建区块。首先确定区块的最小长 度，然后随机选择起始位置，最后为各位置选择 工序。在区块最小长度内，起始位置采用位置信 息素矩阵中的信息选择工序，如图 7，假设 ，选择工件 放入起始位置 。其他 位置采用位置信息素矩阵和相依信息素矩阵的合 并信息，以轮盘赌选择法 (roulette wheel section， RWS)[13]对工序进行筛选，已经入选的工件不再进 行筛选，如图 8，假设 最大，选择工件 放入 位置 。 S1 S2 S3 … Sm J1 P ' 11 P ' 12 P ' 13 … P ' 1m J2 P ' 21 P ' 22 P ' 23 … P ' 2m J3 P ' 31 P ' 32 P ' 33 … P ' 3m … … … … … … Ji P ' i1 P ' i2 P ' i3 … P ' im J1 S1 S2 S1 S2 S3 … Sm 起始位置 J1 … J2 … J3 … … … … … … … Ji … τ ′ 11 τ ′ 21 τ ′ 12 τ ′ 13 τ ′ 22 τ ′ 23 τ ′ 31 τ ′ 32 τ ′ 33 τ ′ i1 τ ′ i2 τ ′ i3 τ ′ im τ ′ 3m τ ′ 2m τ ′ 1m 图 7 起始位置工序挑选 Fig. 7 Starting position process selection 位置信息素矩阵 … … … … … … … … … … … J1 J2 J3 … Jj - … - … - … … … … … … … … - CP2=W'* (τ ′ 22/(τ ′ 22+τ ′ 32+…+τ ′ i2 ))+W* (τ ′ 21/(τ ′ 21+τ ′ 31+…+τ ′ i1 )) CP3=W'* (τ ′ 32/(τ ′ 22+τ ′ 32+…+τ ′ i2 ))+W* (τ ′ 31/(τ ′ 21+τ ′ 31+…+τ ′ i1 )) CPi=W'* (τ ′ i2 /(τ ′ 22+τ ′ 32+…+τ ′ i2 ))+W* (τ ′ i1 /(τ ′ 21+τ ′ 31+…+τ ′ i1 )) … J1 J2 S1 S2 相依信息素矩阵 假设 CP2>CP3>Ă>Cpi 选择J2 S1 S2 S3 Sm J1 J2 J3 Ji τ ′ 11 τ ′ 21 τ ′ 12 τ ′ 13 τ ′ 22 τ ′ 23 τ ′ 31 τ ′ 32 τ ′ 33 τ ′ i1 τ ′ i2 τ ′ i3 J1 J2 J3 Ji τ ′ 21 τ ′ 12 τ ′ 13 τ ′ 1j τ ′ 2j τ ′ 3j τ ′ 23 τ ′ 31 τ ′ 32 τ ′ i1 τ ′ i2 τ ′ i3 τ ′ im τ ′ 3m τ ′ 2m τ ′ 1m 图 8 区块最小长度内其他位置工件选择 Fig. 8 Workpiece selection at other positions within the block's minimum length 当出现两个或多个较大值时随机选择。位置信 息素浓度概率计算公式为 P ′ im = τ ′ mi ∑ i∈uns τ ′ mi i, m = 1,2,··· ,n (4) 相依信息素浓度概率计算公式为 Pi j = τi j ∑ i∈uns τi j , i, j = 1,2,··· ,n (5) 合并概率计算公式 CPi = (W × Pi j)+(W′ × P ′ im), i, j,m = 1,2,··· ,n (6) i j i m n P ′ im i m Pi j j i 式中： 表示工件号； 表示 所连接的上一个工 件号； 表示染色体上的工件的位置； 表示染色 体长度； 表示工件 与位置 在位置矩阵的概 率； 表示相依矩阵中工件 相连于工件 之后 ·544· 智 能 系 统 学 报 第 14 卷