基于正交試驗的機械車間調(diào)度并行遺傳算法參數(shù)優(yōu)化研究*

張生芳，王國慶，馬付建，劉 宇，楊大鵬，沙智華

(大連交通大學 機械工程學院，遼寧 大連 116028)

0 引 言

在大型機械的加工過程中，生產(chǎn)品種和生產(chǎn)設(shè)備的多樣性使得其在生產(chǎn)過程中的組織管理工作更加復(fù)雜化。車間生產(chǎn)調(diào)度是流程工業(yè)和裝備制造業(yè)等相關(guān)工業(yè)企業(yè)生產(chǎn)管理的關(guān)鍵環(huán)節(jié)，合理的生產(chǎn)安排與組織能實現(xiàn)生產(chǎn)過程的最優(yōu)化[1]。

遺傳算法通用性強，具有隱含并行性和全局解空間搜索能力，在生產(chǎn)調(diào)度領(lǐng)域得到了廣泛應(yīng)用[2]。

針對調(diào)度問題的編碼技術(shù)，廖珊等[3]結(jié)合遺傳算法、自適應(yīng)概率和模擬退火算法,重新設(shè)計了基于工件編號的交叉算子和變異算子，提高了算法搜索能力。

在混合遺傳算法方面，Li[4]提出了一種結(jié)合TS算法的混合遺傳算法，改善了算法的搜索能力，提高了求解FJSP問題的效率。

為改進遺傳算法性能，Deb等人[5]對NSGA作了改進，引入了精英保留策略和擁擠度計算，提出了NSGA-Ⅱ算法，提高了算法的性能。朱曉霞等[6]改進了NSGA-Ⅱ算法，采用了合理有效的編解碼方式、遺傳算子和精英策略，解決了協(xié)同制造系統(tǒng)的任務(wù)調(diào)度問題。

借鑒并行理論的高效性，周榮等[7]針對裝卸一體化車輛路徑的成本、路徑、車輛數(shù)等多目標優(yōu)化問題，提出了一種自適應(yīng)并行遺傳算法，并驗證了算法的有效性。陳榮虎等[8]通過對自動化立體倉庫揀選路徑優(yōu)化模型的求解，驗證了并行計算能有效提高算法優(yōu)化效率。李運霞等[9]針對動態(tài)路徑的車間調(diào)度問題，設(shè)計了一種并行遺傳算法，保證了算法的全局搜索性，并采用自適應(yīng)算子，縮短了收斂時間。

圍繞遺傳算法的參數(shù)與算子選擇，HR[10]運用遺傳算法，提出了用田口正交陣列代替全因子實驗設(shè)計，來確定遺傳算法的參數(shù)的方法。劉文豪等[11]以FT06典型車間作業(yè)調(diào)度問題為實例,通過變形遺傳算法實驗,對選擇算子進行了比較分析。洪劉兵等[12]引入人工免疫機制克隆選擇算子和設(shè)計獨特的交叉算子,提高了算法的收斂速度和種群的多樣性。

當前研究主要集中在調(diào)度問題的編碼技術(shù)、混合遺傳算法、動態(tài)自適應(yīng)技術(shù)等方面，但是受種群數(shù)目、交叉概率、變異概率、進化代數(shù)等參數(shù)影響，調(diào)度遺傳算法性能差異較大。

因此，筆者利用正交試驗設(shè)計技術(shù)，研究并行調(diào)度遺傳算法的子群個數(shù)、遷移率、遷移代數(shù)以及各個參數(shù)間的交互作用對算法性能的影響規(guī)律，確定選用優(yōu)化控制參數(shù)的一般方法。

1 調(diào)度并行遺傳算法

1.1 調(diào)度問題描述

調(diào)度問題Job Shop(簡稱JSP)是一類典型的NP問題[13]。

一個3個工件3個加工設(shè)備的典型Job Shop調(diào)度問題(FT03)的算例數(shù)據(jù)如下：

(1)

式中：第1行數(shù)據(jù)—工件1先在設(shè)備2上加工1個單位時間，再在設(shè)備3上加工3個單位時間，最后在設(shè)備1上加工6個單位時間；第i行數(shù)據(jù)—工件i的加工設(shè)備及加工時間。

在滿足工藝約束的同時，該調(diào)度問題還應(yīng)滿足如下約束條件：

(1)同一時間一臺設(shè)備只能加工一個工件；

(2)工件一旦開始加工則不能被中斷；

(3)每個工件的工序必須依次加工。

對于n×m規(guī)模的調(diào)度問題，要求出一個最優(yōu)調(diào)度使最后一個工件完工時間最短，可表示為：

T=min(max(Ci)) (i=1，2，…，n)

(2)

式中：Ci—工件i的完工時間。

1.2 調(diào)度遺傳算法

調(diào)度遺傳算法是通過編碼對潛在調(diào)度解進行表示，然后進行選擇等基本遺傳操作，在潛在解空間里對解進行評估和選擇的算法。

1.2.1 基因編碼與解碼

編碼設(shè)計是遺傳算法應(yīng)用于調(diào)度問題的首要任務(wù)[14]，決定了算法進化過程的效果和效率。Job Shop調(diào)度問題的基因編碼就是對各工件加工先后順序以編碼的形式表現(xiàn)出來。筆者采用文獻[15]所示的雙層整數(shù)編碼方式：第一層為所有工件的加工順序，第二層為工件工序所對應(yīng)的設(shè)備編號。

對于一個n×m規(guī)模的調(diào)度問題，其每層編碼包含n×m位。如式(1)所示的算例，若編碼為：

第一層：2 1 1 3 1 2 3 3 2
第二層：3 2 3 2 1 1 3 1 2

(3)

則解碼時，對應(yīng)某一工件的工序表示為：

Oijk

(4)

式中：Oijk—工件i的工序j在設(shè)備k上加工。

依據(jù)式(3)所示第一層工序碼獲得的加工順序為:O213→O112→O123→O312→O131→O221→O323→O331→O232，對應(yīng)的3×3調(diào)度甘特圖如圖1所示。

圖1 3×3調(diào)度甘特圖

圖1中，最后一個完成加工的為工件2，從開始加工至其加工結(jié)束需32個單位時間，其目標函數(shù)為32。

1.2.2 選擇操作

調(diào)度目標值即最大完工時間T值最小的個體適應(yīng)度最高，應(yīng)以最大概率被選擇。對調(diào)度解目標值從大到小進行排序，個體被選擇的概率為：

Pi=Si/SN

(5)

式中：Si—個體i的排序；SN—總的個體數(shù)。

然后基于輪盤賭的方式選擇交叉?zhèn)€體。每輪產(chǎn)生一個0～1之間的隨機數(shù)，若該隨機數(shù)小于Pi，則該個體被選擇。

1.2.3 交叉操作與變異操作

對于基因串交叉，可以采用基于路徑表示部分匹配交叉操作、順序交叉、循環(huán)交叉等。筆者分別采用二點倒序交叉的方式和二點互換的變異方式。

如式(3)所示的基因編碼，若隨機點為3、7，則交叉操作后基因編碼相應(yīng)變?yōu)椋?/p>

第一層：2 1 3 2 1 3 1 3 2
第二層：3 2 2 1 3 3 1 1 2

(6)

交叉后生成的調(diào)度解加工順序變?yōu)?O213→O112→O312→O221→O123→O323→O131→O331→O232。

如式(6)所示的基因編碼，若隨機點為2、4，則變異操作后基因編碼相應(yīng)變?yōu)椋?/p>

第一層：2 2 3 1 1 3 1 3 2
第二層：3 1 2 2 3 3 1 1 2

(7)

變異后生成的調(diào)度解加工順序變?yōu)?O213→O221→O312→O112→O123→O323→O131→O331→O232。可以看出交叉與變異后基因編碼仍為可行調(diào)度解。

1.3 并行遺傳算法

筆者通過引入并行計算的思想，將遺傳算法中單個種群結(jié)構(gòu)轉(zhuǎn)化為多子群結(jié)構(gòu)[16]。筆者采用文獻[17]所示遷移策略的并行遺傳算法(PGA)的流程圖，如圖2所示。

圖2 并行遺傳算法流程圖

2 正交試驗及結(jié)果分析

2.1 正交試驗因素及水平

此處并行遺傳算法的關(guān)鍵部分為選擇算子、交叉算子、變異算子和遷移算子，主要包括代溝、交叉率、變異率、子群個數(shù)、子群個體數(shù)、插入率、遷移率和遷移代數(shù)8個關(guān)鍵參數(shù)。

筆者選擇三水平試驗，試驗水平表如表1所示。

表1 并行遺傳算法正交試驗水平表

由表1可知：

(1)確定代溝(GGAP)：代溝越大，選擇個體比例越大，交叉?zhèn)€體數(shù)量多，進化速度快。一般代溝應(yīng)為0.5-0.99，實驗值選取{0.5，0.6，0.75}。

(2)確定交叉率(XOVR)：一般交叉率為0.4～0.8，試驗值選取{0.5，0.6，0.7}。

(3)確定變異率(MUTR)：一般變異率為0～0.5，試驗值選取{0.05，0.2，0.5}。

(4)確定子群個數(shù)(SUBPOP)：一般交叉率為2～10，試驗值選取{3，5，7}。

(5)確定子群個體數(shù)(NIND)：群體數(shù)量決定了所能容納的解空間大小。一般為50～500，試驗值選取{50，250，400}。

(6)確定插入率(INSER)：插入率決定了進化后選擇替換原種群的概率。一般為0.1～0.5，試驗值選取{0.5，0.6，0.7}。

(7)確定遷移率(MIGR)：遷移率為各個種群引入精英個體，防止各子群無法跳出局部最優(yōu)，一般為0.1～0.7，試驗值選取{0.1，0.3，0.6}。

(8)確定遷移代數(shù)(MIGGEN)：遷移代數(shù)決定了隔多少代進行一次遷移操作，應(yīng)依據(jù)群體規(guī)模大小和子群數(shù)量選擇，一般為2～8，試驗值選取{3，5，7}。

2.2 正交試驗選擇及結(jié)果

考慮調(diào)度遺傳算法8個關(guān)鍵參數(shù)及GGAP和MUTR、XOVR和MUTR間的交互作用，其正交試驗自由度為8×(3-1)+2×(3-1)2=24<27-1=26，因此，筆者利用Minitab軟件，選取正交設(shè)計表L27(313)，采用6個工件、6個加工設(shè)備的FT06算例進行試驗，將其取得最優(yōu)值的平均運行時間作為試驗指標。

為避免隨機因素的影響，每組試驗重復(fù)20組取其平均值。正交試驗表及結(jié)果如表2所示。

2.3 試驗結(jié)果分析

由表2的數(shù)據(jù)可得極差分析結(jié)果，如表3所示。

表2 正交試驗表及結(jié)果

表3 極差分析結(jié)果

表3中，8種因素對運算時間的影響程度：MUTR>NIND>MIGGEN>SUBPOP>MIGR>GGAP>INSER>XOVR，其中，MUTR、NIND和MIGGEN是主要影響因素，其他是次要影響因素。

主效應(yīng)關(guān)系圖如圖3所示。

圖3 主效應(yīng)關(guān)系圖

圖3中，交叉概率對運算時間的影響相對較小，原因是交叉操作主要作用為大范圍搜索，加之分子群的進化方式優(yōu)化了整體解的分布空間，保證了種群多樣性，且在0.4-0.8的范圍內(nèi)對整體進化過程影響不大。

方差分析結(jié)果如表4所示。

表4 方差分析結(jié)果

表4中，F(xiàn)值反映了各因素間交互作用。

交互作用關(guān)系如圖4所示。

圖4 交互作用關(guān)系圖

由圖4知，曲線之間不平行說明相關(guān)因素間存在交互效應(yīng)，其中，GGAP和MUTR間的交互作用最大，其次是XOVR和MUTR間的交互作用；在并行遺傳算法及相應(yīng)參數(shù)范圍內(nèi)，可以忽略交叉概率與變異率的交互影響。

3 并行遺傳算法參數(shù)優(yōu)選及驗證

3.1 算法性能分析

此處取GGAP=0.75、XOVR=0.6、MUTR=0.05、INSER=0.2；為使種群規(guī)模相同，單種群遺傳算法SUBPOP=1、NIND=1 750、MIGGEN=無窮(即不采取遷移操作)；并行多子群遺傳算法SUBPOP=7、NIND=250、MIGGEN=3、MIGR=0.3。

兩種算法運行中，種群最優(yōu)解及子群平均解進化圖分別如圖5所示。

圖5 單種群與并行多種群進化對比圖

圖5顯示：(1)單種群遺傳算法在130代左右達到最優(yōu)解，而并行遺傳算法在35代左右已達到最優(yōu)值，求解時間縮短；(2)從整群最優(yōu)值來看，多種群并行遺傳算法成梯度式下降，明顯改善了單種群種群過早收斂現(xiàn)象。

下面對算法的求解質(zhì)量和求解時間進行分析：

(1)從收斂性能來看，并行遺傳算法主要是針對普通遺傳算法搜索效率不高和過早收斂問題，通過增加并行子群的方式以分解解空間，利用種群隔離保證了種群多樣性，同時保留優(yōu)良個體基因，避免了種群同化；

(2)從并行性能來看，并行遺傳算法削弱了普通遺傳算法中交叉操作的重要性，降低了交叉率對整體算法中全局搜索的影響。在保持總?cè)后w規(guī)模不變的情況下，并行遺傳算法能夠充分利用各個計算進程，減少運算時間，改善算法性能；

(3)從參數(shù)影響來看，并行遺傳算法改善了普通遺傳算法中交叉概率與變異概率的交互作用，取而代之的是種群數(shù)量、遷移率、遷移代數(shù)之間的影響。

3.2 參數(shù)選取及驗證

綜合考慮，筆者針對FT06問題，MUTR選水平1，NIND選水平1，MIGGEN選水平1，SUBPOP選水平2，MIGR選水平2，GGAP選水平2，INSER選水平1，XOVR選水平2。

隨著問題規(guī)模的擴大，可通過適當增大子群個體數(shù)或子群數(shù)量來增大解容量，同時增大遷移概率及遷移代數(shù)，以適應(yīng)不同規(guī)模調(diào)度問題的求解。

在以上參數(shù)選取的基礎(chǔ)上，筆者針對FT06、FT10、FT20調(diào)度問題進行研究，選取的參數(shù)及相關(guān)運行結(jié)果如表5所示。

表5 并行遺傳算法參數(shù)及結(jié)果

4 結(jié)束語

針對調(diào)度并行遺傳算法受參數(shù)影響，同一規(guī)模調(diào)度問題的求解性能大不相同的問題，筆者采用正交試驗方法，研究了調(diào)度并行遺傳算法中子群個數(shù)、子群個體數(shù)、代溝等8個因素對運行時間的影響規(guī)律。主要結(jié)論如下：

(1)在子群個數(shù)2～8，子群個體數(shù)10～500，代溝0.5～1，交叉率0.4～0.8，變異率0～0.5，插入率0.1～0.6，遷移率0.1～0.7，遷移代數(shù)2～8的范圍內(nèi)，MUTR、NIND和MIGGEN對進化過程對運行時間的影響最大，其他因素的影響程度相比略小。同時，3種因素間存在交互作用，GGAP和MUTR交互作用>XOVR和MUTR交互作用；

(2)在建立調(diào)度并行遺傳算法時，在參數(shù)范圍內(nèi)，可不考慮GGAP與MUTR，XOVR與MUTR間的交互作用。并行子群的方式，能夠保證子群多樣性，一定程度上解決普通遺傳算法過早收斂的問題；

(3)利用所得參數(shù)優(yōu)選規(guī)律，對FT10和FT20類典例進行了試驗，結(jié)果表明：所選參數(shù)能夠有效改善進化過程，在保證算法結(jié)果的基礎(chǔ)上縮短運算時間；通過正交試驗的方式優(yōu)選并行遺傳算法參數(shù)，以改善算法性能的方法是有效的。