改进的装炉组合问题建模与优化算法
王志刚，刘全利，王伟
（大连理工大学信息与控制研究中心，辽宁大连116024）
摘 要：针对罩式炉退火生产中的钢卷组合堆垛优化问题，建立了以最小化钢卷纽炉总加热时间为目标的数学模型。模型综合考虑了钢卷自身属性以及生产工艺约束条件等因素对钢卷组炉加热处理时间的影响。在分析罩式炉退火加热工艺规范的基础上，提出了一种改进自适应遗传算法对模型求解。算法首先类比装炉组合问题与一维装箱问题的相似点分组编码染色体，借鉴装箱问题的优化思想改善初始解种群质量；然后在工艺规则的指导下对遗传基因进行启发式交叉和变异，变异率和交叉率随种群收敛程度自适应调整以保证种群多样性和全局收敛性；最后结合局部穷举搜索方法实现了对上述模型的优化计算。仿真对比实验以及现场实际应用效果均表明该算汝相对其他算法的优越性。
关键词：罩式炉退火；组合优化；装箱问题；分组遗传算法
中图分类号：TP 399 文献标识码：A
1引言
罩式炉退火是冶金企业生产高质量冷轧薄板产品的一道关键工序，是大部分冷轧薄板厂生产的主要瓶颈。装炉组合是罩式炉退火的开始环节，即按照特定的工艺规则将若干钢卷按一定次序放进同一退火炉中。不同装炉组合会对总加热时间在一个范围内调节，所以，优化装炉组合能够直接降低能源消耗。
钢卷装炉组合过程存在诸多约束条件，现场根据生产经验人工完成装炉的方法效率较低。文献[2]对装炉组合问题进行了抽象建模，并采用遗传算法求解，取得了优于入工组合的结果。文献[3]对装炉组合问题进行了两阶段多目标优化。以上文献提出的优化目标均是批次钢卷装炉组合后总加热时间最小，但目标函数却不是总加热时间，而是对退火工艺规则不同理解后的转化形式。这种转化便于模型的求解计算，但模型的抽象均忽略了钢卷钢种和厚度对加热时间的影响。
本文在分析退火工艺规则的基础上，考虑影晌加热时间的各方面因素，建立了以总加热时间为目标函数的装炉组合数学模型。以工艺规则作为启发式指导，给出一种改进的自适应遗传算法对模型寻优，结果较好。
图中可以看出加热时间在退火工艺流程中占较大比重。同时，根据工艺规则加热时间延长也会导致对应冷却时间增加。所以，优化装炉组合对提高生产效率具有重要的现实意义。
钢卷组合堆垛示意图，如图2所示。
组垛装炉过程中要考虑钢卷的外径、宽度、厚度等几何特征，使堆垛的属性与炉子的属性匹配。
现场给出的主要装炉堆垛原则如下：
①不同钢质、不同规格的退火制度，混装时按****质量的要求退火。
②尽可能把具有相同退火工艺制度、规格、钢质的钢卷同炉退火。
③宽度及厚度相同且外径不同的钢卷，按卷径大小自下向上堆放。
④外径相同，宽度不同时，按宽窄自下向上堆放。
⑤外径和宽度相同且厚度不同时，按厚薄自下向上堆放。
⑥同一炉内钢卷数不能超过5。
⑦堆垛离度=钢卷宽度+中间对流板厚度+底部对流板厚度（对流板厚度为70 mm），并且堆垛高度≤4 350 mm。
⑧在安排堆垛时，保持炉内尽可能的****堆垛高度。
每一炉钢卷的加热时间根据退火工艺确定，而不是单纯某项指标的简单解析函数，见表1。
装炉的加热时间与钢卷的钢种、厚度和重量有关。钢种和厚度对加热时间的影响体现于上述原则②不同钢种混装或者同一钢种不同厚度规格（MR，MR2除外）混装的钢卷会造成加热时间的增加。钢卷重量对加热时间的影响表现如下：
加热时间随装炉钢卷总重量的增加在一定范围内呈阶梯状增长，相邻工艺设定重量之差力5t（MR，MR2为2 5 t）。这3个因素相互影响、相互制约，所以摹方面优化得不到****解。
3问题建模
基于上述退火工艺的分析，建立装炉组合的数学模型如下：假设n为待组合的候选钢卷数；m为装炉组合后的装炉计划数，即钢卷堆垛的数量；A 为钢卷集合，其中的元素为钢卷序号；B为装炉计划集合，其中的元素为装炉计划号；h表示序号为z的钢卷的宽度；Hmax=4 350 mm为退火炉所允许的****装炉高度；形表示计划号为j的装炉各钢卷重量集合；cj表示计划号为J的装炉钢卷钢种集合；C表示计划号为j的装炉钢卷厚度集合。
部分钢种的罩式炉退火混装规则，见表2。
0表示计划号为j的装炉加热时间。则装炉组合问题抽象为下述数学模型：
式(1)为优化目标函数，即最小化装炉组合的各炉加热时间之和；式(2)表示装炉的加热时间由装炉规则①和装炉内钢卷的规格（钢种、重量、厚度）查退火工艺表获得；式(3)表示装炉内钢卷的钢种满足混装规则表；式(4)表示任一钢卷只能在所有的装炉计划中出现一次；式(5)表示每炉钢卷的堆垛高度不超过退火炉允许的****高度；式(6)表示每炉钢卷数不超过5。
4优化算法设计
以最小化总加热时间为优化目标的罩式炉退火钢卷组合堆垛问题是典型的NP雉问题。由于装炉的加热时间与钢卷参数之间没有明确的解析表达式关系，难以用精确算法求解。遗传算法作为一种比较成熟的进化算法，具有不依赖于领域知识，不受搜索空间限制以及内在并行性等优势。比较适合解决以上问题。实际上，装炉组合问题类似于经典的一维装箱问题，只是优化目标函数和约束条件略有区别。本文通过借鉴装箱问题的研究成果和思想，对上述模型的优化算法进行寻优指导。
1)适应度函数设计适应度函数为
式(7)表明装炉组合总的加热时间越短，适应度函数越大，个体越优良。
2)染色体编码方式文献[2]和文献[3]的遗传算法都是采用自然数对钢卷进行编码。实际上装炉组合问题的目标函数只与钢卷的组合有关，而与同一装炉计划内的钢卷次序无关，也与不同装炉计划之间的次序无关。所以无论是单独对钢卷还是对装炉编码，冗余度都较大，并且会随问题规模增加大幅上升。文献[3]引入了虚拟钢卷，使装炉计划数固定，方便计算。同时也人为扩大了问题的规模，使解的冗余度增大，增加了不可行解的可能。
装炉组合问题与一维装箱问题类似，都属于一类分组问题，本文采用对装炉和炉内钢卷共向编码的方式。染色体结构为：基因的位置表示装炉计划，基因的值表示该装炉计划中包含的钢卷（按钢卷序号升序排列）。染色体长度为装炉计划个数。例如，有12个钢卷要装炉，则可能的染色体有G1={(1,2,3,4),(5,6,7),(8,9,10,11,12)},g2={(1,2,6,8),(4,5,9,12),(3,7,10,11)},g3={(4，5，9，12)，(1，2，6，8)，(3，7，10，ll)}等。其中，染色体g1表示：1，2，3，4号钢卷组成装炉计划l；5，6，7号钢卷组成装炉计划2；8，9，10，11，12号钢卷组成装炉计划3。染色体g2和g3代表相同的解。这种编码表示使基因既表示钢卷又表示装炉计划，大大减少了冗余。
3)初始种群优化文献[2]和文献[3]的初始种群都是随机生成的，种群的质量难以保证。本文根据退火工艺规则，同时借鉴一维装箱问题的FFD算法，提出一种选择初始次优解的分类MMFFD(MAX-MJN FFD)算法，步骤如下：
Step l 对待组合钢卷按照钢种分类。
Step 2对进行完Step l的每一类钢卷（钢种相同）根据退火工艺衷中对本钢种规定的厚度规格临界值（如表1中的0. 35 mm，0.5 mm）分类。
Sfep3对进行完Step 2的每一类钢卷（钢种和厚度规格范围均相同）先按照钢卷宽度降序排列，然后在保持宽度降序排列的基础上对重量降序排列。
Step 4依次对进行完Step 3的每一类钢卷进行装炉操作如下：假设其中一个分类为集合D={d1，d2，…，dk}插入到本类钢种下一个厚度规格分类的起始部分；如果D为本类钢种最后一个厚度规格分类，则将D合并人P。如果k>3，将d1，d2，…，依次装入同一个装炉计划，直到不满足约束条件(5)或(6)。此时，逆序从dk开始试探，如果满足约束条件则将巩加入此计划。然后继续试探dk-1，以此类推，直到不满足约束条件(5)或(6)。对D中剩余钢卷如前面步骤正序装炉下一个计划，然后再逆序试探。直到D中钢卷均完成装炉（转入下一分类集合）或者余下的钢卷小于3个(插入到下一分类集合起始或者并人P)。
Step 5 对所有分类装炉组合完毕后，如果P≠φ，则按照混装规则采用穷举法对P中钢卷装炉，取****的组合，算法结束；如果P=φ，算法结束。
算法通过分类方法尽量满足装炉堆垛原则②，即相同钢种、规格的钢卷尽量装到同一炉内。混装钢卷集合尸中的元素都是各钢种装炉剩下的钢卷，个数比较少。而且同批次退火的钢种数也比较少，所以，对P可以采用穷举法找出****组合。同时，每一分类中的钢卷装炉组合问题可以转化为一维装箱问题，采用MAX_MIN与FFD相结合的方法使得在原则②的前提下每一炉尽可能多装钢卷以减少装炉数来获取一个初始近似****解。
遗传算法初始种群中的其他解仍然是靠随机生成，但不是完全随机的。因为混装规则的存在可能使完全随机排列出的装炉组合为不可行解，所以先根据混装规则对钢卷进行分类。每一类中的钢卷都是能够混装的，不同类中的钢卷不是能够完全混装的。同一批钢卷根据混装规则可能有多种分类的方法。然后对每类中的钢卷进行随机排列后采用FF( First Fit)算法9装炉，即：每个钢卷都对前面所有已装好的计划进行试探，直到其装入第一个满足约束条件的装炉计划，或者所有已装好的计划都满足，则开启—个新的装炉计划。然后对每类钢卷装炉剩下的铜卷按照混装规则进行装炉。这样的选择使得初始种群完全为可行解，同时既存在较优化的个体来保证种群的初始进化度，又没有收缩种群的搜索空间。
4)选择算子本文采用轮盘赌算法对个体进行选择复制操作。个体s的选择概率P。如下式：
选择过程同时采取****个体保留的策略，选择保留适应值****百分之5传算法，能够根据种群进化的进程自适应调解交叉概率和变异概率，取得了较好的效果。本文采用文献[s]的方法计算交叉概率P1。
文献19]以一个经典分组问题为案例表明了文献[6]方法很大程度依赖于交叉算子的智能。本文借鉴上述思想，对双亲双子交叉策略改进如下：
Step l按交叉概率获取2个参与交叉的个体p1和p2作为父代，并假设由它们交叉生成的子代个体分别为σ1和σ2。
Step 2从父代p1选择随机比例的****良部分基因拷贝到子代σ1。
Step 3对父代P2包含子代。，元素的基因剔除σ1的元素后拷贝到集合Tc。
Step 4将父代p2不包含子代σ1，元素的基因拷贝到子代σ1。
Step 5将t中基因恢复成钢卷状态并依欢试探装入σ1中不足5个钢卷的装炉计划。如果有满足约束条件的装炉则选择装入使加热时间增加最少的装炉计划。
Step 6对Tr中剩余钢卷按混装规则分类。对于钢卷数大于8的类采用FFD算法装炉；否则采用穷举法获取****的装炉组合。
Step 7交换父代P1和P2的角色，重复上面Step 2~Step 6生成子代σ2。
Step 8返回Step l继续筛选、交叉剩下的个体，直到所有个体都计算完毕，操作结束。
6)变异算子 变异概率Pm的计算同文献。变异操作如下：
Step 1 随机选取染色体上的2个基因恢复成钢卷状态放入集合Tm。
Step 2对Tm中的钢卷依次试探加入不足5个钢卷的装炉计划。如果有满足约束条件的装炉则选择装入使加热时间增加最少的装炉计划。
Step 3对Tm中剩余钢卷采用穷尽法装炉，取其中总加热时间最短的组合。
之所以选择2个基因进行变异是因为选择1个基因变异的情况下，如果中所有元素均不能加入已有装炉计划时变异操作将失去意义；而选择3个及其以上的基因时Step 3局部优化搜索策略计算量增加会降低算法效率。
5仿真实验对比分析及应用
本文设计了以下几方面的实验以验证本文算法相对于其他算法的优越性。
1)优化目标函数财比采用文献[3]的遗传算法，针对不同目标函数优化，绘制总加热时间随优化代数变化的曲线，如图3所示。
实验数据从现场数据库中随机选取80个钢卷。算法设计参数：种群数目100，****进化代数500，K1=0.3，K2=0 4．k3=0.8，k4=0.9。可以看出，以总加热时间为优化目标函数能够在进化过程中逐步以较快速度不断减少总加热时间；以装炉高度偏差的平均值为优化目标的方法通过间接优化装炉计划数目（阶梯状下降部分）实现了对总加热时间的有限优化；优化装炉重量偏差平均值的方法未能实现对总加热时间的有效优化。表明了本文目标函数选择的合理性。
2)初始种群质量对比假设随机实验数据中所有钢种均可混装，以消除随机初始化的不可行解。分别采用完全随机和本文提出的分类FF算法生成初始种群，初始种群数目100，绘制种群个体总加热时间随个体序号变化的曲线，如图4所示。
可以看出，本文算法的初始种群质量明显高于随机产生的种群。同时，采用MMFFD算法生成的次优解要明显优于其他初始解。说明工艺规则对算法改善有重要指导意义。
3)算法搜索效率对比将本文算法与一般自适应遗传算法（文献[3]算法，但交叉、变异率均采用文献[8]的计算方法）对比，算法参数选择相同的值，绘制总加热时间随优化代数变化的曲线，如图5所示。
可以看出，本文算法实现了快速收敛到较优解，优于一般算法。原因在于基于规则指导的智能交叉操作使优良基因迅速扩散，同时，局部搜索策略进一步加快了算法对****解的逼近。
算法智能性的提高是以计算量增加为代价的。通过对多组等量随机数据进行测试，本文算法对80个钢卷的装炉组合问题平均计算时间为57.3 s，视不同钢卷对象在Ss范围内波动。装炉组合问题属于“离线”问题，实时性要求不高，算法速度能够满足现场应用要求。
4)优化解对比采用本文算法和一般算法对不同数量钢卷分别进行多组计算后取优化平均值进行对比，绘制平均总加热时间随钢卷数目变化的曲线，如图6所示。
可以看出，钢卷数目较少时两种算法找到的****解基本一致；随着钢卷数目的增多，本文算法****解逐渐优于一般算法。这种现象可以做如下解释：问题规模较小时解空间也较小，两种算法都能充分搜索找到****解。问题规模较大时解空间随之大幅增加，一般算法难以充分有效搜索解空间，而本文算法针对问题特点采用分组编码、智能交叉和变异并结合本地搜索的方法，减少了冗余度，能够有目的地向****解方向探索。
5)现场应用 本文算法已经嵌入文献[2]罩式炉退火优化排产软件中稳定运行了9个多月。累计加热时间与文献[2]算法相比缩短了百分之5.4。某次现场装炉组合自动排产结果：共形成退火计划22个，所有退火计划均符合工艺规定。组合结果不再追求装炉重量尽量贴近工艺设定重量，而是缩短总加热时间，如图7所示。
6 结 语
本文针对罩式炉退火生产的装炉组合工序建立了比较完备的、符合现场工艺规则的数学模型。减少批次装炉总加热时间为目的，在发掘工艺制度 对钢卷组合指导作用的基础上，提出了一种改进自适应遗传法对模型优化求解。方法直观、有效，现场应用取得了相对同类算法更好的效果，提高了装炉效率。
|
