第9期 汪红兵等：应用改进遗传算法求解炼钢连铸生产调度问题 ·1233° 的应用.其中，遗传算法是应用最为广泛的一种进 1算法设计 化算法. 遗传算法(ene tic a gorit四GA)是一类借鉴 设计一个遗传算法，通常要考虑问题编码与解 生物界自然选择和自然遗传机制的高度并行、随机 码、选择算子、交叉算子和变异算子等各个方面. 和自适应搜索算法.该算法是一种模仿自然界生物 1.1问题描述 进化过程中“物竞天择，适者生存”的原理而进行的 一个典型的JSS?就是研究将个工件分配在 一种多参数、多群体同时优化方法，其主要特点是群 m怡机器上加工的组合排序问题.对于炼钢连铸生 体搜索策略和群体中个体之间的信息交换，搜索不 产调度来说。就是研究将n个生产计划分配在m台 依赖于梯度信息.尤其适用于处理传统搜索方法难 处理工序上的组合排序问题，其目标是最小化生产 以解决的复杂和非线性问题 计划的最大完工时间(m业espa.设C为生产计划 实际上，炼钢连铸生产调度可归属为工件工厂 的完工时间，=12；则调度目标表示为 调度问题(b shop scheduling problem JSSP.所谓 m in m ax C)). SS就是研究将n个工件在m台机器上加工的组 1.2编码与解码 合排序问题，每个工件包含一系列必须按照指定顺 编码是完成问题的状态空间到遗传算法的码空 序加工的工序，而每道工序的加工又必须在指定的 间的映射，解码是完成遗传算法的码空间到问题的 机器上进行，要求在满足某些约束条件下确定各个 状态空间的映射.编码在一定程度上决定了各种算 工序的开始和结束时间，并使得加工性能指标达到 子的设计实现，是影响算法性能与效率的重要因素. 最优.这些性能指标可以是成本相关、也可以是时 本文采用基于工序的表达法.假设一个染色体 间相关一般是最小完工时间(makesp码.按照 编码为[13223↓321]，其中1表示工件12 JSSP的定义，炼钢连铸生产调度问题就是将给定的 表示工件23表示工件3该数码=123出现的 个生产计划在m台处理工序上进行的组合排序 次数代表工件的第道工序.例如，第1个1表 问题. 示工件1的第1道工序，最后一个1表示工件1的 由于炼钢连铸生产调度问题可归属为SS则 第3道工序.使用O表示第个工件的第道工序， SSP领域的众多研究成果就可以用来求解炼钢连 则上述染色体解码为Q,9,9,O2Q292 Q,9,Q.再结合每个操作所对应的具体加工机 铸生产调度问题.这里，主要关注遗传算法在SSP 的应用.周辉仁等”提出一种基于矩阵编码的遗传 器，即可以计算该染色体的所对应的完工时间，就完 成染色体的解码过程 算法求解工件车间调度问题，算法取得了较好的收 1.3选择算子 敛速度：张国辉等设计一种全局搜索、局部搜索 目前，大多数遗传算法的选择算子都采用轮盘 和随机产生相结合的初始化方法，提高种群初始解 赌选择法，选择概率的确定根据适应度进行比例分 的质量，加快遗传算法的收敛速度：王小平和曹立 配.但是，这种按比例分配容易导致早熟收敛现 明[9、Xg等0提出自适应遗传算法，前者将算法 象).本文采用基于排序的适应度分配法，其计算 中的交叉率和变异率参数设计为个体适应度和种群 公式如下： 最大适应度之差的线性关系，而后者则将算法中的 Fitness Pos= 交叉率和变异率参数设计为个体适应度和种群最大 2-SP+2(SP-1)(Pos1)/(Nd-1). 适应度之差的指数关系，在算法的求解效率上均取 式中，Nd为种群中个体数目；Pos为个体在种群中 得了一定的成果；Tsujmuray等和Chen等提 的排序位置；P为选择压力，一般取[1.Q2.0],这 出一种部分调度交叉算子，考虑部分调度为自然构 里取2.0例如，种群的适应度列向量为[214 成块，使得后代保留这些块，部分调度使用调度中起 3],则基于排序的适应度分配法的适应度列向量为 始位置和最终位置相同的工件来识别. [1.33332000000.6667]. 本文的工作是在遗传算法的自适应性方面、交 此外，在选择算子的设计上，还考虑采用优良个 叉算子方面，结合基于排序的适应度分配对传统遗 体保留的原则，即优良个体直接进入到后代种群，不 传算法的改进.实验验证了算法的改进效果，并成 参与交叉运算和变异运算 功应用改进遗传算法于炼钢连铸生产调度问题的 1.4交叉算子 求解 传统遗传算法中使用的交叉算子常见的有单点第 9期 汪红兵等:应用改进遗传算法求解炼钢连铸生产调度问题 的应用 .其中, 遗传算法是应用最为广泛的一种进 化算法 . 遗传算法 ( geneticalgorithm, GA)是一类借鉴 生物界自然选择和自然遗传机制的高度并行 、随机 和自适应搜索算法.该算法是一种模仿自然界生物 进化过程中 “物竞天择, 适者生存 ”的原理而进行的 一种多参数 、多群体同时优化方法, 其主要特点是群 体搜索策略和群体中个体之间的信息交换, 搜索不 依赖于梯度信息 .尤其适用于处理传统搜索方法难 以解决的复杂和非线性问题 [ 6] . 实际上, 炼钢连铸生产调度可归属为工件工厂 调度问题 ( jobshopschedulingproblem, JSSP) .所谓 JSSP, 就是研究将 n个工件在 m台机器上加工的组 合排序问题, 每个工件包含一系列必须按照指定顺 序加工的工序, 而每道工序的加工又必须在指定的 机器上进行, 要求在满足某些约束条件下确定各个 工序的开始和结束时间, 并使得加工性能指标达到 最优.这些性能指标可以是成本相关 、也可以是时 间相关, 一般是最小完工时间 ( makespan) .按照 JSSP的定义, 炼钢连铸生产调度问题就是将给定的 n个生产计划在 m台处理工序上进行的组合排序 问题. 由于炼钢连铸生产调度问题可归属为 JSSP, 则 JSSP领域的众多研究成果就可以用来求解炼钢连 铸生产调度问题.这里, 主要关注遗传算法在 JSSP 的应用 .周辉仁等 [ 7]提出一种基于矩阵编码的遗传 算法求解工件车间调度问题, 算法取得了较好的收 敛速度 ;张国辉等 [ 8] 设计一种全局搜索 、局部搜索 和随机产生相结合的初始化方法, 提高种群初始解 的质量, 加快遗传算法的收敛速度;王小平和曹立 明 [ 9] 、Xing等 [ 10] 提出自适应遗传算法, 前者将算法 中的交叉率和变异率参数设计为个体适应度和种群 最大适应度之差的线性关系, 而后者则将算法中的 交叉率和变异率参数设计为个体适应度和种群最大 适应度之差的指数关系, 在算法的求解效率上均取 得了一定的成果;Tsujimuray等 [ 11] 和 Cheng等 [ 12]提 出一种部分调度交叉算子, 考虑部分调度为自然构 成块, 使得后代保留这些块, 部分调度使用调度中起 始位置和最终位置相同的工件来识别 . 本文的工作是在遗传算法的自适应性方面 、交 叉算子方面, 结合基于排序的适应度分配对传统遗 传算法的改进.实验验证了算法的改进效果, 并成 功应用改进遗传算法于炼钢连铸生产调度问题的 求解. 1 算法设计 设计一个遗传算法, 通常要考虑问题编码与解 码、选择算子、交叉算子和变异算子等各个方面. 1.1 问题描述 一个典型的 JSSP, 就是研究将 n个工件分配在 m台机器上加工的组合排序问题 .对于炼钢连铸生 产调度来说, 就是研究将 n个生产计划分配在 m台 处理工序上的组合排序问题, 其目标是最小化生产 计划的最大完工时间 (makespan).设 Ci为生产计划 i的完工时间, i=1, 2, …, n, 则调度目标表示为 T=min{max(Ci) }. 1.2 编码与解码 编码是完成问题的状态空间到遗传算法的码空 间的映射, 解码是完成遗传算法的码空间到问题的 状态空间的映射.编码在一定程度上决定了各种算 子的设计实现, 是影响算法性能与效率的重要因素. 本文采用基于工序的表达法 .假设一个染色体 编码为[ 1, 3, 2, 2, 3, 1, 3, 2, 1], 其中 1表示工件 1, 2 表示工件 2, 3表示工件 3.该数码 i=1, 2, 3出现的 次数 j代表工件 i的第 j道工序 .例如, 第 1个 1表 示工件 1的第 1道工序, 最后一个 1表示工件 1的 第 3道工序 .使用 Oij表示第 i个工件的第 j道工序, 则上述染色体解码为 O11, O31, O21, O22, O32, O12, O33, O23, O13.再结合每个操作所对应的具体加工机 器, 即可以计算该染色体的所对应的完工时间, 就完 成染色体的解码过程. 1.3 选择算子 目前, 大多数遗传算法的选择算子都采用轮盘 赌选择法, 选择概率的确定根据适应度进行比例分 配.但是, 这种按比例分配容易导致早熟收敛现 象 [ 13] .本文采用基于排序的适应度分配法, 其计算 公式如下 : Fitness( Pos) = 2 -SP+2( SP-1) ( Pos-1) /( Nind-1) . 式中, Nind为种群中个体数目 ;Pos为个体在种群中 的排序位置;SP为选择压力, 一般取 [ 1.0, 2.0], 这 里取 2.0.例如, 种群的适应度列向量为 [ 2, 1, 4, 3], 则基于排序的适应度分配法的适应度列向量为 [ 1.333 3, 2.000 0, 0, 0.666 7] . 此外, 在选择算子的设计上, 还考虑采用优良个 体保留的原则, 即优良个体直接进入到后代种群, 不 参与交叉运算和变异运算. 1.4 交叉算子 传统遗传算法中使用的交叉算子常见的有单点 · 1233·