改進灰狼優化算法求解模糊車間調度問題

摘 要：模糊車間調度問題是復雜調度的經典體現，針對此問題設計優秀的調度方案能提高生產效率。目前對于模糊車間調度問題的研究主要集中在單目標上，因此提出一種改進的灰狼優化算法（improved grey wolf optimization，IGWO）求解以最小化模糊完成時間和最小化模糊機器總負載的雙目標模糊柔性作業車間調度問題。該算法首先采用雙層編碼將IGWO離散化，設計一種基于HV貢獻度的策略提高種群多樣性;然后使用強化學習方法確定全局和局部的搜索參數，改進兩種交叉算子協助個體在不同更新模式下的進化;接著使用兩級變鄰域和四種替換策略提高局部搜索能力;最后在多個測例上進行多組實驗分析驗證改進策略的有效性。在多數測例上，IGWO的性能要優于對比算法，具有良好的收斂性和分布性。

關鍵詞：灰狼優化算法； 模糊調度； 強化學習； 變鄰域； 多目標

中圖分類號：TP301.6

文獻標志碼：A

文章編號：1001-3695（2023）07-021-2060-08

doi：10.19734/j.issn.1001-3695.2022.11.0515

Improved grey wolf optimization algorithm for fuzzy Job-Shop scheduling problem

Cheng Jinhai， Xu Hua^?， Yang Jinfeng

（School of Artificial Intelligence amp; Computer Science， Jiangnan University， Wuxi Jiangsu 214122， China）

Abstract：Fuzzy Job-Shop scheduling problem is a classic embodiment of complex scheduling， and an excellent scheduling scheme designed for this problem can improve production efficiency. At present， the research on fuzzy Job-Shop scheduling problem mainly focused on single objective， this paper proposed an improved grey wolf optimization （IGWO） algorithm to solve the bi-objective fuzzy flexible Job-Shop scheduling problem to minimize the fuzzy completion time and the total load of fuzzy machines. This algorithm proposed a two-layer coding method to make IGWO discretization， designed a strategy based on HV contribution degree to improve population diversity. Then it used reinforcement learning method to determine global and local search parameters， improved two crossover operators to help individuals evolve in different update modes， and used two-level variable neighborhood and four replacement strategies to improve local search capability. Finally， this paper carried out several groups of experiments on several examples to verify the effectiveness of the improved strategy. In most test cases， the performance of IGWO algorithm is better than the comparison algorithm， with good convergence and distribution.

Key words：grey wolf optimization; fuzzy scheduling; reinforcement learning; variable neighborhood; multi-objective

0 引言

智能調度決策在生產和制造體系中對于資源的分配有著關鍵作用。車間調度問題（Job-Shop scheduling problem，JSP）是諸多生產調度問題的抽象體現，多目標問題作為一類組合優化問題一直是該領域研究的熱點問題。模糊柔性車間調度問題（fuzzy flexible Job-Shop scheduling problem，FFJSP）是對JSP的一種擴展，是非確定性多項式難（non-deterministic polynomial hard，NP-hard）問題，相較于傳統JSP更加復雜，能更好地體現實際加工過程中出現的機器故障等特殊情況，具有一定研究意義。

國內外學者對FJSP的研究取得了許多成果，唐紅濤等人^［1］針對模糊分布式車間調度問題，利用非線性函數和新穎的權重更新機制有效地解決了FFJSP；李瑞等人^［2］針對雙目標FFJSP提出了一種改進的基于分解的進化算法，設計變鄰域結構增強局部搜索能力，提高算法在求解大型FFJSP測例上的性能；姜天華等人^［3］針對綠色JSP研究現狀提出一種改進灰狼算法，重點解決低碳調度問題中的能耗和時間成本問題；鄭小操等人^［4］提出了一種改進的基于鄰域搜索的人工蜂群算法，使用貪婪式解碼的方式最大化利用機器的空閑時間，對于求解單目標FFJSP取得了一定成效；Zhang等人^［5］研究了基于機器故障的動態FJSP，提出了以卷積神經網絡為基礎的兩階段帝國主義競爭算法，對解決復雜的車間問題研究具有參考意義；Yan等人^［6］建立了一種在有限運輸條件下的FJSP，利用三層編碼的多信息特點和解碼校正的方式，消除傳統傳輸約束的沖突，提出一種調度結果和車間數字孿生系統之間的實體JSON傳輸方法，最終將研究結果應用在車間系統上；Gong等人^［7］研究了考慮工人靈活性的綠色JSP，針對該問題提出了一種改進非支配排序算法，并設計了新的選擇方式和局部搜索方式，在多個測例上驗證了算法的有效性。在解決多目標柔性作業車間調度（multi-objective flexible Job-Shop scheduling problem，MOFJSP）的研究中，Zhu等人^［8］開發一種新穎的基于多微群領導層級的優化器，采用基于作業順序和操作排序的雙層編碼和基于啟發式機器分配的主動解碼方式，提出靈活的FJSP的多目標優化方案；宋存利^［9］設計了一種貪婪變異算子解決混合流水車間調試問題，使改進算法獲得全局和局部搜索能力上的平衡，通過大量實驗驗證了算法的有效性。

灰狼優化算法（grey wolf optimization，GWO） ^［10］是根據狼群狩獵捕食行為和內部等級制度而提出的一種新型群智能優化算法，該算法以收斂速度快、求解精度高的特點解決了大量連續優化問題，在組合優化問題上有一定的應用。Gu等人^［11］使用GWO解決了以能耗成本和完工成本之和最小為目標的低碳作業模糊車間調度問題，針對FFJSP的特點，混合遺傳算法的交叉操作使得GWO能直接在離散域內工作，實驗表明該混合算法具有較好的性能。時維國等人^［12］針對混合流水車間調度問題，使用GWO結合平面鏡成像學習策略解決該算法易陷入局部最優的問題。Zhu等人^［13］針對具有分層作業優先級約束的MOFJSP，使用GWO框架解決該問題，為實現鄰域個體的有效溝通設計一種新的編碼方式和作業優先修復機制，建立一種進化機制評價個體的優劣，通過實驗驗證了該編碼和進化機制的有效性。現有文獻表明GWO在MOFJSP上得到了一定應用，但是也存在經典算法易陷入局部最優等問題。由于FJSP屬于離散問題，灰狼個體在連續問題上的更新策略需要耗費大量時間在連續域與離散域進行轉換，且沒有具體意義。在多目標層面，由于灰狼個體存在相互支配的關系，沒有明確的等級制度，影響了決策層個體的選取。為了克服上述問題，本文提出一種改進灰狼優化算法求解FFJSP，使用交叉算子、變異策略等方式引導個體進化，為獲得擴大狼群搜索空間，提供四種個體替換策略增加激發種群活力;設計了一系列優化策略維持狼群全局和局部搜索的平衡，最終通過大量實例驗證了IGWO在求解FFJSP上的有效性。

1 雙目標模糊柔性作業車間調度問題

1.1 模糊柔性作業車間調度問題

1.7 多目標性能評價指標

評價多目標解集優劣程度的評價指標分為多樣性指標、收斂性指標、綜合性指標。其中解間距度量、熵度量^［15］等屬于多樣性指標，世代距離等屬于收斂性指標，超體積、世代反轉距離等屬于綜合性指標。部分評價指標公式如下：

a）解間距。

其中：|G|表示前沿解的個數;d_i表示第i個解到解集中其余解的最小距離;d是d_i的均值，解間距越小，種群的均勻性和多樣性越好。

b）熵。設種群有K個劃分，則個體在劃分i中概率如下：

其中：num是種群數量;U_i是在劃分i的灰狼數量。種群熵計算如式（6）所示，熵值H越大，種群個體的多樣性越好。

2 灰狼優化算法

GWO是一種新穎的基于群智能的元啟發式算法，主要通過模擬狼群的捕食行為和模仿狼群的社會等級制度提出。狼群的等級主要分為α、β、δ、ω四級。在算法迭代過程中，將狼群個體按照其適應度值大小進行排序，最優秀的個體為α狼，其次為β狼，接著是δ狼，剩余都是ω狼。GWO認為α、β、δ具有較好的狩獵獵物的能力，能夠引領狼群個體包圍和攻擊獵物，最終對獵物進行捕食。GWO具體原理參考文獻［10］。

包圍獵物過程如式（8）～（11）所示，其中D是灰狼與獵物的距離，i是迭代次數，X_p是獵物的位置向量，r₁、r₂是長度為V的隨機數向量，A、C是系數向量。a值由2線性遞減至0，X是灰狼個體當前的位置向量。

狩獵過程如式（12）～（18）所示，表示決策層個體帶領灰狼向獵物移動。X（i+1）表示下一代灰狼的位置向量。

3 改進灰狼算法

3.1 編碼和解碼

基于FFJSP特點，使用雙層編碼表示狼群個體，圖2是表2實例的一個灰狼個體的編碼向量。機器向量中的數字表示邏輯位置，如機器向量中的第二個數字“2”表示為J₃的第1個工序選擇機器庫中的第二個機器;工序向量中的數字表示工件號，出現頻次對應該工件工序號，工序向量中的第一個數字“2”，表示J₂的第一個工序被加工，即O₂₁是第二個被加工的工序。

解碼是將個體向量信息轉換成一個合理的調度方案，使用貪婪插入法^［17］生成的具體調度方案能夠有效利用機器內部的空余時間，減少完成時間。

3.2 Pareto排序理論和外部檔案

多目標問題中個體優劣程度取決于多個目標值，使用快速非支配解排序^［18］方法可以篩選優劣個體。假設Y、Z為種群中兩個個體，當滿足式（19）時，則認為Y支配Z；若沒有個體支配Y，則稱Y是最優個體，所有最優個體的集合稱為Pareto解集。

外部檔案用于存放迭代過程中的最優個體，將每代狼群的Pareto解集加入外部檔案，設置一個值為0的能量標記，并根據Pareto理論更新外部檔案。

3.3 種群初始化策略

優秀的初始化種群策略對種群搜索具有重要作用。對于機器序列，使用改進的全局機器負載最小優先策略^［16］和隨機選擇策略;對于工序序列，使用剩余工序最大優先策略和剩余工作量最大優先策略。

a）改進的全局機器負載最小優先策略，根據模糊數運算法則，為工序選擇使全局負載最小的加工機器。

b）隨機策略，為工序隨機選擇一個機器。

c）剩余工序最大優先策略，選擇當前剩余工序數量最多的工件進行加工。

d）剩余工作量最大優先策略，選擇當前剩余工作量最大的工件進行加工。

基于種群多樣性能算法獲取收斂速度和求解精度上的平衡的前提，本文提出一種基于HV貢獻度的初始化策略，圖3是雙目標優化示意圖，以R=（1，1）為數據歸一化后的參考點，陰影部分為個體c的貢獻度，其貢獻度計算方式為

其中：b、d為c的相鄰個體。個體的貢獻度大小決定了該個體在解集中的HV貢獻水平，個體貢獻度越大，越有利于全局HV值的變大。若兩個個體的目標值十分接近，則其中一個個體貢獻度水平比較低，使用新個體替換其中一個解有利于分散個體，產生多樣性的群體。

結合四種初始化策略產生GN個個體的過程如下：a）使用改進的全局機器負載最小優先策略生成1.6×GN個機器向量，使用隨機選擇策略對重復個體進行替換；b）根據機器向量，使用剩余工序最大優先策略和剩余工作量最大優先策略各生成0.8×GN個個體工序向量，與對應的機器向量組成個體向量；c）循環計算個體貢獻度，刪除個體貢獻度最小的個體，直到狼群數量為GN。

3.4 交叉算子和變異策略

GWO使用連續域上的更新方式并不適用于FFJSP。根據3.1節中的雙層編碼方式，本文提出一種改進的基于工件順序的交叉方式（improved precedence order-based crossover，IPOX）用于工序向量交叉，改進的多點交叉方式（improved multiple point crossover，IMPX）用于機器向量交叉，兩種交叉方式使用可變參數調整交叉幅度。其中IPOX使用整數ip調整移動位次，IMPX使用小數im調整交叉概率，ip∈［－3，3］，im∈［0.3，0.6］。

a）IPOX交叉規則。選擇P₁和P₂作為父代交叉個體，確定工件集合Job₁和Job₂，將P₁中屬于Job₁的工序復制到子代向量C₁對應位置中，再將P₂中屬于Job₂的工序按照順序填入C₁的空位置中，產生隨機數ip，將C₁進行整體的移動（ipgt;0時右移），產生ip－C₁作為一個后代;ip－C₂同理產生。

圖4顯示了IPOX產生其中一個子代的過程。

b）IMPX交叉規則。選擇M₁和M₂作為父代交叉個體，產生隨機數im和長度為V的0-1隨機向量，若該向量對應位置的值大于im，將M₁中機器編號賦值給R₁，否則將M₂中機器編號賦值給M₁，通過此規則產生im－R₁；im－R₂同理產生。圖5顯示了IMPX產生一個子代的過程。

變異策略有利于狼群個體挖掘自身潛力，強化IGWO局部搜索的能力，因此在狼群進化的過程中引入以下變異策略：a）機器變異策略，隨機選擇兩個位置，從機器庫中隨機選擇一個小于當前加工時間的機器；b）工序變異策略，隨機選擇兩個位置，將位置間的工序編碼翻轉。

3.5 變鄰域搜索

變鄰域搜索（variable neighborhood search，VNS）是新型群智能優化算法求解問題的一種有效的局部搜索方式。在灰狼搜索過程中，狼群個體根據決策層個體的信息更新自身位置信息，容易陷入局部最優，決策個體的優劣在很大程度上影響了狼群的進化上限。在MOFFJSP中需要根據目標設計鄰域結構，鄰域結構的設計應遵循簡單原則，滿足隨機變異和定向搜索的要求，避免個體大量使用復雜的鄰域結構造成大量開銷。因此本文設計將兩級變鄰域策略應用到灰狼算法中，設計概率選擇方式選擇優秀的鄰域結構，以提高計算性能。六種變鄰域結構描述如下：

N1：尋找到最后一個加工完成的工序，從機器庫中隨機選擇一個機器替換。

N2：尋找到負載最大的機器，隨機選擇在該機器上加工的一道工序，從機器庫中隨機選擇一個機器替換。

N3：選擇工序量最小的工件J_A和工序量最大的工件J_B，將J_B的最后一道工序和J_A的第一道工序交換。

N4：隨機選擇一道工序，從機器庫中選擇加工時間最小的機器替換原機器。

N5：隨機選擇不同工件的兩個基因位交換。

N6：隨機選擇兩個基因位，將其中一個基因位上的工序插入到另一個工序之前或者之后。

其中，N4、N5、N6是開銷較小的鄰域結構，進行隨機變異;N1、N2、N3是精確鄰域結構，實現定向搜索。鄰域Nj最近i代的帶權累加值表達如式（21）所示，該概率表示鄰域的搜索效能，為提高進化效率，應選擇性能較好的鄰域結構。

其中：t_i∈{0，1}，表示最近第i代該鄰域結構的應用情況。由于GWO容易陷入局部最優，應避免對個體在單次迭代中的過度開發，鄰域結構的有效性對于不同車間實例是不一致的，在迭代過程中選取適應該車間的鄰域結構能增加算法的魯棒性。綜合考慮算法性能和時間開銷成本，本文選用輪盤賭策略選取精確鄰域結構。式（22）表示選取概率。

3.6 個體替換策略

由于灰狼種群在進化的過程中會依賴決策層狼的位置對獵物進行狩獵，而對于處于遠端的獵物無法得到充分搜索，當狼群個體在搜索limit次后仍未進化時，則使用替換策略替換該個體。本文提出四種替換策略用于替換個體，激發種群活力。

a）使用變異策略接受較差的個體替換原個體。

b）根據工序向量對機器向量進行重構，對每道工序考慮選擇使當前全局加工時間最小的機器。

c）根據機器向量對工序向量進行重構，計算每個工件的加工時間，依次選取剩余加工時間最多的工件進行加工。

d）MOFFJSP在種群進化過程中會考慮多個目標值，多個目標值之間的相互約束會減緩對于單目標最優值的搜索。基于該分解思想，在后期使用一種考慮單目標最優值的更新方案，在狼群迭代i次后，使用3.1節中初始化工序向量的方式創建兩個數量為NS的單目標搜索狼群，分別用于搜索最小模糊完工時間和最小機器總負載。狼群使用基于工序的單層編碼方式，工件加工順序與3.1節中雙層編碼中的工序向量含義一致。解碼過程中使用貪婪插入式方法，采用最小完成時間原則^［19］計算工序的機器庫中每個機器的最小完成時間，選擇使得全局加工完成時間最小的機器。對于單目標種群在單次迭代過程中更新方式分為四步，將該更新模塊命名為SE。（a）對個體使用3.5節中N1、N2、N3一種鄰域策略進行更新；（b）對個體使用3.4節中IPOX交叉算子更新；（c）將種群最優解轉換成雙層編碼形式保存在BS集合中，并初始化一個個體替換該最優解；（d）使用3.1節中初始化策略替換連續10次未進化的個體。

此替換方案能夠有效隔離大種群中優秀個體對于單目標最優值的影響，有利于提高Pareto解集的質量。單層編碼具有快速更新的特點，最小完成時間原則適合數量較小的種群更新，因此能夠較好地適用于搜索單目標任務。

3.7 強化學習

強化學習（reinforcement learning，RL）^［20］是一種以結果為導向的控制算法，目的是選擇回報效益高的策略長期獲得更多的獎勵，能夠應用于參數的自適應調整。RL至少由環境（environment）、智能體（agent）、狀態（state）、行動（action）和收益（reward）五要素組成。圖6展示了智能體與環境的交互圖。

GWO協同系數A會由2線性降到0，表明該算法前期會減緩灰狼狩獵速度，進行全局搜索，而在后期更注重局部搜索。由于本文存在個體更新情況，強調動態更新，可以使用RL的方式控制種群全局和局部搜索的比例，學習迭代如式（23）所示。

其中：χ是學習因子;γ是折扣率，滿足0≤γ≤1;R_t是即時獲得的獎勵;Q是行為價值函數，表示預期收益。

將灰狼種群體視為agent，最終目標為學習比例u，選用解間距度量和熵度量兩個指標綜合評價種群多樣性，通過多樣性變化來控制u，優化進化方向。RL屬于一種基于貪心選擇策略的學習方法，使用ε來控制RL的決策強度，即產生一隨機數ra∈［0，1］，若εlt;ra，則隨機選擇動作，否則選擇累計獎勵最大的一個動作。RL的狀態集合、動作集合、獎勵方式如下所示。

a）狀態集合。式（24）中的ΔSp和式（25）中的ΔH表示相鄰兩代間的解間距和熵值變化，i表示迭代次數，根據變化情況分為四個狀態θ。

b）獎勵方式。當種群間的間距變小、熵值變大時，種群多樣性越好，獎勵值越大，以此設置獎勵值。具體狀態對應的獎勵值如表3所示。

c）動作集合。RL的動作是確定比例參數u的變化情況，u的變化情況分為增大、變小和不變。式（26）表示u的相鄰兩代變化情況，τ表示u的變化幅度，i表示迭代次數，設置初始參數u₀=0.5。

3.8 個體進化模式

GWO中，灰狼個體通過與決策層狼群交換信息逼近獵物位置，決策層使用三只灰狼提供位置信息。對于MOFFJSP而言，最終的Pareto解集中往往存在多個個體，意味著決策層僅有三只優秀灰狼的信息是不夠的，因此需要根據狼群的數量增加決策層數量，決策層灰狼個體的最大數量NP為

其中：|PF|為Pareto解集中個體數量；GN為灰狼數量。

IGWO迭代過程中，需要選定決策層個體進行信息交換，本文提出一種基于灰狼能量的選擇方式確定個體，帶領種群進行更新。在將灰狼加入外部檔案時，灰狼的能量是0，能量的大小表示其對種群的影響程度，能量越大，影響程度越大。在一輪迭代過程中，選取能量較低的灰狼進行信息交換，并將灰狼的能量值加1，避免單個個體被重復選用，導致種群陷入局部最優。個體更新模式分為全局模式和局部模式。全局模式是隨機選取種群中兩個個體，使用POX^［21］和MPX^［22］算子進行交叉，使用變異策略進行更新;局部模式是選用Pareto解集中能量較低的灰狼和個體進行信息交換，選用3.4節中的IPOX和IMPX進行交叉，使用變異策略進行更新。

3.9 算法流程

IGWO求解MOFFJSP流程如圖7所示，具體步驟如下：

a）輸入機器和工件信息，設置算法參數：灰狼數量GN，單目標灰狼個數NS，最大迭代次數IM，限定搜索次數limit，交叉概率CR，變異概率MU，加入單目標種群時的迭代次數IC，當前迭代次數It，初始比例u等算法所需參數，轉步驟b）。

b）使用初始化策略產生灰狼種群和單目標搜索種群，使用式（4）～（6）計算種群解間距和熵值，使用非支配排序更新外部檔案，轉步驟c）。

c）產生隨機數Rand₁，判斷是否小于交叉概率CR，若是，則根據u值選擇對應的交叉算子更新個體，轉步驟d）。

d）產生隨機數Rand₂，判斷是否小于變異概率MU，若是，則對灰狼個體使用變異策略更新，轉步驟e）。

e）對每個個體使用兩級變鄰域策略更新個體，轉步驟f）。

f）判斷灰狼個體連續更新未變好次數是否大于limit，若是，轉步驟g），否則轉步驟h）。

g）判斷當前迭代次數It是否大于IC，若是，則使用3.6節中前三種策略替換個體，否則使用SE模塊更新BS，使用BS中的個體替換原個體。

h）使用快速非支配排序求Pareto解集，并更新外部檔案。

i）判斷當前迭代次數It是否大于IM，若是，則算法結束，否則轉步驟j）。

j）使用式（4）～（6）計算種群解間距和熵值，使用式（23）～（25）計算獎勵值更新Q值表，使用式（26）更新u，轉步驟c）。

k）算法結束。

3.10 IGWO復雜性分析

本文中IGWO主要包括五個部分：初始化階段、灰狼算法迭代階段、變鄰域搜索階段、強化學習階段、個體進化階段。算法復雜度主要來源于解碼，NS代表單目標灰狼數量，NP代表初始灰狼數量，IM代表迭代次數，IC代表SE模塊生效時的迭代次數。用解碼次數表達復雜性如下：

初始化階段為Ο（NS+GN）;迭代階段為Ο（2×IM×GN+2×NS×（IM-IC））；變鄰域搜索階段為Ο（4×GN×IM）；強化學習階段為Ο（IM）；替換階段為Ο（GN×IM+NS×（IM-IC））。綜上，IGWO的復雜度上界為Ο（4×GN×IM）。

4 實驗分析與比較

IGWO在MATLAB2021a上編寫，運行環境為：系統內存8 GB，CPU@i5-6300。算法參數設置如下：IM=200，limit=20，NS=40，χ=0.4，ε=0.8，γ=0.6，u₀=0.5。

4.1 數據集

實驗所用數據集分為三組。D^{［23，24］}、R^［25］數據集都是標準FFJSP數據集，其中D是完全柔性的FFJSP，即每個工序都可以在任一機器上加工，R是部分柔性FFJSP，即每個工序只能在部分機器上加工;FMK數據集是由MK^［26］數據集改造而來，是部分柔性的FFJSP，具體來源于文獻［27］。

數據集共有23個測例，最小工序數為40，最大工序數為355，工件數量和機器數量等數據集具體信息如表4所示。

4.2 正交實驗

將交叉概率CR、變異概率MU、灰狼數量GN、加入單目標種群時的迭代次數IC四個參數作為影響IGWO性能的主要參數。為充分挖掘性能，選擇更佳的參數組合，本文采用文獻［28］中的參數整定實驗方法設計正交實驗，表5顯示了各參數的水平設置。

根據各個參數水平，使用正交表L16.4.4設計16種組合方式。對每種參數組合的IGWO在D1上運行10次，得到Pareto解集，計算每組實驗得到的平均HV值ARHV，ARHV值越大，代表該參數組合的算法性能越好。參數組合的正交表設置如表6所示。

總結16組實驗結果，得到每組實驗的ARHV。參數的影響力等級如表7所示，極差越小，參數的影響力水平越低，影響力等級越大。圖8顯示了各個參數下的HV平均值。

交叉算子影響著種群間信息交換的頻率，頻率太大不利于種群探索新的信息，頻率太小則表示種群間信息交流不充分，進化緩慢。變異策略影響著局部搜索的能力，變異程度的提高會增強算法局部搜索的能力，當種群變異達到一定程度時，為避免額外開銷，應選擇使種群搜索達到飽和值的最優參數。

種群數量的增大會擴大種群在解空間搜索的廣度，進而增加算法全局搜索的性能，而使用SE模塊生成單目標最優個體若過早地加入灰狼種群，則會導致灰狼種群在評價多目標方面失衡，而過晚使用該策略則會導致加入的單目標優秀個體與種群的信息交換不充分，無法將單目標的最優值信息有效地帶給全局種群，導致全局搜索不充分。根據表7的16組實驗可知，IC因子組別的HV因子極差最大，影響力等級最高，MU因子組別的HV值較為接近，影響力等級最低。因此在后續實驗中設置實驗參數：CR=0.8，MU=0.8，GN=120，IC=140。

4.3 分離實驗

為驗證IGWO中各部分的有效性，本文分別使用標準GWO、僅使用隨機初始化策略的IGWO-INI、不使用變鄰域策略的IGWO-VNS、不使用替換策略的IGWO-SE和IGWO五種算法進行仿真實驗，使用D、R數據集獨立運行十次，得到各個算法的平均HV值和最優HV值。表8顯示了各個分離算法的Pareto解集HV值，其中ARHV表示平均HV值，BEHV表示最優HV值。IGWO-VNS、IGWO-INI、IGWO-SE得到的HV值遠大于GWO所得HV值，表明IGWO解決離散問題的能力要優于GWO。在多數測例上，使用改進策略所求的ARHV和BEHV都要優于不使用對應策略的ARHV和BRHV，表明了改進策略的有效性。

為驗證使用概率選擇鄰域結構的有效性，在保證開銷相同的情況下選取同一參考點，將IGWO，僅使用一種鄰域結構的IGWO（N1）、IGWO（N2）、IGWO（N3），不使用鄰域結構IGWO（N0）進行對比，每個算法在D1上獨立實驗10次。圖9顯示了使用不同鄰域策略的HV平均值，使用概率選擇鄰域策略性能優于使用單一的鄰域策略，且每種鄰域策略都能使算法獲取更優秀的解集。

為驗證四種替換策略的必要性，本文使用IGWO，僅使用單一替換策略的IGWO（1）、IGWO（2）、IGWO（3）、IGWO（4）和不使用替換策略的IGWO（0）進行對比，每個算法在D1上獨立實驗10次取均值。圖10顯示了每種替換策略的HV平均值，可以發現使用組合替換策略的算法性能要優于使用單一替換策略，并且每種替換策略都具有一定的有效性。

為驗證RL選取的參數對于維持狼群全局和局部搜索的有效性，將IGWO、IGWO（sin）、IGWO（linear）、IGWO（random）、IGWO（tan）進行對比，每個算法在D1上獨立實驗10次取平均值。各算法的比例參數如式（28）～（31）所示。其中i表示迭代次數，IM表示最大迭代次數。圖11顯示了不同經典函數下產生的全局和局部搜索比例，可以發現使用RL產生的自適應參數值更注重種群內部的多樣性信息，因此使IGWO獲得了較好的全局和局部搜索平衡，而經典的三角函數等產生的比例參數隨機性較大，效果不顯著。

4.4 對比實驗

為進一步驗證IGWO的有效性，本文選取三類算法進行對

比，選用HV值表示各個算法所求Pareto解集的收斂性和均勻性。

a）基于分解思想的優化算法：RMOEA/D^［27］和IMOEA/D^［2］。

b）新型種群優化算法：IABC^［4］和MODGWO^［29］。

c）基于解支配關系的多目標優化算法：NSGA-Ⅱ^［19］。

由于IABC是求解單目標FFJSP，所以加入快速非支配排序評價在雙目標MOFFJSP上的個體優劣，將MODGWO的多目標求解改為求解本文的雙目標。對比算法迭代次數、種群數量等參數與IGWO保持一致，其余參數使用原文獻中最佳參數。每個算法在各個測例上單獨運行10次，取最優HV值BEHV和平均HV值ARHV。表9給出了七個算法在所有測例上的Pareto解集的HV值，可以觀察到在多數測例上，IGWO所求Pareto解集的ARHV和BEHV都要優于其余對比算法，IGWO算法性能優于對比算法。IGWO的ARHV和BEHV數值接近，說明IGWO的求解MOFFJSP穩定性較好。在個別測例上，IGWO的BEHV并不是多個算法中的最優值，考慮工序數量增多、機器數量增多等原因，導致組合優化的解空間更大，現有的參數水平使得算法陷入局部最優。對于測例FMK3，該測例的最小加工時間較容易獲得，因此使用種群初始化策略會產生相似度很高的個體，致使種群整體的多樣性不足，ARHV和BEHV較小。

對各算法在R2上獨立做10次實驗取平均值，將最小加工時間去模糊后每隔10代保留一次。圖12顯示了IGWO在前期更偏向全局搜索，而在后期注重局部搜索，與其余算法相比具有更強的跳出局部搜索的能力。圖13顯示了各個算法在迭代過程中最小加工時間的收斂情況，可以發現在使用單目標種群搜索到的最優值替換個體時，IGWO的最小加工時間有明顯下降的過程，而優秀的單目標最優值有利于擴大搜索空間，加強種群個體在目標值上的搜索深度，提高解集的HV值，說明加入單目標種群最優值的改進策略能提高種群全局搜索能力。

5 結束語

為了降低FFJSP在生產制造過程中產生的時間成本和機器損耗，研究最小化完成時間和最小化機器總負載的優化方案，本文提出IGWO求解MOFFJSP。IGWO繼承了GWO的搜索機制，結合提出的初始化策略和新穎的交叉算子，在迭代過程中增加了更新模式和替換策略，并使用兩級變鄰域策略加快局部搜索，使用RL解決了GWO中的參數選擇問題。實驗結果證明了IGWO解決MOFFJSP時具有良好的收斂性能。下一步的工作是考慮多目標的數量和多目標之間的關系，并且結合更加具體的JSP背景研究復雜FFJSP。

參考文獻：

[1]唐紅濤，李悅，王磊.模糊分布式柔性作業車間調度問題的求解算法［J］.華中科技大學學報：自然科學版，2022，50（6）：81-88.（Tang Hongtao， Li Yue， Wang Lei. An improved GWO algorithm for fuzzy distributed flexible Job-Shop scheduling problem［J］.Journal of Huazhong University of Science and Technology： Natural Science Edition，2022，50（6）：81-88.）

［2]李瑞，龔文引.改進的基于分解的多目標進化算法求解雙目標模糊柔性作業車間調度問題［J］.控制理論與應用，2022，39（1）：31-40.（Li Rui， Gong Wenyin. An improved multi-objective evolutionary algorithm based on decomposition for bi-objective fuzzy flexible Job-Shop scheduling problem［J］.Control Theory amp; Applications，2022，39（1）：31-40.）

［3]姜天華.基于灰狼優化算法的低碳車間調度問題［J］.計算機集成制造系統，2018，24（10）：2428-2435.（Jiang Tianhua. Low-carbon workshop scheduling problem based on grey wolf optimization［J］.Computer Integrated Manufacturing Systems，2018，24（10）：2428-2435.）

［4]鄭小操，龔文引.改進人工蜂群算法求解模糊柔性作業車間調度問題［J］.控制理論與應用，2020，37（6）：1284-1292.（Zheng Xiaocao， Gong Wenyin. An improved artificial bee colony algorithm for fuzzy flexible Job-Shop scheduling problem［J］.Control Theory amp; Applications，2020，37（6）：1284-1292.）

［5]Zhang Guohui， Lu Xixi， Liu Xing， et al. An effective two-stage algorithm based on convolutional neural network for the bi-objective flexible Job-Shop scheduling problem with machine breakdown［J］.Expert Systems with Applications，2022，203（10）：117460.

［6]Yan Jun， Liu Zhifeng， Zhang Caixia， et al. Research on flexible Job-Shop scheduling under finite transportation conditions for digital twin workshop［J］.Robotics and Computer-Integrated Manufacturing，2021，72（12）：102198.

［7]Gong Guiliang， Deng Qianwang， Gong Xuran， et al. A non-dominated ensemble fitness ranking algorithm for multi-objective flexible Job-Shop scheduling problem considering worker flexibility and green factors［J］.Knowledge-Based Systems，2021，231（11）：107430.

［8]Zhu Zhenwei， Zhou Xionghui. A multi-objective multi-micro-swarm leadership hierarchy-based optimizer for uncertain flexible Job-Shop scheduling problem with job precedence constraints［J］.Expert Systems with Applications，2021，182（11）：115214.

［9]宋存利.求解多目標混合流水車間調度的改進NSGA-Ⅱ［J］.計算機集成制造系統，2022，28（6）：1777-1789.（Song Cunli. Improved NSGA-Ⅱ algorithm for hybrid flow shop scheduling problem with multi-objective［J］.Computer Integrated Manufacturing Systems，2022，28（6）：1777-1789.）

［10]Mirjalili S， Mirjalili S M， Lewis A. Grey wolf optimizer［J］.Advances in Engineering Software，2014，69（3）：46-61.

［11]Gu Jiuchun， Jiang Tianhua， Zhu Huiqi， et al. Low-carbon Job-Shop scheduling problem with discrete genetic-grey wolf optimization algorithm［J］.Journal of Advanced Manufacturing Systems，2020，19（1）：1-14.

［12]時維國，宋存利.求解混合流水車間調度問題的改進灰狼算法［J］.計算機集成制造系統，2021，27（11）：3196-3208.（Shi Weiguo， Song Cunli. Improved grey wolf optimization for solving hybrid flow shop scheduling problem［J］.Computer Integrated Manufacturing Systems，2021，27（11）：3196-3208.）

［13]Zhu Zhenwei， Zhou Xionghui. An efficient evolutionary grey wolf optimizer for multi-objective flexible Job-Shop scheduling problem with hierarchical job precedence constraints［J］.Computers amp; Industrial Engineering，2020，140（2）：106280.

［14]Sakawa M， Mori T. An efficient genetic algorithm for Job-Shop schedu-ling problems with fuzzy processing time and fuzzy duedate［J］.Computersamp;Industrial Engineering，1999，36（2）：325-341.

［15]李密青，鄭金華，肖桂霞，等.一種多目標進化算法的分布度評價方法［J］.模式識別與人工智能，2008，21（5）：695-703.（Li Miqing， Zheng Jinhua， Xiao Guixia， et al. A diversity metric for multi-objective evolutionary algorithm［J］.Pattern Recognition and Artificial Intelligence，2008，21（5）：695-703.）

［16]While L， Hingston P， Barone L， et al. A faster algorithm for calculating hypervolume［J］.IEEE Trans on Evolutionary Computation，2006，10（1）：29-38.

［17]Zhang Guohui， Gao Liang， Shi Yang. An effective genetic algorithm for the flexible Job-Shop scheduling problem［J］.Expert Systems with Applications，2011，38（4）：3563-3573.

［18]Gao Kaizhou， Yang Fajun， Zhou Mengchu， et al. Flexible Job-Shop rescheduling for new job insertion by using discrete Jaya algorithm［J］.IEEE Trans on Cybernetics，2018，49（5）：1944-1955.

［19]Deb K， Agrawal S， Pratap A， et al. A fast and elitist multi objective genetic algorithm：NSGA-Ⅱ［J］.IEEE Trans on Evolutionary Computation，2002，6（2）：182-197.

［20]Watkins C， Dayan P. Technical note： Q-learning［J］.Machine Learning，1992，8（3）：279-292.

［21]Gao Kaizhou， Suganthan P N， Chua T J， et al. A two-stage artificial bee colony algorithm scheduling flexible Job-Shop scheduling problem with new job insertion［J］.Expert Systems with Applications，2015，42（21）：7₆₅2-7663.

［22]De Jong K A， Spears W M. A formal analysis of the role of multi-point crossover in genetic algorithms［J］.Annals of Mathematics and Artificial Intelligence，1992，5（1）：1-26.

［23]Lei Deming. A genetic algorithm for flexible Job-Shop scheduling with fuzzy processing time［J］.International Journal of Production Research，2010，48（10）：2995-3013.

［24]Lei Deming. Co-evolutionary genetic algorithm for fuzzy flexible Job-Shop scheduling［J］.Applied Soft Computing，2012，12（8）：2237-2245.

［25]Gao Kaizhou， Suganthan P N， Pan Q， et al. An effective discrete harmony search algorithm for flexible Job-Shop scheduling problem with fuzzy processing time［J］.International Journal of Production Research，2015，53（19）：5896-5911.

［26]Brandimarte P. Routing and scheduling in a flexible Job-Shop by Tabu search［J］.Annals of Operations Research，1993，4（3）：157-183.

［27]Li Rui， Gong Wenyin， Lu Chao. A reinforcement learning based RMOEA/D for bi-objective fuzzy flexible Job-Shop scheduling［J］.Expert Systems with Applications，2022，203（10）：117380.

［28]Wang Shengyao， Wang Ling， Liu Min， et al. An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem［J］.International Journal of Production Economics，2013，145（1）：387-396.

［29]顧九春，姜天華，朱惠琦.多目標離散灰狼優化算法求解作業車間節能調度問題［J］.計算機集成制造系統，2021，27（8）：2295-2306.（Gu Jiuchun， Jiang Tianhua， Zhu Huiqi. Energy-saving Job-Shop scheduling problem with multi-objective discrete grey wolf optimization algorithm［J］.Computing Integrated Manufacturing Systems，2021，27（8）：2295-2306.）