·1200· 北京科技大学学报 第34卷 i∈{1,2，…，}，s∈{1,2，，S}; (10) 效性. Q.ye-QU≥0， 针对己经建立的具有多约束的非线性目标的 i∈{1,2，…，I},c∈{1,2，…，C}. (11) 0一1整数规划模型，本文提出一种计算复杂性较低、 目标函数(1)中，E为板坯s匹配给合同i的切 求解性能较好的改进遗传算法，并设计了对非可行 损费用及钢种匹配费用， 解具有启发式修复功能的求解策略.改进遗传算法 Ei= 流程见图1. 「y.(Q.-Q0）+重，+QUCS(aMS,c0,）Q.-QUm>0, 确定实际问题参数 1Q.CS(MS,,GO,) Q.-QU≤0. 出约束5-(11)产生 E为钢卷c匹配给合同i的切损费用及钢种匹配 每一个余材的可选合同集合 1 费用， 随机尘成初始种群 Eie= 「y.(Q.-QUmn）+重.+QUCC(GCe,G0,）Q.-QUx>0, 种群中个体 通过贪心策略对 满见约束(2)？ 种群中个体进行修复 1Q.CC(GC.,GO,) Q.-QUnx≤0. 计算种昨中个体适应度 Lack, 1 mr{Q-(言x.+0o}, 满足停止条件？ >算法结束 N unFinish,= 按照轮盘赌规则选择 个体进行交义操作 有 0 Q-（0+0x≤0. 以概率对个体进行变异操作 1 1否则 变异后产生的 对不清足约束的 目标函数(1)中第一项为板坯和钢卷规格和钢 新个体满足釣束？ 个体进行修复 种总匹配费用，第二项为未被匹配板坯和钢卷的总 惩罚费用，第三项为己匹配合同的优先级奖励费用， 图1改进遗传算法流程图 第四项为己匹配余材的优先级奖励费用，第五项为 Fig.1 Flow chart of the improved GA algorithm 未完成合同的欠量惩罚及未完成合同惩罚费用；约 改进遗传算法的详细设计如下. 束(2)表示匹配给生产合同的钢卷与板坯质量之和 (1)编码.为满足约束条件(3)和(4)，采用分 不超过合同要求的最大总质量：约束(3)表示每块 段整数编码方式，把染色体按照板坯和钢卷分成两 无委托板坯至多匹配给一个合同：约束(4)表示一 段，前段有S个基因位，后段有C个基因位，即染色 个钢卷至多匹配给一个合同：约束(5)表示与板坯s 体Chrom={s1,s2,…,sslc1,c2,…,cc},共计S+C 匹配的合同所要求的钢种要在板坯s可轧制钢种的 个基因位，每个基因位代表一个余材.s,和c。分别 集合范围内；约束(6)表示钢卷与合同的钢种匹配 表示板坯s和钢卷c的匹配情况： 要在合同要求可接受的钢种匹配范围内；约束(7) ri 板坯s匹配给合同i, 表示钢卷的厚度要在合同要求的公差范围内；约束 5,=0没有合同与板坯s匹配： (8)表示生产工艺约束，合同要求的宽度与板坯的 钢卷c匹配给合同i, 宽度要满足轧线的侧压量限制要求：约束(9)表示 =0没有合同与钢卷c优海 钢卷的宽度要在合同要求的宽度公差范围内：约束 (2)初始种群生成.为缩小解的搜索空间，首 (10)和(11)表示与合同匹配的余材的质量须不小 先根据约束条件(5)~(11)生成每个余材可匹配的 于合同要求的最小单元质量. 合同集合OM{}(表示余材j可匹配的合同集合，若 2算法描述 不能匹配给任何合同，则为空集).在每个基因位 上，从其对应的可匹配合同集合中随机选择一个合 遗传算法在解决旅行商问题4-、流水作业调 同（当可匹配合同集合为空集时，产生的合同号为 度问题、柔性作业车间调度问题切和包装问 0,表示没有合适的合同与该余材进行匹配).随机 题图等都有很好的效果，对于解决多背包问 生成Popsize个满足约束(3)~(11)的初始可行解. 题90也比较适合，足见其解决组合优化问题的有 (3)初始种群修复策略.将初始解代入约束条北 京 科 技 大 学 学 报 第 34 卷 i∈{ 1，2，…，I} ，s∈{ 1，2，…，S} ; ( 10) Qcyic － QUi min≥0， i∈{ 1，2，…，I} ，c∈{ 1，2，…，C} ． ( 11) 目标函数( 1) 中，Eis为板坯 s 匹配给合同 i 的切 损费用及钢种匹配费用， Eis = γs ( Qs － QUi max ) + Φs + QUi maxCS( MSs，GOi ) Qs － QUi max ＞ 0， QsCS( MSs，GOi ) Qs － QUi { max≤0． Eic为钢卷 c 匹配给合同 i 的切损费用及钢种匹配 费用， Eic = γc( Qc － QUi max ) + Φc + QUi maxCC( GCc，GOi ) Qc － QUi max ＞ 0， QcCC( GCc，GOi ) Qc － QUi { max≤0． Lacki = max { Qi min － ( ∑ S s = 1 Qsxis + ∑ C c = 1 Qcyic ) ，0 } ， unFinishi = 0 Qi min － ( ∑ S s = 1 Qsxis + ∑ C c = 1 Qcyic ) ≤ 0， 1 否则 { ． 目标函数( 1) 中第一项为板坯和钢卷规格和钢 种总匹配费用，第二项为未被匹配板坯和钢卷的总 惩罚费用，第三项为已匹配合同的优先级奖励费用， 第四项为已匹配余材的优先级奖励费用，第五项为 未完成合同的欠量惩罚及未完成合同惩罚费用; 约 束( 2) 表示匹配给生产合同的钢卷与板坯质量之和 不超过合同要求的最大总质量; 约束( 3) 表示每块 无委托板坯至多匹配给一个合同; 约束( 4) 表示一 个钢卷至多匹配给一个合同; 约束( 5) 表示与板坯 s 匹配的合同所要求的钢种要在板坯 s 可轧制钢种的 集合范围内; 约束( 6) 表示钢卷与合同的钢种匹配 要在合同要求可接受的钢种匹配范围内; 约束( 7) 表示钢卷的厚度要在合同要求的公差范围内; 约束 ( 8) 表示生产工艺约束，合同要求的宽度与板坯的 宽度要满足轧线的侧压量限制要求; 约束( 9) 表示 钢卷的宽度要在合同要求的宽度公差范围内; 约束 ( 10) 和( 11) 表示与合同匹配的余材的质量须不小 于合同要求的最小单元质量． 2 算法描述 遗传算法在解决旅行商问题［14--15］、流水作业调 度问题［16］、柔性作业车间调度问题［17］ 和 包 装 问 题［18］等都有很好的效果，对 于 解 决 多 背 包 问 题［19--20］也比较适合，足见其解决组合优化问题的有 效性． 针对已经建立的具有多约束的非线性目标的 0--1 整数规划模型，本文提出一种计算复杂性较低、 求解性能较好的改进遗传算法，并设计了对非可行 解具有启发式修复功能的求解策略． 改进遗传算法 流程见图 1． 图 1 改进遗传算法流程图 Fig． 1 Flow chart of the improved GA algorithm 改进遗传算法的详细设计如下． ( 1) 编码． 为满足约束条件( 3) 和( 4) ，采用分 段整数编码方式，把染色体按照板坯和钢卷分成两 段，前段有 S 个基因位，后段有 C 个基因位，即染色 体 Chrom = { s1，s2，…，sS | c1，c2，…，cC } ，共计 S + C 个基因位，每个基因位代表一个余材． ss 和 cc 分别 表示板坯 s 和钢卷 c 的匹配情况: ss = i 板坯 s 匹配给合同 i， {0 没有合同与板坯 s 匹配; cc = i 钢卷 c 匹配给合同 i， {0 没有合同与钢卷 c 匹配． ( 2) 初始种群生成． 为缩小解的搜索空间，首 先根据约束条件( 5) ～ ( 11) 生成每个余材可匹配的 合同集合 OM{ j} ( 表示余材 j 可匹配的合同集合，若 不能匹配给任何合同，则为空集) ． 在每个基因位 上，从其对应的可匹配合同集合中随机选择一个合 同( 当可匹配合同集合为空集时，产生的合同号为 0，表示没有合适的合同与该余材进行匹配) ． 随机 生成 Popsize 个满足约束( 3) ～ ( 11) 的初始可行解． ( 3) 初始种群修复策略． 将初始解代入约束条 ·1200·