王 宇 張聞強(qiáng)(河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院 河南 鄭州 450001)

0 引 言

調(diào)度問題研究是將具有相關(guān)具有約束條件的有限資源，按照問題實(shí)際需求合理配給一個(gè)或者多個(gè)目標(biāo)對(duì)象。流水車間調(diào)度問題FSP(Flow shop scheduling problem)是一類經(jīng)典的多目標(biāo)調(diào)度問題，按照實(shí)際工業(yè)生產(chǎn)需求約束后的數(shù)學(xué)建模，屬于NP-hard問題，在工業(yè)自動(dòng)化領(lǐng)域廣泛存在。其中以最短拖期與總完工時(shí)間為雙目標(biāo)的調(diào)度問題意在合理地排列出機(jī)器、工件、時(shí)間等資源分配，有效率地滿足自動(dòng)化生產(chǎn)過程中經(jīng)濟(jì)或性能[1]。在1954年，F(xiàn)SP由Johnson等[2]提出，在此之后大量的論文提出了不同的方法，試圖確定更好的工作序列。平衡找到高品質(zhì)的解決方案，而且消耗合理的計(jì)算時(shí)間。

近年來在工業(yè)自動(dòng)化領(lǐng)域，眾多學(xué)者針對(duì)不同目標(biāo)的FSP問題進(jìn)行了廣泛的探討。研究單臺(tái)機(jī)器混合型車間調(diào)度問題提出分支綁定算法，強(qiáng)調(diào)特殊情況下的啟發(fā)式或最優(yōu)解，盡量減少制造時(shí)間[3]。流程車間調(diào)度問題是典型的組合優(yōu)化問題、解集復(fù)雜、數(shù)據(jù)量大、結(jié)果中通常不存在最優(yōu)解，學(xué)者針對(duì)問題對(duì)最新的智能計(jì)算算法：混合遺傳算法、粒子群優(yōu)化和貓群優(yōu)化算法的四個(gè)元學(xué)說的實(shí)驗(yàn)比較研究[4]。Gao等[5]提出兩種建構(gòu)性啟發(fā)式方法，嵌入局部搜索和修改迭代算子，改進(jìn)了混合啟發(fā)式算法，在約束條件下最大可能地降低調(diào)度的總流程時(shí)間。然而，單目標(biāo)的研究已不能滿足當(dāng)下制造自動(dòng)化的生產(chǎn)環(huán)境，多重約束下的有限資源分配成為主流。為了彌補(bǔ)單一智能算法的弊端，結(jié)合不同算法的優(yōu)勢(shì)。在犧牲一定程度時(shí)間復(fù)雜度的情況下，學(xué)者對(duì)經(jīng)典的演化算法進(jìn)行組合。混合不同的算法使其具有相關(guān)父代算法的優(yōu)勢(shì)特性，針對(duì)實(shí)際環(huán)境優(yōu)化后應(yīng)用前景更加廣泛。楊開兵等[6]根據(jù)成組工件的FSP問題，在保持種群的多樣性與收斂性能上分別引入適應(yīng)度計(jì)算策略和進(jìn)行局部搜索。何啟巍基于粒子群優(yōu)化算法的特點(diǎn)，加入一種變鄰域搜索策略，極大地提高了解的分布性，混合算法用于對(duì)調(diào)度問題進(jìn)行求解，提高了解集的范圍[7]。陳可嘉等[8]通過對(duì)經(jīng)典的NSGA-Ⅱ算法進(jìn)行改進(jìn)，仿真生物食物鏈策略，算法收斂性能有所提高。

差分進(jìn)化算法DE(Differential Evolution)用于解決實(shí)數(shù)優(yōu)化問題，在1997年由Storn等[9]提出，是一種先變異，后交叉的啟發(fā)式全局搜索算法，由于采用浮點(diǎn)數(shù)編碼，算法解析容易實(shí)現(xiàn)，對(duì)連續(xù)空間具有高效的全局搜索能力。標(biāo)準(zhǔn)差分算法文檔中使用錦標(biāo)賽選擇，便于實(shí)現(xiàn)，遺傳方式與眾多智能算法相同。差分算法的主要策略在于變異操作方式，帶有方向目標(biāo)性，區(qū)別種群中優(yōu)勢(shì)的個(gè)體，使得其他個(gè)體根據(jù)決策者的需要以優(yōu)勢(shì)個(gè)體為前提進(jìn)行一定的擾動(dòng)，實(shí)現(xiàn)個(gè)體變異，得到下一代。差分策略根據(jù)種群分布的特點(diǎn)，讓優(yōu)秀的個(gè)體成為“榜樣”，避免傳統(tǒng)遺傳算法隨機(jī)“盲目”式的變異方式，提高算法的搜索能力?，F(xiàn)在，基于差分進(jìn)化算法被廣泛應(yīng)用到數(shù)據(jù)挖掘、自動(dòng)化、機(jī)械工程等各個(gè)領(lǐng)域。同時(shí)，也延伸于多目標(biāo)優(yōu)化與調(diào)度問題。針對(duì)最小化最大完成時(shí)間問題，提出自適應(yīng)鄰域搜索差分演化(NS-SGDE)基于概率模型的指導(dǎo)代理，以指導(dǎo)DE的探索階段來產(chǎn)生后代[10]。差分算法過快的收斂速度容易陷入局部最優(yōu)。通過設(shè)定自適應(yīng)縮放因子，建立分布模型，對(duì)種群進(jìn)化過程中的優(yōu)勢(shì)個(gè)體進(jìn)行統(tǒng)計(jì)，自適性的改變選擇方式，有效地防止子代陷入局部最優(yōu)[11]。可變鄰域(DEVNS)搜索在收斂性方面具有很強(qiáng)的優(yōu)勢(shì)，結(jié)合可變鄰域的差分演化算法來解決流水車間調(diào)度問題具有很高的競(jìng)爭(zhēng)力[12]。張曉霞等運(yùn)用基于概率模型的分布估計(jì)算法，避免算法陷入局部最優(yōu)，求解混合零空閑置換流水車間問題[13]。

向量評(píng)估算法VEGA(Vector evaluated genetic algorithm)[14]利用并行方式解決多目標(biāo)優(yōu)化問題，根據(jù)多目標(biāo)子函數(shù)設(shè)立不同后代、分層成比例的選擇機(jī)制，獨(dú)立種群按照決策者需要可以進(jìn)行獨(dú)立遺傳操作或者融合進(jìn)化。不同的后代群體朝著不同的方向進(jìn)化，這種特性表現(xiàn)出很強(qiáng)的朝著Pareto前沿面的邊緣區(qū)域收斂的能力，同時(shí)分布性不好。一種基于Pareto支配與被支配關(guān)系的適應(yīng)度函數(shù)PDDR-FF(Pareto dominating and dominated relationship-based fitness function)[15]用來判斷個(gè)體之間的區(qū)別。PDDR-FF函數(shù)針對(duì)個(gè)體的支配信息對(duì)其優(yōu)劣程度與位置進(jìn)行區(qū)別劃分，根據(jù)個(gè)體支配數(shù)與被支配數(shù)賦予不同的數(shù)值。個(gè)體在Pareto前沿面分為中心區(qū)域與邊緣區(qū)域，其中中心區(qū)域的可支配面積比邊緣區(qū)域要大。PDDR-FF的特點(diǎn)促使個(gè)體朝著具有更大支配數(shù)的優(yōu)勢(shì)方向前進(jìn),也就是表現(xiàn)為朝著具有更大支配面積的中心區(qū)域進(jìn)化?；旌喜蓸訖C(jī)制不僅具有良好的收斂性能，同時(shí)保護(hù)了種群的分布性?；诨旌喜蓸硬呗缘亩嗄繕?biāo)進(jìn)化算法HSS-MOEA(Multi-objective hybrid evolutionary algorithm)與NSGA-Ⅱ和SPEA2相比，混合采樣后的算法在收斂和分布性能上要好，在時(shí)間消耗、運(yùn)算效率上，也優(yōu)于傳統(tǒng)遺傳算法[16]。

混合采樣策略不僅具有VEGA偏好邊緣區(qū)域的優(yōu)勢(shì)，同時(shí)具有朝Pareto前沿的邊緣區(qū)域收斂的能力，而DE對(duì)精英解進(jìn)一步優(yōu)化。本文在HSS-MOEA的基礎(chǔ)上引入差分策略，設(shè)計(jì)混合算法框架及變異操作中備選個(gè)體的選擇策略。以此提出多目標(biāo)混合差分進(jìn)化算法(HMODE)來解決復(fù)合FSP問題?；旌纤惴ūＡ袅耸諗克俣群头植夹阅?，以及DE提高HSS-MOEA應(yīng)用后的效率性。

1 問題描述

流程車間調(diào)度可以描述如下：在集合J={J1，J2，…，Jn}里有n個(gè)工件。在不同的m個(gè)機(jī)器{M1，M2，…，Mm}進(jìn)行處理。模擬機(jī)器工件在機(jī)器上的操作順序進(jìn)行處理，則Oji被定義為作業(yè)Ji的第i個(gè)操作，并且機(jī)器Mi上的Oji的處理時(shí)間是Pji。目標(biāo)是找到一套相對(duì)最優(yōu)的解決方案，最大限度地減少加工時(shí)間和最大延遲。

令π=(π(1)，π(2)，…，π(1))是作業(yè)的某一組操作順序，πa是排列π的運(yùn)動(dòng)作業(yè)，n是作業(yè)數(shù)。U表示所有可能的過程組合，π∈U。Ci(j)表示機(jī)器Mi上作業(yè)πj的總完成時(shí)間，tji是機(jī)器Mi上的操作完成時(shí)間。如果在機(jī)器Mi上處理操作Oji，則xji=1，否則，xji=0;如果在Okh之前操作Oji，則yjikh=1，否則yjikh=0。FSP的數(shù)學(xué)公式可以描述如下：

(1)

j=2,3,…,ni=2,3,…,m

以最大完工時(shí)間為目的的FSP是從解集U找到一組序列π*:

(2)

所有約束條件如下：

(3)

解決最小化最大拖期與最小化總完工時(shí)間的多目標(biāo)流水車間調(diào)度問題要保證在同一時(shí)間里一個(gè)工件只能在一臺(tái)機(jī)器上加工，約束條件要保證一臺(tái)機(jī)器在某一個(gè)工作時(shí)間內(nèi)只能加工一個(gè)工件，所有工件加工順序相同。約束條件式(3)中前四個(gè)公式表示所有機(jī)器的作業(yè)加工訂單，分別確保加工排列的可行性，作業(yè)的唯一性和機(jī)器的獨(dú)特性。其余方程定義約束條件為非負(fù)。

求解最小化最大拖期是FSP中最常見的問題。假設(shè)Tmax(π)是序列π的最大拖期時(shí)間，Tπ(j)和Dπ(j)分別表示作業(yè)π(j)的拖期和項(xiàng)目時(shí)間。項(xiàng)目時(shí)間由“廠商”確定。類似地，F(xiàn)SP的最大拖期數(shù)學(xué)描述標(biāo)準(zhǔn)如下：

(4)

最大拖期與最大完工時(shí)間雙優(yōu)化目標(biāo)流水車間調(diào)度問題可以形式化為：

min{Cmax(π),Tmax(π)}π∈U

(5)

2 混合多目標(biāo)進(jìn)化算法與差分演化策略結(jié)合

2.1 算法框架

本研究基于多目標(biāo)混合采樣進(jìn)化算法，算法在同時(shí)保證收斂性能和分布性能的前提下，時(shí)間復(fù)雜度盡量降低。在此基礎(chǔ)上，混合DE算法對(duì)精英種群進(jìn)行處理，謀求進(jìn)一步提高最優(yōu)解集的收斂性和分布性，提高算法的性能?；旌纤惴朔渭僁E算法對(duì)于問題的局部搜索能力弱、搜索效率低的弊端，并重新設(shè)計(jì)問題編碼方式、遺傳操作中對(duì)備選個(gè)體的選擇策略以及參數(shù)設(shè)置。促使混合后的算法在Pareto前沿面的各個(gè)方向，盡可能地向著真實(shí)Pareto前沿面收斂并且均勻分布，以彌補(bǔ)單一算法的不足，提升算法的效力和效率。

算法大致框架如圖1所示，以t代HMODE的演進(jìn)過程為例。A(t)表示精英解集，作為第t代的精英保留策略，P(t)代表第t代種群。初始化參數(shù)，設(shè)置結(jié)束條件。一代的解決過程包括5個(gè)階段。

圖1 算法流程圖

1) 第一階段：VEGA采樣策略 在這個(gè)階段，利用VEGA采樣策略選擇優(yōu)秀個(gè)體，利用對(duì)Pareto前沿面邊界地區(qū)的強(qiáng)收斂能力依據(jù)目標(biāo)函數(shù)把P(t)分割成子代種群Sub1-P(t)與Sub2-P(t)。子代種群只考慮單一目標(biāo)演化，是單目標(biāo)最優(yōu)解集，按照降序排列。VEGA特性選擇出來的優(yōu)秀個(gè)體處于Pareto前沿面邊界處。

2) 第二階段：融合交配池(混合采樣) VEGA對(duì)Pareto前沿面邊緣區(qū)域處的搜索能力很好，多個(gè)子種群同時(shí)搜索導(dǎo)致單個(gè)個(gè)體的多樣性欠佳，原因就在于它的選擇偏好。在研究中，采樣得到的單個(gè)目標(biāo)子種群與精英種群A(t)的組合，形成一個(gè)交配池Mating Pool。在交配池中，以一個(gè)目標(biāo)存儲(chǔ)好優(yōu)秀個(gè)體子種群Sub1-P(t)，子種群Sub2-P(t)為另一個(gè)目標(biāo)擁有優(yōu)秀個(gè)體，而精英種群基于PDDR-FF適應(yīng)度函數(shù)選擇后具有多目標(biāo)最優(yōu)解，位于Pareto前沿面中心區(qū)域。因此，在交配池中，三分之一的個(gè)體服務(wù)于一個(gè)目標(biāo)，三分之一是另一個(gè)目標(biāo)，最后三分之一是兩個(gè)目標(biāo)，如圖2所示。

圖2 混合采樣

3) 第三階段：重構(gòu) 交叉操作是遺傳算法的主要操作。只有通過連續(xù)交叉，才能生產(chǎn)新的個(gè)體，獲得好的解集，突變算子是保持解的多樣性。在傳統(tǒng)解決FSP問題方式上，基于問題特性通常采用染色體編碼。本文引入差分進(jìn)化策略，對(duì)問題編碼進(jìn)行實(shí)數(shù)化。從二進(jìn)制編碼的思想出發(fā)，使用模擬二進(jìn)制交叉SBX(simulated binary crossover)與(polynomial mutation)多項(xiàng)式變異。

SBX交叉模擬二進(jìn)制串單點(diǎn)交叉共享重心的屬性特點(diǎn)，交叉生成的子代個(gè)體與父代的重心對(duì)稱。SBX交叉對(duì)于實(shí)數(shù)編碼具有很高的穩(wěn)定性。βi是隨機(jī)數(shù)。

(6)

ci與pi分別表示第i個(gè)基因位的子代與父代個(gè)體。SBX模擬二進(jìn)制碼單點(diǎn)交叉的共享重心特性，對(duì)于子代個(gè)體與父代個(gè)體每一個(gè)變量盡可能地使βi=1，保證了后代與雙親的重心對(duì)稱。

變異操作使用基于多項(xiàng)式分布的多項(xiàng)式變異方法。不均勻的方式改變個(gè)體，服從兩個(gè)原則：突變體應(yīng)隨機(jī)抽樣；隨著算法的演化過程，突變的程度將會(huì)減少。

使用均勻分布U～(0，1)生成多項(xiàng)式分布數(shù)ξ。

(7)

第i個(gè)變量變異方式如下：

(8)

ξj是由式(7)生成的多項(xiàng)式分布隨機(jī)數(shù)。Δmax是xj的最大允許攝動(dòng)。

4) 第四階段：精英保留策略 精英保留思想要把優(yōu)秀的個(gè)體作為“榜樣”傳遞到下一代，直到替換。A(t)作為優(yōu)秀種群在一定程度上代表著當(dāng)代最好的那一批個(gè)體，算法最后輸出也是這個(gè)集合。精英種群和P(t+1)混合成臨時(shí)種群temp-A(t)后按照PDDR-FF值適應(yīng)度值排序。根據(jù)PDDR-FF性質(zhì)，函數(shù)值越小越好，支配的面積大，其適應(yīng)度值不超過1。同時(shí)，被支配個(gè)體的適應(yīng)度值將超過1。此外，即使對(duì)于所有非支配個(gè)體，它們也具有不同的PDDR-FF值。非支配的個(gè)體根據(jù)位置分為邊緣區(qū)域(接近1)和中心區(qū)域(接近0)。

計(jì)算PDDR-FF適應(yīng)度值排序后，按照種群設(shè)置大小，選擇出|A(t)|個(gè)體作為temp-A(t+1)。temp-A(t)中的個(gè)體被復(fù)制形成temp-A(t+1)。這種個(gè)體保留機(jī)制類似于精英抽樣策略，基于PDDR-FF函數(shù)特點(diǎn)保證解集合處于Pareto中心區(qū)域。

5) 第五階段：差分優(yōu)化策略 更新解集以獲取臨時(shí)種群temp-A(t+1)后，應(yīng)用差分進(jìn)化策略對(duì)temp-A(t+1)進(jìn)行優(yōu)化。經(jīng)過DE的突變和交叉運(yùn)算后創(chuàng)建臨時(shí)種群temp-A′(t+1)。此時(shí)的臨時(shí)種群不僅有著上一代優(yōu)秀的個(gè)體，同時(shí)包含根據(jù)“榜樣”個(gè)體引導(dǎo)獲得的下一代。融合后按照決策者對(duì)問題的需要選擇下一代真實(shí)精英種群A(t+1)。與傳統(tǒng)DE不同，應(yīng)用與HSS-MOEA相同的優(yōu)秀個(gè)體保持機(jī)制，對(duì)種群進(jìn)行區(qū)域劃分，依據(jù)PDDR-FF值更新解集。

2.2 混合差分策略

DE不僅加強(qiáng)算法在Pareto前沿面中心區(qū)域和邊界區(qū)域的搜索能力，而且有助于彌補(bǔ)在過于強(qiáng)調(diào)中心和邊界區(qū)域的搜索帶來的剩余區(qū)域搜索能力不足的缺陷。但是需要根據(jù)問題背景的特殊性和復(fù)雜性來設(shè)計(jì)差分策略進(jìn)入的時(shí)機(jī)。此時(shí)機(jī)需要克服單純DE算法基于問題的局部搜索能力弱、搜索效率低的弊端。Pareto前沿面上個(gè)體代表著當(dāng)代優(yōu)秀的種群，作為目標(biāo)向量，向著真實(shí)的Pareto前沿面搜索有利于提升算法的收斂性能；或者沿著當(dāng)前Pareto前沿面搜索將有利于提升算法的均勻分布性能。

變異操作中備選個(gè)體的選擇策略?；贒E算法，需要根據(jù)當(dāng)前個(gè)體、備選個(gè)體個(gè)數(shù)和方向以確定搜索起點(diǎn)、步長(zhǎng)和方向。這些個(gè)體的選擇策略直接決定了新生成個(gè)體的收斂和分布性能。擬采用的變異操作根據(jù)當(dāng)前個(gè)體的適應(yīng)度評(píng)價(jià)函數(shù)值為DE/rand/1，仿真結(jié)果采取的設(shè)置如下：

Ui=X3+F(X1-X2)

(9)

依據(jù)支配關(guān)系把Pareto前沿面可劃分邊界區(qū)域與中心區(qū)域。對(duì)于初始精英解集temp-A(t+1)獲得差分演化算子，隨機(jī)選擇三個(gè)不同的個(gè)體。根據(jù)PDDR-FF值，保證選擇的個(gè)體eval(X1)

圖3 收斂性

圖4 分布性

模式一：X1與X2位于帕累托前沿面相同的區(qū)域時(shí)，不考慮X3個(gè)體位置，進(jìn)化方向有助于提高解集的收斂性能。

模式二：X1與X2位于帕累托前沿面不同的區(qū)域時(shí)，個(gè)體進(jìn)化有助于提高解集的均勻分布性能。

被選最差個(gè)體位于中心區(qū)域，最優(yōu)個(gè)體分布邊界區(qū)域時(shí)，個(gè)體朝兩邊進(jìn)化。

只表示單個(gè)目標(biāo)的優(yōu)勢(shì)個(gè)體集中在邊界處，具有多目標(biāo)的最優(yōu)個(gè)體位于中心區(qū)域，個(gè)體朝中心處移動(dòng)。

混合算法框架如圖3所示，改進(jìn)了遺傳算法，根據(jù)問題的特征采用實(shí)數(shù)編碼引入了DE策略對(duì)精英個(gè)體進(jìn)行優(yōu)化處理，使得算法的收斂性有了較大的改進(jìn)。加入自適應(yīng)密度評(píng)價(jià)函數(shù)PDDR-FF，對(duì)前沿面分塊化，彌補(bǔ)了遺傳算法容易陷入局部最優(yōu)解的缺點(diǎn)，加強(qiáng)了全局搜索的能力，使得算法能夠向多個(gè)方向演變，并在算法中根據(jù)問題相關(guān)的偏好信息設(shè)計(jì)DE策略執(zhí)行時(shí)期，提高算法的搜索速度。算法偽代碼如下所示。

算法1

HMODA?DEforMOPsStep0 Initialization：Sett=0，P(t)和A(t)Step1 Reprodution：1．1PartitionP(t)intoSub?P1(t)andSub?P2(t)byVEGA1．2TheSub?P1(t)，Sub?P2(t)andA(t)mixedintoMatingpool1．3P(t+1)wereobtainedfromthematingbycrossoverandmutationStep2 Differentialevolution：2．1TheA(t)andP(t+1)generatetemp?A(t+1)byelitistretentionstrategy2．2X1，X2andX3selectedfromtemp?A(t+1)．Accordingto?thepropertiesofPDDR?FFfunction，temp?A′(t+1)wereobtainedbydifferentialevolution．Step3 Selection：SelectA(t+1)fromtemp?A(t+1)Utemp?A′(t+1)Step4 StoppingCondition：Ifthestoppingconditionismet，stop；otherwise，sett=t+1andgotoStep1．

3 實(shí)驗(yàn)與結(jié)論

為驗(yàn)證算法可靠性，實(shí)驗(yàn)數(shù)據(jù)來源于Taillard[17]提出的其中10個(gè)隨機(jī)生成的調(diào)度問題，數(shù)據(jù)規(guī)模對(duì)應(yīng)于工業(yè)問題的實(shí)際尺寸。分別為20×5、20×10、20×20，對(duì)應(yīng)為20個(gè)工件。有5臺(tái)、10臺(tái)以及20臺(tái)機(jī)器。目的是最小化完工時(shí)間與最小化最大拖期的雙目標(biāo)。所有的仿真都在Core i5處理器(3.3 GHz)上執(zhí)行，內(nèi)存為8 GB。程序?yàn)镴AVA語(yǔ)言編寫。HMODE和HSS-MOEA使用相同的編碼和遺傳操作，具體參數(shù)值如下：種群大小=100;最大代數(shù)=500;檔案大小=50;交叉概率=0.90;突變概率=1/變量數(shù)，編碼方法是實(shí)數(shù)編碼。有20個(gè)變量。DE交叉概率=0.5，F(xiàn)=0.5。運(yùn)行30次HMODE和HSS-MOEA以比較結(jié)果。在這項(xiàng)研究中，驗(yàn)證收斂性通過比較解集中的個(gè)體與參考點(diǎn)在目標(biāo)空間中所圍成的超立方體的體積HV(Hypervolume)指標(biāo)，比較父代與子代之間的距離的GD(generational distance)指標(biāo)。分布性通過多元化度量DM(Diversification Metric)和SP(Spacing)，比較當(dāng)前點(diǎn)的每個(gè)成員與其最近的鄰居的范圍(距離)的差異，DM通過個(gè)體與其他個(gè)體的最大歐式距離來評(píng)價(jià)，有效地評(píng)測(cè)解集的分布性。

實(shí)驗(yàn)數(shù)據(jù)Box箱線圖如圖5與圖6所示。表1與表2分別表示SP、DM和HV、GD指標(biāo)的平均值和方差。表中顯示，HMODE的分布優(yōu)于HSS-MOEA，表明DE促進(jìn)了進(jìn)一步演變。與HSS-MOEA相比，HMODE在收斂方面具有優(yōu)勢(shì)。由于使用差分策略，編碼方案使用實(shí)數(shù)編碼。HSS-MOEA和HMODE的時(shí)間復(fù)雜度高于順序編碼。同時(shí)，HMODE在計(jì)算上有不止一個(gè)步驟，消耗更多的時(shí)間資源。

圖5 收斂性評(píng)測(cè)：HV與GD指標(biāo)

圖6 分布性評(píng)測(cè)：DM和SP指標(biāo)

表1 DM 和 SP指標(biāo)的均值與標(biāo)準(zhǔn)差

表2 HV和GD指標(biāo)的均值與標(biāo)準(zhǔn)差

對(duì)于算法的效率，與傳統(tǒng)遺傳算法相比較可以從兩方面來討論。1) 距離計(jì)算方面，NSGA-Ⅱ時(shí)間復(fù)雜度為O(mNlogN)；SPEA2計(jì)算復(fù)雜度為O(mN2logN)；由于沒有距離計(jì)算機(jī)制，因此HSS-MOEA與HMODE的時(shí)間復(fù)雜度為O(0)。2) 在適應(yīng)度計(jì)算方面，HSS-MOEA與HMODE采用基于支配關(guān)系的混合采樣，需要進(jìn)行PDDR-FF值的計(jì)算。對(duì)于種群中m個(gè)目標(biāo)，N個(gè)個(gè)體的PDDR-FF值的計(jì)算，總的比較次數(shù)可以按照下式計(jì)算：

m(N-1)+m(N-2)+…+m×2+m×1=mN(N-1)/2

(10)

因此，需要進(jìn)行mN(N-1)/2次比較來計(jì)算PDDR-FF的值，HSS-MOEA的時(shí)間復(fù)雜度為O(mN2)；NSGA-Ⅱ與SPEA2時(shí)間復(fù)雜度同樣為O(mN2)。由于HMODE引入DE計(jì)算，對(duì)每代精英種群進(jìn)行優(yōu)化處理，假設(shè)精英種群大小也為N，染色體長(zhǎng)度為C。首先進(jìn)行PDDR-FF排序，時(shí)間復(fù)雜度為O(mN2)。更新精英解集的最差時(shí)間復(fù)雜度為O(NC)。則HSS-MOEA的時(shí)間按復(fù)雜度為O(mN2)+O(mN2)+O(NC)。綜上所述，HSS-MOEA的運(yùn)算速度要比NSGA-Ⅱ與SPEA2快，HMODE比HSS-MOEA要慢，隨著實(shí)際問題規(guī)模的增大，染色體長(zhǎng)度C越大。與傳統(tǒng)遺傳算法相比時(shí)間復(fù)雜度上優(yōu)勢(shì)不明顯，但收斂性與分布性上則進(jìn)一步提高。以FSP01(20×5)為例，HSS-MOEA時(shí)間消耗的均值有標(biāo)準(zhǔn)差為：1.49e+011.6e+01，HMODE則為4.89e+021.9e+01。

4 結(jié) 語(yǔ)

在本文中，為解決最大完工時(shí)間和最小化最大拖期雙目標(biāo)流水車間調(diào)度問題，一種結(jié)合差分進(jìn)化策略與混合采樣策略的多目標(biāo)優(yōu)化算法HMODE被提出?；旌喜蓸硬呗詫?duì)依據(jù)種群個(gè)體的函數(shù)值與支配關(guān)系在Pareto前沿面進(jìn)行排序與區(qū)域劃分，融合差分進(jìn)化思想，引導(dǎo)每一代的進(jìn)化方向。此外，DE操作對(duì)精英解集的處理，使得解在收斂到真正的Pareto前沿面的能力更大。數(shù)值比較表明，HMODE在收斂性和分布性上優(yōu)于HSS-MOEA。

[1] 王萬良. 生產(chǎn)調(diào)度智能算法及其應(yīng)用[M]. 科學(xué)出版社, 2007.

[2] Johnson S M.Optimal two- and three-stage production schedules with setup times included[J].Naval Research Logistics Quarterly,1954,1(1):61- 68.

[3] Wang S, Liu M, Chu C. A branch-and-sbound algorithm for two-stage no-wait hybrid flow-shop scheduling[J]. International Journal of Production Research, 2015, 53(4):1143- 1167.

[4] Bouzidi A, Riffi M E, Barkatou M. A comparative study of four metaheuristics applied for solving the flow-shop scheduling problem[C]// World Congress on Information and Communication Technologies. IEEE, 2015:140- 145.

[5] Gao K, Pan Q, Suganthan P N, et al. Effective heuristics for the no-wait flow shop scheduling problem with total flow time minimization[J]. International Journal of Advanced Manufacturing Technology, 2013, 66(9- 12):1563- 1572.

[6] 楊開兵, 劉曉冰. 無成組技術(shù)條件下流水車間調(diào)度的多目標(biāo)優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2009, 15(2):348- 355.

[7] 何啟巍, 張國(guó)軍, 朱海平,等. 一種多目標(biāo)置換流水車間調(diào)度問題的優(yōu)化算法[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用, 2013, 22(9):111- 118.

[8] 陳可嘉, 周曉敏. 多目標(biāo)置換流水車間調(diào)度的改進(jìn)食物鏈算法[J]. 中國(guó)機(jī)械工程, 2015, 26(3): 348- 353,360.

[9] Storn R,Price K.Differential Evolution—A Simple and Efficient Heuristic for global Optimization over Continuous Spaces[J].Journal of Global Optimization, 1997, 11(4):341- 359.

[10] Shao W,Pi D.A self-guided differential evolution with neighborhood search for permutation flow shop scheduling[J]. Expert Systems with Applications, 2016, 51:161- 176.

[11] 劉紅平,黎福海. 面向多目標(biāo)優(yōu)化問題的自適應(yīng)差分進(jìn)化算法[J]. 計(jì)算機(jī)應(yīng)用與軟件,2015,32(12):249- 252,269.

[12] Yi W,Gao L,Zhou Y,et al.Differential evolution algorithm with variable neighborhood search for hybrid flow shop scheduling problem[C]// IEEE,International Conference on Computer Supported Cooperative Work in Design.IEEE, 2016:233- 238.

[13] 張曉霞, 呂云虹. 一種求解混合零空閑置換流水車間調(diào)度禁忌分布估計(jì)算法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2017, 34(1):270- 274.

[14] Schaffer J D. Multiple Objective Optimization with Vector Evaluated Genetic Algorithms[C]// International Conference on Genetic Algorithms. L. Erlbaum Associates Inc. 1985:93- 100.

[15] Zhang W,Gen M,Jo J.Hybrid sampling strategy-based multiobjective evolutionary algorithm for process planning and scheduling problem[J]. Journal of Intelligent Manufacturing, 2014, 25(5):881- 897.

[16] 張聞強(qiáng), 盧佳明, 張紅梅. 流水車間調(diào)度問題的快速多目標(biāo)混合進(jìn)化算法[J]. 計(jì)算機(jī)應(yīng)用, 2016, 36(4):1015- 1021.

[17] Taillard E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2):278- 285.