2008年4月中国制造业信息化第37卷第7期 色体编码长度L计算变异基因次数为L×P 操作之后的染色体为q 步骤2:随机选取染色体内不同位置2个基因21321032322102310012013100032313。通过采用 进行互换操作 互换变异,在一定程度上避免了“早熟”,有可能尽 步骤3:重复步骤2直到完成步骤1所计算的快地找到最优解 变异基因次数 2.3解码 例如,对如图2所示的子代个体q1进行变异, 解码的过程其实就是编码的逆过程图3所示 取变异基因率Pm=0.04,变异基因操作次数为为染色体编码q1的解码过程,图中的双下划线表 32×0.04≈1,随机选取互换位置为3,17,则变异示虚基因座,它不进行解码。具体步骤如下 染色体编码q1 1032322102310012013100032313 圆吸圆吸 甘特图 图3解码 步骤1,将所有制品顺序调度工序集O(=3遗传参数选取 0,1,…N-1)对应的位置标记Mark复位到0 由于这里研究的算法与系统主要针对车间生 步骤2,从左到右按顺序取编码基因i 产实践,因此强调的是优化与效率的平衡提升。在 步骤3根据取得的编码基因找到对应制品遗传参数选取上算法以能取得一定优化值且计算 的顺序调度工序集O4 速度能够接受为准则,同时在算法流程设计上也充 步骤4,若对应位置标记Mrk等于O的大小分考虑了这一点。当然,对于不同的问题,参数的 则返回步骤2,否则转到步骤5 选取是不同的。 步骤5,根据O4和Mark获取对应工序信息 a.进化群体的规模。一般取10~20,而对于 包括设备工种类型、计划加工工时和加工物料信息初始群体规模则可稍微加大,一般取12~30,主要 等,同时该位置标记Mark加1 是为了加大初始的全局搜索范围,但这个规模同样 步骤6,根据加工物料信息获取物料到达时是属于较小的 间 b.进化代数。一般选取20代以内。优化过程 步骤7根据设备工种类型到对应设备集中随必须兼顾效率,本算法在小进化代数下能够得到相 机寻找可加工时间晚于物料到达时间的最早开始 设备 对满意的优化值。因此,在进化代数的选取上以小 步骤8在该设备的调度上按该工序的计划加进化代数为主 工工时加入工序,当遭遇到设备计划的停工时段或 c.交叉概率与交叉基因率。交叉操作是在选 维护时段时按照普通排程方法处理 择操作后将得到的个体进行两两交叉,因为选择操 步骤9,重复步骤2~8直到选取完编码所有作由个体适应度决定,所以个体参与交叉的概率是 基因,从而产生一个完整的活动调度。 变化的、自适应的。个体参与交叉的概率直接与其 通过以上的解码过程最终就在数据库中形成适应度值对应的遗传概率挂钧因此优良个体参与 了一个完整的具体时间调度计划,包括设备的加工交又的概率就大,而劣质个体则相反,从而具有自 开始时间和加工结束时间等信息。根据这些信息适应性能。关于遗传参数的交叉基因率,通过实验 检索调度计划的开始时间和结束时间,两者之差便 般选取在0.2~0.5之间 是目标函数f(x)的结果。由于我们的目标是使 d.变异概率与变异基因率。与交叉概率相似 f(x)越小越好,而计算中的适应度值F是越大越由于变异操作在交叉操作后直接进行因此个体进 行变异的概率亦是变化的、自适应的。与交叉操作 好,因此取遗传适应度值函数F(x f(x)° 不同的是,由于变异操作属辅助操作,因此一般需 c1994-2008ChinaAcademicounalElectronicPublishingHouseallrightsreservedhttp://nwww.cnki.ner色体编码长度 L 计算变异基因次数为 L ×P ′ m ; 步骤 2 :随机选取染色体内不同位置 2 个基因 进行互换操作 ; 步骤 3 :重复步骤 2 直到完成步骤 1 所计算的 变异基因次数。 例如 ,对如图 2 所示的子代个体 q1 进行变异 , 取变异基因率 P ′ m = 0. 04 , 变异基因操作次数为 32 ×0. 04 ≈1 ,随机选取互换位置为 3 ,17 ,则变异 操 作 之 后 的 染 色 体 为 q ′ 1 = 21321032322102310012013100032313。通过采用 互换变异 ,在一定程度上避免了“早熟”,有可能尽 快地找到最优解。 2. 3 解码 解码的过程其实就是编码的逆过程 ,图 3 所示 为染色体编码 q ′ 1 的解码过程 ,图中的双下划线表 示虚基因座 ,它不进行解码。具体步骤如下 : 图 3 解码 步骤 1 ,将所有制品顺序调度工序集 Oi ( i = 0 ,1 , …, N - 1) 对应的位置标记 Marki复位到 0 ; 步骤 2 ,从左到右按顺序取编码基因 i ; 步骤 3 ,根据取得的编码基因 i 找到对应制品 的顺序调度工序集 Oi ; 步骤 4 ,若对应位置标记 Marki等于 Oi 的大小 则返回步骤 2 ,否则转到步骤 5 ; 步骤 5 ,根据 Oi 和 Mark i获取对应工序信息 , 包括设备工种类型、计划加工工时和加工物料信息 等 ,同时该位置标记 Marki加 1 ; 步骤 6 ,根据加工物料信息获取物料到达时 间 ; 步骤 7 ,根据设备工种类型到对应设备集中随 机寻找可加工时间晚于物料到达时间的最早开始 设备 ; 步骤 8 ,在该设备的调度上按该工序的计划加 工工时加入工序 ,当遭遇到设备计划的停工时段或 维护时段时按照普通排程方法处理 ; 步骤 9 ,重复步骤 2～8 直到选取完编码所有 基因 ,从而产生一个完整的活动调度。 通过以上的解码过程最终就在数据库中形成 了一个完整的具体时间调度计划 ,包括设备的加工 开始时间和加工结束时间等信息。根据这些信息 检索调度计划的开始时间和结束时间 ,两者之差便 是目标函数 f ( x ) 的结果。由于我们的目标是使 f ( x) 越小越好 ,而计算中的适应度值 F 是越大越 好 ,因此取遗传适应度值函数 F( x ) = 1 f ( x) 。 3 遗传参数选取 由于这里研究的算法与系统主要针对车间生 产实践 ,因此强调的是优化与效率的平衡提升。在 遗传参数选取上算法以能取得一定优化值且计算 速度能够接受为准则 ,同时在算法流程设计上也充 分考虑了这一点。当然 ,对于不同的问题 ,参数的 选取是不同的。 a. 进化群体的规模。一般取 10～20 ,而对于 初始群体规模则可稍微加大 ,一般取 12～30 ,主要 是为了加大初始的全局搜索范围 ,但这个规模同样 是属于较小的。 b. 进化代数。一般选取 20 代以内。优化过程 必须兼顾效率 ,本算法在小进化代数下能够得到相 对满意的优化值。因此 ,在进化代数的选取上以小 进化代数为主。 c. 交叉概率与交叉基因率。交叉操作是在选 择操作后将得到的个体进行两两交叉 ,因为选择操 作由个体适应度决定 ,所以个体参与交叉的概率是 变化的、自适应的。个体参与交叉的概率直接与其 适应度值对应的遗传概率挂钩 ,因此优良个体参与 交叉的概率就大 ,而劣质个体则相反 ,从而具有自 适应性能。关于遗传参数的交叉基因率 ,通过实验 一般选取在 0. 2～0. 5 之间。 d. 变异概率与变异基因率。与交叉概率相似 , 由于变异操作在交叉操作后直接进行 ,因此个体进 行变异的概率亦是变化的、自适应的。与交叉操作 不同的是 ,由于变异操作属辅助操作 ,因此一般需 83 2008 年 4 月 中国制造业信息化 第 37 卷 第 7 期 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net