基于改進NSGA-II算法的多目標生產智能調度

齊 琦，毋 濤

(西安工程大學 計算機科學學院，陜西 西安 710048)

1 概 述

隨著制造業的快速發展，生產過程中生產時間和成本的沖突變得更加明顯。長期以來，生產過程中的平衡問題很大程度上依賴于生產技術人員的個人經驗[1]，致使生產方案很不理想。通過綜合考慮時間、生產成本等多個因數的合理調度策略可以有效提高生產的執行效率。

隨著智能算法的發展，許多學者將智能算法應用到機械制造、電子工業領域，以便得到更加有效的解決方案。最開始出現，有基于遺傳算法、變鄰域搜索[2]、混合人工蜂群[3]、多種群遺傳算法[4]、改帝國競爭算法[5]求解最大完工時間的柔性車間調度問題，這種僅以最大完工時間為目標的研究存在實用性較差的問題。后來，文獻[6-7]提出最大完工時間、提前/拖期懲罰函數、生產總成本的多目標優化問題。這些多目標問題研究更加符合實際生產需求，但現有的多目標優化調度研究多是為不同的優化目標函數設定不同的權重值，把多目標優化問題轉化為一個單目標優化函數來求解[8-9]。這種方法存在的缺點是各權重值難以確定、優化目標之間的非線性相關性導致求解很難得到全局最優[10]，且對于多目標優化問題幾乎不存在單個全局最優解，而使用多目標函數直接求解得到最優解集的方案將會克服以上問題，并且文獻[11-13]研究表明NSGA-II算法在求解多目標優化問題上有著良好的求解能力。

通過對NSGA-II算法的研究，在種群初始化、擁擠度計算、交叉算子選擇環節進行優化改進，提高求解能力及解的質量。并將改進的算法用于西裝上衣縫制的工序編排中進行測試，為實際生產提供了多種有效解決方案，驗證了算法的有效性。

1.1 問題描述

在服裝縫制生產環節，一件衣服可分成n個不同的部件，每個部件又包含多道工序，每道工序可以在m臺機器中的一臺或多臺上完成，且各工序有先后順序，前一道工序做完后一道工序才可以開始，各工序在每臺機器上的加工時間已知，各衣服部件在進行組合前互相不影響。以所有部件完成的加工時間和加工成本為優化目標，在不考慮人為因素的前提下，確定所有工序的加工順序以及使用的機器，得到有效的生產方案。

1.2 數學建模

(1)最小化最大完成時間。

最大完成時間是指所有部件同時進行加工，最后一個部件完成時所花費的時間，時間越短表明方案越好。最小化完成時間的目標函數如式(1)所示。

f(1)=minCmax=min{maxCj|j∈n}

(1)

其中，Cmax表示所有部件加工完成的最大時間；n表示所有的部件總個數；Cj表示部件j的完成時間。

(2)最小化最大生產成本。

機器在加工和待機兩種狀態都會產生能耗，但其單位能耗值不相同。該文將兩種狀態下的能耗作為生產成本進行考慮。用runtimei和waittimei分別表示機器i的加工時間和待機時間，PRi表示機器i加工狀態的單位能耗；PWi表示機器i待機狀態時的單位能耗；m表示機器總個數；得到機器i總的使用時間和生產成本Wi，分別如式(2)、式(3)所示，最小化生產成本的目標函數如式(4)所示：

jj=runtimei+waittimei

(2)

Wi=runtimei*PRi+waittimei*PWi

(3)

(4)

2 算法設計

2.1 編 碼

針對柔性車間調度多目標優化的復雜性，該文采用MSOS染色體編碼方案，個體基因的編碼由兩部分組成：機器選擇部分(前半部分)、工序排序部分(后半部分)。工序排序部分基因位的值為工件號；工件號第幾次出現即表示該工件的第幾道工序，機器選擇部分的基因位根據工序的排列產生，基因位的編碼表示該工序選擇的加工機器在可選擇機器集中的序號。編碼規則如圖1所示。

圖1 染色體編碼示例圖

2.2 解 碼

對工序排序部分和機器選擇部分分別進行解碼。

工序排序部分解碼方式：創建一個矩陣S[1,n]，存放每個工件的出現次數，其中n表示工件個數，如工件2第3次在編碼中出現，就將矩陣的S[2]值變成3；創建一個矩陣H[1,m]，用于存放工序解碼后的信息，其中m表示工序總個數。開始解碼：取編碼的工序部分基因，從第一位開始遍歷：得到基因位基因編碼i，給S[i]的i號工件出現次數加1，用工件號乘以100再加上工件已出現的次數，得到對應的解碼結果記錄到H中。

機器選擇部分解碼方式：遍歷機器編碼基因，依次將H中工序解碼結果除以100取余數，便得到工序編號，將編碼結果減去解出的工序編號，除以100得到工件編號，用工件編號、工序編號以及機器編碼位基因值，在對應的加工時間矩陣中找到該工序的加工時間。將該工序的開始時間和上一道工序的完成時間進行比較，如果前一道工序完成時間小于本工序開始時間就取本工序的開始時間，否則取前道工序的結束時間作為本工序的開始時間，將開始時間加上該工序的加工時間得到該工序的結束時間，將開始時間和結束時間存入到一個矩陣G[2,l]中，其中l表示工序總個數。

經過上述的兩步解碼過程，便得到對應編碼所表示的工序加工順序矩陣H以及工序加工時間矩陣G，完成解碼過程。

2.3 種群初始化

NSGA-II算法中，采用隨機選擇的方式產生初始種群，第一次迭代時相當于一次隨機搜索，由于隨機搜索時種群越大找到最優解的概率就越大，但考慮到算法的復雜度，種群數量也不能無限加大[14]。文中設計在不影響算法復雜度的前提下，在種群初始化階段將初始種群數量設置為種群數量的1.5倍，經過適應度計算和擁擠度排序處理得到種群規模的個體進行后續的迭代，來提高初始種群豐富度，減少隨機性，加大NSGA_II的求得最優的概率。

2.4 選擇操作

根據基因編碼得到所有工序的開始時間和完成時間以及每個機器的加工時間，使用1.2節的最大完成時間和最大生產成本目標函數計算適應度函數值。由于機器待機時間等于使用時間減去加工時間，通過加工功率和待機功率乘以對應的加工時間和待機時間可以求得生產成本。在對子代、父代合并后的種群進行快速非支配排序后，改變NSGA-II算法中固定擁擠度計算方式，采用動態計算擁擠度值并按照精英保留策略選擇個體組成新父種群。

由于NSGA-II算法的求解特點，在迭代后期會出現Pareto層次較少，采用分層序號以及擁擠度作為比較條件的方式，將變成以個體擁擠度作為主要的影響因素的選擇方式[15]。例如，以求解標準測試函數ZDT1為例，某一次迭代后得到的Pareto面上各粒子的分布如圖2所示；如果按照固定擁擠度排序，當個體聚集出現時，可能會造成該區域全部個體被淘汰的情況[16]，使得Pareto解集多樣性降低，解集的分布性較差，篩選后的個體分布如圖3所示。實際上，當某一個體被淘汰后，相鄰個體的擁擠度將會發生變化，不考慮這種擁擠度變化的排序方式不能夠很好地表現解集的分布情況。采用文中的動態擁擠度排序方式選擇個體的結果如圖4所示。

圖2 Pareto最優個體集篩選前分布

圖3 采用固定擁擠度排序方式保留

圖4 采用動態擁擠度排序方式保留

文中采用的動態計算個體擁擠度的方式執行流程如圖5所示。首先根據個體的擁擠度，刪除其中擁擠度系數最小的粒子i，如果沒有達到種群數量，則根據刪除個體i的位置判斷需要重新計算擁擠度的個體，并重新計算該個體的最新擁擠度，更新完成后比較所有個體的擁擠度，刪除整個解集中擁擠度系數最小的個體，直到得到種群數量規模。

圖5 動態擁擠度計算流程

2.5 交叉操作

NSGA-II算法采用的是模擬二進制交叉SBX(simulated binary crossover)對實數編碼，優點是實現簡單，但是搜索的范圍相對較小，容易陷入局部最優解。而NDX(normal distribution crossover)算子比SBX算子的搜索空間要大[13]。NSAG-II算法在迭代初期是主要處于探索階段,此時個體適應度偏低、種群多樣性較高,應促進交叉產生新的基因;在算法后期搜索范圍逐漸變小,應保護優良基因不被破壞。

文中提出一種混合交叉算子，通過迭代次數的變化來改變交叉算子使用比例，在迭代初期為了保證種群的多樣性，使用較多的NDX算子進行交叉以擴大搜索范圍。在迭代后期，由于種群的解集已經趨于一個穩定的區域，可以通過加大SBX算子的使用比例，提高局部搜索性能，保存優秀基因，加快收斂。通過引入基于迭代次數的混合交叉算子,可以保證種群搜索空間的多樣性與解集的分布均勻性。交叉方式的選擇如式(5)所示。

(5)

其中，Pn表示NDX交叉算子的使用概率；Pb表示SBX算子的使用概率；MAXGen表示最大迭代次數；N表示當前迭代次數。

SBX算子的計算公式如式(6)所示。

(6)

其中，p1、p2表示父代個體，c1、c2表示子代個體，i表示代數；βSBX是由式(7)產生的隨機變量，式中令μ為在區間(0,1)上產生的均勻隨機數，γ是自己定義的一個非負數；而NDX算子的βNDX生成函數公式見式(8)。

(7)

(8)

綜合式(5)～式(8)得到混合算子的計算公式，如公式(9)所示：

(9)

2.6 變異操作

變異操作可以起到擴大隨機性的作用，增加算法的搜索能力，在迭代后期可以通過適當增加變異概率的方式來產生多樣性，所以在迭代過程中使用隨迭代次數遞增的線性自適應變異概率可以使變異概率隨迭代次數的增加而增大，適當增加迭代后期的多樣性。設置初始變異概率值為P0,最大變化概率為ρ，最大迭代次數為MAXGen；當前迭代次數為N，變異概率計算公式見式(10)

(10)

2.7 算法流程

算法實現步驟如下：

步驟1：確定種群規模、最大迭代次數；

步驟2：初始化種群，設置參數生成種群數量1.5倍的個體組成的初始種群，對個體求解適應度，進行非支配排序，如果非支配等級相同則選擇擁擠度系數大的，選出種群數量的優秀個體進行后續迭代；

步驟3：將新產生的父代和子代合并成中間種群；

步驟4：選擇父代。使用快速非支配排序對種群進行分層，結合動態計算擁擠距離及精英保留方式選擇優秀的個體進入下一代種群；

步驟 5：生成子代。采用BSX算子和NDX算子的混合交叉算子進行交叉，采用多項式變異產生新的子代；

步驟6：判斷算法是否滿足終止條件。滿足則結束算法，否則返回步驟3。

算法流程如圖6所示。

圖6 改進NSGA-II算法流程

2.8 算法驗證

文中將改進的NSGA-II算法與NSGA-II算法進行對比，采用文獻[11]中的機器加工時間以及加工機器和加工成本信息，以最小加工時間和最小生產成本作為優化目標進行實驗。實驗結果如圖7所示，其中星號表示NSGA-II求解的Pareto前沿，圓點表示改進NSGA-II算法的Pareto前沿。可以看出，改進的NSGA-II算法求得的解質量及分布性都優于原算法，說明改進算法在求解多樣性方面性能較好，具有更好的求解能力。

圖7 改進NSGA-II算法與NSGA-II優化

3 仿真實例

文中以某西裝企業上衣生產縫制環節生產環節為例，對西裝各部件的加工工序排列進行研究，驗證本算法在縫制環節的有效性。按照工序流程及相鄰工序及使用機器的情況分析，對工序進行重新整合，得到西裝上衣縫制環節大致工序，如表1所示。

表1 西裝上衣生產加工工序

續表1

通過對表1分析整理，將該環節生產問題進行數學建模，按照生產部件劃分為：衣領、后背、袖子、掛面、前片5個部件，每個部件劃分10道工序，機器數量為20，并對每個機器進行編碼，機器名稱及編號情況如下(括號中的數表示機器編號,多臺機器使用反斜杠分隔)：訂扣機(1)、定線機(2)、平縫機(3/4)、開袋機(5)、拷邊機(6/17)、撬邊機(7)、切邊機(8)、切邊平縫機(9)、曲邊縫機(10/18)、燙臺(12/13)、雙針平縫機(14/20)、套結機(15)、整燙機(16/19)、裝飾線機(11)。各機器在使用和待機期間的成本消耗情況如表2所示。每個工序生產可用加工機器信息如表3所示，其中第一行第二列的[3,4]表示工件1的第2道工序可使用的機器編號為3和4。各工序在對應機器上的加工時間的信息如表4所示，其中第一行第二列的[13,13]表示工件1的第2道工序使用機器3生產花費的時間為13 s，使用機器4花費的時間為13 s。

表2 各機器單位時間成本

表3 各工序可用機器

表4 各工序加工時間

在筆記本配置為Intel(R) Core(TM) i7-4510U CPU @2.00 GHz上使用MATLAB R2016b進行上述實例仿真實驗。算法參數配置如下：初始種群設置為50，迭代次數為200。實驗得到如圖8所示的Pareto前端，以及Pareto前端第一個解的甘特圖(如圖9所示)和各工序加工時間表(表5所示)。從Pareto前端可以看出，綜合最小完成時間和最小生產成本兩個優化目標得到一個由6個非劣解組成的解集，并且各個解均勻分布，在兩個目標函數相互影響下，都存在時間短或者成本低的優勢，不能區分出哪個解比其他解所得到的效果好。在實際生產過程中，決策者可以根據實際需求選擇合適的方案，根據方案得到的生產甘特圖以及各工序的加工時間表來指導生產。

圖8 Pareto前端解集

通過實驗結果生產的甘特圖以及加工時間表可以直觀地了解各工序的實際開始加工時間和結束時間。在圖9所示的甘特圖中，橫坐標表示時間(單位是秒)，縱坐標表示加工機器，甘特圖中的三位數字編碼的含義是：前面(除去后面兩位)是部位編號，后兩位是該部位所對應的工序編號。如編碼210，表示工件2的第10道工序。表5中用來記錄各工序加工的開始時間和完成時間，其中第1行的第2列[82,95]表示工件1的第2道工序開始加工時間為82 s，結束時間為95 s。

圖9 工序加工甘特圖

表5 各工序加工時間

4 結束語

文中針對智能生產調度的多目標優化問題，通過將多目標轉換成單目標的方式，將多目標問題進行直接求解，減少了前期對各目標函數所占權重的人為制定，充分利用NSGA-II算法的全局收索能力對算法進行改進，通過動態擁擠度以及自適應混合交叉算子保證解的多樣性，有效提高解的質量。以西裝上衣縫制生產環節作為實例，通過改進的NSGA-II算法進行實驗研究，最終得到了有效的工序編排方案。