·772· 智能系统学报 第14卷 此，本研究采用文献[9]中的一种猫行为混合比 工件 相依矩阵D 123456 1 23456 率选择法，具体如图2所示。 1 202 1 -01/52/5025 30 2 /5-01/500 混合比率1 3 000 3/50-1/53/50 M 4 10 4 1/51/525-1/50 1 5 00151/5-1/5 6 100- 61/53/51/500- Ma. 图4相依矩阵更新方式 0 迭代次数 Fig.4 Updating method of dependency matrix 2.4.2组合区块 图2混合比率分配 Fig.2 The allocation of mixed ratio 组合区块能够降低种群迭代复杂度，降低解 的维度，加快收敛速度。以单个机器10个工件的 该线性混合比率的计算公式为 排序为例，如图5所示，未组合区块之前母体中的 Mx=Mg+(M&-Mk.)xT (4) 工件{工件1，工件2，…，工件10}为单独的基因， To 式中：T代表迭代次数；T。代表最大迭代次数。 此时可产生10！种排列组合，而组合区块后排列 组合变为5！种，在很大程度上降低了解的维度。 2.4搜寻模式 为找出含有高竞争优势的区块，本研究从区块挖 2.4.1构建概率模型 掘与区块竞争两个步骤来组合区块。 本研究采用位置矩阵和相依矩阵来记载不同 的加工信息，位置矩阵用来表示工件和所处加工 工件图工件8 组合 工件工件8工件 工件I 工件7 区块 位置之间的关系，相依矩阵用来表示任意两个工 工件4 工件1可 工件正件冈 工件1可 件之间的加工前后顺序。 工件2 工件3 工件2工件9工件3工件6 工件9 对初始解的适应度函数值从小到大排序，选 工件6 择前s个优秀解组成优秀解集合，0={「1，「2，…，T, 图5种群迭代复杂度比较 同时位置矩阵及相依矩阵按以下方式更新： Fig.5 The comparison of iterative complexity of popula- 咸=器流手拉置上 tion (5) 1)区块挖掘 i=1,2,…,nj=1,2,…,mk=1,2,…,s 根据位置矩阵和相依矩阵模型提供的相关信 1,0=7,-0+2统 息，进行相应的区块挖掘。以随机的方式选择区 k=1 (6) 块的起始位置，产生一个符合最小长度的空白区 i=1,2,…,n;j=1,2,…,m;k=1,2,…,s 块，设区块的最小长度为3。 =化架赛工作 在空白区块中放人最适合的工件，为计算方 (7) i=1,2,…,;1=1,2,…,:k=1,2,…,s 便，将各工件在位置矩阵与相依矩阵中的累计结 果转化为概率，同时，将两矩阵的概率整合成一 10=-+2 (8) 个合并概率(combination probability,CP),利用轮 i,l=1,2,…,m:j=1,2,…,m;k=1,2,…,s 盘赌对合并概率进行挑选，其中，起始位置按照 具体位置、相依矩阵更新方式如图3、图4所示。 依据位置矩阵的概率，以轮盘赌进行选择。选出 第1个工件后，以合并概率对第2个、第3个工件 位置 位置矩阵P 123456 123456 等进行选择。经一系列研究发现，在进化前期前 001121 1001/51/52/51/5 后关系相比位置关系更能影响解序列的适应度高 012200 201/52/52/500 低，相反，在进化中后期位置关系比工件前后关 30 0110E33/500550 4 031001 403/51/5001/5 系更重要，因而在进化的不同阶段，令位置矩阵 2 1 1001 52/51/51/5001/5 的权重随着世代数由0.3增加到0.7，反之，相依 6 000122 60001/52/52/5 矩阵由0.7递减到0.3。合并概率的计算如式 图3位置矩阵更新方式 (9)所示，其中，i代表工件编码、y表示i紧前工 Fig.3 Updating method of position matrix 件号码、j表示工件i所在的位置、n表示工件总此，本研究采用文献 [9] 中的一种猫行为混合比 率选择法，具体如图 2 所示。 O MR2 MR1 迭代次数 混合比率 图 2 混合比率分配 Fig. 2 The allocation of mixed ratio 该线性混合比率的计算公式为 MR = MR1 + ( MR2 − MR1 ) ×T T0 (4) 式中： T 代表迭代次数； T0 代表最大迭代次数。 2.4 搜寻模式 2.4.1 构建概率模型 本研究采用位置矩阵和相依矩阵来记载不同 的加工信息，位置矩阵用来表示工件和所处加工 位置之间的关系，相依矩阵用来表示任意两个工 件之间的加工前后顺序。 s ∂ ∂ = {Γ1,Γ2,··· ,Γs} 对初始解的适应度函数值从小到大排序，选 择前 个优秀解组成优秀解集合 ， ， 同时位置矩阵及相依矩阵按以下方式更新： B k i j = { 1, 如果工件i位于j位置上 0, 否则 i = 1,2,··· ,n; j = 1,2,··· ,m; k = 1,2,··· ,s (5) Ti j(t) = Ti j(t−1)+ ∑s k=1 B k i j, i = 1,2,··· ,n; j = 1,2,··· ,m; k = 1,2,··· ,s (6) Y k il = { 1, 如果工件i紧邻l 0, 否则 i = 1,2,··· ,n; l = 1,2,··· ,n; k = 1,2,··· ,s (7) Ti j(t) = Ti j(t−1)+ ∑s k=1 Y k i j, i,l = 1,2,··· ,n; j = 1,2,··· ,m; k = 1,2,··· ,s (8) 具体位置、相依矩阵更新方式如图 3、图 4 所示。 位置 位置矩阵 P 工件 1 2 2 3 3 4 4 5 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 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 6 1 1 1 2 3 4 5 6 2 3 4 5 6 图 3 位置矩阵更新方式 Fig. 3 Updating method of position matrix 工件 相依矩阵 D 工件 1 2 2 3 3 4 4 5 5 6 − 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/5 3/5 1/5 0 1/5 0 − 0 1/5 0 3/5 1/5 0 − 2/5 1/5 1/5 2/5 1/5 1/5 − 1/5 0 0 0 3/5 1/5 − 0 2/5 0 0 0 1/5 − 6 1 1 1 2 3 4 5 6 2 3 4 5 6 图 4 相依矩阵更新方式 Fig. 4 Updating method of dependency matrix 2.4.2 组合区块 ··· 组合区块能够降低种群迭代复杂度，降低解 的维度，加快收敛速度。以单个机器 10 个工件的 排序为例，如图 5 所示，未组合区块之前母体中的 工件{工件 1，工件 2， ，工件 10}为单独的基因， 此时可产生 10！种排列组合，而组合区块后排列 组合变为 5！种，在很大程度上降低了解的维度。 为找出含有高竞争优势的区块，本研究从区块挖 掘与区块竞争两个步骤来组合区块。 组合 工件1 区块 工件1 工件2 工件3 工件2 工件3 工件4 工件5 工件6 工件7 工件8 工件9 工件10 工件4 工件5 工件6 工件8工件7 工件9 工件10 图 5 种群迭代复杂度比较 Fig. 5 The comparison of iterative complexity of popula￾tion 1) 区块挖掘 根据位置矩阵和相依矩阵模型提供的相关信 息，进行相应的区块挖掘。以随机的方式选择区 块的起始位置，产生一个符合最小长度的空白区 块，设区块的最小长度为 3。 i γ i i n 在空白区块中放入最适合的工件，为计算方 便，将各工件在位置矩阵与相依矩阵中的累计结 果转化为概率，同时，将两矩阵的概率整合成一 个合并概率 (combination probability，CP)，利用轮 盘赌对合并概率进行挑选，其中，起始位置按照 依据位置矩阵的概率，以轮盘赌进行选择。选出 第 1 个工件后，以合并概率对第 2 个、第 3 个工件 等进行选择。经一系列研究发现，在进化前期前 后关系相比位置关系更能影响解序列的适应度高 低 [17] ，相反，在进化中后期位置关系比工件前后关 系更重要，因而在进化的不同阶段，令位置矩阵 的权重随着世代数由 0.3 增加到 0.7，反之，相依 矩阵由 0.7 递减到 0.3。合并概率的计算如式 (9) 所示，其中， 代表工件编码、 表示 紧前工 件号码、j 表示工件 所在的位置、 表示工件总 ·772· 智 能 系 统 学 报 第 14 卷