成金海,徐 華

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

0 引 言

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

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

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

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

1 FJSP數(shù)學(xué)模型

1.1 FJSP

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

1.2 符號定義

Oi,j:Ji號工件的第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號工序在機(jī)器k上的加工時間;

Ci:Ji號工件的加工完成時間;

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

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

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

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

1)最小化最大完工時間:

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

(1)

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

(2)

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

(3)

1.4 約束條件

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

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

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

2 MCMSABC求解FJSP

2.1 編碼和解碼

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

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

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

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

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

2.2 種群初始化

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

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

(4)

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

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

(5)

在工序序列初始化時,使用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ī)組成個體序列.

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

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

(6)

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

F3(P)

(7)

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

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

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

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

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

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

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

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

Step2.若Npre不大于Nmax,則將Group中個體全部加入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解集中個體的Harmonic平均距離,刪除平均距離最小的個體后,若解集中剩余個體數(shù)量等于Nmax×q,則全部加入Set,更新Ncur,轉(zhuǎn)Step 5,否則轉(zhuǎn)Step 4;

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

Step6.將該層Pareto解集全部加入Set,若無剩余個體,轉(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中精英個體數(shù)量為N1

4. while(N1>Nmax×q)do

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

6. end while

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

8. While(Ncur0)do

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

10. if(Npf+Ncur≤Nmax)then

11. 將Npf個個體加入Set,更新Group

12. else

13. 計(jì)算Npf個個體平均距離刪除若干距離最小的個體后加入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ù)問題,在雇傭蜂階段對個體給定一個隨機(jī)方向和微小的步長進(jìn)行鄰域搜索.FJSP屬于離散問題,標(biāo)準(zhǔn)ABC鄰域搜索會產(chǎn)生無效解,因此本文根據(jù)繁殖能力使用多種有效鄰域結(jié)構(gòu),將搜索中產(chǎn)生的非支配個體加入伴生蜂群.

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

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

圖2Fig.2

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

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

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

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

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

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

3)計(jì)算每個工件工序的位置下標(biāo)之和,選取最大和最小兩個工件,打亂兩個工件的工序次序,并放回原序列中工序所在位置.如圖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中雇傭蜂階段蜂群對蜜源進(jìn)行鄰域探索后,觀察蜂階段蜂群根據(jù)適應(yīng)度值選擇蜜源,適應(yīng)度值大的蜜源被選擇概率大.在多目標(biāo)問題,標(biāo)準(zhǔn)ABC選擇蜜源的方式已不適合,需要改變評價蜜源適應(yīng)度評判指標(biāo),對于不同蜂群提出兩種競爭方式.工蜂群繁殖能力弱,個體差異小,使用輪盤賭方法選擇蜜源具有公平性,概率選擇如公式(8),Bj為第j個個體支配其余個體的數(shù)量,B為所有個體支配其余個體數(shù)量的總和,Proj是個體被選擇的概率.

(8)

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

(9)

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

(10)

不同蜂群在觀察蜜源時使用的策略不同,在觀察蜜源時產(chǎn)生的非支配個體加入伴生蜂群.蜂王群對于工序序列使用POX交叉,機(jī)器序列使用常見的均勻交叉(Uniform Crossover,UX);工蜂群對于工序序列使用基于工件的交叉方式(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)生一個與工序數(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)化精確性.由于一個調(diào)度方案具有多條關(guān)鍵路徑,導(dǎo)致關(guān)鍵路徑內(nèi)的關(guān)鍵塊所含的關(guān)鍵工序的數(shù)量也不同,因此對于包含不同數(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,要求每個關(guān)鍵塊內(nèi)的關(guān)鍵工序數(shù)量不少于二道,每個個體僅使用一種鄰域結(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ù)量不超過3道.

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

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

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

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

基于關(guān)鍵路徑的鄰域結(jié)構(gòu)如圖3所示,(i,j)表示Oi,j,在滿足兩條規(guī)則時,當(dāng)(1,1)和(2,1)是關(guān)鍵塊時,則可以使用MinE鄰域結(jié)構(gòu);當(dāng)(4,2),(2,2),(1,3),(2,3)是關(guān)鍵塊時,則可以使用MaxI鄰域結(jié)構(gòu),當(dāng)(2,4),(3,3)是關(guān)鍵塊時,則可以使用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)歷雇傭蜂和觀察蜂階段之后,需要對無潛力的個體進(jìn)行更新,以此保證種群的活力,在標(biāo)準(zhǔn)ABC中,偵察蜂會放棄探索次數(shù)超過Limit的蜜源,重新探索新蜜源.由于探索過程的隨機(jī)性,無法保證新蜜源質(zhì)量.本文在偵察蜂階段加入基于學(xué)習(xí)機(jī)制的策略更新蜜源,學(xué)習(xí)優(yōu)秀個體能夠加快蜂群收斂,提高新蜜源質(zhì)量.基于學(xué)習(xí)機(jī)制的更新策略如下:

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

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

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

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

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

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

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

Step4.算法結(jié)束.

2.8 算法流程

算法分為5個階段,階段如下:

Step1.初始化階段:輸入工件和機(jī)器信息,使用2.4節(jié)的策略產(chǎn)生蜂群,計(jì)算個體適應(yīng)度,使用快速非支配排序更新精英檔案.設(shè)置蜂群個數(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é)中提出的對應(yīng)鄰域結(jié)構(gòu).若蜂王鄰域結(jié)構(gòu)的使用閾值為a,a+b,a+b+c,1,則產(chǎn)生一個隨機(jī)數(shù)y,若a

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

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

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

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

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

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

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

(11)

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

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

FC2≥FJ2,FC3≥FJ1

(12)

FC3=FC1

(13)

3 實(shí)驗(yàn)與結(jié)果分析

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

算法由matlab2021a編寫,運(yùn)行環(huán)境為:8GB,CPU為i5-6300.針對不同算例運(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ù).對于Kacem1、Kacem2和Kacem4 3個算例,MCMSABC搜索到的Avg和Best均為最優(yōu)值;對于Kacem3,WSA搜索到的Best是13,MCMSABC搜索到的Best是11,將Best減小2;對于Kacem5,HCSO和WSA搜索到的Best是12,HGWO搜索到的Best是13,MCMSABC能搜索到其余3種算法未搜索到的Best值11,且Avg為11,說明MCMSABC求解質(zhì)量優(yōu)于對比算法.

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

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

表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)解.對于MK01、MK03,MCMSABC和其余算法均能搜索到Best,且Best和Avg相等;對于MK05,MCMSABC和文獻(xiàn)[24]算法能夠搜索到Best172,相對于其余算法搜索到的Best更優(yōu);對于MK07,MCMSABC和文獻(xiàn)[25]算法均能搜索到Best139,相對于HCSO、HGWO、WSA、IDSSA將Best值縮小5以上;對于MK09,MCMSABC相對于HCSO、HGWO、文獻(xiàn)[24]算法、IDSSA均能將Best值更新,相對于WSA將Best縮小62.MCMSABC在5個算例上的Avg與Best均不超過1,說明MCMSABC性能優(yōu)于對比算法,求解大規(guī)模算例時具有穩(wěn)定性.

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

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

針對Kacem1～Kacem5這5個算例進(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解集的對比結(jié)果.對于Kacem1,MCMSABC搜索到的解集能支配HTABC、CSTA解集;對于Kacem2,MCMSABC相對于HTABC能搜索到非支配解(16,73,13),(16,77,11)相對于SAMO-Jaya搜索到非支配解(15,75,12),(16,73,13),(14,77,12),相對于RLNSGA-II搜索到非支配解(16,77,11);對于Kacem3,MCMSABC解集支配HTABC、CSTA解集,并將F2最小值從61變成60;對于Kacem4,MCMSABC均能搜索到每個目標(biāo)的最小值,解集中解的數(shù)量達(dá)到4個,解集支配HTABC解集,相對于SAMO-Jaya搜索到非支配解(8,42,5);對于Kacem5,MCMSABC搜索到的解集支配HTABC、CSTA、RLNSGA-II解集,相對于SAMO-Jaya搜索到非支配解(11,93,10),找到的(11,91,11)支配SAMO-Jaya的(11,93,11).這說明MCMSABC求出的Pareto解集質(zhì)量較好,求解大規(guī)模多目標(biāo)問題具有穩(wěn)定性.觀察到Tcpu時間均較小,說明算法的的時間復(fù)雜度較低,在精度和速度上獲得了平衡.

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

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

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

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

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

(14)

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

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

4 結(jié) 論

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

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