求解柔性作業(yè)車間調(diào)度問題的混合遺傳算法

李雪花，高全力，趙 輝，楊 昊，金 帥，徐國梁

(1.西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710048;2.山東如意毛紡服裝集團(tuán)股份有限公司，山東 濟(jì)寧 272000;3.山東如意恒成產(chǎn)研新材料科技有限公司，山東 濟(jì)寧 272000)

0 引 言

柔性作業(yè)車間調(diào)度問題(Flexible Job-Shop Scheduling Problem，F(xiàn)JSP)是離散制造業(yè)、流程工業(yè)等實(shí)際生產(chǎn)中的核心問題。FJSP問題是JSP(Job-shop Scheduling Problem)問題的擴(kuò)展，包括復(fù)雜的約束條件，包括對(duì)每個(gè)工序加工時(shí)間，工序的加工順序，以及加工設(shè)備的約束。因此，F(xiàn)JSP是一個(gè)典型的NP難問題。解決FJSP問題的常見方法是群智能算法，一些最常用的算法包括遺傳算法、粒子群算法、魚群算法等。

遺傳算法(Genetic Algorithm，GA)是一種通過模擬自然進(jìn)化機(jī)制來搜尋最優(yōu)解的全局優(yōu)化算法[1]，全局搜索能力強(qiáng)，具有可擴(kuò)展性，容易與其他算法結(jié)合，但其局部搜索能力較差，容易“早熟”收斂，且對(duì)初始種群的選擇有一定的依賴性[2]。近些年來一些學(xué)者通過融合遺傳算法與其他算法來改善其魯棒性，實(shí)現(xiàn)性能提升。陶澤等融合了遺傳算法和模擬退火算法，從而提高了種群的收斂速度并防止種群陷入局部最優(yōu)[3]。LI等提出一種將禁忌搜索算法與遺傳算法有效結(jié)合的禁忌混合遺傳算法，增強(qiáng)了遺傳算法局部搜索能力，但計(jì)算成本較高[4]。楊振泰等提出了一種結(jié)合powell搜索法的遺傳算法，改善了GA算法在迭代過程中產(chǎn)生比可行解的情況[5]。賈培豪等融合鯨魚算法和遺傳算法，改進(jìn)傳統(tǒng)遺傳算法后期的局部搜索能力，提高算法求解質(zhì)量[6]。綜上所述,標(biāo)準(zhǔn)的遺傳算法融合其他算法是求解FJSP問題的趨勢(shì)所在。該文提出一種混合遺傳算法，在遺傳算法的基礎(chǔ)上，在初始種群生成時(shí)采用混沌理論產(chǎn)生分布均勻的隨機(jī)數(shù)提高初始種群在解空間分布的均勻性，且根據(jù)FJSP問題特性改進(jìn)交叉、變異規(guī)則,將表現(xiàn)優(yōu)異的個(gè)體加入優(yōu)良種子庫進(jìn)行保護(hù)。并采用混合蛙跳算法對(duì)優(yōu)良種子庫進(jìn)行局部搜索尋優(yōu),將得到的更優(yōu)解與下輪個(gè)體交叉迭代,提高局部搜索能力，改善傳統(tǒng)遺傳算法“早熟”問題。通過對(duì)mk01～mk10標(biāo)準(zhǔn)算例進(jìn)行仿真實(shí)驗(yàn),驗(yàn)證了該算法的有效性與可行性。

1 FJSP概述

1.1 問題描述

FJSP問題一般包含n個(gè)工件，Job={J1,J2,…,Jn}，每個(gè)工件都有一道或多道加工工序，某一工序可以在機(jī)器集M中，M={M1,M2,…,Mn}，任意選擇一臺(tái)進(jìn)行生產(chǎn)加工,其加工時(shí)間與選擇的機(jī)器相關(guān)。處理FJSP問題時(shí)需要考慮工序的加工順序、加工機(jī)器和最大完工時(shí)間。該文以“最小化最大完工時(shí)間”作為優(yōu)化目標(biāo)。

1.2 數(shù)學(xué)模型

為了便于解釋FJSP的數(shù)學(xué)模型,相關(guān)參數(shù)(見表1)如下：

優(yōu)化目標(biāo)：

(1)

約束條件：

(1)每道工序的加工時(shí)間約束：

Si,j+pi,j,k≤Ei,j

(2)

asi,j≥Ei,j-1

(3)

Ej,nj≤Cmax

(4)

(2)同一工件的相鄰兩道工序的加工時(shí)間約束:

Ei,j≤Si,j+1j+1≤ni

(5)

(Si,j+pi,j,.k)bi,j,p,q≤Sp,q,i≠p或j≠q

(6)

(3)某工件的某工序選擇的加工機(jī)器約束:

(7)

表1 FJSP相關(guān)參數(shù)符號(hào)定義

2 混合蛙跳算法

SFLA(Shuffled Frog Leaping Algorithm)[7]是根據(jù)青蛙種群在石塊上覓食時(shí)的分布變化而提出的算法。青蛙所在的池塘中有若干石塊，青蛙們會(huì)按照特定規(guī)則被分配到石塊相應(yīng)位置上。每個(gè)青蛙的位置代表了問題的一個(gè)可行解。在每一代中，每個(gè)石塊上處于最差位置的青蛙會(huì)跳動(dòng)，該青蛙首先會(huì)朝向位于同一石塊上最優(yōu)位置的青蛙跳動(dòng)，若跳動(dòng)后的新位置比原來位置差則向著全局最優(yōu)位置跳動(dòng)，若該位置仍舊比原位置差則再在解空間內(nèi)隨機(jī)跳動(dòng)一次，可見可以跳動(dòng)的青蛙最少跳動(dòng)一次，最多跳動(dòng)三次。當(dāng)每個(gè)石塊上的青蛙都跳動(dòng)后，將各個(gè)石塊上的青蛙合并，并重新合并然后分組，重復(fù)上述跳動(dòng)過程，直到滿足終止條件。流程如圖1所示。

圖1 混合蛙跳算法過程

詳細(xì)步驟如下：

Step1：將優(yōu)良種子庫中的種群作為青蛙種群分為K個(gè)組，位列第1的青蛙被分配給第1組，位列第2的青蛙分配給第2組，以次類推，直至將所有青蛙分別分配到K個(gè)組中，每個(gè)組中包含N/K個(gè)青蛙。

Step2：對(duì)每組執(zhí)行搜索過程。每組中排在最后位置的青蛙R向這個(gè)組中位置第一的青蛙F跳變，跳變規(guī)則為：Oi,j為R青蛙的OS部分與F青蛙的OS部分相異的基因位表示的工序，將此工序當(dāng)前安排的加工機(jī)器替換為此工序可選機(jī)器中時(shí)間加工最短的機(jī)器。若有多個(gè)相異工序，則全部替換。如圖2，F(xiàn)青蛙與R青蛙第三個(gè)位置的基因不同，此基因代表的工序是O3,1，因此根據(jù)規(guī)則將R青蛙MS部分代表O3,1的加工機(jī)器3替換為時(shí)間更短的加工機(jī)器2。然后計(jì)算R青蛙的適應(yīng)度值，若優(yōu)于位置第一的染色體，則替換其位置，否則繼續(xù)變換。

圖2 跳變規(guī)則

Step3：判斷是否滿足停止條件，如滿足停止條件則停止。如不滿足則跳轉(zhuǎn)Step2執(zhí)行。為防止將解劣化，若R青蛙沒有跳動(dòng)則此青蛙保持原來的值。

3 算法的總體過程

整體算法流程如圖3所示。

圖3 算法整體流程

算法具體步驟如下：

Step1：采用1.2節(jié)提出的混沌隨機(jī)數(shù)發(fā)生器生成隨機(jī)數(shù)，并結(jié)合GLR機(jī)器選擇法[8]，其中GS:LS:RS=0.6:0.3:0.1，從而生成分布均勻且個(gè)體適應(yīng)度較好的初始種群，個(gè)體適應(yīng)度值為Fi=1/Cmax。

Step2：若迭代次數(shù)大于MAXGEN，則找到當(dāng)前最優(yōu)解作為問題的最終解；否則，執(zhí)行Step3。

Step3：采用輪盤賭選擇法從種群中選擇子代種群。

Step4：以概率pc在Step3選擇的子代種群中選擇進(jìn)行交叉操作的部分個(gè)體，再以交叉方式選擇概率px選擇采取何種交叉方式。

Step5：根據(jù)變異概率pm，從交叉后的種群中選取需要變異操作的個(gè)體，進(jìn)行變異操作。

Step6：選取適應(yīng)度值高的個(gè)體加入遺傳優(yōu)良種子庫。

Step7：執(zhí)行混合蛙跳算法，在遺傳優(yōu)良種子庫中進(jìn)行局部搜索尋優(yōu)，更新優(yōu)良種子庫。

Step8：跳轉(zhuǎn)執(zhí)行Step2。

3.1 染色體編碼方案

文中染色體編碼方案采用MS-OS編碼方案[6]，如圖4所示，包括四個(gè)工件，每個(gè)工件包括兩道工序。染色體編碼分成兩部分：OS(Operations Sequencing)部分與MS(Machines Selection)部分。OS部分有Osum位，數(shù)字i出現(xiàn)的第j次,代表工序Oi,j。例如圖4中OS部分的第一個(gè)“1”代表O1,1，即第一個(gè)工件的第一道工序，第二個(gè)1代表O1,2，即第一個(gè)工件的第二道工序。

圖4 FJSP染色體編碼示例圖

MS部分也有Osum位，按工件順序排列，第i個(gè)工件領(lǐng)域的第j位置數(shù)字m，表示Oi,j選擇其可選加工機(jī)器的第m個(gè)機(jī)器進(jìn)行加工。如圖4中MS部分有四個(gè)工件，每個(gè)工件有兩道工序，J1領(lǐng)域的第一位數(shù)字“1”，代表O1,1工序選擇在O1,1的可選加工機(jī)器集合Mi,j中的第1個(gè)機(jī)器上；J1領(lǐng)域的第二位數(shù)字“2”，代表O1,2工序需要安排在O1,2的可選加工機(jī)器集合Mi,j中的第1個(gè)機(jī)器上。解碼時(shí)，當(dāng)工序Oi,j被安排在機(jī)器k，即mi,j,k=1，檢查機(jī)器k所有空閑時(shí)區(qū)[ts,te]，若存在區(qū)間滿足max(asi,j,ts)+pi,j,k≤te，則將工序Oi,j插入到區(qū)間[ts,te]中，且Si,j=ts。若不存在則放置到機(jī)器加工隊(duì)列最后。

3.2 種群初始化

基于混沌原理所產(chǎn)生的隨機(jī)數(shù)在限定空間內(nèi)具有更好的遍歷性和隨機(jī)性，并且具有產(chǎn)生速度快、易于實(shí)現(xiàn)等特點(diǎn)。將其應(yīng)用在遺傳算法中，從而提高初始種群在解空間分布的均勻性及降低算法陷入局部最優(yōu)解的可能性。所以文中所有的隨機(jī)參數(shù)均為提出的結(jié)合Tent映射與Logistic映射的混沌隨機(jī)數(shù)發(fā)生器生成。

Tent混沌映射生成器[9]的迭代公式如下:

(8)

Tent映射是在區(qū)間[0,1]之間的兩個(gè)分段的線性迭代,包含一個(gè)參數(shù),其中γ為常數(shù)，γ∈[0,1]。序列的計(jì)算過程為：在區(qū)間(0，1)中任意選擇一個(gè)初始迭代點(diǎn)，迭代計(jì)算Xn+1即可得到一個(gè)該區(qū)間上的混沌映射。Logistic混沌映射的迭代公式如下[10]:

Xn+1=f(xn)=α×xn×(1-xn),0

(9)

其中，α為Logistic參數(shù)，當(dāng)3.569 945 6<α≤4時(shí)，迭代生成的值非周期，有良好的隨機(jī)性。n為其迭代次數(shù)。 該文將Logistic結(jié)合Tent得到隨機(jī)數(shù)生成器，取α=4,γ=0.5。其迭代公式如下：

(10)

3.3 選擇操作

采用輪盤賭選擇法從種群中選擇子代種群[8]，個(gè)體選中的概率與其適應(yīng)度函數(shù)值成正比，即適應(yīng)度越大被選擇進(jìn)行交叉操作的概率Pi越大。Pi計(jì)算方式如下：

(11)

3.4 交叉操作

機(jī)器選擇MS部分采用均勻交叉方式交叉，即依次掃描每個(gè)基因，以概率PS與對(duì)位基因進(jìn)行交叉操作，PS為0.5，如混沌隨機(jī)數(shù)大于PS，則與對(duì)位基因互換，否則不互換。

3.5 OS部分的交叉操作

OS交叉操作選擇改進(jìn)SEX[8](子路徑交交換交叉)交叉方式，如圖5所示。隨機(jī)劃分工件為兩個(gè)非空集合，隨機(jī)選擇其中一個(gè)集合，在兩個(gè)父代染色體中選中此集合基因，然后順序交換兩個(gè)父代其余位置基因，得到兩個(gè)子代。

圖5 子路徑交交換交叉示意圖

3.6 變異算子

(12)

3.7 優(yōu)良種子庫

遺傳算法中交叉算子全部來自于當(dāng)前種群，即有可能當(dāng)前種群經(jīng)過選擇的優(yōu)秀個(gè)體在交叉時(shí)被破壞了。為了解決這一問題，該文采用優(yōu)良遺傳庫策略，將當(dāng)前種群產(chǎn)生的優(yōu)良個(gè)體加入優(yōu)良種子庫，并利用混合蛙跳算法(SFLA)針對(duì)OS序列對(duì)應(yīng)的MS序列尋優(yōu)，從而得到更優(yōu)的目標(biāo)函數(shù)，得到的更優(yōu)解供下一輪迭代的交叉操作，從而保留優(yōu)秀個(gè)體并有目的性地對(duì)MS序列進(jìn)行優(yōu)化。

4 算法測(cè)試與數(shù)值實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

為檢驗(yàn)該算法的有效性與可行性，通過Brandimarte(mk01～mk10)[12]算例對(duì)算法進(jìn)行測(cè)試。算法實(shí)現(xiàn)采用JAVA語言，實(shí)驗(yàn)環(huán)境為windows10系統(tǒng)，處理器為Intel i7 10750H 六核CPU、主頻為2.60 GHz、內(nèi)存16 GB。種群規(guī)模Size=200，最大迭代次數(shù) MAXGEN=200；交叉概率pc=0.8，交叉方式選擇概率px=0.3，變異概率pm=0.05；優(yōu)良種子庫的容量Cseed為種群規(guī)模的10%。為充分體現(xiàn)混合蛙跳算法尋優(yōu)能力，其分組個(gè)數(shù)K=10。

4.2 測(cè)試用例及實(shí)驗(yàn)結(jié)果

將mk01～mk10分別計(jì)算10次，記錄最優(yōu)值及平均值，將其與文獻(xiàn)[6,13]提出的算法結(jié)果及一般GA算法結(jié)果進(jìn)行比較，如表2所示，可以看出除了mk06與mk07算例，其他均得到了所對(duì)比算法中的最優(yōu)解，驗(yàn)證了文中算法的有效性。

表2 各算法對(duì)MK08算例求解結(jié)果對(duì)比分析

以20*10即20個(gè)工件10臺(tái)機(jī)器的mk08算例為例，算例描述如表2所示。圖6對(duì)比了傳統(tǒng)GA、文獻(xiàn)[6,13]所提算法的性能?？梢钥闯鲇捎谖闹兴惴ú捎昧嘶煦缋碚撌钩跏冀庠诮饪臻g分布更均勻，所以初始種群的最優(yōu)值優(yōu)于傳統(tǒng)GA及文獻(xiàn)[6,13]所提算法，且由于改進(jìn)了交叉與變異策略及采用了保優(yōu)策略，算法收斂速度優(yōu)于其他算法且文中算法得到了目前的mk08算例的最優(yōu)解。

圖6 mk08算例求解收斂圖

圖7為文中算法對(duì)mk08算例的最佳調(diào)度甘特圖，查閱mk08算例的源文件得知任何工件的任何工序都沒有涉及到使用機(jī)器6，從圖中也可以看到機(jī)器6為空閑狀態(tài)，從而也從側(cè)面驗(yàn)證了文中算法的可行性與正確性。

圖7 mk08算例調(diào)度甘特圖

5 結(jié)束語

針對(duì)柔性作業(yè)車間調(diào)度中最小化最大完工時(shí)間單目標(biāo)，提出一種融合遺傳算法與混合蛙跳算法的混合算法。對(duì)遺傳算法的變異與交叉規(guī)則根據(jù)柔性作業(yè)車間調(diào)度問題的特性進(jìn)行了改進(jìn)，合理改進(jìn)了算法搜索過程的廣度與深度。通過對(duì)Brandimarte算例的測(cè)試，驗(yàn)證了該算法的可行性與有效性。并運(yùn)用混沌理論生成隨機(jī)數(shù)以使初始解在解空間分布更均勻，設(shè)計(jì)一種存優(yōu)策略，且運(yùn)用混合蛙跳算法提高了局部搜索能力。在未來的研究中，將考慮優(yōu)化數(shù)學(xué)模型，考慮更多影響因素，并且考慮與文獻(xiàn)[14]所用布谷鳥算法融合，使其更符合實(shí)際的生產(chǎn)環(huán)境。