求解柔性作業車間調度問題的混合遺傳算法

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

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

0 引 言

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

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

1 FJSP概述

1.1 問題描述

FJSP問題一般包含n個工件，Job={J1,J2,…,Jn}，每個工件都有一道或多道加工工序，某一工序可以在機器集M中，M={M1,M2,…,Mn}，任意選擇一臺進行生產加工,其加工時間與選擇的機器相關。處理FJSP問題時需要考慮工序的加工順序、加工機器和最大完工時間。該文以“最小化最大完工時間”作為優化目標。

1.2 數學模型

為了便于解釋FJSP的數學模型,相關參數(見表1)如下：

優化目標：

(1)

約束條件：

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

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

(2)

asi,j≥Ei,j-1

(3)

Ej,nj≤Cmax

(4)

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

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)某工件的某工序選擇的加工機器約束:

(7)

表1 FJSP相關參數符號定義

2 混合蛙跳算法

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

圖1 混合蛙跳算法過程

詳細步驟如下：

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

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

圖2 跳變規則

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

3 算法的總體過程

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

圖3 算法整體流程

算法具體步驟如下：

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

Step2：若迭代次數大于MAXGEN，則找到當前最優解作為問題的最終解；否則，執行Step3。

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

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

Step5：根據變異概率pm，從交叉后的種群中選取需要變異操作的個體，進行變異操作。

Step6：選取適應度值高的個體加入遺傳優良種子庫。

Step7：執行混合蛙跳算法，在遺傳優良種子庫中進行局部搜索尋優，更新優良種子庫。

Step8：跳轉執行Step2。

3.1 染色體編碼方案

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

圖4 FJSP染色體編碼示例圖

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

3.2 種群初始化

基于混沌原理所產生的隨機數在限定空間內具有更好的遍歷性和隨機性，并且具有產生速度快、易于實現等特點。將其應用在遺傳算法中，從而提高初始種群在解空間分布的均勻性及降低算法陷入局部最優解的可能性。所以文中所有的隨機參數均為提出的結合Tent映射與Logistic映射的混沌隨機數發生器生成。

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

(8)

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

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

(9)

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

(10)

3.3 選擇操作

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

(11)

3.4 交叉操作

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

3.5 OS部分的交叉操作

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

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

3.6 變異算子

(12)

3.7 優良種子庫

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

4 算法測試與數值實驗

4.1 實驗環境與參數設置

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

4.2 測試用例及實驗結果

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

表2 各算法對MK08算例求解結果對比分析

以20*10即20個工件10臺機器的mk08算例為例，算例描述如表2所示。圖6對比了傳統GA、文獻[6,13]所提算法的性能。可以看出由于文中算法采用了混沌理論使初始解在解空間分布更均勻，所以初始種群的最優值優于傳統GA及文獻[6,13]所提算法，且由于改進了交叉與變異策略及采用了保優策略，算法收斂速度優于其他算法且文中算法得到了目前的mk08算例的最優解。

圖6 mk08算例求解收斂圖

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

圖7 mk08算例調度甘特圖

5 結束語

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