现代设计与先进制造技术·伍晓宇王志勇吴序一基于实虚基因座的车间调…… 制品0顺序调度工序集(基因0)包含4 染色体编码P=21103032122302310232031100012 制品2顺序调度工序集(基因2)包含5工序 制品3顺序调度工序集(基因3)包含8工序 实基因座 ·前虚基因座 后虚基因座 图1遗传编码 先级别而加入的虚位置节点,是制品排程时的延迟论上可以得到最优解。 长度。最紧急的制品其延迟长度为零,不存在前虚2.2遗传操作 基因座节点,它有权优先竞争加工资源。而前虚基 本文采用一种改进的基于位置交叉的方法来 因座节点越多,表示制品起始排程延迟长度越大,进行编码交叉。具体做法如下 由于其他制品的实基因座节点可以插入其间,这样 步骤1,通过上述个体选择办法选中2个交叉 相对这些制品前虚基因座节点所对应的制品越靠个体 后参与加工资源的竞争。所以,前虚基因座可以反 步骤2,根据预先设定的交叉基因率P和染 映制品之间的竞争资源的优先级别 色体编码基因数n确定发生交叉基因的范围大小 b实基因座。实基因座节点表示各制品的实为n×P(取整) 际加工工序以及这些加工工序构成的加工工艺链 步骤3,根据发生交叉基因范围大小随机确定 实基因座节点数就是制品的工序数目。在构建统交叉基因 的染色体编码时,各制品实基因座和虚基因座节 步骤4,保证除了交叉基因外的其他基因位置 点相互穿插形成一条单行队列这一队列也反映了不变遗传到下一代,对2个个体中的交叉基因进 制品内和制品之间工序的排程顺序,即抢占加工资行交叉变换,从而得到2个子代新个体 源的前后顺序。需要指出的是,这一顺序并不是排 例如选中交叉的个体为前面编码例子所产生 程完成后工序的前后顺序,也就是说先进入排程的2个个体p1和p2,P=0.42,n=4,取整后交 的不一定获得较早的开工时间 叉基因范围大小为2个,随机确定交叉基因为1,3, c后虚基因座。它是为了染色体编码而加入则保持基因0,2的位置不变,对p1和p2中的1,3 基因所占的虚位置。由于各制品存在不同长度的进行交叉变换,产生新个体如图2所示,其中0,2 前虚基因座和实基因座为保证总的染色体编码长加下划线表示位置从父代遗传维持不变。这种交 度一致取各制品中前虚基因座+实基因座长度最叉方法保证子代个体从父代中遗传了部分特性同 大值为统一长度其他制品编码尾部的不足部分用时又发生了一定的变化,且由于编码的优势交叉后 后虚基因座节点补足 产生的子代染色体完全符合制造系统的各种约束 染色体编码步骤如下 关系,保证了子代个体的合法性与可行性 步骤1,给不同的制品指定整数编码基因,如 父代个体 0,12等,基因数为n,表示有n个制品参加排程 P2221030133212301211030200213323 步骤2,根据不同制品的优先权值,生成数目 位置遗传基因0.2 不等的前虚基因座节点 子代个体4=2130103232210231021201310002313 42221910331923230123301020021123 步骤3,找到参加排程的制品的前虚基因座+ 实基因座长度(工序长度)最大值m,例如参加排 图2交叉操作 程的制品有4个,它们的前虚基因座和实基因座长 变异操作是模仿生物进化过程中染色体上基因 度分别为2和4.0和6.0和5及0和8,那么m就发生的突变现象,从而使染色体的结构和某些性状 等于8 发生相应的突变。在遗传算法中引入变异操作可以 步骤4,随机加入编码基因组成编码长度为使算法具有局部的随机搜索能力加强算法的搜索 m的编码串表示一个染色体 能力避免陷入局部最优,同时维持群体的多样性 经过分析该编码方法就可行性而言编码空间本文采用一种互换操作变异方法,具体做法如下 仅包含可行解的空间,而且表征整个调度空间,理 步骤1:根据设定的遗传变异基因率P和染 c1994-2008ChinaAcademicJounalElectronicPublishingHouseallrightsreseredhttp://nn.cnki.ner图 1 遗传编码 先级别而加入的虚位置节点 ,是制品排程时的延迟 长度。最紧急的制品其延迟长度为零 ,不存在前虚 基因座节点 ,它有权优先竞争加工资源。而前虚基 因座节点越多 ,表示制品起始排程延迟长度越大 , 由于其他制品的实基因座节点可以插入其间 ,这样 相对这些制品前虚基因座节点所对应的制品越靠 后参与加工资源的竞争。所以 ,前虚基因座可以反 映制品之间的竞争资源的优先级别。 b. 实基因座。实基因座节点表示各制品的实 际加工工序以及这些加工工序构成的加工工艺链 , 实基因座节点数就是制品的工序数目。在构建统 一的染色体编码时 ,各制品实基因座和虚基因座节 点相互穿插形成一条单行队列 ,这一队列也反映了 制品内和制品之间工序的排程顺序 ,即抢占加工资 源的前后顺序。需要指出的是 ,这一顺序并不是排 程完成后工序的前后顺序 ,也就是说 ,先进入排程 的不一定获得较早的开工时间。 c. 后虚基因座。它是为了染色体编码而加入 基因所占的虚位置。由于各制品存在不同长度的 前虚基因座和实基因座 ,为保证总的染色体编码长 度一致 ,取各制品中前虚基因座 + 实基因座长度最 大值为统一长度 ,其他制品编码尾部的不足部分用 后虚基因座节点补足。 染色体编码步骤如下 : 步骤 1 ,给不同的制品指定整数编码基因 ,如 0 ,1 ,2 等 ,基因数为 n ,表示有 n 个制品参加排程 ; 步骤 2 ,根据不同制品的优先权值 ,生成数目 不等的前虚基因座节点 ; 步骤 3 ,找到参加排程的制品的前虚基因座 + 实基因座长度 (工序长度) 最大值 m , 例如参加排 程的制品有 4 个 ,它们的前虚基因座和实基因座长 度分别为 2 和 4 ,0 和 6 ,0 和 5 及 0 和 8 ,那么 m 就 等于 8 ; 步骤 4 ,随机加入编码基因组成编码长度为 L = n ×m 的编码串表示一个染色体。 经过分析 ,该编码方法就可行性而言编码空间 仅包含可行解的空间 ,而且表征整个调度空间 ,理 论上可以得到最优解。 2. 2 遗传操作 本文采用一种改进的基于位置交叉的方法来 进行编码交叉。具体做法如下 : 步骤 1 ,通过上述个体选择办法选中 2 个交叉 个体 ; 步骤 2 ,根据预先设定的交叉基因率 P ′ c 和染 色体编码基因数 n 确定发生交叉基因的范围大小 为 n ×P ′ c (取整) ; 步骤 3 ,根据发生交叉基因范围大小随机确定 交叉基因 ; 步骤 4 ,保证除了交叉基因外的其他基因位置 不变 ,遗传到下一代 ,对 2 个个体中的交叉基因进 行交叉变换 ,从而得到 2 个子代新个体。 例如选中交叉的个体为前面编码例子所产生 的 2 个个体 p1 和 p2 , P ′ c = 0. 42 , n = 4 ,取整后交 叉基因范围大小为2 个 ,随机确定交叉基因为1 ,3 , 则保持基因 0 ,2 的位置不变 ,对 p1 和 p2 中的 1 ,3 进行交叉变换 ,产生新个体如图 2 所示 ,其中 0 ,2 加下划线表示位置从父代遗传维持不变。这种交 叉方法保证子代个体从父代中遗传了部分特性 ,同 时又发生了一定的变化 ,且由于编码的优势交叉后 产生的子代染色体完全符合制造系统的各种约束 关系 ,保证了子代个体的合法性与可行性。 图 2 交叉操作 变异操作是模仿生物进化过程中染色体上基因 发生的突变现象 ,从而使染色体的结构和某些性状 发生相应的突变。在遗传算法中引入变异操作可以 使算法具有局部的随机搜索能力 ,加强算法的搜索 能力避免陷入局部最优 ,同时维持群体的多样性。 本文采用一种互换操作变异方法 ,具体做法如下: 步骤 1 :根据设定的遗传变异基因率 P ′ m 和染 ·现代设计与先进制造技术· 伍晓宇 王志勇 吴序一 基于实虚基因座的车间调 …… 73 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net