改進灰狼優(yōu)化算法在煉鋼過程中的應用

李曉宇，葉春明

（上海理工大學管理學院，上海 200093）

0 引言

灰狼優(yōu)化算法是一種新型的群智能算法，2014 年由Mirjalili 等［1］根據(jù)狼群中的等級制度和捕食過程提出，被廣泛運用于車間調(diào)度、參數(shù)優(yōu)化及預測問題中。然而，該算法在后期容易陷入局部最優(yōu)，無法獲得最優(yōu)解，這一點引起了學者們的關注。劉煉等［2］根據(jù)灰狼優(yōu)化算法后期易陷入局部最優(yōu)的特點，提出反向?qū)W習和基于精英狼群的醉漢漫步策略對其進行改進；黎素涵等［3］分析了非線性收斂因子和重選精英狼群對算法的影響；李陽等［4］提出一種分段可調(diào)節(jié)收斂因子，并對精英狼群采用萊維飛行和隨機游走策略防止算法陷入局部最優(yōu)；王夢璐等［5］提出動態(tài)反向搜索機制和sigmoid 函數(shù)改變線性收斂因子；徐松金等［6］基于遺傳算子提出交叉變異機制，以提高算法的局部收斂能力和收斂速度。

鋼鐵制造業(yè)是工業(yè)生產(chǎn)的基礎，有效的煉鋼連鑄調(diào)度方法可確保鐵水準時運送到需要的工序，有利于減少能源消耗，降低碳排放。國內(nèi)外學者針對煉鋼連鑄這一問題，從不同角度進行了研究。Kumar 等［7］采用組合拍賣方法，將煉鋼調(diào)度問題轉(zhuǎn)化成一個整數(shù)線性規(guī)劃進行求解；韓大勇等［8］為提高煉鋼連鑄生產(chǎn)效率，以加權最大化完工時間和作業(yè)等待懲罰總和最小化為目標對煉鋼連鑄問題進行研究求解；Zarandi 等［9］通過建立混合整數(shù)線性規(guī)劃模型，提出一種基于粒子群優(yōu)化和模糊線性規(guī)劃方法的組合求解煉鋼連鑄（SCC）調(diào)度問題；唐秋華等［10］將文化基因算法與啟發(fā)式規(guī)則相結合，應用于煉鋼連鑄生產(chǎn)調(diào)度中；吳玲等［11］設計了兩階段方法求解多并行機多緩沖區(qū)的煉鋼連鑄生產(chǎn)調(diào)度，最后獲得澆次的最優(yōu)排序。

針對灰狼優(yōu)化算法應用于混合流水車間調(diào)度這一問題，近年來很多學者開展了研究。如時維國等［12］提出改進參數(shù)C 的灰狼優(yōu)化算法，求解加工階段配置不均衡的混合流水車間；成舒凡等［13］利用改進的灰狼優(yōu)化算法求解三階段應急手術調(diào)度模型；張興輝等［14］提出反向改進灰狼算法策略，以優(yōu)化預測模型的超參數(shù)。

綜上所述，目前國內(nèi)外文獻中，將灰狼優(yōu)化算法應用于車間調(diào)度的研究有很多，但將其應用于煉鋼連鑄生產(chǎn)調(diào)度的很少。雖然有學者考慮鋼鐵加工過程中緩沖區(qū)的約束，但很少有學者考慮多并行機的加工問題。因此，本文首先對傳統(tǒng)的灰狼優(yōu)化算法進行改進，通過測試函數(shù)驗證其性能的提升；然后建立多并行機帶有緩沖區(qū)約束的煉鋼連鑄生產(chǎn)模型，并考慮鋼鐵加工過程中等待時間受限和最后一階段無間斷加工等特殊約束，將改進后的IGWO 運用于該模型中，驗證算法和模型的有效性。

1 傳統(tǒng)灰狼優(yōu)化算法

根據(jù)灰狼在大自然中的捕 食行為，Mirjalili 等［1］在2014 年提出了灰狼優(yōu)化算法。其將每一匹狼看作問題的一個解，求解精度最高的解被稱為α 狼，求解精度次高的解為β 狼，求解精度第三高的解為δ 狼，剩下的狼群則為ω狼。ω 狼在α、β 和δ 狼的帶領下不斷更新自己與獵物的距離，無限接近獵物并進行抓捕、追蹤、圍獵和攻擊?；依堑燃壗Y構如圖1所示。

Fig.1 Grey wolf hierarchy圖1 灰狼等級結構

具體公式如下：

1.1 圍獵獵物

式（1）表示個體與獵物之間的距離，式（2）為灰狼位置更新公式，式（3）、式（4）分別為系數(shù)向量更新公式。

其中，t為目前迭代的次數(shù)分別表示獵物和灰狼的位置向量為系數(shù)向量為收斂因子。隨著迭代次數(shù)從2線性減小到0是［0，1］范圍內(nèi)的隨機數(shù)。

1.2 追捕獵物

根據(jù)種群中適應度前3 的狼群位置不斷更新ω狼的位置，如式（5）-（7）所示。公式（8）表示ω狼的最終位置。

2 改進的灰狼優(yōu)化算法

灰狼優(yōu)化算法具有原理簡單、參數(shù)較少、全局搜索能力強及易于實現(xiàn)等優(yōu)點，因此被廣泛應用于綜合能源優(yōu)化調(diào)度［15］、考慮云制造服務協(xié)同的多用戶任務調(diào)度［16］、微電網(wǎng)經(jīng)濟優(yōu)化調(diào)度［17］等領域。因為原始的GWO 算法存在后期全局搜索能力較差、易陷入局部最優(yōu)以及收斂速度慢等問題，所以本文提出一種改進的灰狼優(yōu)化算法（IGWO）。

2.1 基于反向?qū)W習的初始化種群

反向?qū)W習策略是一種智能計算方法，被廣泛應用于各種智能算法中，包括GA、DE、BBO 和ACO 算法等。該策略通過生成反向解以增加種群的多樣性，提高算法的尋優(yōu)性能。因為種群初始化對于算法的搜索效率影響較大，所以本文采用反向搜索策略初始化灰狼種群。具體操作步驟如下：

（1）在搜索空間中隨機初始化N 個灰狼xi，j(i=1，2，...，D；j=1，2，...，N)作為初始種群P，其中N 為灰狼個數(shù)，D 為空間維數(shù)。

（2）生成反向種群。需要每個灰狼個體生成其個體的反向點，假設在D 維空間上存在p=(x1，x2，...，xD)為其中的一個點，xi∈[li，ui]，i=1，2，...，D，則其反向點p'=，其中。隨機產(chǎn)生的每個灰狼個體xi及其反向個體構成反向種群OP。

（3）將種群P 與OP 合并，在2N 個種群中選取適應度排序前N 的灰狼個體作為其初始種群。

2.2 非線性收斂因子

在灰狼優(yōu)化算法中，當|A|＞1 時狼群進行全局搜索，|A|＜1 時搜索范圍減小，即進行局部搜索。由式（3）可知，A 隨著a 的變化而改變。傳統(tǒng)的GWO 收斂因子a 隨著迭代次數(shù)增加而線性遞減，但算法的搜索是非線性變化的，收斂因子線性遞減會導致算法后期的全局搜索能力較差，容易陷入局部最優(yōu)［18］。因此，本文針對GWO 算法的迭代搜索過程，根據(jù)文獻［3］，使用了非線性收斂因子。

非線性收斂因子隨迭代次數(shù)的變化情況如圖2 所示（彩圖掃OSID 碼可見，下同）。

Fig.2 Convergent factor variation圖2 收斂因子變化

其中，直線表示傳統(tǒng)GWO 算法收斂因子的變化情況，曲線表示改進后IGWO 算法收斂因子的變化情況。改進后的收斂因子呈拋物線形狀，前期變化速率慢，可很好地適應種群的全局搜索能力；后期變化速率較快，有助于算法在局部搜索過程中快速、精確地找到最優(yōu)解。本文采用的非線性收斂策略有利于平衡算法的全局搜索與局部搜索能力。

2.3 萊維飛行策略

在傳統(tǒng)的GWO 算法中，隨著a 的遞減，|A|＜1 時狼群開始進行局部搜索，而后期群體中所有的個體均向α狼靠近，易出現(xiàn)早熟收斂的情況，陷入局部最優(yōu)。本文針對這一問題，采用基于精英頭狼的萊維（Lévy）飛行策略擴大后期精英狼α的搜素范圍。

萊維飛行策略是服從萊維分布隨機游走的一種方法，是一種短距離行走和較長距離行走相間的方式，因此萊維飛行具有良好的全局搜索能力。其位置更新公式如下：

式中，Xα(t)表示迭代到第t代時α狼個體的位置；⊕表示點對點乘法；b表示α狼個體的隨機數(shù)，b=表示服從萊維分布的搜索路徑，，其中λ的取值區(qū)間一般為1 ＜λ＜3，Xαbest表示歷史最優(yōu)解，μ和v服從的正態(tài)分布為

采用萊維飛行策略可更新灰狼位置，再采用貪心機制將原始解與新解的適應度進行對比，保留適應度更好的解。

2.4 算法步驟

改進后的IGWO 算法步驟如下：①進行參數(shù)設置：確定種群個數(shù)N、最大迭代次數(shù)Max_iter；②隨機生成N 個種群，采用反向?qū)W習策略生成N 個反向解，合并排序并抽取適應度為前N 的灰狼種群，再將前3 個最優(yōu)個體的位置依次保存為Xα、Xβ、Xδ；③根據(jù)式（1）-式（9）更新灰狼位置，并更新a、A、C 的值；④根據(jù)式（10）更新α 狼；⑤重復步驟③與步驟④，直至達到最大迭代次數(shù)，輸出α 狼的適應度值，算法終止。

3 仿真實驗

3.1 實驗及數(shù)值分析

為測試改進后灰狼優(yōu)化算法（IGWO）的性能，本文選取國際上常用的8 個標準測試集函數(shù)來驗證算法，表1 列出了這些函數(shù)。其中，F(xiàn)1～F5 為單峰值函數(shù)，用于測試算法的局部搜索能力；F6～F8 為多峰值函數(shù)，用于測試算法的全局搜索能力。將改進的IGWO 算法與傳統(tǒng)GWO 算法進行對比，為保證無偏性，設置迭代次數(shù)為500。為排除偶然性，所有實驗均獨立運行30 次，記錄實驗的平均值和標準差來衡量算法性能。

本文實驗環(huán)境為：系統(tǒng)Windows 10，512G 固態(tài)硬盤，INTEL 酷睿I5-1135G7 的CPU 和內(nèi)存為16GB 的PC 機，所有算法均使用MATLAB2016版本完成。

3.2 實驗結果與分析

表2 是30 維下兩種算法測試結果的平均值和標準差，可以看出，不管是平均值還是標準差，改進后的IGWO 算法較改進前求解精度更高。尤其是從函數(shù)F1、F2、F3、F4、F7 可以看出，IGWO 算法的求解精度明顯高于GWO 算法，而對于函數(shù)F5、F6、F8，IGWO 算法的求解精度略高于GWO 算法。仿真實驗結果顯示了改進IGWO 算法的有效性。

為更直觀地表現(xiàn)改進前后GWO 算法的收斂情況，圖3給出了30 維下針對F1-F4 4 個函數(shù)兩種算法的收斂曲線。從圖中可以看出，算法在迭代前期的收斂情況基本一致，而在迭代后期，改進后IGWO 算法的收斂速度、收斂精度相較于GWO 算法都表現(xiàn)更好。

Table 1 Eight standard test functions表1 8個標準測試函數(shù)

Table 2 Comparison of GWO and IGWO on 8 standard test functions表2 GWO算法與IGWO算法針對8個標準測試函數(shù)對比

4 多緩沖區(qū)多并行機的煉鋼連鑄生產(chǎn)調(diào)度問題

4.1 問題描述

煉鋼連鑄生產(chǎn)過程主要分為3 個階段：煉鋼（EAF）—精煉（AOD）—連鑄（CC）。由于實際煉鋼過程中等待時間受限，本文考慮了3 種不同類型的緩沖區(qū)，并利用兩階段的方法求解澆次序列。通過使用緩沖區(qū)壓縮規(guī)則以提高機器利用率、減少空轉(zhuǎn)時間，從而減少機器空轉(zhuǎn)的能耗時間。鋼鐵生產(chǎn)流程（加緩沖區(qū)）如圖4所示。

Fig.3 Convergence curves of the two algorithms for solving F1-F4 functions圖3 兩種算法求解F1-F4函數(shù)的收斂曲線

Fig.4 Steel production process（plus buffer）圖4 鋼鐵生產(chǎn)流程（加緩沖區(qū)）

本文以某鋼廠的工藝流程為例，利用IGWO 算法求解煉鋼連鑄生產(chǎn)調(diào)度問題。共選取10 個待加工澆次，每個澆次包含不同數(shù)量的爐次，在不同類型及不同數(shù)量緩沖區(qū)的約束下，按照同一個工藝路線（即EAF-AOD-LF1-LF2-CC）進行加工。考慮緩沖區(qū)的煉鋼連鑄已有學者研究過，但本文考慮的是多緩沖區(qū)多并行機的加工問題，該領域很少有學者研究。

本文將緩沖區(qū)看作加工時間為0 的生產(chǎn)階段，于是可將求解問題抽象為含有特殊約束的7 階段混合流水車間調(diào)度求解最大完工時間，屬于規(guī)模大、約束多、強耦合的NP-hard 問題［19］。

4.2 煉鋼連鑄數(shù)學模型

4.2.1 參數(shù)設置

具體參數(shù)設置如下：

L：爐次集合，L=｛1，2，3，...，l，...，|L|｝，其中|L|為爐次總數(shù)。

J：澆次集合，J=｛1，2，3，...，j，...，|J|｝，其中|J|為澆次總數(shù)。

S：生產(chǎn)階段集合，S=｛1，2，3，...，s，...，|S|｝，其中|S|為生產(chǎn)階段總數(shù)，本文的|S|=7。

K：爐次事件集合，K=｛1，2，3，...，k，...，|L|｝。

I：澆次事件集合，I=｛1，2，3，...，i，...，|J|｝。

NJ：澆次J包含的爐次總數(shù)。

LJ：澆次J包含的爐次集合。

MS：S 階段包含的機器數(shù)量，M_S=｛1，2，3，...，m，...，|M_S|｝，其中|M_S|為S階段包含的機器總數(shù)。

tk，s，m：爐次K 在S 階段m 臺機器上處理一爐的時間，其中，S∈［1，7］。

P：相鄰澆次間的準備時間（相鄰澆次J 在連鑄階段的預留準備時間），設置為60。

r：有限緩沖區(qū)允許爐次停留的最大時間，超過該時間將影響工件質(zhì)量。

決策變量如下：

xj，i：0-1 變量，當澆次j 分配到澆次事件點i 時等于1，否則為0。

yl，k：0-1 變量，當爐次l 分配到爐次事件點k 時等于1，否則為0。

qk，s，m：0-1 變量，當爐次事件點k 在階段S 分配到機器m 上時等于1，否則為0。

bk，s：連續(xù)變量，表示爐次事件點k_ 在階段S_ 的開始時間。

ck，s：連續(xù)變量，表示爐次事件k在階段S的結束時間。

H：足夠大的常數(shù)。

4.2.2 問題假設

本文考慮在滿足煉鋼連鑄工藝一般性約束中加入特殊性約束，以優(yōu)化最大完工時間，使得研究問題更接近實際生產(chǎn)情況。為構建合理的模型，實驗需要滿足以下假設條件：①每臺機器在工作過程中不會出現(xiàn)故障；②各機器在任一時刻最多只能加工一個爐次；③各階段的爐次連續(xù)加工；④同一階段并行機加工同一爐次的時間一致；⑤使用同一臺連鑄機的，必須考慮相鄰澆次間更換中間包的準備時間；⑥不考慮因溫度降低導致的重調(diào)度問題；⑦在不具備加工能力的階段（即爐次屬于緩沖區(qū)階段），各爐次最多只能分配到一個緩沖區(qū)上。

4.2.3 數(shù)學模型

目標函數(shù)如下：

一般性約束條件如下：

其中，式（11）為目標函數(shù)，表示最小化最大完工時間；式（12）表示澆次與加工次序間存在對應關系；式（13）確定了澆次中的爐次序列；式（14）表示同一澆次內(nèi)的爐次在連鑄階段，需在同一臺機器上不間斷地加工；式（15）表示任何時候一臺機器只能加工一個爐次；式（16）表示爐次在s個階段連續(xù)進行加工；式（17）表示使用同一臺連鑄機器的澆次，必須考慮相鄰澆次間更換中間包的準備時間；式（18）表示在緩沖區(qū)階段，緩沖區(qū)具有緩存能力；式（19）表示在前兩個緩沖區(qū)，緩存時間是無限的；式（20）定義了有限緩沖區(qū)開始到結束之間的關系，以及緩沖區(qū)存儲的時間上限；式（21）定義了在不具備加工能力的階段，各爐次最多只能被分配到一個緩沖區(qū)上；式（22）表示爐次間連續(xù)工作。

5 基于IGWO的煉鋼連鑄調(diào)度求解

目前灰狼優(yōu)化算法已在很多工業(yè)領域有了成功應用。本文將以煉鋼連鑄生產(chǎn)調(diào)度問題為例，采用IGWO 算法求解最大完工時間，結合啟發(fā)式規(guī)則求解澆次內(nèi)和澆次間的排產(chǎn)順序，從而獲得最小化最大完工時間。

5.1 澆次內(nèi)與澆次間啟發(fā)式規(guī)則

對于澆次內(nèi)的爐次，要求最后一階段在同一臺機器上不間斷地進行加工，故本文采用回溯倒排法，即最后一道工序成為第一道工序。獲得最大完工時間后進行正序，即將最大完工時間減去當前求得的工件開始和結束時間，獲得工件調(diào)度的具體時間。由于正序后的加工時間間隔大，生產(chǎn)過程不緊湊，于是利用緩沖區(qū)儲存工件并進行壓縮，以確保爐次（工件）的連續(xù)加工，減少設備空轉(zhuǎn)時間。

對于澆次間的排序，需要考慮最后一階段更換中間包的時間。若相鄰澆次最后一階段在同一臺機器上加工，則需要考慮更換中間包的時間；若相鄰澆次最后一階段不在同一臺機器上加工，只需將后一澆次信息追加到當前調(diào)度方案之后，把整塊信息往前推，直到第一臺設備出現(xiàn)沖突。并且為了滿足工序之間無等待的約束，澆次間利用緩沖區(qū)進行調(diào)整。

5.2 編碼

由于灰狼優(yōu)化算法適合解決連續(xù)解空間中的問題，而煉鋼連鑄生產(chǎn)調(diào)度是連續(xù)和離散相混合的復雜生產(chǎn)過程，為了讓IGWO 算法更好地解決此類HFSP 問題，本文以澆次為最小單位，采用澆次序列進行編碼，將離散的解空間連續(xù)化。通過把每一個澆次看作（0，2）之間的實數(shù)，該澆次對應序列是向量中數(shù)值的大小，例如5 個澆次對應的向量編碼為（1.23，0.84，1.35，0.33，0.98），則澆次的加工順序為（2，4，1，5，3）。數(shù)值代表澆次序號，編碼長度|J|表示待調(diào)度的澆次總數(shù)。

5.3 解碼

由于煉鋼連鑄過程的特殊約束，本文將采用逆序解碼策略。首先，結合澆次內(nèi)的啟發(fā)式規(guī)則對澆次內(nèi)的爐次進行排產(chǎn)，確定各澆次內(nèi)爐次在不同工序上的加工時間和結束時間；然后，在當前澆次未斷澆時仍然繼續(xù)爐次的排產(chǎn)，直至開始下一個澆次；接下來對澆次內(nèi)的爐次進行定時，并將整體置于現(xiàn)有的調(diào)度計劃之后，結合澆次間的啟發(fā)式規(guī)則進行解碼，最終可獲得最大完工時間（適應度值）。

5.4 嵌入變鄰域搜索策略

常見的變領域搜索結構有交換、插入和逆序。為了增強算法的局部搜索能力，對于IGWO 算法嵌入變鄰域搜索進行求解。本文根據(jù)求解問題的特點，采用互換的鄰域結構進行變鄰域搜索。

5.5 實驗仿真與分析

為驗證模型和算法的有效性，本文根據(jù)文獻［20］隨機選取10 個澆次進行實驗，并利用傳統(tǒng)的GWO 算法進行對比實驗。算例的相關設置為：生產(chǎn)階段|S|=7，各階段加工機器數(shù)量如表3所示。

Table 3 Number of processing machines at each stage表3 各階段加工機器數(shù)量

待調(diào)度澆次總數(shù)|J|=10，每個澆次包含的爐次數(shù)NJ∈[1，7]，各個澆次在第7 階段的準備時間P=60min，各爐次在各階段的加工時間如表4所示。

Table 4 Processing time of each stage表4 各階段加工時間

統(tǒng)一設置種群規(guī)模為50，迭代次數(shù)為500，采用本文改進的IGWO 算法和傳統(tǒng)GWO 算法求解最大完工時間。

5.6 實驗結果分析

通過隨機選取澆次進行實驗分析，驗證算法的有效性，本文選取10 個澆次數(shù)的煉鋼連鑄生產(chǎn)數(shù)據(jù)進行實驗。為防止因偶然性出現(xiàn)的偏差，分別對兩組實驗獨立運行20次，并求平均值。算法運行結果如表5 所示。本文實驗環(huán)境為：系統(tǒng)Windows 10，512G 固態(tài)硬盤，INTEL 酷睿I5-1135G7 的CPU，內(nèi)存為16GB 的PC 機，所有算法均使用MATLAB2016版本完成。

Table 5 Running result of the algorithm表5 算法運行結果

從表5 可以看出，改進后IGWO 算法的求解精度優(yōu)于傳統(tǒng)的GWO 算法，證明改進的灰狼優(yōu)化算法相較于傳統(tǒng)算法可跳出局部最優(yōu)，獲得更優(yōu)的值。

為了更好地顯示算法的收斂速度，本文選取第14 次的運行結果繪制兩種算法的收斂曲線，如圖5所示。

Fig.5 Algorithm optimization process圖5 算法尋優(yōu)過程

為更清晰地呈現(xiàn)出澆次間和澆次內(nèi)的排產(chǎn)情況，圖6選取澆次排產(chǎn)序列中相鄰3 個澆次的調(diào)度順序。圖7 表示3 個相鄰澆次中澆次2 的排產(chǎn)情況，可看出該調(diào)度方法明顯提升了設備利用率，生產(chǎn)過程變得更緊湊，澆次在EAF和AOD 階段的完成時間減少，減少了機器的空轉(zhuǎn)時間，從而減少了機器空轉(zhuǎn)產(chǎn)生的碳排放。

Fig.6 Production layout diagram of adjacent casting process圖6 相鄰澆次加工排產(chǎn)圖

Fig.7 Production scheduling of the 2th casting time圖7 澆次2排產(chǎn)情況

6 結語

本文研究了利用改進的灰狼優(yōu)化算法求解煉鋼連鑄生產(chǎn)調(diào)度問題，結合實際生產(chǎn)情況，在緩沖區(qū)的約束下建立煉鋼連鑄生產(chǎn)調(diào)度模型，并根據(jù)求解問題的特點對改進的灰狼算法引入變鄰域搜索策略，結合啟發(fā)式的解碼規(guī)則求解煉鋼連鑄過程中的最大完工時間，通過合理的排產(chǎn)順序可提高設備利用率。最后通過算例進行模擬實驗，將改進的灰狼優(yōu)化算法與傳統(tǒng)灰狼優(yōu)化算法尋優(yōu)過程所求結果進行對比，結果表明，改進的灰狼優(yōu)化算法在求解煉鋼連鑄調(diào)度上有較大優(yōu)勢。

本文建立的煉鋼連鑄生產(chǎn)調(diào)度模型可減少機器等待時間、提高設備利用率，但沒有用數(shù)據(jù)和實驗證明改變調(diào)度方案對于煉鋼連鑄過程中所排放二氧化碳的減少情況。接下來將結合機器空轉(zhuǎn)、工件等待散熱以及工件加工過程中的二氧化碳排放情況，研究采用何種方法可大幅減少碳排放量，并研究在碳限額政策下如何在保證低碳生產(chǎn)的同時降低經(jīng)濟成本的問題。