第17卷 智能系统学报 ·462· s=1时，将分派到在同一台机器处理的工件按照 E.MP MMM MH M MH M ME MS 最短处理时间规则进行排序，当s>1时，对同一台 ! 机器上处理的工件采用先到先加工规则生成处理 E:M MMM MMM MM MS 序列，然后基于最早空闲机器原则依次将各工件 ↓ 安排在所分配机器。对于工件的忽略工序，则按 D.M MME MMMMM MP M 照约束式(3)确定其在忽略工序的完工时间。 MMMMMM MH MM MS D:MM ME N MM MHM M MS 图4均匀两点交叉（g1) MMM MP MMMM MM Fig.4 Uniform two-point crossover (g=1 MMM MR MM MP MM MS 采用自适应更新策略确定交叉概率专，用以确 定是否执行上述交叉操作，计算如下： MMMMMM MM MM 5-传s-5B+F-n F(g) F(g)≥Fawe 图2初始种群 Fig.2 Initial population F(g)<Favg 式中：A为当前迭代数；B为最大迭代数；Fw为当 本文的目标是最小化最大完工时间，故将适 前种群的平均适应度值。 应度函数表示为目标函数的倒数，即个体g的适应 2.3变异操作 度函数为F(g)=1/Cmax(g)。采用轮盘赌选择法，个 体适应度值越大，被选择的概率也越大。 变异操作是根据变异概率通过改变父代个体 2.2交叉操作 的机器号以产生子代个体的过程。本文提出了基 于随机机器选择的单点变异和基于机器最短处理 采用单点交叉和均匀两，点交叉两种方式执行 时间的多点变异两种方式。 交叉操作。在0和1中随机生成一个整数v,当 1)基于随机机器选择的单点变异 v=0时，执行单点交叉，即随机选择两个父代个体 从父代个体E,中随机选择一个工序位x(1≤ E,和E2,随机生成一个工序位x(1≤x≤nh(1-p), 交换E,和E,中所选工序位x的机器号，保持其他工 x≤nh(1-p),将该工序位的机器号重新在1，m,] 之间随机生成，如图5。 序位的机器号不变，从而生成子代个体D和D2,如 图3。当v=1时，执行均匀两点交叉，首先，随机 E:M MME MMM MMI M ME 选择两个父代个体E和E2,随机生成两个工序位 x和y(1≤x<y≤nh(1-p),将E和E2分为3段，然 D MMM MEMMS M MY M MS 后，从{0,1,2}中随机产生一个数q,当q=0时，将 图5基于随机机器选择的单点变异 E,和E2中处于工序位x之前的区段交换，作为子代 Fig.5 Single point mutation based on random machine se- 个体D和D2的第一段；q=1时，交换E,和E2中工序 lection 位x和y之间的区段，作为D,和D2的中间段； 2)基于机器最短处理时间的多点变异 q=2时，对E,和E2中处于工序位y之后的区段进行 推广Chang等2的研究，提出基于机器最短 交换，作为D和D2的第三段；保留子代个体中其他 处理时间的多点变异操作。从父代个体E依次取 段与父代个体相同，以产生子代个体D,和D2,如 出工序位x的机器号，比较从区间[O,1]生成的随 图4。 机数w与变异概率山，若w<山，则从工序位x可利用 的并行机中选择处理时间最短的机器替换原有机 E MMM MP MM MMP ME M 器号，否则，保持原有机器号不变，对个体内所有 E:MMMMM"MM MY MMS 工序位完成上述操作后，生成新个体D,如图6。 ↓ E MM M MP MM MMP MMS D.M MME MMMM MS MEMS DM MMM MM M MS M MS D:M MM MP MMM MS MM 图6基于机器最短处理时间的多点变异 图3单点交叉 Fig.6 Multi-point mutation based on the shortest pro- Fig.3 Single-point crossover cessing time of the machines = 1 s > 1 时，将分派到在同一台机器处理的工件按照 最短处理时间规则进行排序，当 时，对同一台 机器上处理的工件采用先到先加工规则生成处理 序列，然后基于最早空闲机器原则依次将各工件 安排在所分配机器。对于工件的忽略工序，则按 照约束式 (3) 确定其在忽略工序的完工时间。 M1 13 M1 14 M2 12 M2 13 M3 14 M3 15 M4 14 M4 15 M5 12 M5 15 M1 23 M1 24 M2 22 M2 23 M3 24 M3 25 M4 24 M4 25 M5 22 M5 25 M1 33 M1 34 M2 32 M2 33 M3 34 M3 35 M4 34 M4 35 M5 32 M5 35 M1 e3 M1 e4 M2 e2 M2 e3 M3 e4 M3 e5 M4 e4 M4 e5 M5 e2 M5 e5 ... 图 2 初始种群 Fig. 2 Initial population g F(g) = 1/Cmax(g) 本文的目标是最小化最大完工时间，故将适 应度函数表示为目标函数的倒数，即个体 的适应 度函数为 。采用轮盘赌选择法，个 体适应度值越大，被选择的概率也越大。 2.2 交叉操作 v v = 0 E1 E2 x(1 ⩽ x ⩽ n · h ·(1− p)) E1 E2 x D1 D2 v = 1 E1 E2 x y(1 ⩽ x < y ⩽ n · h ·(1− p)) E1 E2 q q = 0 E1 E2 x D1 D2 q = 1 E1 E2 x y D1 D2 q = 2 E1 E2 y D1 D2 D1 D2 采用单点交叉和均匀两点交叉两种方式执行 交叉操作。在 0 和 1 中随机生成一个整数 ，当 时，执行单点交叉，即随机选择两个父代个体 和 ，随机生成一个工序位 ， 交换 和 中所选工序位 的机器号，保持其他工 序位的机器号不变，从而生成子代个体 和 ，如 图 3。当 时，执行均匀两点交叉，首先，随机 选择两个父代个体 和 ，随机生成两个工序位 和 ，将 和 分为 3 段，然 后，从{0, 1, 2}中随机产生一个数 ，当 时，将 和 中处于工序位 之前的区段交换，作为子代 个体 和 的第一段； 时，交换 和 中工序 位 和 之间的区段，作为 和 的中间段； 时，对 和 中处于工序位 之后的区段进行 交换，作为 和 的第三段；保留子代个体中其他 段与父代个体相同，以产生子代个体 和 ，如 图 4。 M1 13 M1 14 M2 12 M2 13 M3 14 M3 15 M4 14 M4 15 M5 12 M5 E 15 1 M1 33 M1 34 M2 32 M2 13 M3 34 M3 35 M4 34 M4 35 M5 32 M5 D 35 2 M1 33 M1 34 M2 32 M2 33 M3 34 M3 35 M4 34 M4 35 M5 32 M5 E 35 2 M1 13 M1 14 M2 12 M2 33 M3 14 M3 15 M4 14 M4 15 M5 12 M5 D 15 1 图 3 单点交叉 Fig. 3 Single-point crossover M1 33 M1 34 M2 32 M2 13 M3 14 M3 15 M4 14 M4 35 M5 32 M5 D 35 2 M1 33 M1 34 M2 32 M2 33 M3 34 M3 35 M4 34 M4 35 M5 32 M5 E 35 2 M1 13 M1 14 M2 12 M2 13 M3 14 M3 15 M4 14 M4 15 M5 12 M5 E 15 1 M1 13 M1 14 M2 12 M2 33 M3 34 M3 35 M4 34 M4 15 M5 12 M5 D 15 1 图 4 均匀两点交叉（q=1） Fig. 4 Uniform two-point crossover（q=1） 采用自适应更新策略确定交叉概率 ξ ，用以确 定是否执行上述交叉操作，计算如下[29] ： ξ =    ξmax −(ξmax −ξmin) ( λ β + F(g) Fmax − Favg ) , F(g) ⩾ Favg ξmin, F(g) < Favg 式中： λ 为当前迭代数； β 为最大迭代数； Favg为当 前种群的平均适应度值。 2.3 变异操作 变异操作是根据变异概率通过改变父代个体 的机器号以产生子代个体的过程。本文提出了基 于随机机器选择的单点变异和基于机器最短处理 时间的多点变异两种方式。 1）基于随机机器选择的单点变异 E1 x(1 ⩽ x ⩽ n · h ·(1− p)) [1,ms] 从父代个体 中随机选择一个工序位 ，将该工序位的机器号重新在 之间随机生成，如图 5。 E1 D1 M1 13 M1 14 M2 12 M2 13 M3 14 M3 15 M4 14 M4 15 M5 12 M5 15 M1 13 M1 14 M2 ′12 M2 13 M3 14 M3 15 M4 14 M4 15 M5 12 M5 15 图 5 基于随机机器选择的单点变异 Fig. 5 Single point mutation based on random machine se￾lection 2）基于机器最短处理时间的多点变异 E1 x w ψ w < ψ x D1 推广 Chang 等 [29] 的研究，提出基于机器最短 处理时间的多点变异操作。从父代个体 依次取 出工序位 的机器号，比较从区间 [0, 1] 生成的随 机数 与变异概率 ，若 ，则从工序位 可利用 的并行机中选择处理时间最短的机器替换原有机 器号，否则，保持原有机器号不变，对个体内所有 工序位完成上述操作后，生成新个体 ，如图 6。 E1 D1 M1 13 M1 14 M2 12 M2 13 M3 14 M3 15 ... M4 14 M4 15 M5 12 M5 15 M1 ′13 M1 14 M2 12 M2 13 M3 14 M3 15 M4 14 M4 15 M5 12 M5 ′15 图 6 基于机器最短处理时间的多点变异 Fig. 6 Multi-point mutation based on the shortest pro￾cessing time of the machine 第 17 卷 智 能 系 统 学 报 ·462·