·844· 北京科技大学学报 第34卷 一.遗传算法(genetic algorithms,.GA)是模仿自然 坯向各个加热炉的分配，其入炉和出炉时间由钢坯 界生物进化中的遗传、变异和自然选择过程，对解空 的到达时间、加热炉和轧机的生产限制来决定 间的点进行遗传操作的一类模拟进化算法围.大 当加热炉个数非2"(n≥1)时，仍可采用上述编 多数工程优化问题中，由于常常带有复杂的约束条 码方式，取合适的n值使2”最接近且大于加热炉个 件，简单的遗传算法往往不能很好地解决这类工程 数，其中无法与加热炉对应的二进制可以采用随机 优化问题.在遗传算法中增加所求解问题的先验知 分配的方式指定加热炉或依次指定给每座加热炉的 识对于求解效果的影响很大.本文选用遗传算 方式实现与加热炉的对应. 法和禁忌搜索相结合的遗传禁忌搜索算法进行求 (2)交叉算子.本文的交叉算子同时作用于两 解，其详细步骤如下 个父代，综合这两个父代的特点产生一个子代，交叉 Step1:随机生成N个初始解，形成种群(N为 算子采用了一种“局部方案保留”的策略，局部方案 种群规模)： 对应的是某些钢坯的加热炉选择方式，通过保留某 Step2:对种群中每个解执行变异运算： 个父代的局部方案来保留父代中比较优良的基因， Step3:将当前种群的个体进行两两配对，按照 以一定的概率P。执行交叉运算. 交叉概率P。随机截取配对中两个个体的部分组成 (3)变异算子.引入变异算子是为了达到全局 新的个体，按照变异概率P执行变异运算后形成新 优化的效果.本文采用的变异运算分为两次进行. 个体，存储于子代种群中； 第一次，执行完交叉算子后，以一定的概率Pm执行 Stp4:将当前种群和子代种群转化为加热炉区 变异算子，方法是随机选取一定数目的钢坯，对其反 生产计划，并计算评价值： 映加热炉分配的二进制字符串执行取反操作.第二 Step5:对当前种群和子代种群通过选择运算选 次，选取下一代种群后，对种群中所有解的编码执行 出N个子代形成新一代种群： 取反、与同等长度的二进制字符串“101010…”和 Step6:对新一代种群中的每个个体进行禁忌搜 010101…”执行异或操作，从而将一个解扩展为四 索，若得到的解优于原解则取代相应的原子代个体， 个解.第一次变异运算是为了引入突变，第二次变 将新一代种群作为当前种群； 异运算是为了引入多种选择，假设有四块钢坯，其编 Step7:判断是否满足停止条件，如满足算法终 码为00011011，则执行第二部分变异后结果为 止，输出当前种群中的最优解；如不满足，则跳转 00011011 Step 2. 11100100 实现优化问题的遗传禁忌搜索算法求解，除了 10110001 要构建遗传算法的组成部分，还要实现禁忌搜索 01001110 本文采用的编码方式、交叉算子、变异算子、适应值 由以上四种编码可以看出，执行变异算子后每 函数、选择机制、禁忌搜索和停止条件如下 一块钢坯都有了进入四座加热炉的机会，有利于寻 (1)解的编码方式.解的编码功能是将问题的 找全局最优解 解用一种便于遗传操作的方式表现出来.本文在求 (4)适应值函数.采用式(1)和式(2)的优化 解加热炉调度问题时使用二进制表示钢坯选择的加 函数目标值作为适应度函数值.根据式(1)和式 热炉，将钢坯的加热炉号按照钢坯的轧制顺序排列 (2)的重要性，在计算中分阶段进行寻优 成一个二进制字符串进行处理.假设有八块待加热 (⑤)选择机制.当前种群经过遗传变异后生成 钢坯(1,2,3,4,5,6,7,8)和四座加热炉，轧制顺序 子代种群，将当前种群并入到子代种群，计算适应 为(1,2,3,4,5,6,7,8,00”表示分配到加热炉1"， 值，然后将适应值最好的前几个个体直接复制到新 “01”表示分配到加热炉2,10”表示分配到加热炉 一代种群中，剩余的个体根据种群规模按照随机通 3”,11”表示分配到加热炉4”，一种可能的分配就 用采样方法的确定是否复制到新一代种群 可以编码为如下二进制字符串： (6)禁忌搜索.将所有钢坯两两配对，形成钢 0001101100011011. 坯对群，针对每次遗传运算所得到的新一代种群中 根据编码可以得知钢坯号为1和5的钢坯分配 的每一个解，根据禁忌表依次交换分配到不同加热 给加热炉1”，钢坯号为2和6的钢坯分配给加热炉 炉的钢坯对，得到新的解，计算其适应值，找到适应 2”,钢坯号为3和7的钢坯分配给加热炉3”，钢坯号 值优于原解的新解取代原来的解，更新禁忌表为下 为4和8的钢坯分配给加热炉4”.编码中仅体现钢 一次遗传运算中的禁忌搜索做准备，若无则保持北 京 科 技 大 学 学 报 第 34 卷 一． 遗传算法( genetic algorithms，GA) 是模仿自然 界生物进化中的遗传、变异和自然选择过程，对解空 间的点进行遗传操作的一类模拟进化算法［13］． 大 多数工程优化问题中，由于常常带有复杂的约束条 件，简单的遗传算法往往不能很好地解决这类工程 优化问题． 在遗传算法中增加所求解问题的先验知 识对于求解效果的影响很大［14］． 本文选用遗传算 法和禁忌搜索相结合的遗传禁忌搜索算法进行求 解，其详细步骤如下． Step 1: 随机生成 N 个初始解，形成种群( N 为 种群规模) ; Step 2: 对种群中每个解执行变异运算; Step 3: 将当前种群的个体进行两两配对，按照 交叉概率 pc随机截取配对中两个个体的部分组成 新的个体，按照变异概率 pm执行变异运算后形成新 个体，存储于子代种群中; Step 4: 将当前种群和子代种群转化为加热炉区 生产计划，并计算评价值; Step 5: 对当前种群和子代种群通过选择运算选 出 N 个子代形成新一代种群; Step 6: 对新一代种群中的每个个体进行禁忌搜 索，若得到的解优于原解则取代相应的原子代个体， 将新一代种群作为当前种群; Step 7: 判断是否满足停止条件，如满足算法终 止，输出当前种群中的最优解; 如不满足，则跳转 Step 2． 实现优化问题的遗传禁忌搜索算法求解，除了 要构建遗传算法的组成部分，还要实现禁忌搜索． 本文采用的编码方式、交叉算子、变异算子、适应值 函数、选择机制、禁忌搜索和停止条件如下． ( 1) 解的编码方式． 解的编码功能是将问题的 解用一种便于遗传操作的方式表现出来． 本文在求 解加热炉调度问题时使用二进制表示钢坯选择的加 热炉，将钢坯的加热炉号按照钢坯的轧制顺序排列 成一个二进制字符串进行处理． 假设有八块待加热 钢坯( 1，2，3，4，5，6，7，8) 和四座加热炉，轧制顺序 为( 1，2，3，4，5，6，7，8) ，“00”表示分配到加热炉 1# ， “01”表示分配到加热炉 2# ，“10”表示分配到加热炉 3# ，“11”表示分配到加热炉 4# ，一种可能的分配就 可以编码为如下二进制字符串: 0001101100011011． 根据编码可以得知钢坯号为 1 和 5 的钢坯分配 给加热炉 1# ，钢坯号为 2 和 6 的钢坯分配给加热炉 2# ，钢坯号为 3 和 7 的钢坯分配给加热炉 3# ，钢坯号 为 4 和 8 的钢坯分配给加热炉 4# ． 编码中仅体现钢 坯向各个加热炉的分配，其入炉和出炉时间由钢坯 的到达时间、加热炉和轧机的生产限制来决定． 当加热炉个数非 2n ( n≥1) 时，仍可采用上述编 码方式，取合适的 n 值使 2n 最接近且大于加热炉个 数，其中无法与加热炉对应的二进制可以采用随机 分配的方式指定加热炉或依次指定给每座加热炉的 方式实现与加热炉的对应． ( 2) 交叉算子． 本文的交叉算子同时作用于两 个父代，综合这两个父代的特点产生一个子代，交叉 算子采用了一种“局部方案保留”的策略，局部方案 对应的是某些钢坯的加热炉选择方式，通过保留某 个父代的局部方案来保留父代中比较优良的基因， 以一定的概率 pc 执行交叉运算． ( 3) 变异算子． 引入变异算子是为了达到全局 优化的效果． 本文采用的变异运算分为两次进行． 第一次，执行完交叉算子后，以一定的概率 pm 执行 变异算子，方法是随机选取一定数目的钢坯，对其反 映加热炉分配的二进制字符串执行取反操作． 第二 次，选取下一代种群后，对种群中所有解的编码执行 取反、与同等长度的二进制字符串“101010 …”和 “010101…”执行异或操作，从而将一个解扩展为四 个解． 第一次变异运算是为了引入突变，第二次变 异运算是为了引入多种选择，假设有四块钢坯，其编 码为 00011011，则执行第二部分变异后结果为 0 0 0 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 1 0 由以上四种编码可以看出，执行变异算子后每 一块钢坯都有了进入四座加热炉的机会，有利于寻 找全局最优解． ( 4) 适应值函数． 采用式( 1) 和式( 2) 的优化 函数目标值作为适应度函数值． 根据式( 1) 和式 ( 2) 的重要性，在计算中分阶段进行寻优． ( 5) 选择机制． 当前种群经过遗传变异后生成 子代种群，将当前种群并入到子代种群，计算适应 值，然后将适应值最好的前几个个体直接复制到新 一代种群中，剩余的个体根据种群规模按照随机通 用采样方法［15］确定是否复制到新一代种群． ( 6) 禁忌搜索． 将所有钢坯两两配对，形成钢 坯对群，针对每次遗传运算所得到的新一代种群中 的每一个解，根据禁忌表依次交换分配到不同加热 炉的钢坯对，得到新的解，计算其适应值，找到适应 值优于原解的新解取代原来的解，更新禁忌表为下 一次遗传运算中的禁忌搜索做准备，若无则保持 ·844·