一種求解車間調(diào)度的混合免疫遺傳算法

徐 雨，黃海松，胡 淶

（貴州大學(xué)現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽 550025）

1 引言

車間作業(yè)調(diào)度問題（job shop scheduling problem，JSP）是企業(yè)制造系統(tǒng)中的一個關(guān)鍵環(huán)節(jié)，其通過合理的安排零件加工時間和次序、合理的分配現(xiàn)有資源來制定在生產(chǎn)過程中的生產(chǎn)計劃。JSP問題直接關(guān)系著企業(yè)管理及其生產(chǎn)效率。有效的優(yōu)化JSP問題，能夠降低企業(yè)生產(chǎn)成本、提高生產(chǎn)資源的利用率、快速響應(yīng)市場的需求，從而提高企業(yè)競爭力。JSP屬于NP（nondeterministic polynomial）問題[1]。目前應(yīng)用在車間作業(yè)調(diào)度問題的優(yōu)化算法主要有免疫算法[2]、遺傳算法[3-4]、粒子群算法[5]、蟻群算法[6]和模擬退火算法[7]等，而且這些算法在JSP方面都擁有杰出的成果。免疫遺傳算法（Immune genetic algorithm，IGA）是一種免疫算法與遺傳算法相結(jié)合的混合算法，其相比較于一般的遺傳算法，在種群進(jìn)化過程中，免疫遺傳算法通過免疫操作能有效的提高算法的搜索能力和加快算法的收斂速度。免疫遺傳算法已經(jīng)被應(yīng)用到多個研究領(lǐng)域，車間調(diào)度問題[2]也包括在其中。文獻(xiàn)[8]對免疫算法的產(chǎn)生和發(fā)展進(jìn)行了概述，且對免疫算法的發(fā)展前景進(jìn)行了展望。文獻(xiàn)[9]中設(shè)計了抽取和接種疫苗的免疫操作，即將加工機(jī)器的基因片段作為疫苗，并以加工機(jī)器為基準(zhǔn)接種疫苗，此算法有效的提高了算法的準(zhǔn)確性與收斂效率，但算法在求解較大規(guī)模的車間問題時偏差較大。文獻(xiàn)[10]中設(shè)計一種改進(jìn)的優(yōu)先操作交叉算子，同時重新設(shè)計了免疫算子，該算法能對較大規(guī)模的車間調(diào)度問題得到很好地解決，但隨機(jī)運(yùn)算次數(shù)過多，運(yùn)算時間較長。文獻(xiàn)[11]中將免疫遺傳算法和模擬退火算法結(jié)合使用，利用分解策略對車間調(diào)度進(jìn)行求解，該算法在抑制種群退化，防止算法陷入局部最優(yōu)和加快算法的收斂速度方面做出了貢獻(xiàn)，但就精英個體選擇方面考慮欠佳。為此，將模擬退火算法的局部搜索理論與免疫遺傳算法的全局性、多樣性和自適應(yīng)性結(jié)合起來，互相取長補(bǔ)短，形成性能優(yōu)良的全局尋優(yōu)的混合免疫遺傳算法，并設(shè)置了自適應(yīng)精英選擇操作，最后將其應(yīng)用在作業(yè)車間調(diào)度問題的求解中。

2 車間作業(yè)調(diào)度問題描述

車間作業(yè)調(diào)度問題（JSP）主要研究：n個工件，在m臺機(jī)器上加工完成，每個工件i的工序數(shù)為oi，每個工件的不同工序在不同的機(jī)器上加工完成，其相應(yīng)的加工時間也各不相同。假設(shè)：（A）同一機(jī)器，可以加工多道工序，但是同一時刻最多只有一個工件在上面加工。（B）每個工件的每道工序加工機(jī)器和時間已知。（C）工序開始加工后，不能中斷加工。（D）不同工件的工序加工沒有先后順序的要求。（E）同一工件在加工過程中，有預(yù)設(shè)的加工順序。數(shù)學(xué)符號定義，如表1所示。

表1 數(shù)學(xué)符號定義Tab.1 Mathematical Symbol Definition

3 求解JSP問題的改進(jìn)IGA算法

3.1 編碼與解碼

遺傳算法在車間作業(yè)調(diào)度問題（JSP）方面的編碼方式主要有兩種，即間接編碼與直接編碼。其中，間接編碼的染色體是由一組工件的分配規(guī)則編碼而成，其調(diào)度方案則是由分配規(guī)則序列得到的。而直接編碼的染色體直接由一個調(diào)度方案編碼而成。

考慮到直接編碼方式編碼和解碼方式簡單、柔性高和防死鎖等優(yōu)點(diǎn)，采用一種基于工序的直接編碼方式[12]。直接編碼過程就是：在求解有m臺機(jī)器加工n個工件的JSP問題時，假設(shè)每個工件有m道工序，這些工序分別在m臺機(jī)器上加工，所以編碼的染色體組成的基因個數(shù)為n*m，每條染色體都可視為一個調(diào)度方案，染色體中同一工件的加工工序序號相同。在一條染色體中，若同一工件的加工工序序號第k次出現(xiàn)，則這個第k次出現(xiàn)的基因表示這一工件的第k道工序。例如：一個3×3的JSP問題，如表2所示?？蓪⑺囊粋€工序序列設(shè)為［3 1 1 2 3 2 2 3 1］。其中，1，2，3分別表示工件wp1，wp2和wp3，工序序列中從左到右三個1分別表示工件wp1的第一道工序，第二道工序和第三道工序，2和3同1類似。

表2 一個3＊3的JSP問題Tab.2 A 3＊3 JSP Problem

解碼就是將計算機(jī)語言轉(zhuǎn)化到實(shí)際問題的一種映射過程，在車間作業(yè)調(diào)度問題中，解碼就是將染色體轉(zhuǎn)化成一個調(diào)度方案。采用的解碼方法是一種插入式貪婪解碼算法[13]。貪婪解碼過程為：首先按照染色體上加工工序的從左到右依次降低工序的優(yōu)先權(quán)重，然后安排染色體上的工序序列的第1道工序進(jìn)行加工，再然后依次安排各工件剩余工序，并將其插入到對應(yīng)機(jī)器上可行的最佳加工時刻加工，最終達(dá)到所有的加工工序都安排在對應(yīng)機(jī)器上最佳可行的時刻加工。例如：上述的3×3的調(diào)度問題，其中一條染色體為［3 1 1 2 3 2 2 3 1］，對應(yīng)加工時間序列為［1 3 2 2 3 2 3 3 4］，機(jī)器序列表述為［2 1 3 2 3 1 3 1 2］，該染色體通過貪婪式解碼后可得到：機(jī)器1上的工件加工順序?yàn)?-3-2，機(jī)器2上的工件加工順序?yàn)?-1-3，機(jī)器3上的工件加工順序?yàn)?-3-1。使用貪婪解碼方法與半主動解碼方法，如圖1、圖2所示。由圖可知使用一般解碼方法的時間為11，而使用貪婪解碼的時間為10。

圖1 貪婪解碼方法Fig.1 Greedy Decoding Method

圖2 半自動解碼方法Fig.2 Semi-Automatic Decoding Method

3.2 精英保留策略

在抗體評價過程中，一方面提高了適應(yīng)度高的個體的選擇概率，而另一方面又降低了濃度高的個體的選擇概率。而在抑制高濃度的個體過程中，很容易丟失最優(yōu)解。所以利用精英保留策略來保留已獲得的優(yōu)質(zhì)的進(jìn)化成果。傳統(tǒng)的精英保留策略只保留某一固定數(shù)量適應(yīng)度最高的個體，這種保留策略不利于算法的收斂，且容易導(dǎo)致算法陷入局部最優(yōu)?；诖藛栴}提出了一種自適應(yīng)精英保留策略。

為了確定種群進(jìn)化程度，引入了成熟度的概念。若單個抗體v的適應(yīng)度和濃度分別為Agv，Cv，則成熟度為：

式中：M—種群進(jìn)化的成熟度；α—常數(shù)，為了加權(quán)適應(yīng)度與濃度的響。

精英保留在種群的成熟度較低的時候應(yīng)該保留較多的精英個體，加快收斂速度，成熟度較高時，選擇較少精英個體，提高種群的多樣性。所以，其保留精英個體數(shù)的公式為：

式中：Ne—精英保留個體數(shù)；N—抗體總數(shù)；b—預(yù)設(shè)正整數(shù)，防止初期保留太多精英個體，導(dǎo)致算法陷入局部最優(yōu)；ceil—向上取整。

3.3 變異算子

為了有效的提高算法的收斂速度和避免算法陷入局部最優(yōu)，該算法將變尺度變異與自適應(yīng)概率變異進(jìn)行了融合，提出了混合變異算子。其中，自適應(yīng)變異概率為：

式中：pm—變異概率；farg—群體的平均適應(yīng)度值；fmax—群體最大適應(yīng)度值；f—變異個體適應(yīng)度值；取pc1=0.1，pc2=0.001。

在算法早期，種群大多數(shù)是由隨機(jī)產(chǎn)生的，離最優(yōu)解相差甚遠(yuǎn)，種群中的大多數(shù)抗體的適應(yīng)度低，大概率的采用反轉(zhuǎn)變異可以提高算法在早期的查找效率。在算法后期，種群抗體的適應(yīng)度高，如果也采用反轉(zhuǎn)法變異將會產(chǎn)生過多的冗余信息。為了避免盲目搜索，提高算法執(zhí)行效率，又不至于陷入局部最優(yōu)，該算法采用基于自適應(yīng)變異概率的小步成熟機(jī)制的換位變異法進(jìn)行變異操作。

混合變異算子的流程為：

（1）計算當(dāng)代種群平均適應(yīng)度與需要變異抗體的適應(yīng)度。

（2）比較（1）中兩適應(yīng)度的大小，若變異抗體適應(yīng)度大于平均適應(yīng)度，選擇小步成熟機(jī)制的換位法變異；若變異抗體適應(yīng)度小于等于平均適應(yīng)度，則采用反轉(zhuǎn)變異法

（3）根據(jù)自適應(yīng)變異公式計算變異概率，開始變異操作。

3.4 免疫算子

3.4.1 疫苗的提取與接種

免疫操作分兩步進(jìn)行，即提取疫苗和接種疫苗。適當(dāng)?shù)倪M(jìn)行疫苗注射可以有效的避免種群退化和提高種群的適應(yīng)度，從而大大加快了算法的收斂速度和提高算法的尋優(yōu)能力。

這里算法所采用的疫苗提取方法為基于加工機(jī)器的基因片段提取疫苗[8]。

提取疫苗的流程為：

①將上代抗體中親和力最大的若干個體抽取出來。

②將抽取出來的抗體按加工機(jī)器打碎成基因片段，將所得到的基因片段保存在疫苗庫中。

接種疫苗是利用前面提取的疫苗來修改所選的部分個體染色體的某些位置的某些基因，從而有效的避免種群退化和提高種群的適應(yīng)能力。

疫苗接種操作如下：

（1）將父代種群的部分個體選取出來。

（2）隨機(jī)選取疫苗庫中的疫苗作為注射疫苗。

（3）取第（1）步操作中的未注射疫苗的一個個體作為疫苗注射對象。

（4）將疫苗的基因順序代替注射對象同一機(jī)器所對應(yīng)位置基因的順序。

（5）重復(fù)（2）到（4）步操作，直到第（1）步操作所選取出來的個體全部注射疫苗。

3.4.2 抗體評價及退火免疫選擇

以抗體v的繁殖概率ev即免疫選擇率作為個體的評價標(biāo)準(zhǔn)。繁殖概率是由抗體的親和度與該抗體的濃度共同決定的。利用繁殖概率這種選擇機(jī)制選擇抗體既有效的鼓勵了適應(yīng)度高的個體，又適當(dāng)?shù)囊种屏藵舛雀叩目贵w，其計算公式為：

為了更好地接受適應(yīng)度高的抗體，并且適當(dāng)?shù)囊种茲舛雀叩目贵w，提出了基于抗體評價的模擬退火選擇。

模擬退火選擇可以分為檢測抗體和選擇抗體兩步來進(jìn)行。第一步，檢測抗體，檢測注射疫苗的抗體的適應(yīng)度并將其適應(yīng)度值與舊抗體的適應(yīng)度值進(jìn)行比較，若新抗體適應(yīng)度更高，則以抗體的繁殖概率選取新抗體進(jìn)入下一代；若舊抗體適應(yīng)度更高，則說明出現(xiàn)了種群退化現(xiàn)象，需要進(jìn)入第二步操作。第二步是利用模擬退火的Metropolis接受準(zhǔn)則來決定接受新抗體的概率。即①若Δfv=

式中：T0—退火初始溫度；γ∈（0，1）—降溫系數(shù)；Tk—當(dāng)前退火溫度；p—Tk溫度下的接受概率；Δfv—新個體適應(yīng)度與舊體適應(yīng)度之差；fvs—新個體適應(yīng)度值；fv（s-1）—上一次迭代中舊個體適應(yīng)度值。

3.5 算法流程

算法流程圖，如圖3所示。

圖3 算法流程圖Fig.3 Algorithm Flow Chart

（1）設(shè)置算法參數(shù)并隨機(jī)初始化種群。

（2）設(shè)置迭代次數(shù)為0，計算種群的適應(yīng)度、濃度以及期望繁殖概率。

（3）自適應(yīng)精英選擇精英個體，更新記憶庫，對種群進(jìn)行免疫遺傳操作。

（4）進(jìn)行選擇操作，自適應(yīng)交叉。

（5）判斷抗體適應(yīng)度是否大于平均適應(yīng)度，若是，則計算變異概率pm2執(zhí)行換位變異；若不是，則計算變異概率pm1執(zhí)反轉(zhuǎn)變異。

（6）退火選擇，更新退火溫度，更新種群。

（7）判斷是否達(dá)到最大迭代次數(shù)，如果未到達(dá)進(jìn)入下一次迭代，如果達(dá)到進(jìn)入（8）。

（8）判斷退火溫度是否達(dá)到結(jié)束溫度，若未達(dá)到返回（2），若達(dá)到輸出最優(yōu)解，結(jié)束算法。

4 計算結(jié)果和比較分析

為驗(yàn)證算法的有效性與高效性，下面用Muth和Thompson提出的著名的MT06作為該算法的測試基準(zhǔn)。利用該算法不同參數(shù)對MT06問題仿真試驗(yàn)20次，取最優(yōu)的算法參數(shù)，參數(shù)設(shè)置如下：種群規(guī)模為 47；交叉概率（0.6～0.9），初始值為 0.9；變異概率為0.01；闕值T為0.95；初始溫度為10000；衰減系數(shù)為0.90；迭代次數(shù)為110。使用MATLAB2010b在Windows環(huán)境下運(yùn)行。算法收斂曲線，如圖3所示。由圖4可知，混合免疫遺傳算法在第四十次迭代就完成了收斂，找到最優(yōu)值，說明了算法的高效性；最佳工件加工順序圖，如圖5所示。得到最短生產(chǎn)時間為55s，達(dá)到最優(yōu)，說明了算法的有效性。

圖4 收斂曲線圖Fig.4 Convergence Curve

圖5 工件加工甘特圖Fig.5 Workpiece Processing Gantt Chart

基于MT06問題的不同算法的比較，如表3所示。就MT06問題而言本算法比一般的IGA，SA算法得到最優(yōu)解的概率要高很多，而且平均偏差僅為2.03%；不同算法性能比較，如表4所示。對于MT20問題，這里算法比其他算法得到的結(jié)果更優(yōu)，對MT06和MT10問題，雖然各個算法都能得到最優(yōu)值，但這里算法的出錯率更低。綜上所述，這里算法前期能夠快速收斂，后期能夠跳出局部收斂，防止“早熟”，顯示了其良好的全局尋優(yōu)能力。

表3 基于MT06問題的不同算法的比較Tab.3 Comparison of Different Algorithms Based on MT06 Problem

表4 不同算法性能比較Tab.4 Comparison of Performance of Different Algorithms

5 結(jié)論

通過對免疫遺傳算法及模擬退火算法的了解，結(jié)合了兩者的優(yōu)點(diǎn)，提出了一種混合免疫遺傳算法并用其求解了著名的JSP問題。通過仿真試驗(yàn)結(jié)果證明了算法的可行性和高效性。具體表現(xiàn)為：（1）算法通過對MT06問題的仿真，生成了最優(yōu)的調(diào)度方案。其中，最大完成時間達(dá)到了最優(yōu)的55s，說明了算法的可行性；算法在第四十次就達(dá)到了收斂，說明了算法的高效性。（2）就MT06問題而言，混合IGA算法比普通的SA算法和IGA算法擊中最優(yōu)解的概率更高，而且偏差更小。（3）在求解相對復(fù)雜的MT10問題時，混合IGA算法比普通的SA算法和IGA算法離最優(yōu)解更近，離最優(yōu)解相差只有1s。