·460· 北京科技大学学报 第34卷 间点进行遗传操作的一类模拟进化算法.根据问题 定，最终可得到类似如下排序的结果： 的特征，首先随机地选择一组初始解构成初始种群， C=B275641]. 用遗传算子对其进行变换，每变换一次就会形成下 依次计算热轧批量计划中相邻两板坯的跳跃惩 一代待选种群，评价其适应性，适应性好的在下一代 罚值，若d6=∞，则在板坯5和6之间插入分割符 中优先予以选择，形成下一代种群后继续运算，直到 从而得到完整的解向量： 达到停止条件. C=B275*641] 实现优化问题的遗传算法求解，需要根据问题 3.2.4选择机制 特征设计解的编码方式和遗传算子、选择适应值函 当前种群经过遗传变异后生成子代种群，将当 数、给定合适的选择机制和停止条件.本文采用的 前种群并入到子代种群，计算适应值，然后将适应值 编码方式、遗传算子、适应值函数、选择机制和停止 最好的前几个个体直接复制到新一代种群中，剩余 条件如下， 的个体根据种群规模按照随机通用采样方法的确 3.2.1解的编码方式 定是否复制到新一代种群 每一个解表示一种热轧批量计划，采用一个向 3.2.5停止条件 量表示，在这个向量中包括板坯的加工顺序和轧制 停止条件设置为算法运行到一个预先设定的迭 单元的划分两类信息.采用板坯号的排列顺序表示 代次数时停止并取当前种群中最好的结果输出 热轧加工顺序，分隔符作为不同轧制单元的间隔标 3.3禁忌搜索算法 志.假设有7块板坯（实际生产中每次热轧批量计 禁忌搜索是解决组合优化问题的一种策略，它 划板坯数一般为150个以上)，一种可能的组批和 于1970年首先应用于非线性覆盖问题的优化过程， 排序方式可以编码为如下的向量： 后来又应用于从图论到一般纯整数规划问题和混合 023*45*67]. 整数规划问题及旅行商问题等.文献6]详细阐述 根据编码可知，板坯1、2和3为第一个轧制单元，板 了禁忌搜索算法的原理和应用.禁忌搜索的特点 坯4和5为第二个轧制单元，板坯6和7为第三个 是：为了避免搜索陷入死循环，构造了一个短期循环 轧制单元，板坯加工顺序为1、2、3、4、5、6和7. 记忆表一禁忌表，表中存放刚进行过的I引（禁忌 3.2.2适应值函数 表的长度)个邻域移动，每个移动在以后的11次循 采用式(1)、式(2)和式(3)的优化函数目标值 环内是禁止的，禁忌表在搜索过程中不断修改，使搜 作为适应度函数值.根据式(1)、式(2)和式(3)的 索向着更好的方向前进 重要性，在计算中分阶段进行寻优 本文采用的方法是：将所有板坯两两配对，形成 3.2.3遗传算子 板坯对群，针对每次遗传算法运算所得到的下一代 遗传算子采用两交换启发交叉算法.其基 种群中的每一个解，依次交换每对板坯对，得到新的 本思想为：以7块板坯为例，假设7块板坯分别为 解，计算其适应值，找到适应值优于原解的新解取代 1、2、3、4、5、6和7.随机选出一对未匹配的双亲去 原来的解，若无则保持不变.具体方法为：假设下一 除分隔符后， 代种群中的一个解0=B275*641],去除分隔 F=7264153], 符后0。=B275641],则会有C=21对板坯 M=B217564]. 对，依次交换每对板坯对形成21个新的解向量，假 随机选出初始板坯的位置号j=3,板坯号S,= 设选取的板坯对为(6,5)，则新的解向量为O,=B 7,左转动使两双亲的第三个位置的板坯号为7， 276541],计算紧邻轧制的两块板坯跳跃的惩罚 F=5372641], 值，若d.6=∞则在板坯7和6之间插入分隔符，从 M1=2175643], 而得到新的解0=B27*6541].重复上述过 C=xx7xxxx]. 程，会得到21个新解，计算其适应值与原有的解进 然后，选择位置号j=4处的板坯.若d2>ds, 行比较，选取最优的解取代原有的解 则F,以5为中心左转得到如下中间代： 3.4混合算法 F=41x5326], 在大多数工程优化问题中，由于常常带有复杂 M2=21x5643], 的约束条件，简单的遗传算法往往不能很好地解决 C2=xx75xxx 这类工程优化问题.在遗传算法中增加所求解问题 重复上述过程直到子代中所有位置的板坯都确 的先验知识对于求解效果的影响很大叼.本文选北 京 科 技 大 学 学 报 第 34 卷 间点进行遗传操作的一类模拟进化算法． 根据问题 的特征，首先随机地选择一组初始解构成初始种群， 用遗传算子对其进行变换，每变换一次就会形成下 一代待选种群，评价其适应性，适应性好的在下一代 中优先予以选择，形成下一代种群后继续运算，直到 达到停止条件． 实现优化问题的遗传算法求解，需要根据问题 特征设计解的编码方式和遗传算子、选择适应值函 数、给定合适的选择机制和停止条件． 本文采用的 编码方式、遗传算子、适应值函数、选择机制和停止 条件如下． 3. 2. 1 解的编码方式 每一个解表示一种热轧批量计划，采用一个向 量表示，在这个向量中包括板坯的加工顺序和轧制 单元的划分两类信息． 采用板坯号的排列顺序表示 热轧加工顺序，分隔符作为不同轧制单元的间隔标 志． 假设有 7 块板坯( 实际生产中每次热轧批量计 划板坯数一般为 150 个以上) ，一种可能的组批和 排序方式可以编码为如下的向量: ［1 2 3 * 4 5 * 6 7］． 根据编码可知，板坯 1、2 和 3 为第一个轧制单元，板 坯 4 和 5 为第二个轧制单元，板坯 6 和 7 为第三个 轧制单元，板坯加工顺序为 1、2、3、4、5、6 和 7． 3. 2. 2 适应值函数 采用式( 1) 、式( 2) 和式( 3) 的优化函数目标值 作为适应度函数值． 根据式( 1) 、式( 2) 和式( 3) 的 重要性，在计算中分阶段进行寻优． 3. 2. 3 遗传算子 遗传算子采用两交换启发交叉算法［14］． 其基 本思想为: 以 7 块板坯为例，假设 7 块板坯分别为 1、2、3、4、5、6 和 7． 随机选出一对未匹配的双亲去 除分隔符后， F =［7 2 6 4 1 5 3］， M =［3 2 1 7 5 6 4］． 随机选出初始板坯的位置号 j = 3，板坯号 Sj = 7，左转动使两双亲的第三个位置的板坯号为 7， F =［5 3 7 2 6 4 1］， M1 =［2 1 7 5 6 4 3］， C1 =［x x 7 x x x x］． 然后，选择位置号 j = 4 处的板坯． 若 d72 ＞ d75， 则 F1以 5 为中心左转得到如下中间代: F =［4 1 x 5 3 2 6］， M2 =［2 1 x 5 6 4 3］， C2 =［x x 7 5 x x x］． 重复上述过程直到子代中所有位置的板坯都确 定，最终可得到类似如下排序的结果: C =［3 2 7 5 6 4 1］． 依次计算热轧批量计划中相邻两板坯的跳跃惩 罚值，若 d56 = ∞ ，则在板坯 5 和 6 之间插入分割符 从而得到完整的解向量: C =［3 2 7 5 * 6 4 1］． 3. 2. 4 选择机制 当前种群经过遗传变异后生成子代种群，将当 前种群并入到子代种群，计算适应值，然后将适应值 最好的前几个个体直接复制到新一代种群中，剩余 的个体根据种群规模按照随机通用采样方法［15］确 定是否复制到新一代种群． 3. 2. 5 停止条件 停止条件设置为算法运行到一个预先设定的迭 代次数时停止并取当前种群中最好的结果输出． 3. 3 禁忌搜索算法 禁忌搜索是解决组合优化问题的一种策略，它 于 1970 年首先应用于非线性覆盖问题的优化过程， 后来又应用于从图论到一般纯整数规划问题和混合 整数规划问题及旅行商问题等． 文献［16］详细阐述 了禁忌搜索算法的原理和应用． 禁忌搜索的特点 是: 为了避免搜索陷入死循环，构造了一个短期循环 记忆表———禁忌表，表中存放刚进行过的 | θ | ( 禁忌 表的长度) 个邻域移动，每个移动在以后的 | θ | 次循 环内是禁止的，禁忌表在搜索过程中不断修改，使搜 索向着更好的方向前进． 本文采用的方法是: 将所有板坯两两配对，形成 板坯对群，针对每次遗传算法运算所得到的下一代 种群中的每一个解，依次交换每对板坯对，得到新的 解，计算其适应值，找到适应值优于原解的新解取代 原来的解，若无则保持不变． 具体方法为: 假设下一 代种群中的一个解 O =［3 2 7 5 * 6 4 1］，去除分隔 符后 O0 =［3 2 7 5 6 4 1］，则会有 C2 7 = 21 对板坯 对，依次交换每对板坯对形成 21 个新的解向量，假 设选取的板坯对为( 6，5) ，则新的解向量为 O1 =［3 2 7 6 5 4 1］，计算紧邻轧制的两块板坯跳跃的惩罚 值，若 d7，6 = ∞ 则在板坯 7 和 6 之间插入分隔符，从 而得到新的解 O =［3 2 7 * 6 5 4 1］． 重复上述过 程，会得到 21 个新解，计算其适应值与原有的解进 行比较，选取最优的解取代原有的解． 3. 4 混合算法 在大多数工程优化问题中，由于常常带有复杂 的约束条件，简单的遗传算法往往不能很好地解决 这类工程优化问题． 在遗传算法中增加所求解问题 的先验知识对于求解效果的影响很大［17］． 本文选 ·460·