第4期 裴小兵，等：改进猫群算法求解置换流水车间调度问题 ·773· 数、CP,表示工件i的合并概率、Waom与Wap分别 CP:=(Wdom X Pim)+(Wdep x PP) (9) 表示当前位置矩阵与相依矩阵的合并权重值、 i,y=1,2,…,;j=1,2,…,m 计算出所有工件的合并概率，并运用轮盘赌 P为位置矩阵中工件i处于位置j上的概率、 选择出区块的第2个工件及第3个工件等，具体 P为相依矩阵中工件j紧前于工件i的概率。 如图6所示。 位置矩阵 相依矩阵 位置矩阵 相依矩阵 123456 23456 23.456 1001121 001121 01202 位置矩阵“ 2012200 012200 -0130 123456 3300110 00 300110 311-000 100/S32S/S 031001 4112-10 0W32S2300 4031001 0 3/s00/5S0 5200▣ 0 5211001 50011- 0 3/5 L/S 00 L/S 6000122 6 3 0 6000122 613100- 52/s/S1/3001/s 6000232 合并概率 合并概率 小轮盘赌 工件1的合并概率=0.3×1/5)+0.7×(1/5)=0.2 工.件1的合并概率=0.3×(2/5)+0.7×(0/5)=0.12 位置31 置4位置 牛3的合并概率=0.3×(1/5)+0.7×(0/5)=0.06 工件4的合并概率=0.3×(0/5)+0.7×(1/5=0.14 工件3的合并概率=0.3×1/5+0.7×1/5=02 块 工件5的合并概率=0.3×1/5)+0.7×(3/5)=0.48 工件4的合并概率=0.3×(0/5)+0.7×(1/5=0.14 工件5的合并概率=0.3×(2/5)+0.7×(0/5)=0.12 工件6的合并概率=0.3×2/5+0.7×(15=026 ↓轮盘赌 0轮盘赌 位置3位置4位置5 位置3位置4位置5 25 256 图6以合并概率挖掘区块 Fig.6 Mining blocks by combining probability 随着区块长度的增长，总概率逐渐降低，即错 式中：h为区块编号；B为第i个区块的第l个工 误的概率越大。例如，一个由5个工件{工件1， 件；j为B的位置；m1为当前区块长度。 工件2，工件3，工件4，工件5}组成的区块，其概 具体的区块竞争如图7所示，新产生的2个 率分别为0.5、0.8、0.6、04、0.3，此区块的总概率 区块{D,D2},区块库包含3个区块{D3,D4,D}, 0.5×0.8×0.6×0.4×0.3=0.0288,若该区块由3个工件 新产生的区块D,与区块库中的D,重复出现工件 {工件1，工件2，工件3}组成，则总概率为0.5× 6,此时对D,与D3的平均概率进行比较，D,的平 0.8×0.6=0.24,由此可见，错误概率随着区块长度 均概率为0.26，大于D3的平均概率0.23，故D1取 的增长而变大。为保证区块的质量不会随着区块 代D3进入区块库中，D3被淘汰删除。D2与D,在 长度的增加而降低，设计一个阈值用以筛选上述 挖掘的区块，阈值随着迭代次数的增加由0.24增 位置11重叠，比较与D,的平均D2概率由图可知 到0.8。将符合阈值的区块暂存在区块库中，区块 D2高于D4,故淘汰D4。D,未与任何区块发生工 库中保留着本次迭代中全部符合阈值的区块。 件或位置重复，因此继续保存于区块库中。 2)区块竞争 区块 区块库 区块挖掘完成后，利用区块竞争选择竞争力 位置3位置4位置5 位置3位置4置3 较大的区块，每迭代一次，其产生的区块与区块 D,256平均概率 D128 平均概率 0.26 0.24 位置13也置14位置1 平均概率 库中的区块进行比较，最终选择其中竞争优势较 位置11位置12位置13 D1037 大的区块，更新区块库。区块进行竞争时，如果 D:91114门平均概率 0.30 0.37 位置17置18位置19 D12615平均概率 0.42 几个区块之间工件重复或者区块之间包含的位置 出现重复，利用平均概率对这几个区块比较，淘 汰概率较小的区块。 区块库 平均概率的计算方法：区块的第一个工件位 位置3位置4位置3 D256 平均概率 置矩阵概率加上其余工件的合并概率之和除以区 0.26 位置11位置12位置1 D291114 平均概率 块总长度，即可求出该区块的平均概率。平均概 0.37 位置17他置18位置19 率的计算如式(10)所示： D,2615平均概率 0.42 P+CP时 (10) 图7区块竞争 n Fig.7 The competition of blocksCPi i Wdom Wdep P dom i, j P dep i,γ 数、 表示工件 的合并概率、 与 分别 表示当前位置矩阵与相依矩阵的合并权重值、 为位置矩阵中工件 i 处于位置 j 上的概率、 为相依矩阵中工件 j 紧前于工件 i 的概率。 CPi = (Wdom × P dom i, j )+(Wdep × P dep i,γ ) i, γ = 1,2,··· ,n; j = 1,2,··· ,m (9) 计算出所有工件的合并概率，并运用轮盘赌 选择出区块的第 2 个工件及第 3 个工件等，具体 如图 6 所示。 空白 区块 轮盘赌 位置3位置4位置5 2 位置矩阵 1 2 2 3 3 4 4 5 6 5 6 0 0 3/5 0 2/5 0 0 1/5 0 3/5 1/5 0 1/5 2/5 0 1/5 1/5 0 1/5 2/5 1/5 0 0 1/5 2/5 0 1/5 0 0 2/5 1/5 0 0 1/5 1/5 2/5 1 轮盘赌 位置3 位置4 位置5 2 5 合并概率 位置矩阵 相依矩阵 工件1的合并概率 = 0.3×(1/5) + 0.7×(1/5) = 0.2 工件3的合并概率 = 0.3×(1/5) + 0.7×(0/5) = 0.06 工件4的合并概率 = 0.3×(0/5) + 0.7×(1/5) = 0.14 工件5的合并概率 = 0.3×(1/5) + 0.7×(3/5) = 0.48 工件5的合并概率 = 0.3×(2/5) + 0.7×(0/5) = 0.12 1 2 3 4 5 6 0 0 3 0 2 0 0 1 0 3 1 0 1 2 0 1 1 0 1 2 1 0 0 1 2 0 1 0 0 2 1 0 0 1 1 2 − 1 1 1 0 1 0 − 1 1 0 3 1 0 − 2 1 1 2 1 0 − 1 0 0 3 0 1 − 0 2 0 0 0 1 − 1 2 3 4 5 6 1 2 3 5 6 4 1 2 3 5 6 4 轮盘赌 位置3 位置4 位置5 2 5 6 位置矩阵 相依矩阵 合并概率 工件1的合并概率 = 0.3×(2/5) + 0.7×(0/5) = 0.12 工件3的合并概率 = 0.3×(1/5) + 0.7×(1/5) = 0.2 工件4的合并概率 = 0.3×(0/5) + 0.7×(1/5) = 0.14 工件6的合并概率 = 0.3×(2/5) + 0.7×(1/5) = 0.26 0 0 3 0 2 0 0 1 0 3 1 0 1 2 0 1 1 0 1 2 1 0 0 1 2 0 1 0 0 2 1 0 0 1 1 2 − 1 1 1 0 1 0 − 1 1 0 3 1 0 − 2 1 1 2 1 0 − 1 0 0 3 0 1 − 0 2 0 0 0 1 − 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 5 6 4 1 2 3 5 6 4 图 6 以合并概率挖掘区块 Fig. 6 Mining blocks by combining probability 随着区块长度的增长，总概率逐渐降低，即错 误的概率越大。例如，一个由 5 个工件{工件 1， 工件 2，工件 3，工件 4，工件 5}组成的区块，其概 率分别为 0.5、0.8、0.6、0.4、0.3，此区块的总概率 0.5×0.8×0.6×0.4×0.3=0.028 8，若该区块由 3 个工件 {工件 1，工件 2，工件 3}组成，则总概率为 0.5× 0.8×0.6=0.24，由此可见，错误概率随着区块长度 的增长而变大。为保证区块的质量不会随着区块 长度的增加而降低，设计一个阈值用以筛选上述 挖掘的区块，阈值随着迭代次数的增加由 0.24 增 到 0.8。将符合阈值的区块暂存在区块库中，区块 库中保留着本次迭代中全部符合阈值的区块。 2) 区块竞争 区块挖掘完成后，利用区块竞争选择竞争力 较大的区块，每迭代一次，其产生的区块与区块 库中的区块进行比较，最终选择其中竞争优势较 大的区块，更新区块库。区块进行竞争时，如果 几个区块之间工件重复或者区块之间包含的位置 出现重复，利用平均概率对这几个区块比较，淘 汰概率较小的区块。 平均概率的计算方法：区块的第一个工件位 置矩阵概率加上其余工件的合并概率之和除以区 块总长度，即可求出该区块的平均概率。平均概 率的计算如式 (10) 所示： P AVG Bi = P dom B h l + ∑n1 l=2 CPB h l n1 (10) B h l i B h l n1 式中：h 为区块编号； 为第 个区块的第 l 个工 件；j 为 的位置； 为当前区块长度。 具体的区块竞争如图 7 所示，新产生的 2 个 区块{D1，D2}，区块库包含 3 个区块{D3，D4，D5}， 新产生的区块 D1 与区块库中的 D3 重复出现工件 6，此时对 D1 与 D3 的平均概率进行比较，D1 的平 均概率为 0.26，大于 D3 的平均概率 0.23，故 D1 取 代 D3 进入区块库中，D3 被淘汰删除。D2 与 D4 在 位置 11 重叠，比较与 D4 的平均 D2 概率由图可知 D2 高于 D4，故淘汰 D4。D5 未与任何区块发生工 件或位置重复，因此继续保存于区块库中。 区块 区块库 区块库 D1 D2 D1 D2 D3 D4 D5 D5 位置3 位置4 位置5 位置3 位置4 位置5 位置3 位置4 位置5 位置11位置12位置13 位置17位置18位置19 位置13位置14位置15 位置17位置18位置19 位置11位置12位置13 平均概率 0.37 平均概率 0.26 平均概率 0.24 平均概率 0.30 平均概率 0.42 平均概率 0.26 平均概率 0.37 平均概率 0.42 2 5 6 1 2 8 10 3 7 12 6 15 2 5 6 9 11 14 12 6 15 9 11 14 图 7 区块竞争 Fig. 7 The competition of blocks 第 4 期 裴小兵，等：改进猫群算法求解置换流水车间调度问题 ·773·