论文部分内容阅读
[摘 要]炼钢-连铸阶段批量生产排程中的炉次计划问题，其实质是基于合同板坯和炼钢炉的多背包问题，属于组合优化中的NP完备问题，本文针对某大型钢铁企业炉次计划中的具体问题设计了一种基于启发式规则的改进的人工鱼群算法，并在生产计划问题中进行了成功运用。
[关键词]启发式规则；炉次计划；改进人工鱼群算法
中图分类号：V547.45 文献标识码：A 文章编号：1009-914X（2017）20-0272-03
一、炉次计划数学模型
由于炼钢生产工艺的惯性和大规模的批量生产方式，单炉产量具有一定的范围限制。标准炉重与实际生产炉重之间的偏差称为流平衡重，编制炉次计划要尽可能减小流平衡重，通过合理高效的板坯组合设计炉次来减少产生的余材量。针对组炉多目标优化问题，炉次计划模型作如下假设：
（1）炉次计划数目已知；
（2）单个合同板坯需求量小于炼钢炉容量且不可分解；
（3）炼钢炉容量为已知常量。
组炉问题可描述为如下优化模型：
x以上目标函数进行加权处理可将该多目标优化问题简化单目标优化问题，得到如下模型。
问题优化的各个目标都可以看做是组合费用，式（1-1）表示最小化炉次余材量，式（1-2）表示最小化总的炉次流平衡重，式（1-4）表示模型优化的总目标即实现最小化的组合费用。式（1-5）表示单炉产量必须满足炼钢炉容量的约束，式（1-6）、（1-7）和（1-8）表示变量的取值范围。
（一）模型参数
用到的符号说明如下：
表示炉次中产生的余材量；值为1表示板坯i组合在炉次中，否则值为0；表示板坯的必要板坯重量；表示炉次计划数；表示板坯总数；表示总的炉次的集合；表示炉次的炉重下限值；表示炉次的炉重上限值；表示板坯序号；表示炉次序号。
（二）算法的基本思想
人工鱼群算法是以具有人工智能思想的人工鱼为基础进行移动行为模拟和引导，求解中存在的不足主要包括：随机移动的人工鱼随机移动时难以跳出平坦搜索区域，收敛速度慢甚至过早收敛；算法的寻优速度在后期较慢，原因是参数的设置比较符合前期广阔的搜索区域，当区域变小不再适用设定的参数；对于大规模的组合寻优问题求解，随机试探的行为选择策略将导致计算量很大。设置休眠因子帮助人工鱼跳出局部极值点，缓解了算法后期搜索性能降低收敛速度下降的情况。采用随机算子丰富了种群的多样性；人工鱼邻域中心点用鱼群的中心点替换，并用全局极值点替换邻域极值点，采用有进步即可的移动选择策略，促进寻优的快速收敛。
（三）人工鱼行动策略描述
在一个维搜索空间中，由条人工鱼组成的人工鱼群中，人工鱼个体用向量表示，代表了一个备选的方案，其中是要寻优的变量，若，表示合同板坯未编入任何一个炉次；若，表示合同板坯被选入方案中；人工鱼当前状态下对应的目标函数值为；在这里目标函数值越小，表示食物浓度越大。在AFSA中定义了3个控制参数：人工鱼群的拥挤度因子，人工鱼移动的最大尝试次数，人工鱼视野范围，最大寻优代数，人工鱼之间的距离表示两者之间不同分量个体的数目，。
（1）觅食行为。当前状态，目标函数值为，在其视野内随机选择目标，目标函数值为。如果 （对于极小化问题，以下同），满足处食物浓度大于当前状态，则往方向前进一步，即的下一个状态，对第一个不相等的分量，并遵循移动的启发式规则，其他，完成觅食[58-59]；否则，搜索新目标。并判断是否满足觅食前进条件，若达到最大尝试次数，则向已知整个鱼群的最优解移动一步，这样既保持移动的进步，有助于跳出局部极值点，也保留了解的多样性。
（2）追尾行为。当前状态在其视野内最优的邻居，目标函数值为。周围邻居的数目，如果满足，表明周围食物较多且不太拥挤，则往方向前进一步，即的下一个状态，对第一个不相等的分量，并遵循移动的启发式规则，其他；否则进行觅食行为。
（3）聚群行为。当前状态在其视野内的所有个邻居中心位置，目标函数值为。如果满足，则往方向移动一步，即人工鱼的下一个状态Xa +1=（xa +1，1，xa +1，2，…，xa+1，n），对第一个不相等的分量xa，k≠xcenter，k，xa+1，k=xcenter，k，并遵循移动的启发式规则，其他xa+1，k=xa，k，1≤k≤n；否则人工鱼进行觅食行为。
（4）随机行为。启发式随机行为：炼钢组炉问题的解是一个n 维整数向量（n个合同板坯所在炉次号的顺序序列，炉号为0的表示未组入任何一炉次中），对第a 条鱼的n 个分量依次进行随机变异，并遵循以下启发式规则：
步骤一：在随机过程中，设将合同板坯i随机组入炉次j 中，Cj 为炉次j的剩余容量，根据不同的情况采取相应的移动策略。若满足随机化条件，即合同板坯i的重量wiCj，则不断从炉次j中随机取出合同板坯e，并将e 的炉号改为0，直至滿足移动条件wi>Cj，并执行随机化。
步骤二：当所有m条鱼都执行了步骤一，则结束随机过程，否则转步骤一继续。
随机过程能够产生发散的随机解有助于人工鱼摆脱局部极值点，能有效地改善算法后期收敛速度减慢性能降低的不足。
（5）公告板。公告板是为了记录算法各代搜素到的最优解。个体在寻优过程中，通过比较聚群和追尾的行为预期，选择结果更好的行为进行更新，默认方式为觅食行为。每次移动后通过比较决定是否刷新公告板，如果自身当前状态的目标函数值优于公告板状态的目标函数值，则以自身刷新公告板状态，从而记录下历史最优的状态。如果在一代完整的循环中，所有人工鱼的状态都差于公告板，则把公告板的状态随机赋给一条人工鱼，用当前最优解引导下一代寻优循环。 （6）移动选择策略。人工鱼移动采取有进步即可选择策略，减小组炉问题的计算量。每条鱼优先进行追尾行为，若失败则进行群聚行为，若仍失败则进行觅食行为。每次行动尝试结果如果优于公告板，则刷新公告板并结束当前行为，否则继续。
（7）休眠因子。为了弥补算法在寻优过程中存在的不足，用休眠因子记录寻优过程中公告板保持最优的连续代数。当寻优后期，跳不出局部极值点时，即休眠因子达到其上限值时，激活算法中的启发式随机行为，改善算法的寻优动作。
二、算法实现
（一）人工鱼编码
设有个重量为的合同板坯，个炉次，将个合同板坯按顺序组成一个字符串，。例如，表示将十个物品分别装包，1号炉次装入第5，6，9号合同板坯；2号炉次装入第2，10号合同板坯；3号炉次装入第3，8号板坯；4号炉次装入第1，4号合同板坯，第7个板坯未组炉。
（二）算法流程
求炼钢组炉问题的改进人工鱼群算法（ IASFA），算法的步骤如下：
（1）初始化。设定群体大小fish_size =200，感知距离visual =50；拥挤度因子δ=0.6；休眠因子上限值max_sleep，觅食最大的试探次数max_try，最大寻优代数max_iter。在可行域范圍内随机生成fish_size 条人工鱼个体， 形成初始鱼群，分别计算其目标函数值，以最优的个体初始化刷新公告板。为了使人工鱼尽量靠近搜索域的约束边界，初始化时应尽量将背包装满，如果合同板坯i的重量是否小于炉次j的剩余容量，即wi≤Cj，则将合同板坯i装入炉次j，炉次j的剩余容量；否则合同板坯i 不装入任何炉次。
（2）采取有进步即可的移动选择策略，减小组炉问题的计算量。每条鱼优先进行追尾行为，若失败则进行群聚行为，若仍失败则进行觅食行为。每次行动尝试结果如果优于公告板，则刷新公告板并转（3），否则继续尝试其他行为。
（3）当所有fish_size条鱼都执行了操作（2），则转（4），否则转（2）继续。
（4）进化代数加1，若公告板进行了更新， 则休眠因子sleep_cnt清零，否则休眠因子加1。若休眠因子达到其上限值max_sleep，则执行启发式随机过程。若在一代完整的循环中，所有状态都差于公告板，则把公告板的状态随机赋给一条人工鱼，用当前最优解引导下一代寻优循环。
（5）若进化代数达到最大的寻优代数或者获得满足业务要求足够好的适应值、满足设定的精度、鱼群中个体的平均目标值不再有改进则输出计算结果，结束算法，否则转（2）继续。
三、系统实现和应用效果
现以某钢铁厂一天的合同板坯订单数据为例，原始订单数据共有206个板坯，共有七个钢种，参数如表1所示。
选取钢种为ZF4H6100，断面规格为260mm×2070mm的数据，算例的已知参数为：炉次计划数m=10，合同板坯数量n=97，总重1328.652t，WL=144t，WU=150t，WN=147t。算法中，设定人工鱼群的群体大小取80，迭代次数取200，人工鱼的感知距离取10，每次移动最大的试探次数取50， 拥挤度因子取0.618，计算结果如表3所示。
表2表示的是出钢记号为ZF4H6100的板坯分组中包含的7个断面的板坯和相应的板坯数量，以本组数据为例计算所得表3结果。
四、总结
本文针对某大型钢铁企业炉次生产计划中的具体问题设计了一种基于启发式规则的人工鱼群算法，并在炼钢组炉问题中进行运用。通过设置休眠因子帮助人工鱼跳出局部极值点，缓解了算法后期搜索性能降低收敛速度下降的问题。采用随机算子丰富了种群的多样性；邻域中心点用鱼群的中心点替换，并用全局极值点替换邻域极值点，采用有进步即可的移动选择策略，促进了寻优的快速收敛。开发了智能炼钢组炉系统，实际生产数据计算结果表明，改进后的算法在一定的生产条件下，能在合理的时间范围内给出一批合同最优的组炉方案，使得炉次计划的流平衡重较小，可明显降低组炉计划余材量，具有一定的可行性和优越性。本文算法对于其他有约束的组合优化问题也具有重要的价值。
参考文献
[1] 卢克斌.炼钢-连铸生产计划与调度的优化方法研究及应用[博士学位论文].沈阳：东北大学，2010.
[2] A. M. Frisch， I. Miguel， T. Walsh. Modeling a steel mill slab design problem[C]， Proceedings of the IJCAI Workshop on Modeling and Solving Problems with Constraints， 2011.
[3] 何琨，黄文奇，金燕.基于动作空间求解二维矩形Packing问题的高效算法[J].软件学报，2012，23（5）：1037-1044.
[4] 江贺.超启发式算法：跨领域的问题求解模式[J] .中国计算机学会通讯，2011，7（3）：63-70.
[5] S. Heinz， T. Schlechte， R. Stephan， M. Winkler. Solving steel mill slab design problems [J]. Constraints ， 2012， 17（1）： 39-50
[6] 李春梅，马良.求解多维–0-1背包问题的人工鱼群算法[J].数学的实践与认识，2010，40（17）： 195-199.
[7] 李跃松，樊金生，张巧迪.用改进的人工鱼群算法求解TSP问题[J].石家庄铁道大学学报（自然科学版），2011，24（2）：103-110.
[关键词]启发式规则；炉次计划；改进人工鱼群算法
中图分类号：V547.45 文献标识码：A 文章编号：1009-914X（2017）20-0272-03
一、炉次计划数学模型
由于炼钢生产工艺的惯性和大规模的批量生产方式，单炉产量具有一定的范围限制。标准炉重与实际生产炉重之间的偏差称为流平衡重，编制炉次计划要尽可能减小流平衡重，通过合理高效的板坯组合设计炉次来减少产生的余材量。针对组炉多目标优化问题，炉次计划模型作如下假设：
（1）炉次计划数目已知；
（2）单个合同板坯需求量小于炼钢炉容量且不可分解；
（3）炼钢炉容量为已知常量。
组炉问题可描述为如下优化模型：
x以上目标函数进行加权处理可将该多目标优化问题简化单目标优化问题，得到如下模型。
问题优化的各个目标都可以看做是组合费用，式（1-1）表示最小化炉次余材量，式（1-2）表示最小化总的炉次流平衡重，式（1-4）表示模型优化的总目标即实现最小化的组合费用。式（1-5）表示单炉产量必须满足炼钢炉容量的约束，式（1-6）、（1-7）和（1-8）表示变量的取值范围。
（一）模型参数
用到的符号说明如下：
表示炉次中产生的余材量；值为1表示板坯i组合在炉次中，否则值为0；表示板坯的必要板坯重量；表示炉次计划数；表示板坯总数；表示总的炉次的集合；表示炉次的炉重下限值；表示炉次的炉重上限值；表示板坯序号；表示炉次序号。
（二）算法的基本思想
人工鱼群算法是以具有人工智能思想的人工鱼为基础进行移动行为模拟和引导，求解中存在的不足主要包括：随机移动的人工鱼随机移动时难以跳出平坦搜索区域，收敛速度慢甚至过早收敛；算法的寻优速度在后期较慢，原因是参数的设置比较符合前期广阔的搜索区域，当区域变小不再适用设定的参数；对于大规模的组合寻优问题求解，随机试探的行为选择策略将导致计算量很大。设置休眠因子帮助人工鱼跳出局部极值点，缓解了算法后期搜索性能降低收敛速度下降的情况。采用随机算子丰富了种群的多样性；人工鱼邻域中心点用鱼群的中心点替换，并用全局极值点替换邻域极值点，采用有进步即可的移动选择策略，促进寻优的快速收敛。
（三）人工鱼行动策略描述
在一个维搜索空间中，由条人工鱼组成的人工鱼群中，人工鱼个体用向量表示，代表了一个备选的方案，其中是要寻优的变量，若，表示合同板坯未编入任何一个炉次；若，表示合同板坯被选入方案中；人工鱼当前状态下对应的目标函数值为；在这里目标函数值越小，表示食物浓度越大。在AFSA中定义了3个控制参数：人工鱼群的拥挤度因子，人工鱼移动的最大尝试次数，人工鱼视野范围，最大寻优代数，人工鱼之间的距离表示两者之间不同分量个体的数目，。
（1）觅食行为。当前状态，目标函数值为，在其视野内随机选择目标，目标函数值为。如果 （对于极小化问题，以下同），满足处食物浓度大于当前状态，则往方向前进一步，即的下一个状态，对第一个不相等的分量，并遵循移动的启发式规则，其他，完成觅食[58-59]；否则，搜索新目标。并判断是否满足觅食前进条件，若达到最大尝试次数，则向已知整个鱼群的最优解移动一步，这样既保持移动的进步，有助于跳出局部极值点，也保留了解的多样性。
（2）追尾行为。当前状态在其视野内最优的邻居，目标函数值为。周围邻居的数目，如果满足，表明周围食物较多且不太拥挤，则往方向前进一步，即的下一个状态，对第一个不相等的分量，并遵循移动的启发式规则，其他；否则进行觅食行为。
（3）聚群行为。当前状态在其视野内的所有个邻居中心位置，目标函数值为。如果满足，则往方向移动一步，即人工鱼的下一个状态Xa +1=（xa +1，1，xa +1，2，…，xa+1，n），对第一个不相等的分量xa，k≠xcenter，k，xa+1，k=xcenter，k，并遵循移动的启发式规则，其他xa+1，k=xa，k，1≤k≤n；否则人工鱼进行觅食行为。
（4）随机行为。启发式随机行为：炼钢组炉问题的解是一个n 维整数向量（n个合同板坯所在炉次号的顺序序列，炉号为0的表示未组入任何一炉次中），对第a 条鱼的n 个分量依次进行随机变异，并遵循以下启发式规则：
步骤一：在随机过程中，设将合同板坯i随机组入炉次j 中，Cj 为炉次j的剩余容量，根据不同的情况采取相应的移动策略。若满足随机化条件，即合同板坯i的重量wi
步骤二：当所有m条鱼都执行了步骤一，则结束随机过程，否则转步骤一继续。
随机过程能够产生发散的随机解有助于人工鱼摆脱局部极值点，能有效地改善算法后期收敛速度减慢性能降低的不足。
（5）公告板。公告板是为了记录算法各代搜素到的最优解。个体在寻优过程中，通过比较聚群和追尾的行为预期，选择结果更好的行为进行更新，默认方式为觅食行为。每次移动后通过比较决定是否刷新公告板，如果自身当前状态的目标函数值优于公告板状态的目标函数值，则以自身刷新公告板状态，从而记录下历史最优的状态。如果在一代完整的循环中，所有人工鱼的状态都差于公告板，则把公告板的状态随机赋给一条人工鱼，用当前最优解引导下一代寻优循环。 （6）移动选择策略。人工鱼移动采取有进步即可选择策略，减小组炉问题的计算量。每条鱼优先进行追尾行为，若失败则进行群聚行为，若仍失败则进行觅食行为。每次行动尝试结果如果优于公告板，则刷新公告板并结束当前行为，否则继续。
（7）休眠因子。为了弥补算法在寻优过程中存在的不足，用休眠因子记录寻优过程中公告板保持最优的连续代数。当寻优后期，跳不出局部极值点时，即休眠因子达到其上限值时，激活算法中的启发式随机行为，改善算法的寻优动作。
二、算法实现
（一）人工鱼编码
设有个重量为的合同板坯，个炉次，将个合同板坯按顺序组成一个字符串，。例如，表示将十个物品分别装包，1号炉次装入第5，6，9号合同板坯；2号炉次装入第2，10号合同板坯；3号炉次装入第3，8号板坯；4号炉次装入第1，4号合同板坯，第7个板坯未组炉。
（二）算法流程
求炼钢组炉问题的改进人工鱼群算法（ IASFA），算法的步骤如下：
（1）初始化。设定群体大小fish_size =200，感知距离visual =50；拥挤度因子δ=0.6；休眠因子上限值max_sleep，觅食最大的试探次数max_try，最大寻优代数max_iter。在可行域范圍内随机生成fish_size 条人工鱼个体， 形成初始鱼群，分别计算其目标函数值，以最优的个体初始化刷新公告板。为了使人工鱼尽量靠近搜索域的约束边界，初始化时应尽量将背包装满，如果合同板坯i的重量是否小于炉次j的剩余容量，即wi≤Cj，则将合同板坯i装入炉次j，炉次j的剩余容量；否则合同板坯i 不装入任何炉次。
（2）采取有进步即可的移动选择策略，减小组炉问题的计算量。每条鱼优先进行追尾行为，若失败则进行群聚行为，若仍失败则进行觅食行为。每次行动尝试结果如果优于公告板，则刷新公告板并转（3），否则继续尝试其他行为。
（3）当所有fish_size条鱼都执行了操作（2），则转（4），否则转（2）继续。
（4）进化代数加1，若公告板进行了更新， 则休眠因子sleep_cnt清零，否则休眠因子加1。若休眠因子达到其上限值max_sleep，则执行启发式随机过程。若在一代完整的循环中，所有状态都差于公告板，则把公告板的状态随机赋给一条人工鱼，用当前最优解引导下一代寻优循环。
（5）若进化代数达到最大的寻优代数或者获得满足业务要求足够好的适应值、满足设定的精度、鱼群中个体的平均目标值不再有改进则输出计算结果，结束算法，否则转（2）继续。
三、系统实现和应用效果
现以某钢铁厂一天的合同板坯订单数据为例，原始订单数据共有206个板坯，共有七个钢种，参数如表1所示。
选取钢种为ZF4H6100，断面规格为260mm×2070mm的数据，算例的已知参数为：炉次计划数m=10，合同板坯数量n=97，总重1328.652t，WL=144t，WU=150t，WN=147t。算法中，设定人工鱼群的群体大小取80，迭代次数取200，人工鱼的感知距离取10，每次移动最大的试探次数取50， 拥挤度因子取0.618，计算结果如表3所示。
表2表示的是出钢记号为ZF4H6100的板坯分组中包含的7个断面的板坯和相应的板坯数量，以本组数据为例计算所得表3结果。
四、总结
本文针对某大型钢铁企业炉次生产计划中的具体问题设计了一种基于启发式规则的人工鱼群算法，并在炼钢组炉问题中进行运用。通过设置休眠因子帮助人工鱼跳出局部极值点，缓解了算法后期搜索性能降低收敛速度下降的问题。采用随机算子丰富了种群的多样性；邻域中心点用鱼群的中心点替换，并用全局极值点替换邻域极值点，采用有进步即可的移动选择策略，促进了寻优的快速收敛。开发了智能炼钢组炉系统，实际生产数据计算结果表明，改进后的算法在一定的生产条件下，能在合理的时间范围内给出一批合同最优的组炉方案，使得炉次计划的流平衡重较小，可明显降低组炉计划余材量，具有一定的可行性和优越性。本文算法对于其他有约束的组合优化问题也具有重要的价值。
参考文献
[1] 卢克斌.炼钢-连铸生产计划与调度的优化方法研究及应用[博士学位论文].沈阳：东北大学，2010.
[2] A. M. Frisch， I. Miguel， T. Walsh. Modeling a steel mill slab design problem[C]， Proceedings of the IJCAI Workshop on Modeling and Solving Problems with Constraints， 2011.
[3] 何琨，黄文奇，金燕.基于动作空间求解二维矩形Packing问题的高效算法[J].软件学报，2012，23（5）：1037-1044.
[4] 江贺.超启发式算法：跨领域的问题求解模式[J] .中国计算机学会通讯，2011，7（3）：63-70.
[5] S. Heinz， T. Schlechte， R. Stephan， M. Winkler. Solving steel mill slab design problems [J]. Constraints ， 2012， 17（1）： 39-50
[6] 李春梅，马良.求解多维–0-1背包问题的人工鱼群算法[J].数学的实践与认识，2010，40（17）： 195-199.
[7] 李跃松，樊金生，张巧迪.用改进的人工鱼群算法求解TSP问题[J].石家庄铁道大学学报（自然科学版），2011，24（2）：103-110.