基于改進(jìn)精英策略的PCA-NSGAⅡ的高維目標(biāo)調(diào)度優(yōu)化

劉 瓊，熊書平，湛夢夢

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

0 引言

現(xiàn)實(shí)生活中，存在許多多目標(biāo)優(yōu)化問題(Multi-objectives Optimization Problems，MOP)，當(dāng)優(yōu)化目標(biāo)個(gè)數(shù)增加到4個(gè)及以上時(shí)，即視為高維目標(biāo)優(yōu)化問題[1]。由于目標(biāo)函數(shù)之間經(jīng)常是沖突的，其最優(yōu)解并非單一解，而是一組非支配解[2]。一個(gè)目標(biāo)的優(yōu)化將可能導(dǎo)致其他目標(biāo)的惡化，只能采用折中的方式讓各個(gè)目標(biāo)盡可能達(dá)到最優(yōu)。而且，優(yōu)化過程導(dǎo)致計(jì)算復(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ī)模大，加工路徑多樣，這些因素?cái)U(kuò)大了可行解的搜索范圍，與傳統(tǒng)車間調(diào)度問題相比規(guī)模更大，更復(fù)雜；且隨著問題規(guī)模的增大，計(jì)算的復(fù)雜度將呈指數(shù)增長[4]。同時(shí)，資源共享需兼顧各個(gè)企業(yè)的需求，通常涉及多個(gè)優(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)個(gè)數(shù)增加到4個(gè)及以上時(shí)，即可視為高維目標(biāo)調(diào)度優(yōu)化問題，目標(biāo)個(gè)數(shù)2或3個(gè)的調(diào)度優(yōu)化問題為多目標(biāo)調(diào)度優(yōu)化問題。在實(shí)際生產(chǎn)調(diào)度中，企業(yè)可考慮的優(yōu)化目標(biāo)有很多，包括完工時(shí)間、成本、提前/拖期懲罰、設(shè)備利用率、設(shè)備負(fù)荷、碳排放等，企業(yè)可根據(jù)自身需要選擇合適的優(yōu)化目標(biāo)。目前多目標(biāo)調(diào)度優(yōu)化問題研究較多，一般通過非劣解排序(Pareto排序)來選擇個(gè)體和確定優(yōu)化方向，如張超勇等[5]提出一種改進(jìn)的非支配排序遺傳算法，設(shè)計(jì)新的編碼解碼機(jī)制，解決了以時(shí)間和成本為優(yōu)化目標(biāo)的多目標(biāo)柔性作業(yè)車間調(diào)度問題。Liu等[6]采用基于Pareto排序的混合果蠅算法來解決以減少最大完工時(shí)間和制造過程中碳排放為目標(biāo)的多目標(biāo)調(diào)度優(yōu)化問題。當(dāng)優(yōu)化的目標(biāo)數(shù)增加至4個(gè)或以上形成高維目標(biāo)時(shí)，算法的選擇壓力減弱，非支配解的個(gè)數(shù)將呈指數(shù)增長，基于Pareto排序的多目標(biāo)調(diào)度優(yōu)化算法優(yōu)化效果大大降低。針對該問題，現(xiàn)有研究大都通過給目標(biāo)賦予不同權(quán)重來減少目標(biāo)的維數(shù)，以增強(qiáng)算法的種群選擇能力。吳秀麗等[7]建立了以完工時(shí)間、成本、交貨期滿意度和設(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]建立了以完工時(shí)間、拖期懲罰、機(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ù)量增加，錯(cuò)誤目標(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]將一種用來確定個(gè)體間支配關(guān)系的優(yōu)勝關(guān)系與進(jìn)化算法相結(jié)合來解決電路設(shè)計(jì)中高維優(yōu)化問題，若解a在更多目標(biāo)上優(yōu)于解b，則a支配b，但該優(yōu)勝關(guān)系不具有傳遞性，當(dāng)存在a支配b，b支配c，c又支配a的循環(huán)情況時(shí)，無法對所有個(gè)體完全排序，易出現(xiàn)選擇壓力退化。郭思涵等[13]提出帶有正交E占優(yōu)策略的算法，采用正交試驗(yàn)初始化種群，采用E占優(yōu)代替Pareto排序，通過求解標(biāo)準(zhǔn)測試問題來對比說明改進(jìn)后的算法比原算法具有更好的收斂性能，但算法的參數(shù)難以確定，易受主觀干擾，同時(shí)改動(dòng)了個(gè)體的真實(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ù)驗(yàn)證了算法的有效性。采用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ǔ)上，提出增加一個(gè)外部種群，對算法精英策略進(jìn)行改進(jìn)，將算法中優(yōu)化后的優(yōu)秀個(gè)體放入外部種群中，原種群和外部種群同時(shí)進(jìn)化，并通過優(yōu)先選擇外部種群中個(gè)體的方式，引導(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)成一個(gè)制造系統(tǒng)，多臺機(jī)器可共同完成各工件的加工任務(wù)。

1.1 問題描述

1.2 條件假設(shè)

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

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

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

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

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

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

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

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

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

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

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

目前生產(chǎn)調(diào)度中考慮的優(yōu)化目標(biāo)有很多，如完工時(shí)間、成本、提前/拖期懲罰、設(shè)備利用率、設(shè)備負(fù)荷、碳排放等，依據(jù)企業(yè)的實(shí)際需求，以總成本、最大完工時(shí)間和總提前/拖期懲罰為主要考慮目標(biāo)。同時(shí)，近年來環(huán)境問題日益突出，制造過程產(chǎn)生的碳排放已越來越引起企業(yè)和公眾的關(guān)注，未來制造模式將向低排放、低污染、低能耗方向發(fā)展，故將制造過程碳排放作為一個(gè)優(yōu)化目標(biāo)。因此以總成本最小、最大完工時(shí)間最小、總拖期/提前懲罰最小以及制造過程中碳排放最小為目標(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)表示最大完工時(shí)間Ctime，即從第一個(gè)工件的第一道工序在機(jī)器上開始加工到最后一個(gè)工件的最后一道工序在機(jī)器上加工完成之間的時(shí)間；式(3)表示總拖期/提前懲罰ET，即衡量工件實(shí)際加工完成時(shí)間與規(guī)定交貨期之間的偏差；式(4)表示制造碳排放CP，式中第一項(xiàng)表示機(jī)器加工時(shí)消耗電能所產(chǎn)生的碳排放，第二項(xiàng)表示機(jī)器空轉(zhuǎn)時(shí)消耗電能所產(chǎn)生的碳排放，第三項(xiàng)表示機(jī)器加工不同工件時(shí)調(diào)整所產(chǎn)生的碳排放，第四項(xiàng)表示工件在機(jī)器間運(yùn)輸時(shí)油耗所引起的碳排放。

約束(5)表示加工機(jī)器k上任務(wù)Oi-j的開始加工時(shí)間Sijk不能小于加工機(jī)器k上的緊前任務(wù)Oh-l的完工時(shí)間Chlk與這兩個(gè)任務(wù)在加工機(jī)器k上的調(diào)整時(shí)間thik的和；約束(6)表示工件i任務(wù)j在加工機(jī)器k上的開工時(shí)間Sijk與該工件的緊前任務(wù)j-1在加工機(jī)器k′上的完工時(shí)間Ci(j-1)k′的間隔不能小于該工件從上一加工機(jī)器k′搬運(yùn)到加工機(jī)器k所需的時(shí)間tt,ij；約束(7)表示工件i的第j道任務(wù)的完工時(shí)間cijk不能小于該任務(wù)的開始加工時(shí)間Sijk與加工時(shí)間tijk的和；約束(8)是為了確保最大完工時(shí)間Ctime不小于任何一個(gè)任務(wù)的完工時(shí)間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)確性。同時(shí)，采用一般算法求解時(shí)具有明顯的高計(jì)算復(fù)雜度，且精度大幅下降?；赑areto的算法在求解高維目標(biāo)調(diào)度優(yōu)化非線性模型時(shí)，其選擇壓力減弱，非支配解的個(gè)數(shù)將呈指數(shù)增長，算法優(yōu)化效果大大降低，無法獲得滿意的解，甚至無法求解。針對其計(jì)算復(fù)雜度高、求解難度大和易導(dǎo)致算法選擇壓力不足的難點(diǎn)，本文設(shè)計(jì)了一種基于改進(jìn)精英策略的主成分分析—快速非支配排序遺傳算法(Principal Component Analysis-Non-dominated Sorting Genetic Algorithm Ⅱ, PCA-NSGAⅡ)。為降低算法的計(jì)算復(fù)雜度，增加算法選擇壓力以提高收斂性，設(shè)計(jì)了快速非支配排序算子以及擁擠度比較算子；為了改善解的質(zhì)量，提高尋優(yōu)效率，改進(jìn)了算法的精英保留策略，在原有將父代和子代合并同時(shí)優(yōu)化產(chǎn)生下一代的精英保留機(jī)制的基礎(chǔ)上，提出增加一個(gè)外部種群，豐富種群個(gè)體的多樣性，用于保留每代的精英個(gè)體，外部種群同時(shí)進(jìn)行優(yōu)化，并在選擇操作時(shí)優(yōu)先選擇外部種群中的個(gè)體。算法具體流程如圖1所示。

2.1 編碼和解碼

設(shè)計(jì)一種基于任務(wù)和機(jī)器的二段式編碼，第一段為任務(wù)加工順序編碼，由工件號組成，工件號i在基因串中從左至右出現(xiàn)的次數(shù)j表示該加工方案中工件i的第j道任務(wù)，圖2中3個(gè)工件的加工任務(wù)的加工順序?yàn)椋篛1-1→O1-2→O3-1→O2-1→O1-3→O2-2→O3-2→O3-3；第二段為機(jī)器分配編碼，確定各任務(wù)對應(yīng)的加工機(jī)器?；虼袕淖笾劣乙来螢楣ぜ?的第一道任務(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ī)器編碼段上的兩個(gè)基因，在其對應(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)化，得到一個(gè)非支配種群，再對非支配種群對應(yīng)的目標(biāo)進(jìn)行PCA分析，得到目標(biāo)的權(quán)重向量。假設(shè)M個(gè)目標(biāo)的權(quán)重向量為w，w={w1,w2,…,wM}，則種群個(gè)體間的占優(yōu)關(guān)系判斷標(biāo)準(zhǔn)如下：

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

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

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

2.4 外部種群

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

3 算例驗(yàn)證

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

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

表3 制造工廠間的距離 km

表4 機(jī)器功率 kW

表5 機(jī)器加工不同工件間的調(diào)整時(shí)間 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是最大完工時(shí)間最小的解(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個(gè)算法在4個(gè)目標(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解集中個(gè)體的數(shù)量為47，與設(shè)置的種群規(guī)模N=60很接近，這也驗(yàn)證了傳統(tǒng)基于Pareto排序的進(jìn)化算法在解決目標(biāo)維度大于或等于4的高維目標(biāo)問題時(shí)，非支配解的數(shù)量會隨著目標(biāo)個(gè)數(shù)的增加而增長，從而導(dǎo)致算法選擇能力減弱這一現(xiàn)象。

從表10可以看出，改進(jìn)精英策略的PCA-NSGAⅡ算法在最好值上除了生產(chǎn)總成本外的其他3個(gè)目標(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個(gè)目標(biāo)上分別多減少了3.86%、7.30%、16.53%和9.24%；改進(jìn)精英策略的PCA-NSGAⅡ算法最好值除在生產(chǎn)總成本這一目標(biāo)外在其他3個(gè)目標(biāo)比基于ε支配的NSGA-Ⅱ分別多減少3.55%、0.5%和43.7%，特別在拖期懲罰上減少效果明顯。在生產(chǎn)總成本上的最好值，基于ε支配的NSGA-Ⅱ比改進(jìn)精英策略的PCA-NSGAⅡ多減少7.49%；故從4個(gè)目標(biāo)整體來看，改進(jìn)精英策略的PCA-NSGAⅡ算法在解決高維優(yōu)化問題上，其總體優(yōu)化效果比其他3種算法的優(yōu)化效果好。

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

4 結(jié)束語

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

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