劉 瓊，熊書平，湛夢夢

(華中科技大學(xué) 數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗室,湖北 武漢 430074)

0 引言

現(xiàn)實(shí)生活中，存在許多多目標(biāo)優(yōu)化問題(Multi-objectives Optimization Problems，MOP)，當(dāng)優(yōu)化目標(biāo)個數(shù)增加到4個及以上時，即視為高維目標(biāo)優(yōu)化問題[1]。由于目標(biāo)函數(shù)之間經(jīng)常是沖突的，其最優(yōu)解并非單一解，而是一組非支配解[2]。一個目標(biāo)的優(yōu)化將可能導(dǎo)致其他目標(biāo)的惡化，只能采用折中的方式讓各個目標(biāo)盡可能達(dá)到最優(yōu)。而且，優(yōu)化過程導(dǎo)致計算復(fù)雜度和搜索空間急劇擴(kuò)增，高維目標(biāo)優(yōu)化問題已成為目前國內(nèi)外智能優(yōu)化領(lǐng)域最難解決的問題之一[3]，有效地解決高維目標(biāo)優(yōu)化問題具有廣泛的理論和實(shí)際意義。

在中國制造2025的背景下，企業(yè)間趨于協(xié)同合作，制造資源互相開放、共享。企業(yè)的產(chǎn)品加工需求可以通過各企業(yè)制造資源間的協(xié)同合作完成。由于協(xié)同合作涉及的加工任務(wù)多，設(shè)備規(guī)模大，加工路徑多樣，這些因素擴(kuò)大了可行解的搜索范圍，與傳統(tǒng)車間調(diào)度問題相比規(guī)模更大，更復(fù)雜；且隨著問題規(guī)模的增大，計算的復(fù)雜度將呈指數(shù)增長[4]。同時，資源共享需兼顧各個企業(yè)的需求，通常涉及多個優(yōu)化目標(biāo)，目標(biāo)間不是完全線性相關(guān)，呈現(xiàn)出高維目標(biāo)特性。因此，解決協(xié)同加工中調(diào)度優(yōu)化問題，需要在滿足各企業(yè)不同需求的基礎(chǔ)上，從整體進(jìn)行優(yōu)化，使企業(yè)能快速響應(yīng)市場需求，減少固定資產(chǎn)投入，提高資源利用率。

文獻(xiàn)[1]認(rèn)為，當(dāng)調(diào)度優(yōu)化問題的目標(biāo)個數(shù)增加到4個及以上時，即可視為高維目標(biāo)調(diào)度優(yōu)化問題，目標(biāo)個數(shù)2或3個的調(diào)度優(yōu)化問題為多目標(biāo)調(diào)度優(yōu)化問題。在實(shí)際生產(chǎn)調(diào)度中，企業(yè)可考慮的優(yōu)化目標(biāo)有很多，包括完工時間、成本、提前/拖期懲罰、設(shè)備利用率、設(shè)備負(fù)荷、碳排放等，企業(yè)可根據(jù)自身需要選擇合適的優(yōu)化目標(biāo)。目前多目標(biāo)調(diào)度優(yōu)化問題研究較多，一般通過非劣解排序(Pareto排序)來選擇個體和確定優(yōu)化方向，如張超勇等[5]提出一種改進(jìn)的非支配排序遺傳算法，設(shè)計新的編碼解碼機(jī)制，解決了以時間和成本為優(yōu)化目標(biāo)的多目標(biāo)柔性作業(yè)車間調(diào)度問題。Liu等[6]采用基于Pareto排序的混合果蠅算法來解決以減少最大完工時間和制造過程中碳排放為目標(biāo)的多目標(biāo)調(diào)度優(yōu)化問題。當(dāng)優(yōu)化的目標(biāo)數(shù)增加至4個或以上形成高維目標(biāo)時，算法的選擇壓力減弱，非支配解的個數(shù)將呈指數(shù)增長，基于Pareto排序的多目標(biāo)調(diào)度優(yōu)化算法優(yōu)化效果大大降低。針對該問題，現(xiàn)有研究大都通過給目標(biāo)賦予不同權(quán)重來減少目標(biāo)的維數(shù)，以增強(qiáng)算法的種群選擇能力。吳秀麗等[7]建立了以完工時間、成本、交貨期滿意度和設(shè)備利用率為目標(biāo)的高維目標(biāo)調(diào)度模型，采用基于集成權(quán)重系數(shù)和小生境技術(shù)的混合遺傳算法，通過隨機(jī)權(quán)重混合集成法將多目標(biāo)轉(zhuǎn)化為單目標(biāo)再優(yōu)化，但權(quán)重分配隨機(jī)，導(dǎo)致算法沿著隨機(jī)方向搜索，搜索效率不高。白俊杰等[8]建立了以完工時間、拖期懲罰、機(jī)床利用率和機(jī)床總負(fù)荷為目標(biāo)的高維目標(biāo)調(diào)度模型，并采用基于偏好信息的粒子群算法，定量表達(dá)決策者對各目標(biāo)的偏好，僅對感興趣的區(qū)域進(jìn)行搜索排序，有效引導(dǎo)搜索方向，提高了求解速度。但上述算法的本質(zhì)是通過采用權(quán)重法將高維目標(biāo)轉(zhuǎn)化為單目標(biāo)優(yōu)化來解決，即使有權(quán)系數(shù)的變化機(jī)制，也不能保證Pareto最優(yōu)性和解的質(zhì)量[9]。目前，解決高維目標(biāo)優(yōu)化問題方面的理論算法很多，其中包括通過采用降維法的算法來解決高維目標(biāo)優(yōu)化問題，如陳小紅等[10]提出基于稀疏特征選擇的目標(biāo)降維算法，將高維目標(biāo)空間投影至低維目標(biāo)空間實(shí)現(xiàn)降維，對比其他降維算法，求解高維目標(biāo)優(yōu)化測試問題能得到更好的結(jié)果，但隨著目標(biāo)數(shù)量增加，錯誤目標(biāo)子集數(shù)增多，準(zhǔn)確性無法保障。劉立佳等[11]提出了分組進(jìn)化算法，通過對目標(biāo)函數(shù)進(jìn)行分組來降維，求解各組目標(biāo)Pareto非支配解集，再對全部解集采用SPEA2求得整體最優(yōu)解，雖然通過求解標(biāo)準(zhǔn)測試函數(shù)與其他降維算法對比證明了其性能上的優(yōu)勢，但目標(biāo)函數(shù)分組具有較大的隨意性，分組不同將導(dǎo)致不同的優(yōu)化結(jié)果，無法保證解的質(zhì)量。目前而言，采用降維法的算法解決高維目標(biāo)優(yōu)化的研究效果并不理想。此外，還有通過寬松Pareto支配的算法來解決高維目標(biāo)優(yōu)化問題。Drechsler等[12]將一種用來確定個體間支配關(guān)系的優(yōu)勝關(guān)系與進(jìn)化算法相結(jié)合來解決電路設(shè)計中高維優(yōu)化問題，若解a在更多目標(biāo)上優(yōu)于解b，則a支配b，但該優(yōu)勝關(guān)系不具有傳遞性，當(dāng)存在a支配b，b支配c，c又支配a的循環(huán)情況時，無法對所有個體完全排序，易出現(xiàn)選擇壓力退化。郭思涵等[13]提出帶有正交E占優(yōu)策略的算法，采用正交試驗初始化種群，采用E占優(yōu)代替Pareto排序，通過求解標(biāo)準(zhǔn)測試問題來對比說明改進(jìn)后的算法比原算法具有更好的收斂性能，但算法的參數(shù)難以確定，易受主觀干擾，同時改動了個體的真實(shí)目標(biāo)值，易導(dǎo)致無法真正收斂到Pareto前沿。楊順生[14]提出基于主成分分析法(Principal Component Analysis, PCA)占優(yōu)機(jī)制的PCA-NSGAⅡ算法，通過對目標(biāo)矩陣進(jìn)行PCA分析得到各目標(biāo)的權(quán)重，再對各目標(biāo)值與權(quán)重的積進(jìn)行差值求解來選擇非支配解，代替?zhèn)鹘y(tǒng)Pareto占優(yōu)排序機(jī)制，從而增大了選擇壓力。求解標(biāo)準(zhǔn)測試函數(shù)驗證了算法的有效性。采用PCA占優(yōu)機(jī)制的算法考慮了所有目標(biāo)的特性，使原有目標(biāo)屬性被保留和體現(xiàn)，提高了解的分布性。但仍需進(jìn)一步完善收斂性能和解質(zhì)量。目前這些算法還未在生產(chǎn)調(diào)度領(lǐng)域中得到應(yīng)用，故將基于PCA占優(yōu)機(jī)制的算法引入到解決生產(chǎn)調(diào)度領(lǐng)域的高維目標(biāo)調(diào)度優(yōu)化問題中，并針對基于PCA的占優(yōu)機(jī)制的算法缺少精英引導(dǎo)策略、求解質(zhì)量和收斂效果還不夠理想的問題，提出一種改進(jìn)精英策略的PCA-NSGAⅡ算法來求解所建立的高維目標(biāo)調(diào)度優(yōu)化模型。在原有PCA-NSGAⅡ算法的基礎(chǔ)上，提出增加一個外部種群，對算法精英策略進(jìn)行改進(jìn)，將算法中優(yōu)化后的優(yōu)秀個體放入外部種群中，原種群和外部種群同時進(jìn)化，并通過優(yōu)先選擇外部種群中個體的方式，引導(dǎo)種群進(jìn)化方向，改善種群的質(zhì)量，提升種群整體進(jìn)化水平，以提高算法的求解質(zhì)量和收斂效果來有效地解決高維目標(biāo)調(diào)度優(yōu)化問題。

1 高維目標(biāo)調(diào)度優(yōu)化建模

各制造企業(yè)將自己的具有某種加工功能的加工機(jī)器，通過協(xié)調(diào)優(yōu)化，在滿足各企業(yè)不同需求的情況下，實(shí)現(xiàn)資源快速共享提高資源利用率。各制造企業(yè)擁有一臺或多臺加工機(jī)器，構(gòu)成一個制造系統(tǒng)，多臺機(jī)器可共同完成各工件的加工任務(wù)。

1.1 問題描述

1.2 條件假設(shè)

為便于研究，作如下假設(shè)：

(1)各工件的工藝路線已知，且所有加工任務(wù)僅涉及機(jī)加工車間，不涉及熱處理和毛坯工藝；

(2)各加工機(jī)器在首個工件抵達(dá)后啟動；

(3)加工機(jī)器在整個加工過程中只開關(guān)一次，所有加工機(jī)器的啟動、預(yù)熱和停止能耗引起的碳排放在優(yōu)化目標(biāo)中為一個常量，對優(yōu)化結(jié)果不產(chǎn)生影響，故在計算中忽略；

(4)忽略機(jī)器使用潤滑油和冷卻液產(chǎn)生的碳排放；

(5)制造工廠間使用小型貨車運(yùn)輸工件，搬運(yùn)工件產(chǎn)生的能耗只與運(yùn)輸距離有關(guān)；忽略工廠內(nèi)部機(jī)器間運(yùn)輸時間和運(yùn)輸產(chǎn)生的碳排放；

(6)加工任務(wù)開始后不允許中斷，且工件的每個加工任務(wù)只能在一臺機(jī)器上加工；

(7)不同工件的加工任務(wù)間沒有優(yōu)先級；

(8)在零時刻，所有的工件都可以開始加工；

(9)所有工件只能在前一道任務(wù)完成后才能進(jìn)入下一道任務(wù)的加工。

1.3 調(diào)度優(yōu)化模型

目前生產(chǎn)調(diào)度中考慮的優(yōu)化目標(biāo)有很多，如完工時間、成本、提前/拖期懲罰、設(shè)備利用率、設(shè)備負(fù)荷、碳排放等，依據(jù)企業(yè)的實(shí)際需求，以總成本、最大完工時間和總提前/拖期懲罰為主要考慮目標(biāo)。同時，近年來環(huán)境問題日益突出，制造過程產(chǎn)生的碳排放已越來越引起企業(yè)和公眾的關(guān)注，未來制造模式將向低排放、低污染、低能耗方向發(fā)展，故將制造過程碳排放作為一個優(yōu)化目標(biāo)。因此以總成本最小、最大完工時間最小、總拖期/提前懲罰最小以及制造過程中碳排放最小為目標(biāo)，建立高維目標(biāo)調(diào)度優(yōu)化模型。具體優(yōu)化模型如下，模型參數(shù)如表1所示。

(1)

minCtime=max{Cijk|i∈N;j∈J;k∈Mij};

(2)

min(0,Cipik-di)×Ei);

(3)

(4)

s.t.

Sijk≥Chlk+thikh,i∈N,j,l∈J;
k∈Mij∩Mhl;

(5)

Sijk≥Ci(j-1)k′+tt,ij，i∈N,j>2,j∈M,

k∈Mij,k′∈Mij-1;

(6)

Cijk≥Sijk+tijk，i∈N,j∈J,k∈Mij;

(7)

Ctime≥Cijk，i∈N,j∈J,k∈Mij;

(8)

(9)

表1 模型參數(shù)

其中：式(1)表示生產(chǎn)總成本Ccost，由加工成本和運(yùn)輸成本組成；式(2)表示最大完工時間Ctime，即從第一個工件的第一道工序在機(jī)器上開始加工到最后一個工件的最后一道工序在機(jī)器上加工完成之間的時間；式(3)表示總拖期/提前懲罰ET，即衡量工件實(shí)際加工完成時間與規(guī)定交貨期之間的偏差；式(4)表示制造碳排放CP，式中第一項表示機(jī)器加工時消耗電能所產(chǎn)生的碳排放，第二項表示機(jī)器空轉(zhuǎn)時消耗電能所產(chǎn)生的碳排放，第三項表示機(jī)器加工不同工件時調(diào)整所產(chǎn)生的碳排放，第四項表示工件在機(jī)器間運(yùn)輸時油耗所引起的碳排放。

約束(5)表示加工機(jī)器k上任務(wù)Oi-j的開始加工時間Sijk不能小于加工機(jī)器k上的緊前任務(wù)Oh-l的完工時間Chlk與這兩個任務(wù)在加工機(jī)器k上的調(diào)整時間thik的和；約束(6)表示工件i任務(wù)j在加工機(jī)器k上的開工時間Sijk與該工件的緊前任務(wù)j-1在加工機(jī)器k′上的完工時間Ci(j-1)k′的間隔不能小于該工件從上一加工機(jī)器k′搬運(yùn)到加工機(jī)器k所需的時間tt,ij；約束(7)表示工件i的第j道任務(wù)的完工時間cijk不能小于該任務(wù)的開始加工時間Sijk與加工時間tijk的和；約束(8)是為了確保最大完工時間Ctime不小于任何一個任務(wù)的完工時間Cijk；約束(9)表示一道任務(wù)只能在一臺加工機(jī)器上加工。

2 改進(jìn)精英策略的PCA-NSGAⅡ

高維目標(biāo)調(diào)度優(yōu)化模型中，各優(yōu)化目標(biāo)和約束條件呈非線性關(guān)系，若采用線性化處理求解該模型，會嚴(yán)重影響模型的準(zhǔn)確性。同時，采用一般算法求解時具有明顯的高計算復(fù)雜度，且精度大幅下降?；赑areto的算法在求解高維目標(biāo)調(diào)度優(yōu)化非線性模型時，其選擇壓力減弱，非支配解的個數(shù)將呈指數(shù)增長，算法優(yōu)化效果大大降低，無法獲得滿意的解，甚至無法求解。針對其計算復(fù)雜度高、求解難度大和易導(dǎo)致算法選擇壓力不足的難點(diǎn)，本文設(shè)計了一種基于改進(jìn)精英策略的主成分分析—快速非支配排序遺傳算法(Principal Component Analysis-Non-dominated Sorting Genetic Algorithm Ⅱ, PCA-NSGAⅡ)。為降低算法的計算復(fù)雜度，增加算法選擇壓力以提高收斂性，設(shè)計了快速非支配排序算子以及擁擠度比較算子；為了改善解的質(zhì)量，提高尋優(yōu)效率，改進(jìn)了算法的精英保留策略，在原有將父代和子代合并同時優(yōu)化產(chǎn)生下一代的精英保留機(jī)制的基礎(chǔ)上，提出增加一個外部種群，豐富種群個體的多樣性，用于保留每代的精英個體，外部種群同時進(jìn)行優(yōu)化，并在選擇操作時優(yōu)先選擇外部種群中的個體。算法具體流程如圖1所示。

2.1 編碼和解碼

設(shè)計一種基于任務(wù)和機(jī)器的二段式編碼，第一段為任務(wù)加工順序編碼，由工件號組成，工件號i在基因串中從左至右出現(xiàn)的次數(shù)j表示該加工方案中工件i的第j道任務(wù)，圖2中3個工件的加工任務(wù)的加工順序為：O1-1→O1-2→O3-1→O2-1→O1-3→O2-2→O3-2→O3-3；第二段為機(jī)器分配編碼，確定各任務(wù)對應(yīng)的加工機(jī)器。基因串中從左至右依次為工件1的第一道任務(wù)到最后一道任務(wù)的所選加工機(jī)器，其中基因k表示機(jī)器Mk。圖2中加工機(jī)器分配方案為：工件1的第一、二、三道任務(wù)分別在M4、M2、M5上加工；工件2的第一、二道任務(wù)分別在M3、M4上加工；工件3的第一、二、三道任務(wù)分別在M1、M4、M3上加工。

2.2 種群初始化以及選擇、交叉、變異操作

(1)種群初始化 采用隨機(jī)生成的方式產(chǎn)生任務(wù)加工順序編碼和機(jī)器分配編碼。

(2)選擇操作 采用二元錦標(biāo)賽方法對解集的非支配等級以及擁擠距離進(jìn)行選擇。優(yōu)先選擇非支配等級低的解，若解的非支配等級相同，則比較擁擠距離，選擇擁擠距離大的解。

(3)交叉操作 對加工順序編碼段進(jìn)行交叉操作(Precedence Operation crossover, POX)[15]；對機(jī)器分配編碼段采用多點(diǎn)交叉操作(Multi-point Preservative crossover, MPX)[5]。上述兩種交叉依次以設(shè)定的概率進(jìn)行。

(4)變異操作 采用文獻(xiàn)[5]中的兩種變異操作，第一種擴(kuò)展的插入變異操作用于任務(wù)加工順序編碼段；第二種機(jī)器分配編碼段的變異操作，隨機(jī)選取機(jī)器編碼段上的兩個基因，在其對應(yīng)的任務(wù)的可選加工機(jī)器集中隨機(jī)選取加工機(jī)器對該基因進(jìn)行替換。

2.3 PCA占優(yōu)機(jī)制

PCA占優(yōu)是一種基于主成分(PCA)分析的差值求解選取非支配的方法。先用NSGAⅡ算法對高維目標(biāo)問題進(jìn)行迭代優(yōu)化，得到一個非支配種群，再對非支配種群對應(yīng)的目標(biāo)進(jìn)行PCA分析，得到目標(biāo)的權(quán)重向量。假設(shè)M個目標(biāo)的權(quán)重向量為w，w={w1,w2,…,wM}，則種群個體間的占優(yōu)關(guān)系判斷標(biāo)準(zhǔn)如下：

個體a與個體b對于任意目標(biāo)fi，若存在：

fi′(a)-fi′(b)+Temp<0，

則個體a占優(yōu)個體b。其中：fi(a)為個體a在目標(biāo)fi上取得的目標(biāo)值，wi為目標(biāo)fi的權(quán)重系數(shù)。

2.4 外部種群

為提高PCA-NAGAⅡ算法的尋優(yōu)效果和收斂性能，對算法的精英保留策略進(jìn)行改進(jìn)，通過每次迭代保留子代與父代合并后生成的組合種群中部分好的個體生成一個外部種群P1。對外部種群P1和原有種群P進(jìn)行選擇、交叉、變異。外部種群P1的子代、父代與原有種群P的子代、父代一同合并成組合種群，從而增加種群中較優(yōu)個體的數(shù)量。豐富種群個體的多樣性，引導(dǎo)算法的尋優(yōu)方向，加快算法向較優(yōu)解逼近，提升收斂性能，使最終解質(zhì)量更好。

3 算例驗證

從合作企業(yè)中選取由3個制造工廠和8個加工機(jī)器組成的制造系統(tǒng)作為研究對象，3個工件作為加工對象，工件1、2和3分別包含6、5和8個加工任務(wù)。制造工廠U1包含加工機(jī)器M1,M2,M3，制造工廠U2包含加工機(jī)器M4,M5，制造工廠U3包含加工機(jī)器M6,M7,M8。各任務(wù)可選加工機(jī)器以及其對應(yīng)的加工時間和加工成本如表2所示。制造工廠間的搬運(yùn)工具為小型貨車，其平均速度為28.7 km/h，耗油均值為0.121 4 L/km[16]。小型貨車所使用的柴油價格為6.5元/L。表3為各制造工廠間的距離；表4為各加工機(jī)器加工各工件任務(wù)時的平均加工功率，空載功率以及調(diào)整功率；表5為各加工機(jī)器加工工件時的調(diào)整時間。電能的碳排放因子參照香港中小企業(yè)碳審計工具箱[17]，取值為0.674 7 kg CO2/kW·h，由文獻(xiàn)[16]對各類貨車CO2碳排放因子的計算中查得小型貨車CO2碳排放因子的均值為326.88 g CO2/km。

表2 工件任務(wù)可選機(jī)器以及加工時間和加工成本

表3 制造工廠間的距離 km

表4 機(jī)器功率 kW

表5 機(jī)器加工不同工件間的調(diào)整時間 s

采用Python編程，參數(shù)設(shè)置為：種群規(guī)模N=60，最大迭代次數(shù)m=500，交叉率C=0.85，變異率A=0.2，得到一組Pareto解集如表6所示。

表6 改進(jìn)精英策略的PCA-NSGAⅡ算法所得解集

由表6可知，序號解1是制造過程中碳排放最小的解(Cp=45.723 7 kg CO2)；序號解7是最大完工時間最小的解(Ctime=5 861.298 s)；序號解23是貨拖期/提前懲罰最小的解(ET=58.140 6元)；序號解26是生產(chǎn)總成本最小的解(Ccost=440.443 8元)。其中對碳排放最小的解進(jìn)行解碼所得到甘特圖如圖3所示。圖中：“-”前的數(shù)字表示工件編號；“-”后的數(shù)字表示該工件的任務(wù)編碼。

為了說明本文算法對高維目標(biāo)調(diào)度優(yōu)化的效果，將所提算法的優(yōu)化結(jié)果分別與傳統(tǒng)的基于Pareto排序的NSGAⅡ算法得的結(jié)果、基于ε支配的NSGA-Ⅱ算法以及原PCA-NSGAⅡ算法所得結(jié)果進(jìn)行比較。同樣設(shè)置種群規(guī)模N=60，最大迭代次數(shù)m=500，交叉率C=0.85，變異率A=0.2，3種算法得到的非支配解集分別如下表7、表8和表9；3個算法在4個目標(biāo)上的結(jié)果對比如表10所示。

表7 原PCA-NSGAⅡ算法所得解集

表8 NSGAⅡ算法所得Pareto解集

續(xù)表8

表9 基于ε支配的NSGAⅡ算法所得Pareto解集

表10 算法結(jié)果對比

續(xù)表10

續(xù)表10

由表8可以看出，采用NSGA-Ⅱ算法迭代優(yōu)化后所得的Pareto解集中個體的數(shù)量為47，與設(shè)置的種群規(guī)模N=60很接近，這也驗證了傳統(tǒng)基于Pareto排序的進(jìn)化算法在解決目標(biāo)維度大于或等于4的高維目標(biāo)問題時，非支配解的數(shù)量會隨著目標(biāo)個數(shù)的增加而增長，從而導(dǎo)致算法選擇能力減弱這一現(xiàn)象。

從表10可以看出，改進(jìn)精英策略的PCA-NSGAⅡ算法在最好值上除了生產(chǎn)總成本外的其他3個目標(biāo)均優(yōu)于其他3種算法，在生產(chǎn)總成本上的最好值同樣優(yōu)于原PCA-NSGAⅡ算法和NSGA-Ⅱ算法，略差于基于ε支配的NSGA-Ⅱ算法；且在所有目標(biāo)上無論是最好值、最壞值還是平均值均明顯優(yōu)于NSGA-Ⅱ算法；除了總拖期/提前懲罰目標(biāo)上的最壞值和平均值外的其他目標(biāo)無論最好值、最壞值還是平均值均明顯優(yōu)于原PCA-NSGAⅡ算法。其中，改進(jìn)精英策略的PCA-NSGAⅡ算法所有最好值都優(yōu)于原PCA-NSGAⅡ算法，在4個目標(biāo)上分別多減少了3.86%、7.30%、16.53%和9.24%；改進(jìn)精英策略的PCA-NSGAⅡ算法最好值除在生產(chǎn)總成本這一目標(biāo)外在其他3個目標(biāo)比基于ε支配的NSGA-Ⅱ分別多減少3.55%、0.5%和43.7%，特別在拖期懲罰上減少效果明顯。在生產(chǎn)總成本上的最好值，基于ε支配的NSGA-Ⅱ比改進(jìn)精英策略的PCA-NSGAⅡ多減少7.49%；故從4個目標(biāo)整體來看，改進(jìn)精英策略的PCA-NSGAⅡ算法在解決高維優(yōu)化問題上，其總體優(yōu)化效果比其他3種算法的優(yōu)化效果好。

為了驗證所提增加一個外部種群，與原始種群共同進(jìn)化的改進(jìn)精英策略是否有效，對改進(jìn)精英策略的PCA-NSGAⅡ算法和原PCA-NSGAⅡ算法在收斂性上進(jìn)行比較。為了考慮模型中所有目標(biāo)在整個優(yōu)化過程中的收斂情況，選取了國內(nèi)外通用的收斂性評價標(biāo)準(zhǔn)[18]即世代距離(GD)來衡量算法的收斂性能，為了避免隨機(jī)性導(dǎo)致的誤差，取5次計算結(jié)果的平均值作為對比值。其結(jié)果如表11所示。

表11 世代距離(GD)對比

可以看出，改進(jìn)精英策略的PCA-NSGAⅡ算法獲得的平均GD值明顯小于原PCA-NSGAⅡ算法，說明改進(jìn)精英策略的PCA-NSGAⅡ算法在收斂性上具有一定的優(yōu)勢。由此可見，所提改進(jìn)的精英策略能有效地提升算法的收斂性能，使算法向好的方向優(yōu)化，改善算法的優(yōu)化結(jié)果，從而說明了改進(jìn)精英策略的有效性。

為進(jìn)一步驗證所提算法對求解不同規(guī)模的高維調(diào)度優(yōu)化問題的有效性，將其他規(guī)模算例的結(jié)果也進(jìn)行了對比分析。選取其他2種不同規(guī)模的算例2×7×3×15、4×11×5×25(制造工廠數(shù)×加工機(jī)器數(shù)×工件數(shù)×加工任務(wù)數(shù))進(jìn)行測試，具體各目標(biāo)最優(yōu)值的結(jié)果對比和GD均值分別如表12和表13所示。

表12 其他規(guī)模算例結(jié)果對比

表13 其他規(guī)模算例的世代距離均值對比

可以看出，改進(jìn)精英策略的PCA-NSGAⅡ算法在解決不同規(guī)模的高維問題上，其優(yōu)化結(jié)果均優(yōu)于其他3種算法的優(yōu)化結(jié)果，且所提改進(jìn)的精英策略能有效地提升算法的收斂性能，驗證了所提算法的有效性。

4 結(jié)束語

為了探索如何有效地解決制造系統(tǒng)中的高維目標(biāo)調(diào)度優(yōu)化問題，以生產(chǎn)總成本最小、最大完工時間最小、交貨拖期/提前懲罰最小和制造過程中碳排放最小為目標(biāo)構(gòu)建高維目標(biāo)調(diào)度模型，設(shè)計了改進(jìn)精英策略的PCA-NSGAⅡ算法，用PCA占優(yōu)機(jī)制代替?zhèn)鹘y(tǒng)算法中Pareto排序來解決高維目標(biāo)調(diào)度優(yōu)化問題。為了保證種群多樣性，提高算法尋優(yōu)質(zhì)量，對算法精英策略進(jìn)行改進(jìn)，提出增加一個外部種群引導(dǎo)種群進(jìn)化方向，改善種群的質(zhì)量，提高算法的收斂性，并通過算例對比與分析，說明所提出的改進(jìn)精英策略的PCA-NSGAⅡ算法在處理高維目標(biāo)調(diào)度優(yōu)化問題時的有效性。

高維目標(biāo)問題在實(shí)際應(yīng)用中計算的復(fù)雜度很高，當(dāng)數(shù)據(jù)量更加龐大時，對算法的運(yùn)算速度有更高的要求，后續(xù)研究擬關(guān)注算法對大規(guī)模問題的計算速度。另外，關(guān)于如何有效地解決高維目標(biāo)優(yōu)化問題，后續(xù)研究還可考慮一些非Pareto排序的排序方法，設(shè)計新的適應(yīng)度計算準(zhǔn)則和多樣性維護(hù)機(jī)制，增加個體的選擇壓力，提升算法的搜索能力，保證算法的優(yōu)化效果。