深圳大学学报理工版 第23卷 2.2个体选择 传,维持不变.这种交叉方法保证子代个体从父代 个体选择运算操作以其适应度值评估为基础,中遗传了部分特性,同时又发生了一定的变化,且 理论上要求适应度值高的染色体具有较大的概率遗由于编码的优势交叉后产生的染色体完全符合非量 传到下一代.个体选择是保证遗传向着期望方向前产模式制造系统的各种约束关系,保证了子代个体 进的关键,本文进行的遗传运算包含两次选择:第的合理性与可行性 次选择进行遗传操作的个体;第二次选择遗传到2.4变异操作 下一代的个体.第一次选择采用最常见的适应度比 本文采用互换操作变异方法,具体步骤为:① 例选择法(称转轮赌或蒙特卡罗选择),第二次根据设定的遗传变异基因率P‘和染色体编码长度 选择采用最佳个体保留法,个体被选中的概率与其L,计算变异基因次数=L×n’(取整);②随机选 适应度值成正比.若设群体的大小为G.个体的适取染色体内不同位置两个基因进行互换操作;③ 应度值为F,则个体被选中的概率为 重复②直到完成①所计算的变异基因次数.例如将 q进行变异,取变异基因率Pn′=0.04.变异基因 P=F/∑Fn 1.2 (2)次数=32×0.04=1,随机选取互换位置为3和17 显然,个体的适应度值大,即选中概率P,高 则变异后的染色体为 但这种方法需要产生随机数进行选择,因此可能出 q′=21321032322102310012013100032313 现不正确的反映个体的选择,存在统计误差.本文 采取两次选择操作,在第一次选择中,群体进化的2.5解码与个体适应度值计算 每一代均随机选择多个个体进行交叉操作;第二次工的具体做法为:①将所有制品顺序调度 选择操作,采用最佳个体保留.因此,能有效克服 复位到0;②从左到右按顺序取编码基因t③根 统计误差引起劣质个体被选中的非理想结果 据取得的编码基因找到对应制品的顺序调度工序 2.3交叉操作 交叉操作是利用父代染色体通过交叉变换重新集O;④若对应位置标记Ma等于O,,则返回 组合制造出新个体,要求在尽量降低有效模式被破②,否则,继续⑤,⑤根据O,和Mak获取对应工 坏的基础上,对解空间进行改进有效的搜索以找到序信息,包括设备工种类型、计划加工工时和加工 物料信息等,同时该位置标记Mak加1;⑥根据 最优解.由于采用一般字符串编码,所以在交叉时 使用组合优化中的置换编码米进行本文采用一种根据设备工种类型到对应设备集中随机寻找可加工 操作.其步骤为:①选中两个交叉个体;②根据 时间晚于物料到达时间的最早开始设备;⑧在该 交叉基因率P。和染色体编码基因数n确定发生交设备的调度上按工序计划加工工时加入工序,当遇 叉基因的范围大小;③根据发生交叉基因范围大 到计划停工时段或维护时段时按照上文描述系统约 小随机确定交叉基因;④保证除了交又基因外的東⑦处理;⑨重复步骤②~③直到编码完所有基 其他基因位置不变,对两个个体中的交叉基因进行 因,从而产生一个完整的调度计划 交叉变换,从而得到两个新个体 通过以上解码过程,最终在数据库形成一个完 例如,选中交叉的个体为前面编码例子所产生整的调度计划,包括设备加工的开始与结束时间 的两个父代个体A和p2,选取P2=0.42.n=4等.需要注意的是,制品顺序调度工序集仅决定工 相乘取整得到交叉基因范围大小为2,随机确定交序进入调度的先后,因此后进入调度的工序,只要 叉基因为1和3,则保持基因0和2的位置不变 其约束许可,便有可能比先进入调度的工序先开始 对A和中的1和3进行交叉变换,产生新个体为加工,从而实现互相没有约束关系的同一制品子层 工件具有并行加工的可能.再通过检索调度计划的 qh=2130103232102310212013100032313 开始时间和结束时间,两者之差便是目标函数f(x) q=22101033102323013302002111323 的结果.由于调度目标是使∫(x)越小越好,而计 其中,o和2加下划线表示基因位置从父代个体遗算中的适应度值F是越大越好,遗传向着适应度值 2o1994-2009ChinacademicJournalElectronicPublishingHouse.Allrightsreserved.http:/wnwcnkiner© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 274 深圳大学学报理工版 第 23卷 212 个体选择 个体选择运算操作以其适应度值评估为基础 , 理论上要求适应度值高的染色体具有较大的概率遗 传到下一代. 个体选择是保证遗传向着期望方向前 进的关键 , 本文进行的遗传运算包含两次选择 : 第 一次选择进行遗传操作的个体 ; 第二次选择遗传到 下一代的个体. 第一次选择采用最常见的适应度比 例选择法 (又称转轮赌或蒙特卡罗选择 ) , 第二次 选择采用最佳个体保留法. 个体被选中的概率与其 适应度值成正比. 若设群体的大小为 G, 个体 i的适 应度值为 Fi , 则个体 i被选中的概率为 Pi = Fi /∑ G n =1 Fn , n = 1, 2, …, G. (2) 显然 , 个体的适应度值大 , 即选中概率 Pi 高. 但这种方法需要产生随机数进行选择 , 因此可能出 现不正确的反映个体的选择 , 存在统计误差. 本文 采取两次选择操作 , 在第一次选择中 , 群体进化的 每一代均随机选择多个个体进行交叉操作 ; 第二次 选择操作 , 采用最佳个体保留. 因此 , 能有效克服 统计误差引起劣质个体被选中的非理想结果. 213 交叉操作 交叉操作是利用父代染色体通过交叉变换重新 组合制造出新个体 , 要求在尽量降低有效模式被破 坏的基础上 , 对解空间进行改进有效的搜索以找到 最优解. 由于采用一般字符串编码 , 所以在交叉时 使用组合优化中的置换编码来进行. 本文采用一种 改进的基于位置交叉 PX的交叉方法 [ 2 ]来进行交叉 操作. 其步骤为 : ①选中两个交叉个体 ; ②根据 交叉基因率 Pc ′和染色体编码基因数 n, 确定发生交 叉基因的范围大小 ; ③根据发生交叉基因范围大 小随机确定交叉基因 ; ④保证除了交叉基因外的 其他基因位置不变 , 对两个个体中的交叉基因进行 交叉变换 , 从而得到两个新个体. 例如 , 选中交叉的个体为前面编码例子所产生 的两个父代个体 p1 和 p2 , 选取 Pc ′= 0142, n = 4, 相乘取整得到交叉基因范围大小为 2, 随机确定交 叉基因为 1和 3, 则保持基因 0和 2的位置不变 , 对 p1和 p2中的 1和 3进行交叉变换 , 产生新个体为 q1 = 21301032322102310212013100032313, q2 = 22101033102323012330102002111323. 其中 , 0和 2加下划线表示基因位置从父代个体遗 传 , 维持不变. 这种交叉方法保证子代个体从父代 中遗传了部分特性 , 同时又发生了一定的变化 , 且 由于编码的优势交叉后产生的染色体完全符合非量 产模式制造系统的各种约束关系 , 保证了子代个体 的合理性与可行性. 214 变异操作 本文采用互换操作变异方法 , 具体步骤为 : ① 根据设定的遗传变异基因率 Pm ′和染色体编码长度 L, 计算变异基因次数 =L ×Pm ′(取整 ) ; ②随机选 取染色体内不同位置两个基因进行互换操作 ; ③ 重复 ②直到完成 ①所计算的变异基因次数. 例如将 q1 进行变异 , 取变异基因率 Pm ′= 0104, 变异基因 次数 = 32 ×0104∆ 1, 随机选取互换位置为 3和 17, 则变异后的染色体为 q1 ′= 213 2 103232210231 0 012013100032313. 215 解码与个体适应度值计算 解码的具体做法为 : ①将所有制品顺序调度 工序集 Oi ( i = 0, 1, …, N - 1) 对应的位置标记 Ma rki 复位到 0; ②从左到右按顺序取编码基因 i; ③根 据取得的编码基因 i找到对应制品的顺序调度工序 集 Oi; ④若对应位置标记 Marki 等于 Oi , 则返回 ②, 否则 , 继续 ⑤; ⑤根据 Oi和 Marki获取对应工 序信息 , 包括设备工种类型、计划加工工时和加工 物料信息等 , 同时该位置标记 Marki 加 1; ⑥根据 加工物料信息获取物料约束与物料到达时间 ; ⑦ 根据设备工种类型到对应设备集中随机寻找可加工 时间晚于物料到达时间的最早开始设备 ; ⑧在该 设备的调度上按工序计划加工工时加入工序 , 当遇 到计划停工时段或维护时段时按照上文描述系统约 束 ⑦处理 ; ⑨重复步骤 ②～⑧直到编码完所有基 因 , 从而产生一个完整的调度计划. 通过以上解码过程 , 最终在数据库形成一个完 整的调度计划 , 包括设备加工的开始与结束时间 等. 需要注意的是 , 制品顺序调度工序集仅决定工 序进入调度的先后 , 因此后进入调度的工序 , 只要 其约束许可 , 便有可能比先进入调度的工序先开始 加工 , 从而实现互相没有约束关系的同一制品子层 工件具有并行加工的可能. 再通过检索调度计划的 开始时间和结束时间 , 两者之差便是目标函数 f ( x) 的结果. 由于调度目标是使 f ( x) 越小越好 , 而计 算中的适应度值 F是越大越好 , 遗传向着适应度值