鄭 堃 練志偉 顧新艷 朱長建 徐 慧 馮雪晴

1.南京工程學院汽車與軌道交通學院,南京,2111672.中德智能制造研究院,南京,211800 3.大全集團有限公司,鎮(zhèn)江,212211

0 引言

混合流水車間調(diào)度問題[1](hybrid flow-shop scheduling problem, HFSP)拓展了經(jīng)典流水車間調(diào)度問題,具有很高的研究價值和廣闊的應用前景。在以最大完工時間最小化為目標的情況下,HFSP一般指的是已知各工件加工時間,確定各工件的加工順序以及各階段上工件被優(yōu)化分配機器的情況,是一個典型的NP-Hard問題。HFSP被分為三種類型:相同并行機、均勻并行機和不相關并行機[2],其中,不相關并行機混合流水車間調(diào)度問題(hybrid flow-shop scheduling problem with unrelated parallel machine, HFSP-UPM)指某個加工階段的加工時間取決于加工工件與加工機器的匹配程度,因問題模型應用更為廣泛,而受到學者越來越多的關注。

目前求解HFSP-UPM以元啟發(fā)式方法為主,通過借鑒自然界的規(guī)律,可以很好地求解調(diào)度問題,常用的算法有遺傳算法(genetic algorithm, GA)[3]、基于激素調(diào)節(jié)機制的改進粒子群優(yōu)化(particle swarm optimization, PSO)算法[4]、變鄰域搜索混合的果蠅優(yōu)化算法(fruit fly optimization algorithm, FOA)[5]、人工蜂群(artificial bee colony, ABC)算法[6]、分布估計算法(estimation of distribution algorithm, EDA)[7]、離散化的蜻蜓算法(dragonfly algorithm, DA)[8]等。GA應用廣泛,但自身算子設計限制及參數(shù)選擇影響了應用效果。從元啟發(fā)式方法的研究現(xiàn)狀來看,算法混合是提高求解性能的必要手段。薛玲玲[9]在GA的基礎上混合塊結構的鄰域搜索,以突出GA的局部開發(fā)優(yōu)勢,解決GA早熟等問題。吳樹景等[10]將GA、變鄰域搜索方法與精英保護策略結合,提出運算效率和求解性能均佳的混合算法。軒華等[11]結合NEH啟發(fā)式方法、局域搜索和GA的結構優(yōu)勢來提高混合GA求解的質(zhì)量。雖然混合算法能提高求解的性能,但會導致算法的復雜度高和擴展性低,因此算法自身的優(yōu)化成為當前的熱點研究方向[12]。

針對GA自身算子參數(shù)選擇困難等缺陷,王雷等[13]受人體系統(tǒng)中激素調(diào)節(jié)規(guī)律的啟發(fā),將激素調(diào)節(jié)機制應用至GA的交叉和變異參數(shù)設計中,提出了基于激素調(diào)節(jié)機制的改進型自適應遺傳算法(improved adaptive genetic algorithm, IAGA),通過激素調(diào)節(jié)的自適應參數(shù),使得算法在中后期具備較強的精細化搜索能力,從而提高算法的收斂性能。文獻[4]將激素調(diào)節(jié)機制應用至PSO的慣性因子w,實驗表明激素調(diào)節(jié)機制可增強算法的求解效率。文獻[14]針對激素調(diào)節(jié)規(guī)律在目標函數(shù)較大時出現(xiàn)失調(diào)的現(xiàn)象進行深入研究,提出激素調(diào)節(jié)的選擇概率及改進兩點交叉算子(improved two-points crossover, ITPX),并通過標準算例驗證了所提算法的綜合性能。激素調(diào)節(jié)機制和ITPX可有效提高算法性能,但激素調(diào)節(jié)選擇概率與ITPX的性能對算法有何種影響尚未進行深入研究,結合激素調(diào)節(jié)機制進一步增強ITPX和算法的收斂性也需進一步深入分析。

本文在前述研究基礎上,提出基于改進兩點交叉算子的改進自適應遺傳算法(ITPX-IAGA),并將該算法應用于復雜的HFSP-UPM。本文具體工作如下:①闡述了ITPX的理論,細化ITPX的發(fā)展過程及依賴性,從解的質(zhì)量和時間的消耗兩個不同維度對其性能進行定性和定量分析;通過實驗論證了ITPX解決傳統(tǒng)TPX缺陷的效果及其在算法中后期的探索與開發(fā)能力;②利用工程算例驗證了基于激素調(diào)節(jié)機制的自適應選擇概率,論證其對算法收斂性的影響。

１ 混合流水車間調(diào)度問題

1.1 符號說明

為更好描述HFSP-UPM,給出了符號及其釋義,如表1所示。

1.2 問題描述

HFSP-UPM描述如下:n個相互獨立工件{J1,J2,…,Jn}需經(jīng)過s個加工階段,每個階段有mk臺加工機器{M1,M2,…,Mmk}可供選擇,每個工件在每個階段的加工時間可能不同;調(diào)度目標為優(yōu)化工件在每個階段加工機器的選擇以及在機器上的加工順序,使得所有工件的最大完工時間Cmax最小,圖1為該問題的示意圖,并做出如下約束:①初始時刻,所有工件和加工機器準備就緒;②流水線具有固定的順序,所有工件需以相同的順序經(jīng)過每個加工階段;③每個階段至少存在一臺加工機器,并且至少有一個階段存在多臺加工機器;④一個工件在每階段不同機器上的加工時間可有所不同;⑤工件在每個階段只可選擇一臺機器進行加工;⑥任意時刻一臺機器只可加工一個工件;⑦機器一旦開始加工,就不能中斷。

圖1 HFSP-UPM示意圖

1.3 模型建立

HFSP-UPM的數(shù)學模型如下:

Cmax=min(max{C(k,i)|i=1,2,…,n;

k=1,2,…,s})

(1)

(2)

(3)

C(k,i)=S(k,i)+P(k,j,i)

(4)

(5)

S(k+1,i)-S(k,i)≥P(k,j,i)

(6)

Yki1i2+Yki2i1≤1

(7)

S(k,i1)-C(i2,k)+L(3-Yki2i1-Xi1kj-Xi2kj)≥0

(8)

i=1,2,…,ni1≠i2

k=1,2,…,sj=1,2,…,mk

式中,L為足夠大的常數(shù)。

式(2)、式(3)分別為任意工件選擇機器和加工順序的變量約束;式(5)表示任意工件在任意階段只能選擇一臺加工機器進行加工;式(6)表示任意工件只有完成上一階段的加工任務后才能開始下一階段的加工任務;式(7)、式(8)表示一臺機器在某一時刻只可加工一個工件。

2 應用ITPX的IAGA

2.1 ITPX-IAGA流程

ITPX-IAGA流程如圖2所示,具體過程如下:

(1)設計算法參數(shù);

(2)生成初始種群;

(3)計算自適應參數(shù)(自適應選擇概率Po、自適應交叉概率Pc、自適應變異概率Pm)和初始化或更新染色體池,若滿足最大迭代次數(shù),則輸出記憶因子攜帶的信息,并且退出運行,否則轉至步驟(4);

(4)執(zhí)行ITPX交叉流程,若隨機概率P

(5)執(zhí)行變異流程,若P

(6)迭代新種群,并跳轉步驟(3)。

2.2 激素調(diào)節(jié)規(guī)律在GA參數(shù)中的應用

受內(nèi)分泌激素基本規(guī)律[15]的啟發(fā),文獻[13-14]設計了與種群優(yōu)劣程度相關的自適應選擇概率、交叉概率和變異概率因子函數(shù),具體如下。

自適應交叉概率[13]:

Pc=

(9)

自適應變異概率[13]

Pm=

(10)

自適應選擇概率[14]

Po=

(11)

2.3 應用ITPX-IAGA求解HFSP-UPM

2.3.1染色體編碼

U=(U1,U2,…,Un)表示工件集在第一階段的加工順序,U的元素為工件號,如U=(1,4,3,5,2)對應工件的加工順序為J1→J4→J3→J5→J2。

2.3.2染色體解碼

HFSP解碼分為工件排序和機器分配,工件排序方式為先到先處理。第一個加工階段,工件按照染色體編碼順序安排加工;其他加工階段,按照工件到達該階段的順序安排加工機器,若到達順序相同則隨機排序。

機器分配方式如下:比較工件i在此階段上機器j的釋放時間rj和工件i上一階段的完工時間C(k-1,i),取最大值為工件i在機器j上的最早開始加工時間aj即aj=max(rj,C(k-1,i)),計算工件i在此階段每個可選機器上的值{aj+P(k,j,i)},選取其中具有min{aj+P(k,j,i)}的機器作為工件i在此階段的加工機器,若有最小值相同的機器,則隨機選擇。

2.3.3初始化方法

本文采用的反向學習法(opposition-based learning, OBL)[16]設工件號為1、2、…、n,若某加序的編碼為Ui,則Ui的反向學習編碼為

U′i=1+n-Ui

(12)

因此本文的初始化過程如下:

(1)設置初始種群個體數(shù)為N,生成初始種群P1。按式(12)對種群P1中的所有染色體進行反向學習,生成初始種群P2。

(2)合并種群P1和P2,按照目標函數(shù)值從小到大的順序進行排序,然后選取合并種群中的前N個染色體作為初始種群。

2.3.4適應度函數(shù)

本文適應度的計算方法分為兩個部分:①將染色體解碼的目標函數(shù)值Makespan作為該染色體的適應度,即f1=min{Cmax(U)},此方法用于比較個體之間的優(yōu)劣,f1越小代表該染色體的適應能力越強;②計算自適應選擇概率、交叉概率和變異概率時,種群中染色體的適應度f2=1/min{Cmax(U)}[13-14],以保證激素調(diào)節(jié)規(guī)律在GA中的應用效果。

2.3.5選擇操作

GA的選擇算子通過篩選種群進化過程中的個體來影響種群的進化結果。在種群進化前期,選擇算子使高性能個體以更大的概率生存,有利于種群向優(yōu)質(zhì)個體區(qū)域快速收斂;在種群進化后期,控制高性能個體的遺傳有利于保持種群多樣性。基于激素調(diào)節(jié)的選擇概率可滿足GA迭代中的需求,進一步提高算法的收斂性能。本文采用GOLDBERG等[17]提出的錦標賽選擇方法,并設置由激素調(diào)節(jié)的選擇概率Po,隨機從種群中選出若干個體,并標記其中具有最小f1(最優(yōu))和最大f1(最劣)的個體;若隨機概率P

2.3.6交叉操作

交叉是GA全局優(yōu)化的主要手段,通過對2個匹配父代基因的重新組合高效搜索解空間,因此對GA的優(yōu)化性能有巨大影響。匹配機制及父代之間的交叉操作存在諸多問題,如匹配的父代是同一染色體、交叉重新組合的基因具有一致性等問題,這使得GA易出現(xiàn)全局收斂慢、解的質(zhì)量不理想或局部收斂等現(xiàn)象。

排列編碼方式通常采用兩點交叉算子(two-points crossover, TPX)[14,18]產(chǎn)生子代,如圖3所示。TPX產(chǎn)生的子代性能與交叉點的選取關系緊密。選取交叉點的結果如圖4所示時,子代個體與父代相同,因此隨機取點的方式會導致重組基因一致,使TPX存在冗余度高、效率低和無法高效搜索解空間等缺陷。因此,如何取點讓TPX產(chǎn)生有效子代成為提高算法性能的重要途徑之一。研究發(fā)現(xiàn),TPX的交叉點在選取時,必須包含2條父代基因中的差異位且不能囊括所有差異位的基因(2條父代在等位比較下不同的基因)或兩端差異位中任意相鄰的基因,這樣才能產(chǎn)生有效子代。如圖5所示,交叉點包含所有差異位的基因或右端的差異位基因相鄰的基因,使得父代與子代一致。因此,匹配父代是同一或相似染色體時,ITPX不產(chǎn)生任何無效子代,從而提高算法效率。

圖3 TPX算子

圖5 TPX產(chǎn)生子代與父代相同的取點方式

根據(jù)上述ITPX取點的要求,設2個交叉點n1和n2(n1為左交叉點,n2為右交叉點)。產(chǎn)生有效子代的具體實現(xiàn)方法如下:

(1)如圖6所示,從首端開始比對2條父代之間的基因,并標記差異位的基因,直至末端結束,其中,首端基因位為n1必取的點,末端基因位為n2必取的點。以n1進行中心取點時,n1的可取點只能是差異位基因區(qū)域中的點,此時固定n1的取點,則對應的n2根據(jù)ITPX產(chǎn)生有效子代的要求進行取點;同理可得以n2為中心的取點方式。

圖6 TPX算子的精確交叉取點方式

(2)首先以n1為中心進行取點,n1可取G1、G2和G3。n2根據(jù)圖5中的約束進行取點,即n2取點不能使重組基因囊括所有差異位的基因或兩端差異位中任意相鄰的基因,因此n2右端點為G5。n2左端點由當前n1及當前n1從左向右的相鄰點是否均屬于差異位的基因區(qū)域來決定。如圖6所示,當前的n1(G1)及當前的n1(G1)從左向右的相鄰點(G2)均屬于差異位的基因區(qū)域時,將當前的n1(G1)作為n2的左端點;同理,當前的n1(G2)可作為n2的左端點,而當前的n1(G3)不作為n2的左端點時,n2左端點為當前的n1(G3)從左向右的相鄰點(G4)。對應n2的取點按照父代從左向右的順序,由n2左端點開始至右端點處結束。

(3)以n2為中心進行取點,除去步驟(2)中n1取過的點(G1、G2和G3)外,n2可取G7。n1則根據(jù)圖5中的約束進行取點,即與步驟(2)中n2可取點的機制類似,因此n1左端點為G3。n1的右端點由當前的n2及當前的n2從右向左的相鄰點是否均屬于差異位的基因區(qū)域來決定。同樣地,從圖6可以發(fā)現(xiàn),當前的n2(G7)屬于差異位的基因區(qū)域,但當前的n2(G7)從右向左的相鄰點(G6)卻不屬于差異位的基因區(qū)域,所以當前的n2(G7)不作為n1的右端點,則n1的右端點為當前的n2(G7)從右向左的相鄰點(G6)。對應n1的取點按照父代從右向左的順序,由n1右端點開始依此遞進至n1左端點處結束。

綜上,本文改進現(xiàn)有TPX的取點方式,進而設計出精確取點的ITPX,通過盡可能地產(chǎn)生2父代的全部有效子代,然后從各自子代集選取性能最優(yōu)的進入下一次迭代,并利用記憶因子實時監(jiān)測這一過程,避免最優(yōu)染色體的丟失。除此之外,建立優(yōu)質(zhì)染色體池,實現(xiàn)與種群不同區(qū)域的交叉:①2條父代染色體分別從優(yōu)質(zhì)染色體池中隨機選取和從種群中按選擇操作選取,然后以Pc概率交叉;②2條父代染色體均按選擇操作從種群中選取并以1-Pc概率交叉。

2條染色體等位比對不同基因的個數(shù)稱為海明距離H。不同基因數(shù)越多,相似度越低,H越大,因此ITPX只有在2條父代相似度較低時,即H較大才具有很強的全局搜索能力,所以在種群進化的后期保持種群多樣性十分重要。

2.3.7優(yōu)質(zhì)染色體池

本文在交叉算子中引入優(yōu)質(zhì)染色體池并利用記憶因子記錄種群迭代中出現(xiàn)的優(yōu)質(zhì)解,保證優(yōu)質(zhì)解的遺傳。優(yōu)質(zhì)染色體池構成如下:

(1)記憶因子。記錄交叉算子中所有父代產(chǎn)出的子代和變異算子中特定的擾動,若有優(yōu)于記憶因子攜帶的染色體,則更新記憶因子。

(2)初始化。設優(yōu)質(zhì)染色體池容量為NP。染色體池前NP/2的容量由初始化種群按照適應度從小到大的排序進行填充,剩余容量按更新策略填充;記憶因子標記其中性能最優(yōu)的染色體。

在心肌梗塞患者治療期間,按照相關要求測量患者的血脂和血糖指標,定期監(jiān)測患者的血壓和心電圖的變化。吸煙的判定標準為現(xiàn)在吸煙,并且吸煙史在超過3年,每天吸煙超過20支,原發(fā)性高血壓和糖尿病的判定標準為WHO公布的診斷標準,血脂異常的判定標準參照防治建議[1]。

(3)更新策略。①染色體池有剩余容量時,將種群個體與染色體池中最劣個體比較,若優(yōu)于最劣個體且染色體池無此適應度的個體,則將此種群個體放入染色體池,否則計算兩者的H,若H=0,則不填充,否則填充;② 當染色體池沒有剩余容量且滿足①中的填充要求時,則替換優(yōu)質(zhì)染色體池中的最劣個體。

2.3.8變異操作

擾動操作:①打亂互換,隨機選擇染色體的不同基因,然后打亂,重新組織;②插入,隨機將染色體中的一個基因插入到另一個基因的左側;③反轉逆序,隨機反轉逆序2個不同基因之間所有基因;④兩點互換,隨機選擇染色體的2個不同基因,并互換。

變異:取隨機整數(shù)r∈{0,1,2,3},若r=0,則執(zhí)行擾動①;若r=1,則執(zhí)行擾動②;若r=2,則執(zhí)行擾動③;若r=3,連續(xù)執(zhí)行擾動④n次,并利用記憶因子監(jiān)測此過程。

2.3.9算法復雜性分析

(13)

其中,Ev1是以n1為中心取點時n1可取點的數(shù)量;L1d為當前的n1取點時n2可取的左端點基因位置,d=1,2,…,Ev1;Lright為2條父代右端不同的基因位置。

ITPX交叉點以n2為中心時,2條父代的取點次數(shù)為

(14)

其中,Ev2是以n2為中心取點時n2可取點的數(shù)量;L2d為當前的n2取點時n1可取的右端點基因位置,d=1,2,…,Ev2;Lleft為2條父代左端不同的基因位置。

3 試驗仿真與結果分析

3.1 實驗設計

為驗證本文算法性能,使用文獻[7-8,20]中的5個工程實例進行測試,如表2所示,其中,實例1有12個工件、3階段(規(guī)模12×3)。建立18個中大規(guī)模的隨機算例(參數(shù)見表3)進行測試。使用最佳相對誤差δBRE、平均相對誤差δARE和最差相對誤差δWRE評價本文算法結果:

表2 實例測試集

表3 隨機算例的參數(shù)設置

(15)

(16)

(17)

式中,LB為問題已知的最優(yōu)值;Cbest、Cavg、Cworst分別為算法在規(guī)定次數(shù)內(nèi)求解算例得到的最優(yōu)值、平均值和最差值。

誤差越小表示該算法的性能越好。

改進的遺傳算法采用DEV C++編程,程序在Intel Core 主頻2.3GHZ、內(nèi)存8GB的PC上運行。為驗證本文所提算法的性能,將開展以下實驗:

ITPX與TPX的對比實驗(實驗1)。對比GA采用ITPX和TPX得到解的質(zhì)量。實驗選擇實例5進行測試,因為變異算子會提高算法性能、增強交叉算子對算法性能的影響,故將ITPX對比實驗分為不帶變異的ITPX比較實驗和帶變異的ITPX比較實驗,前者注重ITPX本身的開發(fā)性能,后者側重在變異算子下ITPX的探索性能。相關實驗參數(shù)如表4所示,每次實驗均獨立運行20次。

表4 ITPX比較實驗參數(shù)

基于激素調(diào)節(jié)的自適應選擇概率對比實驗(實驗2)。由于自適應交叉概率和變異概率已在文獻[13-14]中驗證,因此本文只對自適應選擇概率Po進行對比測試,對比GA采用自適應Po和固定值Po得到解的質(zhì)量。為客觀評價自適應選擇概率對整體算法性能的提升提供依據(jù)。實驗選擇實例5進行測試,實驗參數(shù)如表5所示,自適應Po的參數(shù)如表6所示,每次實驗均獨立運行20次。

表5 自適應選擇概率比較實驗參數(shù)

表6 ITPX-IAGA實驗參數(shù)

ITPX-IAGA對比實驗(實驗3)。利用5個工程實例比較ITPX-IAGA與其他幾種算法,每次實驗均獨立運行10次。利用18個中大規(guī)模隨機算例比較ITPX-IAGA與TPX-IAGA,每次實驗均獨立運行20次。為客觀評價ITPX-IAGA性能,選擇表6所示的實驗參數(shù)。

3.2 ITPX與TPX的對比實驗

為驗證ITPX對算法性能的影響,對ITPX進行了不帶變異和帶變異的比較實驗(ITPX和TPX采用同一初始種群)。由2.3.9節(jié)可知,在GA的進化過程下,TPX的總交叉次數(shù)遠多于ITPX的總交叉次數(shù)。比較實驗的統(tǒng)計結果如表7～表9所示。表7、表8中,tI為ITPX的運行時間,t為TPX的運行時間;表9中,tav為20次實驗獨立運行的平均時間。由表7可發(fā)現(xiàn),ITPX、TPX能找到的最優(yōu)解分別為111和114;在20次實驗中,ITPX、TPX的平均值分別為115.75和116.10;在運行時間上,90%以上的tI小于t。由表8可發(fā)現(xiàn),ITPX、TPX的最優(yōu)解均為112,但ITPX和TPX求得最優(yōu)解112的概率分別為25%和5%;在20次實驗中,ITPX、TPX的平均值分別為113.5和114.1;運行時間上,tI均小于t。由表9可發(fā)現(xiàn),不帶變異ITPX與帶變異ITPX的δARE差值為2.4,不帶變異的TPX與帶變異的TPX的δARE差值為1.8;ITPX的平均運行時間均遠小于TPX的平均運行時間,因此可見,與TPX相比,ITPX對解的探索與開發(fā)效率更高,在變異的作用下,ITPX的求解性能更優(yōu)。

表7 不帶變異的ITPX比較實驗統(tǒng)計結果

表8 帶變異的ITPX比較實驗統(tǒng)計結果

表9 ITPX的相對誤差

由圖7、圖8可以發(fā)現(xiàn),ITPX整體的收斂性均優(yōu)于TPX,因此ITPX能有效提高算法求解的效率。

圖7 不帶變異的ITPX與TPX平均適度收斂曲線圖

圖8 帶變異的ITPX與TPX平均適度收斂曲線圖

3.3 基于激素調(diào)節(jié)的自適應選擇概率對比實驗

由文獻[13-14]可知式(9)～式(11)中的fav為激素濃度,fmax-fmin為閾值。種群迭代初始階段中,激素濃度、閾值、激素濃度與閾值的比值產(chǎn)生較大變化將導致自適應參數(shù)波動;種群迭代中后期內(nèi),種群趨于收斂使得自適應參數(shù)波動的需求減小。因此,在種群初期,自適應參數(shù)Po具有不固定上限;在種群中后期,自適應參數(shù)Po具固定下限特性。

對于實例5,Po不固定上限0.90左右,Po固定下限Po,dow為0.437 55。為驗證自適應選擇概率Po對算法性能的影響,分別取Po的上限Po,top=0.90、下限Po,down=0.44與Po進行對比實驗。對比實驗的統(tǒng)計結果如表10～表12所示。表10、表11中,X為自適應參數(shù)Po下算法得出的解,Y為Po,top或Po,down下算法得出的解,tX為X的運行時間,tY為Y的運行時間。在表12中,tav為20次實驗獨立運行的平均時間。由表10可以發(fā)現(xiàn),X、Y的最優(yōu)值分別為111和113;20次實驗中,X、Y的平均值分別為113.75和114.2。由表11可以發(fā)現(xiàn),X、Y的最優(yōu)值分別為112和111,但Y的最優(yōu)值111只出現(xiàn)1次(112出現(xiàn)4次),而X的最優(yōu)值112出現(xiàn)7次;20次實驗中,X、Y的平均值分別為113.15和113.65。由表12發(fā)現(xiàn),X的δARE均優(yōu)于Y;Po,top=0.90時,X的δARE小于Y,X的tav略大于Y;Po,down=0.44時,X的δARE小于Y,X的tav略小于Y。因此Po在運行時間上無明顯優(yōu)勢,但在求解的性能優(yōu)于Po,top或Po,down下的算法。

表10 Po,top=0.90的對比實驗統(tǒng)計結果

表11 Po,down=0.44的對比實驗統(tǒng)計結果

表12 自適應選擇概率相對誤差

由圖9、圖10可以發(fā)現(xiàn),不管是Po,top還是Po,down,自適應Po下解的收斂性都要更優(yōu),且收斂也較快。由圖11可以發(fā)現(xiàn),自適應Po的上限具有微小的波動,直到收斂于穩(wěn)定下限0.437 55。Po的對比實驗證明自適應參數(shù)Po能有效提高算法的搜索質(zhì)量。

圖9 Po,top =0.9與Po下的平均適應度收斂曲線圖

圖10 Po,down=0.44與Po下的平均適應度收斂曲線

圖11 平均自適應參數(shù)Po變化曲線(Po,top=0.9,Po,down=0.44)

3.4 ITPX-IAGA實驗

3.4.1工程實例測試

對于實例1,將ITPX-IAGA與ABC[6]、FOA[20]、GA[21]、差分進化(differential evolutionary, DE)算法[22]和改進差分進化(improved differential evolutionary, IDE)算法[23]進行比較,其中,GA、DE、FOA和ABC的評價次數(shù)為10 000,IDE的評價次數(shù)為200。所有算法均獨立運行10次,實驗結果的誤差如表13所示。

表13 基于實例1的算法結果的誤差

對于實例2,將ITPX-IAGA與EDA[7]、GA[21]和引力搜索算法(gravitational search algorithm, GSA)[24]進行比較,其中,GA和EDA的評價次數(shù)為10 000,GSA的運行時間不超過10 s。所有算法均獨立運行10次,實驗結果的誤差如表14所示。

表14 基于實例2的算法結果誤差

對于實例3,將ITPX-IAGA與FOA[20]、種群增量學習(population-based incremental learning, PBIL)[23]、改進分布估計算法(improved estimation of distribution algorithm, IEDA)[23]和IDE[23]進行比較,其中,PBIL、IEDA和FOA的評價次數(shù)為3000,IDE的評價次數(shù)為200。所有算法均獨立運行10次,實驗結果的誤差如表15所示。

表15 基于實例3的算法結果誤差

對于實例4,將ITPX-IAGA與ABC[6]、DE[22]、IEDA[23]、IDE[23]和FOA[20]進行比較,其中,IEDA、DE、ABC和FOA的評價次數(shù)為18 000,IDE的評價次數(shù)為200。所有算法均獨立運行10次,實驗結果的誤差如表16所示。

表16 基于實例4的算法結果誤差

對于實例5,將ITPX-IAGA與GA[8]和DA[8]進行比較,其中,GA和DA的評價次數(shù)為300,且只有一次仿真結果,實驗結果的誤差如表17所示。

表17 基于實例5的算法結果誤差

由表13可以發(fā)現(xiàn),GA、DE和IDE均無法找到已知最優(yōu)解,ABC和FOA在δARE和δWRE的誤差均不為0,ITPX-IAGA的各種誤差指標均為0,算法性能最優(yōu)。表14中,GA和EDA均無法找到已知最優(yōu)解,GSA在δBRE和δWRE的誤差均不為0,ITPX-IAGA在10次實驗中均找到已知最優(yōu)解。表15中,PBIL和IEDA均無法找到最優(yōu)解,而IDE、FOA和ITPX-IAGA均在10次實驗中找到最優(yōu)解。如表16所示,DE無法找到已知最優(yōu)解,IEDA、IDE和FOA雖然可以找到已知最優(yōu)解,但δARE和δWRE的誤差均不為0,ABC和ITPX-IAGA在10次實驗中均可找到最優(yōu)解;比較可得ITPX-IAGA優(yōu)于ABC。表17中,GA、DA、ITPX-IAGA的δBRE分別為26.13、15.31和0;ITPX-IAGA的δWRE為2.70,優(yōu)于GA和DA的δBRE;ITPX-IAGA的δARE僅為1.26,可見ITPX-IAGA平均收斂性較好,其在求解較大規(guī)模的HFSP-UPM上具有很大優(yōu)勢。

3.4.2隨機算例測試

TPX-IAGA與ITPX-IAGA的區(qū)別只有交叉算子不同,且交叉算子均滿足2.3.9節(jié)的計算復雜度。實驗的比較結果如表18所示,其中,tav為20次實驗獨立運行的平均時間。由表18可以發(fā)現(xiàn),在Cbest的取值上,ITPX-IAGA可獲得15個較優(yōu)解,TPX-IAGA只獲得8個較優(yōu)解;在Cavg的取值上,ITPX-IAGA有17個較優(yōu)解,TPX-IAGA只有1個較優(yōu)解;在Cworst的取值上,ITPX-IAGA有14個較優(yōu)解,TPX-IAGA只有8個較優(yōu)解;在tav的取值,及各項指標的平均值(AVG),ITPX-IAGA的求解性能均優(yōu)于TPX-IAGA。

表18 中大規(guī)模隨機算例下算法的結果

為更好表明ITPX-IAGA對TPX-IAGA的優(yōu)勢,引入優(yōu)越度這一概念,其公式為

PXY=(Y-X)/Y

(18)

式中,PXY為變量X相較于變量Y的優(yōu)越度。

本文中,X、Y分別為ITPX-IAGA和TPX-IAGA相同指標的求解結果?；诟魉惴ǖ那蠼饨Y果和優(yōu)化時間等指標,計算相應的PXY,得出箱型圖(圖12、圖13),其中,AVG表示本圖中各指標(Cbest、Cavg、Cworst和tav)均值的優(yōu)越度。由圖12可知,ITPX-IAGA在4個解的性能指標上均有一定優(yōu)勢;由圖13可知,ITPX-IAGA在tav等指標上具有較大優(yōu)越性,其可縮短40%以上的優(yōu)化時間。由此可以得出,ITPX-IAGA可在節(jié)省大量優(yōu)化時間的基礎上,提高ITPX算法的優(yōu)化性能。綜上所述,ITPX-IAGA在解決HFSP-UPM上具有良好的優(yōu)化效果。

圖12 ITPX-IAGA解的優(yōu)越度箱型圖

圖13 ITPX-IAGA 平均優(yōu)化時間的優(yōu)越度箱型圖

4 結論

本文針對TPX隨機取點方式存在的不足,提出一種改進TPX,即利用ITPX的精確取點方式提高算法的搜索效率和中后期的開發(fā)能力。為提高GA的求解性能,將激素調(diào)節(jié)機制用于選擇算子,利用自適應的選擇概率增強GA的收斂能力;將IAGA與ITPX結合,提出一種基于ITPX的IAGA調(diào)度方法來求解不相關并行機的混合流水車間調(diào)度問題。ITPX和自適應選擇概率對比實驗證明了ITPX算子和基于激素調(diào)節(jié)的自適應選擇概率能有效提高算法的求解性能。工程實例和隨機算例驗證了ITPX-IAGA的有效性,證明了ITPX算法既能縮短40%以上優(yōu)化時間,又能提高算法的求解性能。ITPX與TPX的算法復雜性分析,以及ITPX-IAGA實驗結果說明,ITPX在單次取點時,ITPX-IAGA具有優(yōu)越性。

未來,ITPX-IAGA可以在以下方向上繼續(xù)深入研究:①基于強化學習,尋找最具潛在價值的異點區(qū)間,以進一步節(jié)省優(yōu)化時間,提高算法性能;②ITPX的應用范圍受限于解的編碼方式,因此結合其他形式的調(diào)度問題,分析ITPX在其他編碼方法中的切入點,有利于擴展ITPX的應用場景;③探索局部搜索方法或其他操作算子與ITPX的結合,進一步加快算法收斂,提高解的質(zhì)量。