改進(jìn)遺傳算法對(duì)實(shí)際JobShop問(wèn)題的解決

陶麗華，許之強(qiáng)

（長(zhǎng)春工業(yè)大學(xué) 機(jī)電工程學(xué)院，長(zhǎng)春 130012）

0 引言

Job shop（JSP）問(wèn)題作為典型的NP-hard 問(wèn)題一直是制造自動(dòng)化領(lǐng)域中的經(jīng)典和熱點(diǎn)問(wèn)題，設(shè)計(jì)求解JSP 的有效算法一直是調(diào)度優(yōu)化領(lǐng)域的重要課題。

遺傳算法（GA）作為一種全局優(yōu)化搜索算法，具有簡(jiǎn)單、高效、很容易與其他算法相結(jié)合［1］的特點(diǎn)，國(guó)內(nèi)外學(xué)者對(duì)遺傳算法的應(yīng)用進(jìn)行了大量的研究。但是在應(yīng)用GA 求解實(shí)際生產(chǎn)調(diào)度中的JSP 問(wèn)題時(shí)，常常由于產(chǎn)品工藝復(fù)雜，生產(chǎn)約束條件較多，對(duì)傳統(tǒng)遺傳算法在編碼方式、遺傳算子和解碼方式的設(shè)計(jì)上提出了很高的要求，標(biāo)準(zhǔn)的遺傳算法常常會(huì)因?yàn)樗阉餍实?、容易提前收斂、陷入局部最?yōu)解等問(wèn)題而無(wú)法滿(mǎn)足企業(yè)生產(chǎn)調(diào)度的實(shí)際需要。

本文根據(jù)離散制造業(yè)中典型的Job Shop 調(diào)度問(wèn)題的需求，在標(biāo)準(zhǔn)遺傳算法全局搜索的基礎(chǔ)上，利用極值優(yōu)化算法對(duì)遺傳算子進(jìn)行改進(jìn)，提出了一種具有基于工序的編碼、活動(dòng)解碼、自適應(yīng)交叉和變異運(yùn)算的改進(jìn)遺傳算法，并通過(guò)軟件仿真實(shí)驗(yàn)，驗(yàn)證了改進(jìn)遺傳算法的性能。

1 JobShop 問(wèn)題描述

典型的Job Shop 調(diào)度問(wèn)題可描述為：有n 個(gè)工件可在m 臺(tái)機(jī)器上加工，每個(gè)工件由多道工序加工完成，需要考慮如下約束：

1）每個(gè)工件必須按照工藝約束要求按順序依次在指定的機(jī)器上加工，即必須在每個(gè)工件的前一道工序加工完成后才可以開(kāi)始后一道工序；

2）工件在一臺(tái)機(jī)器上一旦開(kāi)始加工，便不可以中斷，必須等到此工件加工完成后，才能在該機(jī)器上加工另外的工件，即一臺(tái)機(jī)器在某一時(shí)刻只能加工一個(gè)工件；

3）兩臺(tái)或多臺(tái)機(jī)器不能同時(shí)加工一個(gè)工件；

4）兩個(gè)或多個(gè)工件不能同時(shí)在一臺(tái)機(jī)上加工；

5）工件加工工藝事先給定。

JobShop 調(diào)度問(wèn)題就是求解最小加工周期的最優(yōu)化調(diào)度方案。

2 極值優(yōu)化算法

極值優(yōu)化算法（EO）是在國(guó)際遺傳與進(jìn)化計(jì)算會(huì)議上，Boettcher 受自組織臨界理論的啟發(fā)而提出的一種優(yōu)化算法，其具有統(tǒng)計(jì)物理中的遠(yuǎn)離平衡態(tài)的動(dòng)力學(xué)特征［2-3］。該算法與諸如蟻群算法、模擬退火算法（SA）、遺傳算法（GA）等傳統(tǒng)智能優(yōu)化算法不同的是，EO 算法不會(huì)收斂到一個(gè)平衡狀態(tài)，其總是選擇當(dāng)前解中適應(yīng)度最差的相互關(guān)聯(lián)的變量進(jìn)行變異，產(chǎn)生的波動(dòng)使算法具有更好地跳出局部最優(yōu)解并繼續(xù)搜索的能力。EO算法易于實(shí)現(xiàn)，算法調(diào)節(jié)參數(shù)相對(duì)較少，算法效果好，而且還具有收斂速度快、局部搜索能力強(qiáng)等特點(diǎn)。EO算法流程如圖1 所示。

圖1 EO 算法流程圖

3 改進(jìn)遺傳算法設(shè)計(jì)

通過(guò)改進(jìn)選擇操作、自適應(yīng)的交叉算子和自適應(yīng)的變異算子可以有效地克服標(biāo)準(zhǔn)遺傳算法對(duì)參數(shù)要求高的的缺點(diǎn)，將極值優(yōu)化算法具有的容易跳出局部最優(yōu)解的特點(diǎn)與標(biāo)準(zhǔn)遺傳算法的全局搜索相結(jié)合，可有效地改善遺傳算法的尋優(yōu)性能。

3.1 基于工序的染色體編碼

求解JSP 問(wèn)題的遺傳算法的編碼必須考慮染色體的可行性、合法性、有效性以及對(duì)問(wèn)題解空間表征的完全性。本文采用一種基于工序的染色體編碼方式，每個(gè)染色體都是由多個(gè)基因組成的有序集，每個(gè)基因元素代表工件的一道工序，每個(gè)染色體由各工件的所有工序的有序排列組成，染色體基因的數(shù)量等于各工件工序的總數(shù)，同一個(gè)工件的各工序使用相同的數(shù)字符號(hào)［4］，在染色體中數(shù)字符號(hào)出現(xiàn)的先后次序代表該工件的不同工序。以3 工件/3 機(jī)床調(diào)度問(wèn)題為例，染色體［2，2，1，3，2，3，3，1，1］表示每個(gè)工件都有3 道工序，第一個(gè)“2”代表工件2 的第1道序，第二個(gè)“2”代表工件2 的第2 道序，第三個(gè)“2”代表工件2 的第3 道序等等。

3.2 活動(dòng)解碼

解碼問(wèn)題是“基因型”到“表現(xiàn)型”的轉(zhuǎn)換，也就是將染色體型解轉(zhuǎn)化為所求問(wèn)題的解［5］。由第1 節(jié)可知，編碼是調(diào)度方案的基因形式，種群產(chǎn)生之后要進(jìn)行基因型到表現(xiàn)型的映射，即設(shè)計(jì)解碼操作。本文采用活動(dòng)調(diào)度方法設(shè)計(jì)解碼操作，即從染色體的第一位基因開(kāi)始，依次將每個(gè)基因所代表的工序安排到相應(yīng)的設(shè)備上。具體方法如下：

1）從染色體的第一位基因開(kāi)始，查找基因在工藝表中所使用的設(shè)備和工時(shí)，如染色體［2，2，1，3，2，3，3，1，1］，若查找的基因?yàn)榈谝晃?，由3.1 節(jié)可知為工件2 的第一道工序，查工藝表得到所使用的機(jī)床號(hào)m′和工時(shí)p′。

2）判斷機(jī)床m′從開(kāi)始時(shí)刻到當(dāng)前時(shí)刻的各加工空閑能否滿(mǎn)足工件2 的第一道工序的插入。判斷的工序如果不是第一道工序，還需要考慮工件的工藝約束問(wèn)題，即該工序插入的開(kāi)始時(shí)間一定要大于其前一道工序的完成時(shí)間。

3）若能滿(mǎn)足插入條件，則在最早出現(xiàn)的空閑時(shí)間段，按照最早開(kāi)始時(shí)間原則插入該工序。

4）依次判斷染色體的下一位基因，直到把每個(gè)基因所代表的工序都安排到機(jī)器上為止。

3.3 適應(yīng)度函數(shù)

在遺傳算法中，適應(yīng)值體現(xiàn)個(gè)體在生存環(huán)境中的適應(yīng)程度，適應(yīng)程度高的個(gè)體將獲得更多的產(chǎn)生后代的機(jī)會(huì)。適應(yīng)值用fn表示，fn可以從目標(biāo)值Pn轉(zhuǎn)化來(lái)：

其中，k 主要用于放大或縮小fn的值以便于計(jì)算機(jī)處理，避免由于fn太小而導(dǎo)致超出計(jì)算機(jī)精度，b 值主要調(diào)節(jié)種群個(gè)體的適應(yīng)度差異。

3.4 基于改進(jìn)輪盤(pán)賭的選擇操作

選擇是遺傳算法中體現(xiàn)染色體優(yōu)劣競(jìng)爭(zhēng)的階段。最常用的“輪盤(pán)賭法”主要根據(jù)個(gè)體的適應(yīng)度值占所有個(gè)體適應(yīng)度總和的百分比進(jìn)行選擇，其優(yōu)點(diǎn)是對(duì)適應(yīng)度低的個(gè)體給予選擇的機(jī)會(huì)，缺點(diǎn)是種群中個(gè)體的適應(yīng)度差異過(guò)大則容易陷入局部最優(yōu)，差異過(guò)小將導(dǎo)致進(jìn)化緩慢，因此，本文對(duì)輪盤(pán)賭法進(jìn)行改進(jìn)，首先根據(jù)個(gè)體適應(yīng)值從大到小進(jìn)行排序，然后，對(duì)每個(gè)個(gè)體按排列的順序依次定義每個(gè)個(gè)體的適應(yīng)率，定義的方法如式（2），其中種群數(shù)量為M，適應(yīng)值越大的個(gè)體的適應(yīng)率越大，個(gè)體間適應(yīng)率成等比數(shù)列，公比為1-q，所有個(gè)體的適應(yīng)率之和為1。最后，根據(jù)個(gè)體的適應(yīng)率進(jìn)行選擇操作。

3.5 自適應(yīng)交叉算子的設(shè)計(jì)

為了使子代能夠繼承父代的優(yōu)良基因，且不出現(xiàn)非法解。本文采用一種改進(jìn)的順序交叉法（POX）。若配對(duì)的兩個(gè)父代染色體為v1和v2，隨機(jī)產(chǎn)生工件集｛1，2，3，…，n｝的一個(gè)非空子集J1。然后，復(fù)制v1中包含有J1中的基因到子代v1′中，并保留它們的位置；在配對(duì)的另一個(gè)父染色體v2中刪除J1所包含的基因，并從左到右依次填入子染色體v1′中的空白基因位。同理，復(fù)制v2中包含有J1中的基因到子代v2′中，并保留它們的位置；然后在配對(duì)的另一個(gè)父染色體v1中刪除J1所包含的基因，并從左到右依次填入子染色體v2′中的空白基因位。POX 交叉操作實(shí)例見(jiàn)圖2 所示。

圖2 交叉操作示實(shí)例

在進(jìn)化過(guò)程中為了能盡量地保留較優(yōu)的個(gè)體，盡快淘汰較差的個(gè)體，采用自適應(yīng)交叉概率進(jìn)行種群的交叉運(yùn)算，即當(dāng)兩個(gè)父代個(gè)體適應(yīng)度的平均值低于種群平均適應(yīng)度值時(shí)，需要提高交叉概率，以便能盡快產(chǎn)生新的個(gè)體，淘汰較差的個(gè)體；當(dāng)兩個(gè)父代個(gè)體適應(yīng)度的平均值高于種群平均適應(yīng)度值時(shí)，需要降低交叉概率，盡量保留較優(yōu)個(gè)體。自適應(yīng)交叉概率

式中：Pc為自適應(yīng)交叉概率；Pc_max為最大交叉概率，Pc_min為最小交叉概率，fmax為種群最優(yōu)解適應(yīng)值，favg為種群平均適應(yīng)值，f′為兩個(gè)父染色體適應(yīng)值的平均值。

3.6 自適應(yīng)變異算子的設(shè)計(jì)

為了使變異操作既增加種群的多樣性，同時(shí)又能得到性能較好的子代，本文采用一種基于鄰域搜索的變異操作，即通過(guò)變異運(yùn)算在鄰域范圍內(nèi)產(chǎn)生多個(gè)子代，選擇性能較好的子代作為變異后的個(gè)體。具體操作如下：

1）產(chǎn)生一個(gè)隨機(jī)數(shù)η，0＜η＜1，如果η 小于變異概率Pm，轉(zhuǎn)步驟2），否則轉(zhuǎn)步驟4）。

2）在父代染色體中，隨機(jī)選取k 個(gè)基因位，k＞2，然后，在k 個(gè)基因位置上對(duì)k 個(gè)基因進(jìn)行排序，將每個(gè)排序的結(jié)果作為子代上該位置的基因，可得到k！個(gè)子染色體；最后，刪除父染色體中k 個(gè)基因位置上的基因后，將剩余的基因從左到右依次填入每個(gè)子染色體中可得到k！個(gè)子染色體。

3）評(píng)價(jià)k！個(gè)子染色體的適應(yīng)值，選取最優(yōu)的一個(gè)子染色體作為變異結(jié)果。

4）結(jié)束。

為了能盡量地保留較優(yōu)的個(gè)體，盡快淘汰較差的個(gè)體，變異操作采用自適應(yīng)變異策略來(lái)改善進(jìn)化性能，自適應(yīng)變異公式為

式中：Pm為自適應(yīng)變異概率，Pm_max為最大變異概率，Pm_min為最小變異概率，fmax為種群最優(yōu)解適應(yīng)值，favg為種群平均適應(yīng)值，f′為父染色體適應(yīng)值。

3.7 精英保留策略

在標(biāo)準(zhǔn)遺傳算法中由于遺傳算子操作的隨機(jī)性可能造成最優(yōu)個(gè)體的丟失，甚至導(dǎo)致收斂周期較長(zhǎng)［6-9］的問(wèn)題，本文擬采用精英保留策略解決該問(wèn)題。在每一代進(jìn)化過(guò)程中，將子代種群的最優(yōu)個(gè)體與父代種群的最優(yōu)個(gè)體進(jìn)行比較，若子代的好，則子代直接進(jìn)入下一代父代種群；若父代的好，則父代的最優(yōu)個(gè)體隨機(jī)替換子代的任意個(gè)體，生成的種群作為下一代父代種群，這樣就可以避免最優(yōu)個(gè)體的丟失。

3.8 基于極值優(yōu)化算法的變異算子

在GA 算法的進(jìn)化過(guò)程中，由于最優(yōu)個(gè)體的適應(yīng)值遠(yuǎn)遠(yuǎn)大于平均適應(yīng)值，若按照適應(yīng)值比例進(jìn)行選擇的話(huà)，會(huì)導(dǎo)致種群中較優(yōu)個(gè)體的數(shù)目迅速增加，從而容易陷入局部最優(yōu)。雖然在GA 中采用自適應(yīng)變異算子在一定程度上保證了種群的多樣性，但其概率比較小，也無(wú)法徹底解決算法提前收斂的問(wèn)題。因此，本文采用極值優(yōu)化（EO）算法，針對(duì)種群中最差的染色體進(jìn)行局部尋優(yōu)，逐步淘汰種群中適應(yīng)度最差的個(gè)體，在保持種群多樣性的情況下達(dá)到對(duì)整個(gè)種群進(jìn)化的目的［10-11］。極值優(yōu)化算法步驟如下：

1）i=1，選出當(dāng)代適應(yīng)值最小的染色體X，其適應(yīng)值為P；

2）在染色體X 上隨機(jī)取λ 個(gè)不同的基因做變異操作，變異方法見(jiàn)3.6 節(jié)，產(chǎn)生多個(gè)染色體Xi，求出每個(gè)Xi的適應(yīng)值Pi；

3）找出Pi中適應(yīng)值最大的Pim對(duì)應(yīng)的染色體Xim；

4）如果Pim＞P，則X 會(huì)被Xim替換，否則X 保持不變；

5）如果i＜Psize（Psize為種群大小)，那么i=i+1，返回步驟1）。

3.9 改進(jìn)的遺傳算法流程

本文將啟發(fā)式算法、極值優(yōu)化算法和自適應(yīng)策略、精英保留策略綜合應(yīng)用到求解JSP 問(wèn)題的遺傳進(jìn)化過(guò)程中，提出了一種改進(jìn)的遺傳算法，算法流程見(jiàn)圖3。其中，在初始化種群中，可通過(guò)啟發(fā)式算法找到相對(duì)較好的解形成初始種群；根據(jù)3.3 節(jié)設(shè)計(jì)適應(yīng)度函數(shù)，根據(jù)3.4 節(jié)進(jìn)行選擇操作，根據(jù)3.5 節(jié)、3.6 節(jié)進(jìn)行自適應(yīng)的交叉和變異操作，并利用3.8 節(jié)的EO 算法避免算法的提前收斂，最后通過(guò)3.7 節(jié)保證算法可獲得最優(yōu)解。

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

為了驗(yàn)證本文所述求解Job Shop 問(wèn)題的改進(jìn)遺傳算法的性能，針對(duì)文獻(xiàn)［6］中5個(gè)經(jīng)典Job Shop 問(wèn)題，采用本文提出的改進(jìn)遺傳算法進(jìn)行作業(yè)計(jì)劃排序，基本參數(shù)設(shè)置為：Psize=100，Pc_max=1，Pc_min=0.1，Pm_max=1，Pm_min=0.1。為便于比較，對(duì)5個(gè)經(jīng)典Job Shop問(wèn)題均作20次隨機(jī)仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表1 所示。其中GA、SA、AHEA 算法的數(shù)據(jù)取自文獻(xiàn)［6］。由表中可見(jiàn)，本文所述的改進(jìn)遺傳算法和其它算法相比生產(chǎn)周期最短，具有良好的魯棒性和收斂性。

圖3 改進(jìn)遺傳算法流程圖

表1 各種算法最優(yōu)結(jié)果比較

表1 中n為工件數(shù)，m為每個(gè)工件的工序數(shù)，C**為理論最優(yōu)解，C*為每個(gè)算法求解獲得的最優(yōu)解。

5 結(jié)語(yǔ)

本文通過(guò)將極值優(yōu)化算法（EO）、啟發(fā)式算法（HA）和遺傳算法（SA）的有機(jī)結(jié)合，針對(duì)Job Shop 調(diào)度優(yōu)化問(wèn)題構(gòu)造了一種改進(jìn)的遺傳算法，并對(duì)算法的操作算子進(jìn)行了改進(jìn)設(shè)計(jì)。利用著名的Fisher 和Thompson 的FT10、FT20、LA16、LA21 和LA26 5 個(gè)調(diào)度問(wèn)題對(duì)算法進(jìn)行測(cè)試，并和相關(guān)的文獻(xiàn)中的研究結(jié)果進(jìn)行比較，測(cè)試結(jié)果表明，本文提出的改進(jìn)遺傳算法具有良好的魯棒性和收斂性。

［1］玄光男，程潤(rùn)偉.遺傳算法與工程設(shè)計(jì)［M］.北京：科學(xué)出版社，2000.

［2］李曉紅，熊盛武.極值優(yōu)化算法研究［J］.武漢理工大學(xué)學(xué)報(bào)，2009，31（3）：41-44.

［3］齊潔，汪定偉.極值優(yōu)化算法綜述［J］.控制與決策，2007，22（10）：1081-1085.

［4］陳勇.基于遺傳算法的Job-shop 車(chē)間作業(yè)調(diào)度及其實(shí)現(xiàn)技術(shù)研究［D］.南京：南京理工大學(xué)，2007.

［5］張超勇，饒運(yùn)清，劉向軍，等.基于POX 交叉的遺傳算法求解Job-Shop 調(diào)度問(wèn)題［J］.中國(guó)機(jī)械工程，2004，15（23）：2149-2153.

［6］段亞南，何霆.基于自適應(yīng)混合啟發(fā)算法求解一類(lèi)JSP 問(wèn)題［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2004，25（7）：1206-1207.

［7］王凌.車(chē)間調(diào)度及其遺傳算法［M］.北京：清華大學(xué)出版社，2003.

［8］王小平，曹立明.遺傳算法理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安：西安交通大學(xué)出版社，2002.

［9］陸濤棟.求解車(chē)間作業(yè)調(diào)度的遺傳算法［D］.大連：大連理工大學(xué)，2005.

［10］BOETTCHER S，PERCUS A G.Optimization with extremal dynamics［J］.PhysRev.Lett.，200l，86（23）：5211-5214.

［11］BOETTCHER S.Extremal optimization of graph partitioning at th percolation threshold［J］.J Phys A：Math Gen，1999，3（28）：520l-5211.