基于改進(jìn)NSGA-II算法的多目標(biāo)生產(chǎn)智能調(diào)度

齊 琦，毋 濤

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

1 概 述

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

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

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

1.1 問題描述

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

1.2 數(shù)學(xué)建模

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

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

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

(1)

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

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

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

jj=runtimei+waittimei

(2)

Wi=runtimei*PRi+waittimei*PWi

(3)

(4)

2 算法設(shè)計

2.1 編 碼

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

圖1 染色體編碼示例圖

2.2 解 碼

對工序排序部分和機(jī)器選擇部分分別進(jìn)行解碼。

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

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

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

2.3 種群初始化

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

2.4 選擇操作

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

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

圖2 Pareto最優(yōu)個體集篩選前分布

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

圖4 采用動態(tài)擁擠度排序方式保留

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

圖5 動態(tài)擁擠度計算流程

2.5 交叉操作

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

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

(5)

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

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

(6)

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

(7)

(8)

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

(9)

2.6 變異操作

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

(10)

2.7 算法流程

算法實(shí)現(xiàn)步驟如下：

步驟1：確定種群規(guī)模、最大迭代次數(shù)；

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

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

步驟4：選擇父代。使用快速非支配排序?qū)ΨN群進(jìn)行分層，結(jié)合動態(tài)計算擁擠距離及精英保留方式選擇優(yōu)秀的個體進(jìn)入下一代種群；

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

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

算法流程如圖6所示。

圖6 改進(jìn)NSGA-II算法流程

2.8 算法驗證

文中將改進(jìn)的NSGA-II算法與NSGA-II算法進(jìn)行對比，采用文獻(xiàn)[11]中的機(jī)器加工時間以及加工機(jī)器和加工成本信息，以最小加工時間和最小生產(chǎn)成本作為優(yōu)化目標(biāo)進(jìn)行實(shí)驗。實(shí)驗結(jié)果如圖7所示，其中星號表示NSGA-II求解的Pareto前沿，圓點(diǎn)表示改進(jìn)NSGA-II算法的Pareto前沿?？梢钥闯觯倪M(jìn)的NSGA-II算法求得的解質(zhì)量及分布性都優(yōu)于原算法，說明改進(jìn)算法在求解多樣性方面性能較好，具有更好的求解能力。

圖7 改進(jìn)NSGA-II算法與NSGA-II優(yōu)化

3 仿真實(shí)例

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

表1 西裝上衣生產(chǎn)加工工序

續(xù)表1

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

表2 各機(jī)器單位時間成本

表3 各工序可用機(jī)器

表4 各工序加工時間

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

圖8 Pareto前端解集

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

圖9 工序加工甘特圖

表5 各工序加工時間

4 結(jié)束語

文中針對智能生產(chǎn)調(diào)度的多目標(biāo)優(yōu)化問題，通過將多目標(biāo)轉(zhuǎn)換成單目標(biāo)的方式，將多目標(biāo)問題進(jìn)行直接求解，減少了前期對各目標(biāo)函數(shù)所占權(quán)重的人為制定，充分利用NSGA-II算法的全局收索能力對算法進(jìn)行改進(jìn)，通過動態(tài)擁擠度以及自適應(yīng)混合交叉算子保證解的多樣性，有效提高解的質(zhì)量。以西裝上衣縫制生產(chǎn)環(huán)節(jié)作為實(shí)例，通過改進(jìn)的NSGA-II算法進(jìn)行實(shí)驗研究，最終得到了有效的工序編排方案。