采用改進(jìn)兩點(diǎn)交叉算子的改進(jìn)自適應(yīng)遺傳算法求解不相關(guān)并行機(jī)混合流水車(chē)間調(diào)度問(wèn)題

鄭 堃 練志偉 顧新艷 朱長(zhǎng)建 徐 慧 馮雪晴

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

0 引言

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

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

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

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

１ 混合流水車(chē)間調(diào)度問(wèn)題

1.1 符號(hào)說(shuō)明

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

1.2 問(wèn)題描述

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

圖1 HFSP-UPM示意圖

1.3 模型建立

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

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)分別為任意工件選擇機(jī)器和加工順序的變量約束;式(5)表示任意工件在任意階段只能選擇一臺(tái)加工機(jī)器進(jìn)行加工;式(6)表示任意工件只有完成上一階段的加工任務(wù)后才能開(kāi)始下一階段的加工任務(wù);式(7)、式(8)表示一臺(tái)機(jī)器在某一時(shí)刻只可加工一個(gè)工件。

2 應(yīng)用ITPX的IAGA

2.1 ITPX-IAGA流程

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

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

(2)生成初始種群;

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

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

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

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

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

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

自適應(yīng)交叉概率[13]:

Pc=

(9)

自適應(yīng)變異概率[13]

Pm=

(10)

自適應(yīng)選擇概率[14]

Po=

(11)

2.3 應(yīng)用ITPX-IAGA求解HFSP-UPM

2.3.1染色體編碼

U=(U1,U2,…,Un)表示工件集在第一階段的加工順序,U的元素為工件號(hào),如U=(1,4,3,5,2)對(duì)應(yīng)工件的加工順序?yàn)镴1→J4→J3→J5→J2。

2.3.2染色體解碼

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

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

2.3.3初始化方法

本文采用的反向?qū)W習(xí)法(opposition-based learning, OBL)[16]設(shè)工件號(hào)為1、2、…、n,若某加序的編碼為Ui,則Ui的反向?qū)W習(xí)編碼為

U′i=1+n-Ui

(12)

因此本文的初始化過(guò)程如下:

(1)設(shè)置初始種群個(gè)體數(shù)為N,生成初始種群P1。按式(12)對(duì)種群P1中的所有染色體進(jìn)行反向?qū)W習(xí),生成初始種群P2。

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

2.3.4適應(yīng)度函數(shù)

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

2.3.5選擇操作

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

2.3.6交叉操作

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

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

圖3 TPX算子

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

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

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

圖6 TPX算子的精確交叉取點(diǎn)方式

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

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

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

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

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

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

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

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

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

(3)更新策略。①染色體池有剩余容量時(shí),將種群個(gè)體與染色體池中最劣個(gè)體比較,若優(yōu)于最劣個(gè)體且染色體池?zé)o此適應(yīng)度的個(gè)體,則將此種群個(gè)體放入染色體池,否則計(jì)算兩者的H,若H=0,則不填充,否則填充;② 當(dāng)染色體池沒(méi)有剩余容量且滿(mǎn)足①中的填充要求時(shí),則替換優(yōu)質(zhì)染色體池中的最劣個(gè)體。

2.3.8變異操作

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

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

2.3.9算法復(fù)雜性分析

(13)

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

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

(14)

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

3 試驗(yàn)仿真與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

表2 實(shí)例測(cè)試集

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

(15)

(16)

(17)

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

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

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

ITPX與TPX的對(duì)比實(shí)驗(yàn)(實(shí)驗(yàn)1)。對(duì)比GA采用ITPX和TPX得到解的質(zhì)量。實(shí)驗(yàn)選擇實(shí)例5進(jìn)行測(cè)試,因?yàn)樽儺愃阕訒?huì)提高算法性能、增強(qiáng)交叉算子對(duì)算法性能的影響,故將ITPX對(duì)比實(shí)驗(yàn)分為不帶變異的ITPX比較實(shí)驗(yàn)和帶變異的ITPX比較實(shí)驗(yàn),前者注重ITPX本身的開(kāi)發(fā)性能,后者側(cè)重在變異算子下ITPX的探索性能。相關(guān)實(shí)驗(yàn)參數(shù)如表4所示,每次實(shí)驗(yàn)均獨(dú)立運(yùn)行20次。

表4 ITPX比較實(shí)驗(yàn)參數(shù)

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

表5 自適應(yīng)選擇概率比較實(shí)驗(yàn)參數(shù)

表6 ITPX-IAGA實(shí)驗(yàn)參數(shù)

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

3.2 ITPX與TPX的對(duì)比實(shí)驗(yàn)

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

表7 不帶變異的ITPX比較實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

表8 帶變異的ITPX比較實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

表9 ITPX的相對(duì)誤差

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

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

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

3.3 基于激素調(diào)節(jié)的自適應(yīng)選擇概率對(duì)比實(shí)驗(yàn)

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

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

表10 Po,top=0.90的對(duì)比實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

表11 Po,down=0.44的對(duì)比實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

表12 自適應(yīng)選擇概率相對(duì)誤差

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

圖9 Po,top =0.9與Po下的平均適應(yīng)度收斂曲線圖

圖10 Po,down=0.44與Po下的平均適應(yīng)度收斂曲線

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

3.4 ITPX-IAGA實(shí)驗(yàn)

3.4.1工程實(shí)例測(cè)試

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

表13 基于實(shí)例1的算法結(jié)果的誤差

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

表14 基于實(shí)例2的算法結(jié)果誤差

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

表15 基于實(shí)例3的算法結(jié)果誤差

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

表16 基于實(shí)例4的算法結(jié)果誤差

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

表17 基于實(shí)例5的算法結(jié)果誤差

由表13可以發(fā)現(xiàn),GA、DE和IDE均無(wú)法找到已知最優(yōu)解,ABC和FOA在δARE和δWRE的誤差均不為0,ITPX-IAGA的各種誤差指標(biāo)均為0,算法性能最優(yōu)。表14中,GA和EDA均無(wú)法找到已知最優(yōu)解,GSA在δBRE和δWRE的誤差均不為0,ITPX-IAGA在10次實(shí)驗(yàn)中均找到已知最優(yōu)解。表15中,PBIL和IEDA均無(wú)法找到最優(yōu)解,而IDE、FOA和ITPX-IAGA均在10次實(shí)驗(yàn)中找到最優(yōu)解。如表16所示,DE無(wú)法找到已知最優(yōu)解,IEDA、IDE和FOA雖然可以找到已知最優(yōu)解,但δARE和δWRE的誤差均不為0,ABC和ITPX-IAGA在10次實(shí)驗(yàn)中均可找到最優(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,可見(jiàn)ITPX-IAGA平均收斂性較好,其在求解較大規(guī)模的HFSP-UPM上具有很大優(yōu)勢(shì)。

3.4.2隨機(jī)算例測(cè)試

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

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

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

PXY=(Y-X)/Y

(18)

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

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

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

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

4 結(jié)論

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

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