成金海,徐 華

(江南大學(xué) 人工智能與計(jì)算機(jī)學(xué)院,江蘇 無(wú)錫 214122)

調(diào)度問(wèn)題是制造流程規(guī)劃和管理領(lǐng)域中一個(gè)重要問(wèn)題,其中作業(yè)車(chē)間調(diào)度問(wèn)題(Job-shop Scheduling Problem,JSP)是這個(gè)領(lǐng)域中最困難的問(wèn)題之一[1].FJSP是經(jīng)典JSP的拓展,FJSP存在多對(duì)多映射關(guān)系,工序可以由不同的機(jī)器加工,機(jī)器也可以加工不同的工序,是典型的非確定性多項(xiàng)式難(Non-deterministic Polynomial Hard,NP-hard)組合優(yōu)化問(wèn)題.在實(shí)際的車(chē)間優(yōu)化調(diào)度問(wèn)題中,多目標(biāo)柔性作業(yè)車(chē)間調(diào)度(Multi-Objective Flexible Job-shop Scheduling Problem,MOFJSP)是比單目標(biāo)FJSP更困難但更貼近車(chē)間實(shí)際生產(chǎn)環(huán)境的車(chē)間調(diào)度優(yōu)化問(wèn)題.

近年來(lái),MOFJSP受到廣泛關(guān)注,學(xué)術(shù)界產(chǎn)生了大量成果.其中,Zhang[2]等設(shè)計(jì)了兩層遺傳算法,使用新的交叉策略求解多目標(biāo)問(wèn)題,算法獲得了一定數(shù)量的非支配解,擁有較好的深度搜索和跳出局部最優(yōu)的能力.Dong[3]等設(shè)計(jì)了一種四食物源編碼方法,結(jié)合入侵腫瘤生長(zhǎng)優(yōu)化算法結(jié)構(gòu)和NSGA-Ⅲ中對(duì)解的篩選機(jī)制,提出一種收斂更快且解集分布更均勻的多目標(biāo)算法.Soto C[4]等設(shè)計(jì)一種并行分支定界法求解MOFJSP,實(shí)現(xiàn)15.64倍的時(shí)間加速比,提高搜索Pareto解集的效率.Wu[5]等提出一種改進(jìn)灰熵關(guān)聯(lián)度的適應(yīng)度值分配策略,設(shè)計(jì)一種基于正態(tài)云的狀態(tài)轉(zhuǎn)移模型,能夠有效提高精度和加快收斂速度.

人工蜂群算法(Artificial Bee Colony,ABC)是一個(gè)由蜂群行為啟發(fā)的算法,在2005年由Karaboga小組為優(yōu)化代數(shù)問(wèn)題而提出[6].在車(chē)間調(diào)度領(lǐng)域,Zhao[7]等人為克服單一算法在求解MOFJSP時(shí)在最優(yōu)性和多樣性方面產(chǎn)生的不足,提出一種多策略融合的人工蜂群算法,實(shí)現(xiàn)協(xié)同搜索,獲得全局和局部最優(yōu)的平衡.Zheng[8]等針對(duì)模糊FJSP設(shè)計(jì)一種基于鄰域搜索的改進(jìn)人工蜂群算法,采用四種鄰域結(jié)構(gòu)增加局部搜索能力,設(shè)計(jì)一種新穎的交叉方式加速種群的收斂,較好的解決了以最小化最大模糊完工時(shí)間為目標(biāo)的模糊柔性作業(yè)車(chē)間調(diào)度問(wèn)題.Li[9]等設(shè)計(jì)一種基于禁忌搜索的混合人工蜂群算法,在初始化階段使用基于聚類(lèi)分組的輪盤(pán)賭方法產(chǎn)生種群,有效的解決紡織行業(yè)的實(shí)際FJSP.

從現(xiàn)有文獻(xiàn)可以觀察到MOFJSP是當(dāng)前熱門(mén)的調(diào)度問(wèn)題,MOFJSP涉及組合優(yōu)化問(wèn)題,在組合優(yōu)化領(lǐng)域常用Pareto解集來(lái)表示一組優(yōu)化解.ABC算法作為啟發(fā)式算法,在組合優(yōu)化問(wèn)題方面有一定運(yùn)用.MOFJSP為獲得精度和速度的平衡,對(duì)于各單目標(biāo)的搜索水平有限,且多數(shù)算法是從優(yōu)化算法結(jié)構(gòu)、調(diào)整參數(shù)、改進(jìn)搜索策略等角度進(jìn)行優(yōu)化,在解決大規(guī)模問(wèn)題時(shí)仍存在局限.因此本文提出一種基于分支限界法思想的數(shù)據(jù)預(yù)處理方式來(lái)排除無(wú)效的搜索空間,多數(shù)文獻(xiàn)使用單一的進(jìn)化方式并不能體現(xiàn)個(gè)體差異,本文根據(jù)蜂群個(gè)體的差異性使用多種進(jìn)化策略,使用學(xué)習(xí)策略激發(fā)種群活力,設(shè)計(jì)兩條規(guī)則避免碰撞搜索,將人工蜂群算法應(yīng)用于求解FJSP,提出MCMSABC,并通過(guò)多個(gè)測(cè)例和實(shí)例驗(yàn)證其有效性.

1.1 FJSP

FJSP涉及兩個(gè)主體:一是工件集合J={Ji,1≤i≤n},二是機(jī)器集合M={Mk,1≤k≤m},每個(gè)工件由βi(βi>0)道工序組成,共有Dim道工序組成.解決該問(wèn)題是在約束條件下確定工序間的加工順序和每個(gè)工序選擇的加工機(jī)器,使各指標(biāo)達(dá)到最優(yōu)值.

1.2 符號(hào)定義

Oi,j:Ji號(hào)工件的第j道工序;

Pi,j:Oi,j的加工機(jī)器集合;

Si,j,k:Oi,j在機(jī)器k上的加工狀態(tài),Si,j,k=1表示Oi,j能在機(jī)器k上加工,Si,j,k=0則不能加工;

Ti,j,k:Oi,j號(hào)工序在機(jī)器k上的加工時(shí)間;

Ci:Ji號(hào)工件的加工完成時(shí)間;

Dh:第h道工序在不同機(jī)器上的加工時(shí)間集合;

Prk:機(jī)器k的加工成本.

1.3 目標(biāo)函數(shù)

FJSP主要關(guān)注以下幾個(gè)目標(biāo):最大完工時(shí)間,機(jī)器加工最小總負(fù)荷,單個(gè)機(jī)器最大負(fù)荷,加工成本等.本文主要研究以下3個(gè)目標(biāo):

1)最小化最大完工時(shí)間:

F1=min{Ci|1≤i≤n}

(1)

2)最小化機(jī)器加工總負(fù)荷:

(2)

3)最小化單個(gè)機(jī)器最大負(fù)荷:

(3)

1.4 約束條件

1)機(jī)器不存在物理故障,工序之間無(wú)等待時(shí)間,任一工序加工過(guò)程為連續(xù)過(guò)程.不同機(jī)器在零時(shí)間開(kāi)始獨(dú)立工作.

2)同一工件的工序有加工順序,后一工序須等待前一工序加工完成,即Oi,j完成后才可加工Oi,(j+1).

3)任一機(jī)器在某一時(shí)刻只能加工一個(gè)工序,即在某一時(shí)刻,存在Si,j,k=1時(shí),必不會(huì)存在Sz,v,k=1,(z≠i,v≠j).

2.1 編碼和解碼

本文根據(jù)FJSP特點(diǎn)使用分段式編碼,蜜源向量由機(jī)器編碼和工序編碼組成,機(jī)器編碼長(zhǎng)度和工序編碼長(zhǎng)度均為各工序的工件數(shù)量總和.

圖1展示了蜜源向量的編碼序列,機(jī)器序列對(duì)應(yīng)的工序順序?yàn)镺1,1…O1,β1…Oi,1…Oi,βi…On,1…On,βn,每個(gè)工序的加工機(jī)器集合為{Mi,Mj…Mk,i

圖1 蜜源向量編碼Fig.1 Coding of honey source vector

機(jī)器編碼中的數(shù)字代表該工序選擇的機(jī)器在集合中的位置,如J3的第2個(gè)位置的數(shù)字“2”,則表示為J3的第2個(gè)工序選擇機(jī)器庫(kù)中的第2個(gè)機(jī)器,即M3;工序序列中的第1個(gè)數(shù)字“2”,表示J2的第1個(gè)工序被加工,即O2,1是第2個(gè)被加工的工序.

解碼是將蜜源向量中的機(jī)器信息和工序信息轉(zhuǎn)換成一個(gè)可行的調(diào)度方案,將工序插入到對(duì)應(yīng)機(jī)器上最早可行的時(shí)刻加工有利于最小化最大完工時(shí)間,因此使用貪婪插入法[10]生成調(diào)度方案.

2.2 種群初始化

初始化蜂群的優(yōu)劣對(duì)整個(gè)搜索過(guò)程有著關(guān)鍵的影響,較好的初始化策略有利于提高蜂群的求解質(zhì)量.本文在初始化機(jī)器序列時(shí),使用Zhao等[11]提出的基于機(jī)器序列的改進(jìn)全局和局部選擇方法,并使用邏輯混沌映射產(chǎn)生個(gè)體,增加種群多樣性.公式(4)是邏輯映射的數(shù)學(xué)表達(dá)式,Xi,t為第i個(gè)個(gè)體第t道工序選擇的機(jī)器在機(jī)器集合中的位置,μ是邏輯映射參數(shù),當(dāng)μ=4時(shí),系統(tǒng)處于完全混沌狀態(tài),產(chǎn)生的初始蜂群分布最廣,通過(guò)邏輯混沌映射產(chǎn)生個(gè)體的機(jī)器序列.

Xi,(t+1)=μXi,t*(1-Xi,t),Xi,t∈(0,1)

(4)

公式(5)是為滿(mǎn)足FJSP離散的特點(diǎn),將個(gè)體向量從連續(xù)空間映射到離散空間.其中NJt表示第t道工序可選的機(jī)器總數(shù),low=1表示每個(gè)工序至少能被一臺(tái)機(jī)器加工,round為四舍五入函數(shù).

Xi,t=round(1+(NJi-1)*Xi,t)

(5)

在工序序列初始化時(shí),使用Zhao[7]等提出的MWR、MOR和RS的排序規(guī)則.其中,MWR是優(yōu)先加工剩余工作量較大的工件,MOR是優(yōu)先加工剩余工序量較大的工件,RS是隨機(jī)加工未完成的工件.

改善全局策略、改善局部策略、隨機(jī)策略使用比例為0.4,0.4,0.2,MWR、MOR、RS使用比例為0.4,0.4,0.2,機(jī)器序列和工序序列隨機(jī)組成個(gè)體序列.

2.3 改進(jìn)快速非支配排序策略和精英檔案

初始化蜂群后需評(píng)價(jià)個(gè)體質(zhì)量.Deb等提出NSGA-Ⅱ處理多目標(biāo)優(yōu)化問(wèn)題,使用快速非支配排序和擁擠距離評(píng)價(jià)個(gè)體的優(yōu)劣和密集程度[12].本文選用F1,F2,F3作為個(gè)體指標(biāo).P、Q為兩蜂群個(gè)體,若P、Q滿(mǎn)足條件(6),則P支配Q,P質(zhì)量高于Q.

(6)

根據(jù)條件(6),若P的多目標(biāo)值為(14,81,12),Q的多目標(biāo)值為(15,75,12),此時(shí)P與Q互不支配,但實(shí)際搜索過(guò)程中,P的多目標(biāo)值由于工序序列不合理,產(chǎn)生(15,81,12),(16,81,12)等多目標(biāo)值,此時(shí)被Q支配,從而導(dǎo)致潛力蜜源未被完全開(kāi)發(fā).針對(duì)此問(wèn)題,本文提出改進(jìn)策略,在條件(6)基礎(chǔ)上添加條件(7).兩個(gè)體F3相等時(shí)不作為支配的條件,該支配條件能夠保留潛力個(gè)體,對(duì)個(gè)體進(jìn)行深度開(kāi)發(fā),增大多目標(biāo)搜索的空間.

F3(P)

(7)

多目標(biāo)問(wèn)題中蜂群探索蜜源,若探索一次蜜源,蜜源質(zhì)量未變好,則該蜜源的被搜索次數(shù)增加1,反之歸0.在每一輪迭代過(guò)程中,使用快速非支配排序得到每個(gè)蜂群的最優(yōu)個(gè)體集合,即該蜂群的Pareto解集,稱(chēng)為該蜂群的精英集合.將每輪迭代過(guò)程中每個(gè)蜂群的精英集合匯入一個(gè)檔案,對(duì)檔案中的個(gè)體進(jìn)行快速非支配排序,得到當(dāng)前搜索到的最好個(gè)體集合,稱(chēng)為精英檔案,檔案中的個(gè)體稱(chēng)為精英個(gè)體.

2.4 蜂群進(jìn)化策略

由于蜂群個(gè)體的初始化質(zhì)量差異性較大,使用單一的進(jìn)化策略會(huì)減慢收斂速度和降低求解質(zhì)量,采用多蜂群的策略可以提高蜂群進(jìn)化的有效性.本文使用性別判定法[13]將蜂群按照分割比例分為蜂王群和工蜂群,增強(qiáng)進(jìn)化的適應(yīng)性.蜂群性別判定法步驟如下:

Step1.設(shè)置蜂群數(shù)量Fnum,測(cè)試蜂群數(shù)量Tnum,蜂群分割比例γ,初始化測(cè)試蜂群.

Step2.計(jì)算個(gè)體繁殖能力,即能尋出優(yōu)秀蜜源的數(shù)量.在機(jī)器序列上隨機(jī)選擇測(cè)試蜂中兩個(gè)工序的機(jī)器替換原蜂對(duì)應(yīng)工序的機(jī)器,在工序序列上測(cè)試蜂和原蜂使用常見(jiàn)的基于工件順序的交叉方式(Precedence Order-based Crossover,POX)生成新工序.若生成的新個(gè)體支配原個(gè)體,則該個(gè)體繁殖能力加1;

Step3.選擇繁殖能力大的前Fnum×γ個(gè)個(gè)體進(jìn)入蜂王群,其余進(jìn)入工蜂群;若繁殖能力相同,則優(yōu)先考慮有較小F1的原蜂,其次考慮有較小F3的原蜂,若全部相同,則隨機(jī)選擇.

在蜂群探索蜜源的過(guò)程中,會(huì)產(chǎn)生多個(gè)互不支配的解,會(huì)存在是否更新原個(gè)體的問(wèn)題,此時(shí)不更新原解,將另一非支配解添加至伴生蜂群.為達(dá)到快速收斂和增大搜索空間的平衡,需要對(duì)伴生蜂群進(jìn)行裁剪,控制其數(shù)量,裁剪過(guò)程中使用Harmonic平均距離[14]作為評(píng)判標(biāo)準(zhǔn),該距離與擁擠距離相比能較好的評(píng)價(jià)個(gè)體間密集程度.控制伴生蜂群數(shù)量裁剪步驟如下:

Step1.設(shè)置伴生蜂群最大數(shù)量Nmax=Fnum×p,伴生蜂群Group當(dāng)前數(shù)量為Npre,伴生比例p,Group中精英個(gè)體比例為q,設(shè)置容量為Nmax的伴生數(shù)組Set,Set當(dāng)前容量Ncur,轉(zhuǎn)Step 2;

Step2.若Npre不大于Nmax,則將Group中個(gè)體全部加入Set,轉(zhuǎn)Step 7,否則轉(zhuǎn)Step 3;

Step3.使用改進(jìn)的快速非支配排序計(jì)算伴生蜂群中Pareto解集中解的數(shù)量N1,若N1≤Nmax×q,則全部加入Set,更新Ncur,轉(zhuǎn)Step 5,否則轉(zhuǎn)Step 4;

Step4.計(jì)算Pareto解集中個(gè)體的Harmonic平均距離,刪除平均距離最小的個(gè)體后,若解集中剩余個(gè)體數(shù)量等于Nmax×q,則全部加入Set,更新Ncur,轉(zhuǎn)Step 5,否則轉(zhuǎn)Step 4;

Step5.使用改進(jìn)的快速非支配排序計(jì)算Group中剩余個(gè)體的Pareto解數(shù)量Npf,若加入Set后Ncur大于Nmax,則計(jì)算解集中個(gè)體Harmonic平均距離,刪除平均距離較小的若干個(gè)體,使剩余個(gè)體加入Set后使Ncur等于Nmax,轉(zhuǎn)Step 7,否則轉(zhuǎn)Step 6;

Step6.將該層Pareto解集全部加入Set,若無(wú)剩余個(gè)體,轉(zhuǎn)Step 7,否則轉(zhuǎn)Step 5;

Step7.將Set更新為Group,算法結(jié)束.

該算法偽代碼如下:

算法.更新伴生蜂群

輸入：蜜蜂數(shù)量Fnum,裁剪比例p,精英比例q,大小為Npre伴生蜂群Group

輸出：伴生蜂群Group

1.創(chuàng)建大小為Nmax=Fnum×p的伴生數(shù)組Set,記容量為Ncur

2.if(Npre>Nmax)then

3. 計(jì)算Group中精英個(gè)體數(shù)量為N1

4. while(N1>Nmax×q)do

5. 計(jì)算Harmonic平均距離,刪除距離最小個(gè)體

6. end while

7. 將剩余精英個(gè)體加入Set,更新Ncur,更新Group

8. While(Ncur0)do

9. 計(jì)算Group的Pareto解集中個(gè)體數(shù)量Npf

10. if(Npf+Ncur≤Nmax)then

11. 將Npf個(gè)個(gè)體加入Set,更新Group

12. else

13. 計(jì)算Npf個(gè)個(gè)體平均距離刪除若干距離最小的個(gè)體后加入Set

14. end if

15. end while

16.end if

17.將Set更新為Group

18.return Group

2.5 雇傭蜂階段

標(biāo)準(zhǔn)ABC多用于解決連續(xù)型函數(shù)問(wèn)題,在雇傭蜂階段對(duì)個(gè)體給定一個(gè)隨機(jī)方向和微小的步長(zhǎng)進(jìn)行鄰域搜索.FJSP屬于離散問(wèn)題,標(biāo)準(zhǔn)ABC鄰域搜索會(huì)產(chǎn)生無(wú)效解,因此本文根據(jù)繁殖能力使用多種有效鄰域結(jié)構(gòu),將搜索中產(chǎn)生的非支配個(gè)體加入伴生蜂群.

機(jī)器鄰域結(jié)構(gòu):

1)隨機(jī)選取1至2個(gè)工序的加工機(jī)器變異,選取產(chǎn)生最好解的一組變異方式更新.若選擇的工序個(gè)數(shù)為1,則在該工序的機(jī)器集合中選擇一個(gè)使個(gè)體最優(yōu)秀的機(jī)器,若選擇的工序個(gè)數(shù)為2,則如圖2(a),從第1道工序和第6道工序的機(jī)器組合方案中選擇使個(gè)體最優(yōu)秀的一組方案,即機(jī)器M1和M3.

圖2Fig.2

2)確定最大負(fù)荷機(jī)器,將該機(jī)器的一道加工工序指派到另一機(jī)器加工.

3)確定加工工序數(shù)量最多的機(jī)器,將該機(jī)器的一道加工工序指派到另一機(jī)器加工.

4)隨機(jī)選擇若干工序,選擇該工序加工時(shí)間最小的機(jī)器.

工序鄰域結(jié)構(gòu):

1)隨機(jī)選擇兩道工序,將前一道工序插入到后一道工序后或?qū)⒑笠坏拦ば虿迦氲角耙坏拦ば蚯?若選擇的工序?qū)儆谙嗤ぜ?則重新選擇.

2)隨機(jī)選擇兩道工序交換,若選擇的工序?qū)儆谙嗤ぜ?則重新選擇.

3)計(jì)算每個(gè)工件工序的位置下標(biāo)之和,選取最大和最小兩個(gè)工件,打亂兩個(gè)工件的工序次序,并放回原序列中工序所在位置.如圖2(b)中,J1的加工順序位次和為7,J2的加工順序位次和為5,J3的加工順序位次和為9,則將J2和J3的工序打亂順序后填入原位置.

工蜂群使用機(jī)器結(jié)構(gòu)比例為0.3,0.3,0.3,0.1,工序結(jié)構(gòu)的比例為0.4,0.4,0.2.蜂王群使用機(jī)器結(jié)構(gòu)比例為0.1,0.2,0.2,0.5,工序結(jié)構(gòu)比例為0.25,0.25,0.5,伴生蜂群結(jié)構(gòu)使用比例和蜂王群相同.

2.6 觀察蜂階段

在標(biāo)準(zhǔn)ABC中雇傭蜂階段蜂群對(duì)蜜源進(jìn)行鄰域探索后,觀察蜂階段蜂群根據(jù)適應(yīng)度值選擇蜜源,適應(yīng)度值大的蜜源被選擇概率大.在多目標(biāo)問(wèn)題,標(biāo)準(zhǔn)ABC選擇蜜源的方式已不適合,需要改變?cè)u(píng)價(jià)蜜源適應(yīng)度評(píng)判指標(biāo),對(duì)于不同蜂群提出兩種競(jìng)爭(zhēng)方式.工蜂群繁殖能力弱,個(gè)體差異小,使用輪盤(pán)賭方法選擇蜜源具有公平性,概率選擇如公式(8),Bj為第j個(gè)個(gè)體支配其余個(gè)體的數(shù)量,B為所有個(gè)體支配其余個(gè)體數(shù)量的總和,Proj是個(gè)體被選擇的概率.

(8)

蜂王群繁殖能力強(qiáng),個(gè)體差異大,因此使用一種基于損失值的排序方式選擇蜜源,通過(guò)比較損失值體現(xiàn)個(gè)體的差異性,為防止個(gè)體差異性太大導(dǎo)致個(gè)別蜜源被選擇概率極低,根據(jù)損失值將蜜源進(jìn)行排名.損失值計(jì)算如公式(9),Fi表示該個(gè)體的第i個(gè)目標(biāo)值,Fimin為第i個(gè)目標(biāo)搜索到的最小值.

(9)

使用公式(10)計(jì)算蜜源選擇概率,其中index(j)表示第j個(gè)個(gè)體在蜂群中的排名,num是蜂王群數(shù)量,Iter是最大迭代次數(shù).當(dāng)解的Loss最小時(shí),index(j)=1.在算法初期,I較小時(shí),φ較小,可避免蜂群搜索陷入局部最優(yōu),保持蜂群多樣性;在算法后期,個(gè)體差異小時(shí)增大φ值提高較差個(gè)體被選擇的概率加速種群探索,防止算法搜索陷入停滯狀態(tài).

(10)

不同蜂群在觀察蜜源時(shí)使用的策略不同,在觀察蜜源時(shí)產(chǎn)生的非支配個(gè)體加入伴生蜂群.蜂王群對(duì)于工序序列使用POX交叉,機(jī)器序列使用常見(jiàn)的均勻交叉(Uniform Crossover,UX);工蜂群對(duì)于工序序列使用基于工件的交叉方式(Job-based Crossover,JBX),機(jī)器序列使用多點(diǎn)交叉(Multiple Point Crossover,MPX).

JBX交叉規(guī)則:選擇父代序列P1和P2,將工件集合JS隨機(jī)分為JS1和JS2,將P1中屬于JS1,P2中屬于JS2的工序分別復(fù)制到產(chǎn)生到子代序列O1和O2中相同位置,再將P1中屬于JS1,P2中屬于JS2的工序按照原順序分別復(fù)制到O2和O1的空位置.

MPX交叉規(guī)則:選擇父代序列P1和P2,產(chǎn)生一個(gè)與工序數(shù)量相同的“0-1”向量,若該向量某位置為0,則將P1中機(jī)器復(fù)制M1,P2中機(jī)器復(fù)制到M2,若為1,則將P1中機(jī)器復(fù)制M2,P2中機(jī)器復(fù)制到M1.

在標(biāo)準(zhǔn)ABC中鄰域搜索在雇傭蜂階段,本文在觀察蜂階段使用基于關(guān)鍵路徑的鄰域搜索策略,提高進(jìn)化精確性.由于一個(gè)調(diào)度方案具有多條關(guān)鍵路徑,導(dǎo)致關(guān)鍵路徑內(nèi)的關(guān)鍵塊所含的關(guān)鍵工序的數(shù)量也不同,因此對(duì)于包含不同數(shù)量關(guān)鍵工序的關(guān)鍵塊需要設(shè)計(jì)不同的鄰域結(jié)構(gòu).N6[15]和M&G[16]兩種鄰域結(jié)構(gòu)能夠保證連通性并縮小鄰域規(guī)模,在FJSP上得到了廣泛的應(yīng)用.基于連通性要求和小規(guī)模鄰域結(jié)構(gòu)能獲得精度和速度的平衡.根據(jù)此鄰域結(jié)構(gòu)設(shè)計(jì)思想,本文提出3種基于關(guān)鍵路徑的鄰域結(jié)構(gòu)MaxI,MinE,RandD,要求每個(gè)關(guān)鍵塊內(nèi)的關(guān)鍵工序數(shù)量不少于二道,每個(gè)個(gè)體僅使用一種鄰域結(jié)構(gòu).

MaxI:選擇包含最多道關(guān)鍵工序的關(guān)鍵塊,將關(guān)鍵塊內(nèi)的一道工序插入到塊首工序前或塊尾工序后,該關(guān)鍵塊內(nèi)關(guān)鍵工序數(shù)量不少于3道.

MinE:選擇包含最少道關(guān)鍵工序的關(guān)鍵塊,將關(guān)鍵塊內(nèi)的一道工序與相鄰工序進(jìn)行交換,該關(guān)鍵塊內(nèi)工序數(shù)量不超過(guò)3道.

RandD:將關(guān)鍵塊內(nèi)加工時(shí)間最長(zhǎng)的一道工序指派到其他機(jī)器,若該工序僅有一個(gè)可加工機(jī)器,則嘗試次長(zhǎng)工序的機(jī)器指派.

上述3種基于關(guān)鍵路徑的鄰域結(jié)構(gòu)需要滿(mǎn)足以下兩條規(guī)則,否則為無(wú)效鄰域.

1)關(guān)鍵塊內(nèi)某工序向前插入或交換時(shí),其開(kāi)始加工時(shí)間必須大于前序工序結(jié)束時(shí)間.

2)關(guān)鍵塊內(nèi)某工序向后插入或交換時(shí),其結(jié)束加工時(shí)間必須小于后續(xù)工序開(kāi)始時(shí)間.

基于關(guān)鍵路徑的鄰域結(jié)構(gòu)如圖3所示,(i,j)表示Oi,j,在滿(mǎn)足兩條規(guī)則時(shí),當(dāng)(1,1)和(2,1)是關(guān)鍵塊時(shí),則可以使用MinE鄰域結(jié)構(gòu);當(dāng)(4,2),(2,2),(1,3),(2,3)是關(guān)鍵塊時(shí),則可以使用MaxI鄰域結(jié)構(gòu),當(dāng)(2,4),(3,3)是關(guān)鍵塊時(shí),則可以使用RandD將(3,3)的機(jī)器變更為M1.

圖3 基于關(guān)鍵路徑的3種鄰域結(jié)構(gòu)Fig.3 Three neighborhood structures based on critical path

2.7 偵察蜂階段

在經(jīng)歷雇傭蜂和觀察蜂階段之后,需要對(duì)無(wú)潛力的個(gè)體進(jìn)行更新,以此保證種群的活力,在標(biāo)準(zhǔn)ABC中,偵察蜂會(huì)放棄探索次數(shù)超過(guò)Limit的蜜源,重新探索新蜜源.由于探索過(guò)程的隨機(jī)性,無(wú)法保證新蜜源質(zhì)量.本文在偵察蜂階段加入基于學(xué)習(xí)機(jī)制的策略更新蜜源,學(xué)習(xí)優(yōu)秀個(gè)體能夠加快蜂群收斂,提高新蜜源質(zhì)量.基于學(xué)習(xí)機(jī)制的更新策略如下:

1)在機(jī)器部分將精英個(gè)體加入蜂群,對(duì)蜂群使用混合列交叉[17],在工序部分選取精英個(gè)體,與蜂群個(gè)體使用JBX交叉方式;

2)對(duì)于1)中的個(gè)體,若該個(gè)體連續(xù)探索蜜源次數(shù)超過(guò)仍Limit未發(fā)現(xiàn)質(zhì)量高的蜜源,則

(1)使用隨機(jī)初始化策略重構(gòu)個(gè)體;

(2)使用學(xué)習(xí)策略將個(gè)體重構(gòu),使用學(xué)習(xí)策略重構(gòu)個(gè)體步驟如下:

Step1.從精英檔案中隨機(jī)選取一個(gè)精英個(gè)體,隨機(jī)選取精英個(gè)體機(jī)器編碼段的兩個(gè)位置.若兩位置距離小于Dim/2,轉(zhuǎn)Step 2,否則轉(zhuǎn)Step 3;

Step2.將精英個(gè)體兩個(gè)位置之間的編碼段復(fù)制給子代個(gè)體,將原個(gè)體中剩余兩側(cè)的編碼段復(fù)制給子代個(gè)體.工序序列選定同樣位置,將原個(gè)體兩個(gè)位置之間的編碼段復(fù)制給子代個(gè)體,剩余兩側(cè)的編碼段打亂后復(fù)制給子代個(gè)體,轉(zhuǎn)Step 4;

Step3.將原個(gè)體兩個(gè)位置之間的編碼段復(fù)制給子代個(gè)體,將精英個(gè)體中剩余兩側(cè)的編碼段復(fù)制給子代個(gè)體.工序序列選定同樣位置,將原個(gè)體兩個(gè)位置之間的編碼段打亂后復(fù)制給子代個(gè)體,剩余兩側(cè)的編碼段復(fù)制給子代個(gè)體,轉(zhuǎn)Step 4;

Step4.算法結(jié)束.

2.8 算法流程

算法分為5個(gè)階段,階段如下:

Step1.初始化階段:輸入工件和機(jī)器信息,使用2.4節(jié)的策略產(chǎn)生蜂群,計(jì)算個(gè)體適應(yīng)度,使用快速非支配排序更新精英檔案.設(shè)置蜂群個(gè)數(shù)等基礎(chǔ)參數(shù)、性別判定法相關(guān)參數(shù)、鄰域結(jié)構(gòu)相關(guān)參數(shù),轉(zhuǎn)Step 2.

Step2.雇傭蜂階段:使用性別判定法將蜂群拆分為蜂王群和工蜂群,蜂王群和工蜂群根據(jù)產(chǎn)生的隨機(jī)數(shù)與參數(shù)的大小關(guān)系選擇2.5節(jié)中提出的對(duì)應(yīng)鄰域結(jié)構(gòu).若蜂王鄰域結(jié)構(gòu)的使用閾值為a,a+b,a+b+c,1,則產(chǎn)生一個(gè)隨機(jī)數(shù)y,若a

Step3.觀察蜂階段:蜂王群和工蜂群使用2.6節(jié)的兩種競(jìng)爭(zhēng)方法選擇個(gè)體,選擇2.6節(jié)的蜂群對(duì)應(yīng)交叉方式進(jìn)行交叉.對(duì)所有個(gè)體使用基于關(guān)鍵路徑的鄰域探索策略,產(chǎn)生精英集合,更新檔案.伴生蜂群使用蜂王群交叉算子和基于關(guān)鍵路徑的鄰域探索后使用裁剪策略,產(chǎn)生精英集合,更新檔案,轉(zhuǎn)Step 4.

Step4.偵察蜂階段:對(duì)于蜂王群和工蜂群使用2.7節(jié)1)策略進(jìn)行個(gè)體更新,使用2.7節(jié)2)策略進(jìn)行個(gè)體重構(gòu),并將蜂王群和工蜂群合并,伴生蜂群作為獨(dú)立蜂群.若迭代結(jié)束,轉(zhuǎn)Step 5,否則轉(zhuǎn)Step 2.

Step5.結(jié)束階段:輸出更新后的精英檔案.

2.9 針對(duì)單目標(biāo)改進(jìn)的算例數(shù)據(jù)預(yù)處理策略

對(duì)于任一工序都能被所有機(jī)器加工的FJSP稱(chēng)為完全柔性作業(yè)車(chē)間調(diào)度問(wèn)題(Total Flexible Job-shop Scheduling Problem,T-FJSP),由于T-FJSP存在較大的無(wú)效搜索空間,因此對(duì)算例進(jìn)行數(shù)據(jù)預(yù)處理.分支限界法是找出滿(mǎn)足約束條件的解,設(shè)計(jì)合理的剪枝函數(shù)能夠在早期淘汰不良個(gè)體,FJSP是優(yōu)化問(wèn)題,剪枝函數(shù)設(shè)計(jì)應(yīng)參考目前搜索的最小值,在算例中排除加工時(shí)間過(guò)長(zhǎng)的情況.記測(cè)試蜂群的F1min為SC,對(duì)于Ti,j,k提出兩條規(guī)則:

規(guī)則1.由于F1≥F3,若Ti,j,k>SC,則從此工序的Pi,j中刪除該機(jī)器;

規(guī)則2.刪除Ti,j,k較大的加工機(jī)器,滿(mǎn)足約束條件(11)時(shí)從此工序的Pi,j中刪除該機(jī)器,ceil是向上取整函數(shù),rand產(chǎn)生0到1的隨機(jī)數(shù),τ是規(guī)則2的系數(shù),m是機(jī)器數(shù)量;

(11)

2.10 針對(duì)多目標(biāo)改進(jìn)的蜜源更新策略

由于蜜源的潛力有限,且蜜源質(zhì)量取決于機(jī)器向量和工序向量?jī)刹糠?機(jī)器向量決定蜜源質(zhì)量上限,當(dāng)蜜源質(zhì)量達(dá)到上限時(shí),改變工序序列不會(huì)改進(jìn)解的質(zhì)量,會(huì)產(chǎn)生無(wú)效的碰撞搜索.因此設(shè)計(jì)兩種方案提高蜜源質(zhì)量上限.從精英檔案中隨機(jī)選取一個(gè)精英,其探索的蜜源目標(biāo)值分別為F1,F2,F3,蜂群中一個(gè)體探索的蜜源目標(biāo)值為FC1,FC2,FC3,當(dāng)滿(mǎn)足條件(12)或(13)時(shí),需要重構(gòu)機(jī)器序列.滿(mǎn)足條件(12)時(shí),該個(gè)體解被精英解支配,不會(huì)在全局上產(chǎn)生更優(yōu)解;滿(mǎn)足條件(13)時(shí),該個(gè)體解已達(dá)最優(yōu).

FC2≥FJ2,FC3≥FJ1

(12)

FC3=FC1

(13)

為驗(yàn)證MCMSABC有效性,本文從Kacem等[18]提出的5個(gè)算例和Brandimarte[19]等提出的5個(gè)算例驗(yàn)證算法,并通過(guò)車(chē)間實(shí)例驗(yàn)證算法的實(shí)用性.Tcpu為10次實(shí)驗(yàn)中算例運(yùn)行的平均時(shí)間(單位:min).

算法由matlab2021a編寫(xiě),運(yùn)行環(huán)境為:8GB,CPU為i5-6300.針對(duì)不同算例運(yùn)行10次,并與文獻(xiàn)比較.參數(shù):Fnum=80,Iter=300,Limit=30,γ=0.5.

3.1 單目標(biāo)FJSP實(shí)驗(yàn)分析

表1顯示了MCMSABC與HCSO[20]、HGWO[21]、WSA[22]在F1上的結(jié)果,其中Best為10次實(shí)驗(yàn)的最優(yōu)解,Avg為10次實(shí)驗(yàn)的平均解,I(O)為10次實(shí)驗(yàn)中達(dá)到O值的平均迭代次數(shù),若未能搜索到O值則為最大迭代次數(shù).對(duì)于Kacem1、Kacem2和Kacem4 3個(gè)算例,MCMSABC搜索到的Avg和Best均為最優(yōu)值;對(duì)于Kacem3,WSA搜索到的Best是13,MCMSABC搜索到的Best是11,將Best減小2;對(duì)于Kacem5,HCSO和WSA搜索到的Best是12,HGWO搜索到的Best是13,MCMSABC能搜索到其余3種算法未搜索到的Best值11,且Avg為11,說(shuō)明MCMSABC求解質(zhì)量?jī)?yōu)于對(duì)比算法.

表1 F1單目標(biāo)Kacem算例對(duì)比結(jié)果Table 1 Comparison results of single target(Kacem examples)

為了驗(yàn)證規(guī)則1和規(guī)則2的合理性,在不使用初始化和伴生蜂群策略的條件下對(duì)MCMSABC、MCMSABC1(應(yīng)用規(guī)則1)、不同參數(shù)下的MCMSABC2(應(yīng)用規(guī)則2)進(jìn)行實(shí)驗(yàn).表2顯示了4個(gè)T-FJSP在不同規(guī)則下的Avg和I(O).MCMSABC1比MCMSABC具有較小的I(O)和Avg,說(shuō)明較小的搜索空間能加速搜索到最優(yōu)解,體現(xiàn)了規(guī)則1的合理性.τ較小時(shí),MCMSABC2比MCMSABC有較小的I(O)和Avg,體現(xiàn)了規(guī)則2在解決T-FJSP時(shí)具有一定的合理性.

表2 不同規(guī)則下的最優(yōu)解和迭代次數(shù)Table 2 Optimal solution and iteration times under different rules

表3顯示了MCMSABC在MK算例上的F1和文獻(xiàn)[2]、HCSO[20]、HGWO[21]、IDSSA[23]、文獻(xiàn)[24]、文獻(xiàn)[25]的比較結(jié)果,加黑值為比較算法搜索到的最優(yōu)解.對(duì)于MK01、MK03,MCMSABC和其余算法均能搜索到Best,且Best和Avg相等;對(duì)于MK05,MCMSABC和文獻(xiàn)[24]算法能夠搜索到Best172,相對(duì)于其余算法搜索到的Best更優(yōu);對(duì)于MK07,MCMSABC和文獻(xiàn)[25]算法均能搜索到Best139,相對(duì)于HCSO、HGWO、WSA、IDSSA將Best值縮小5以上;對(duì)于MK09,MCMSABC相對(duì)于HCSO、HGWO、文獻(xiàn)[24]算法、IDSSA均能將Best值更新,相對(duì)于WSA將Best縮小62.MCMSABC在5個(gè)算例上的Avg與Best均不超過(guò)1,說(shuō)明MCMSABC性能優(yōu)于對(duì)比算法,求解大規(guī)模算例時(shí)具有穩(wěn)定性.

表3 F1單目標(biāo)Brandimarte算例對(duì)比結(jié)果Table 3 Comparison results of single target(Brandimarte examples)

3.2 MOFSJP實(shí)驗(yàn)分析

針對(duì)Kacem1～Kacem5這5個(gè)算例進(jìn)行多目標(biāo)分析,選取F1,F2,F3函數(shù)作為多目標(biāo)優(yōu)化函數(shù).表4顯示了MCMSABC所求Pareto解集與HTABC[26]、SAMO-Jaya[27]、CSTA[5]、RLNSGA-II[28]Pareto解集的對(duì)比結(jié)果.對(duì)于Kacem1,MCMSABC搜索到的解集能支配HTABC、CSTA解集;對(duì)于Kacem2,MCMSABC相對(duì)于HTABC能搜索到非支配解(16,73,13),(16,77,11)相對(duì)于SAMO-Jaya搜索到非支配解(15,75,12),(16,73,13),(14,77,12),相對(duì)于RLNSGA-II搜索到非支配解(16,77,11);對(duì)于Kacem3,MCMSABC解集支配HTABC、CSTA解集,并將F2最小值從61變成60;對(duì)于Kacem4,MCMSABC均能搜索到每個(gè)目標(biāo)的最小值,解集中解的數(shù)量達(dá)到4個(gè),解集支配HTABC解集,相對(duì)于SAMO-Jaya搜索到非支配解(8,42,5);對(duì)于Kacem5,MCMSABC搜索到的解集支配HTABC、CSTA、RLNSGA-II解集,相對(duì)于SAMO-Jaya搜索到非支配解(11,93,10),找到的(11,91,11)支配SAMO-Jaya的(11,93,11).這說(shuō)明MCMSABC求出的Pareto解集質(zhì)量較好,求解大規(guī)模多目標(biāo)問(wèn)題具有穩(wěn)定性.觀察到Tcpu時(shí)間均較小,說(shuō)明算法的的時(shí)間復(fù)雜度較低,在精度和速度上獲得了平衡.

表4 多目標(biāo)Kacem算例對(duì)比結(jié)果Table 4 Comparison results of multi-objective(Kacem examples)

3.3 車(chē)間實(shí)例實(shí)驗(yàn)分析

為驗(yàn)證本算法在車(chē)間實(shí)例上的有效性,選取文獻(xiàn)[29]的車(chē)間實(shí)例來(lái)測(cè)試.該車(chē)間實(shí)例的數(shù)據(jù)規(guī)模為6×6,即6個(gè)工件和6個(gè)機(jī)器.表5為實(shí)例的實(shí)驗(yàn)結(jié)果對(duì)比,表5中給出了MCMSABC和PDABC[17]、CEMOFJSP[29]、CSTA[5]這3種算法的比較結(jié)果.本文算法搜索到的6個(gè)Pareto前沿解均能支配3種算法的解集,對(duì)于CEMOFJSP和PDABC兩種算法,在F1上得到了提升,將最大加工時(shí)間從10減少到了9.MCMSABC搜索到的F1,F2,F3均為3種算法的最優(yōu)值,搜索到的Pareto解集中有6個(gè)解,解的數(shù)量最多.MCMSABC求解車(chē)間實(shí)例更加有效.

表5 多目標(biāo)車(chē)間實(shí)例對(duì)比結(jié)果Table 5 Comparison results of multi-objective workshop examples

為探究本文算法在不同多目標(biāo)指標(biāo)下的適用性,選取文獻(xiàn)[17]的車(chē)間算例來(lái)測(cè)試,該車(chē)間實(shí)例的數(shù)據(jù)規(guī)模為5×8,即5個(gè)工件和8個(gè)機(jī)器.使用F1,F2,F4作為多目標(biāo)優(yōu)化函數(shù),其中公式(14)代表最小化機(jī)器加工成本F4,為提高種群的適應(yīng)性,增加隨機(jī)初始化策略的比例.本實(shí)例中隨機(jī)初始化策略比例為0.4,其余策略比例為均為0.3.

(14)

表6給出了該車(chē)間實(shí)例兩組多目標(biāo)的Pareto解集,F1,F2均能探索到最小值,表明在修改目標(biāo)函數(shù)的情況下,MCMSABC對(duì)車(chē)間實(shí)例仍具有較好的適應(yīng)性.

表6 不同多目標(biāo)下的解集對(duì)比Table 6 Comparison of solution sets under different multi-objective conditions

本文針對(duì)FJSP的特點(diǎn)提出一種基于多策略的多蜂群人工蜂群算法,在單目標(biāo)問(wèn)題上驗(yàn)證了數(shù)據(jù)預(yù)處理的效果,在參數(shù)適合的情況下能夠獲得更快的收斂速度和最優(yōu)解的次數(shù).在多目標(biāo)問(wèn)題上使用基于關(guān)鍵塊大小的鄰域結(jié)構(gòu),學(xué)習(xí)策略和蜜源更新策略,在算例上獲得更為優(yōu)秀的Pareto解集.

本文提出的算法在FJSP具有一定的實(shí)用性,通過(guò)工廠實(shí)例驗(yàn)證了該算法的可行性.下一步工作是研究帶有約束條件的MOFJSP,滿(mǎn)足特定環(huán)境下的車(chē)間調(diào)度問(wèn)題,設(shè)計(jì)更高效的蜂群算法.

猜你喜歡 蜜源支配鄰域 貴州寬闊水國(guó)家級(jí)自然保護(hù)區(qū)蜜源植物資源調(diào)查研究*貴州科學(xué)(2023年6期)2024-01-02林下拓蜜源 蜂業(yè)上臺(tái)階林業(yè)與生態(tài)(2022年5期)2022-05-23被貧窮生活支配的恐懼意林(2021年9期)2021-05-28稀疏圖平方圖的染色數(shù)上界吉林大學(xué)學(xué)報(bào)（理學(xué)版）(2020年3期)2020-05-29跟蹤導(dǎo)練（四）4時(shí)代英語(yǔ)·高一(2019年1期)2019-03-13基于鄰域競(jìng)賽的多目標(biāo)優(yōu)化算法自動(dòng)化學(xué)報(bào)(2018年7期)2018-08-20指示蜜源的導(dǎo)蜜鳥(niǎo)高中生·天天向上(2018年1期)2018-04-14基于決策空間變換最近鄰方法的Pareto支配性預(yù)測(cè)自動(dòng)化學(xué)報(bào)(2017年2期)2017-04-04關(guān)于-型鄰域空間周口師范學(xué)院學(xué)報(bào)(2016年5期)2016-10-17隨心支配的清邁美食探店記Coco薇(2016年8期)2016-10-09

推薦訪問(wèn):蜂群 作業(yè) 求解