一種求解作業車間調度問題的改進遺傳算法

（長安大學 道路施工技術與裝備教育部重點實驗室，西安 710064）

0 引言

作業車間調度問題（Job Shop Scheduling Problem，JSP）是一類典型的組合優化問題，科學、合理的調度方案能夠有效提高生產效率、降低加工成本，而問題的求解方法則是實現這些目標的重要保證。遺傳算法（Genetic Algorithm，GA）作為一種群智能算法，具有隱式并行性和全局搜索特性[1～3]，是求解作業車間調度問題的有力工具，但標準遺傳算法存在早熟收斂、解的穩定性差、遺傳參數難以確定等諸多缺點[4,5]。

本文針對標準遺傳算法的不足之處對其作了相應的改進，提出了一種新的個體適應度值計算方法，采用三種方式對染色體進行配對交叉以增強個體的多樣性，在選擇階段引入了精英保留策略[6]來確保算法的收斂性，在迭代過程中使算法自動對交叉和變異概率進行動態調整，并討論了動態概率調整函數中的參數取不同值時算法性能的變化情況。

1 JSP問題的數學模型

JSP問題的一般性描述為：n個工件在m臺機器上加工，工件每道工序的加工機器和加工時間確定，同時滿足以下約束條件：1）每個工件的工序按其工藝路線順次加工，中途不得中斷；2）同一時刻，一道工序只能在一臺機器上加工；3）同一時刻，一臺機器只能加工一道工序，4）每個工件在每臺機器上只加工一次。所要解決的問題是對各工件的加工順序進行合理安排以優化一個或多個加工性能指標。

本文以最小化最大完工時間為優化目標，假設安裝與調整時間包含在工序的加工時間內，各工件無加工優先級之分，相應的數學模型如下：

優化目標：

約束條件：

式(1)為優化目標函數；式(2)表示工序約束；式(3)表示機器約束；式(4)表示工件完工時間大于零；式(5)表示各下標變量的取值范圍。

式中，Cmax為最大完工時間；Cip為工件i在機器p上的完工時間；m為機器總數；n為工件總數；Sip為工件i在機器p上的開工時間；M是一個極大的正數；i, j為工件編號；p，q為機器編號。

2 算法設計

2.1 染色體編碼

本文采用基于工序的實數編碼來表示個體（染色體）[7]，一組編碼代表一種可行的加工方案，如對于工序碼[3 2 1 1 2 3 2 3 1]，各個數字代表被加工件的工件號，數字第幾次出現就代表相應工件的第幾道工序，如第一個“3”表示三號工件的第一道工序，第二個“3”表示三號工件的第二道工序。

2.2 種群初始化

初始種群用于生成第一代子代個體，本文采用隨機方式生成初始種群，利用MATLAB軟件自帶的隨機排序函數“randperm”隨機打亂一組染色體的編碼，通過多次調用該函數來獲得所需規模的初始種群。

2.3 計算個體適應度值

在以最小化最大完工時間為優化目標時，以往的研究大多以目標函數值的倒數作為個體的適應度值，這種方式所求得的個體的適應度值均較為接近，難以體現出個體差異，從而不利于在選擇階段將具有不同適應度值的個體有效區分開來。因此，對適應度函數進行改進以拉開個體間的差距，并采用精英保留策略使最優個體存活下來不受遺傳操作的破壞而直接遺傳到下一代。

設Ms(i)表示個體i對應的最大完工時間，Max和Min分別表示種群中的最大值與最小值，定義個體的適應度函數為：

假設有5個個體，對應的最大完工時間依次為：[10, 11, 12, 13, 14]，按傳統方法算得的個體適應度值分別為：[0.1, 0.0909, 0.0833, 0.0769, 0.0714]，個體的選擇概率如圖1(a)所示；按式(6)算得的個體適應度值為：[1, 0.6818, 0.4161, 0.1923, 0]，對應的個體選擇概率如圖1(b)所示。

對比圖1(a)和圖1(b)可以看出，傳統的適應度值計算法中，每個個體幾乎占據了相同的扇形面積，即所有個體將以近似相等的概率被選中，而改進的適應度值計算方法中，個體之間則具有較高的區分度，能夠保證適應度值最低的個體（如個體5）在選擇階段被淘汰，而適應度值高的個體以較大的概率被復制，從而在真正意義上體現出了遺傳算法“優勝劣汰”的特點。

2.4 選擇算子

采用輪盤賭法[8,9]選擇個體，計算公式如下：

圖1 個體的選擇概率

式中，sum(f)表示個體適應度值之和，p(i)表示個體i被選擇的概率，q(i)為個體i的累計概率，產生一個取值在區間[0,1]內的隨機數δ，若δ≤q(1)，則選中第1個個體，否則的話，若q(i-1)＜δ≤q(i)，則選中第i個個體。

2.5 交叉與變異算子

2.5.1 交叉與變異方式

本文采用優先工序交叉法（Precedence Operation Crossover，POX）進行交叉操作[10]，并對其進行了擴展。標準POX法中，首先隨機產生兩個基序列J1、J2，將配對的父代個體P1、P2所含的J1中的基因按原位復制到子代個體C1、C2中，而將所含的J2中的基因按原有順序依次填入到子代個體C2、C1的空位基因處[11]，從而得到交叉后的子代個體C1和C2。

POX法的第一種擴展方式為：將父代個體P1、P2所含的J2中的基因逆序后再填入到子代個體C2、C1中；第二種擴展方式為：將父代個體P1、P2所含的J2中的基因隨機打亂順序后再填入到子代個體C2、C1中。兩種改進的POX法中，父代個體所含的J1中的基因的處理方式與標準POX法相同。迭代時隨機選擇基本POX法與改進的POX其中的一種交叉方式，從而以多種方式使子代繼承父代的優良基因，提高了子代個體的多樣性。

變異屬于小概率事件，但有利于擴大種群的多樣性，本文采用互換法（Reciprocal Exchange Mutation，REM）進行變異操作[12]，即隨機選擇兩個含有不同基因的基因位，將對應元素調換位置。

2.5.2 交叉與變異概率

標準遺傳算法以固定的交叉概率和變異概率進行相應的操作，當二者取值較小時會使搜索范圍變小，不利于尋找到更優解，而取值較大時則可能導致已有的優良個體在交叉和變異操作后變得更差。因此，本文設計了一種動態自適應交叉概率和變異概率，一方面根據個體在種群中的較高或較低的地位（適應度值越大，地位越高，反之則越低）來給予其較小或較大的交叉與變異概率，另一方面通過動態概率調整函數使迭代初期個體以較大的概率進行交叉和變異，以擴大尋優范圍，避免算法早熟收斂，而在迭代后期則減小交叉與變異概率，以降低前期所得到的優秀個體被交叉和變異操作所破壞的概率，同時保證算法盡快收斂。

改進后的動態自適應交叉概率和變異概率的計算公式如下：

式中，i為當前迭代次數，N為終止迭代次數，指數v是調整參數，取值為區間[1,5]內的整數，Pc為交叉概率，Pm為變異概率，kc, km分別為區間[0,1]內的常數，fc為兩個交叉個體的較大的適應度值，fm為變異個體的適應度值，fa和fmax分別為當前種群的平均適應度值和最大適應度值。

式(9)中，指數v取不同值時，得到的動態概率調整函數cos(u)的圖形如圖1所示。

圖2 動態概率調整函數圖形

從圖中可以看出，隨著迭代次數增加，函數cos(u)的值從1變為0，斜率逐漸增大，從而在迭代初期保持較大的Pc和Pm進行尋優，在迭代后期則以較小Pc和Pm來加速收斂，而指數v取值越大時，曲線凸起程度越大，從而在越多的迭代次數范圍內以大概率進行交叉與變異，以擴大種群多樣性來搜索更優解，但同時也會使收斂速度降低。因此，當要求算法具有更強的尋優能力時，應取較大的v值，當要求算法具有更快的收斂速度時，應取較小的v值。

改進遺傳算法的流程圖如圖3所示。

圖3 改進遺傳算法計算過程

3 實例驗證

以Ft06基準算例[13]來驗證改進后的遺傳算法的性能，試驗數據如表1所示，程序運行平臺為Windows7操作系統下的MATLAB軟件，取種群規模為PS=40，迭代次數為FC=200，標準遺傳算法采用基本POX法進行交叉操作，采用互換法進行變異操作，交叉和變異概率分別為Pc=0.7，Pm=0.1，改進遺傳算法由式(6)計算個體適應度值，隨機選擇三種交叉方式中的一種進行交叉操作，變異操作仍采用互換變異法，交叉概率Pc和變異概率Pm分別由式(10)和式(11)確定，式中，取kc=0.9，km=0.12，指數v分別取1、2、3、4、5，將標準遺傳算法和指數v的不同取值下的改進遺傳算法各運行20次，所得結果如表2所示。

表1 各工序加工機器（加工時間）

由表2可知，標準遺傳算法求得的最優解為56，而改進遺傳算法求得的最優解為55，且后者最優解的個數遠大于前者，雖然在v=4，5時，改進算法的平均迭代次數大于標準遺傳算法，但無論指數v取何值，改進遺傳算法所求目標函數的平均值均小于標準遺傳算法對應的值。可見，在最優解的質量和數量上，改進遺傳算法均優于標準遺傳算法，表明了改進后的遺傳算法的有效性與可行性，標準遺傳算法與改進遺傳算法所求最優解的調度甘特圖如圖4、圖5所示。

表2 改進前/后算法試驗結果對比

根據表2數據，得到改進遺傳算法中指數v分別取1，2，3，4，5時的目標函數均值與平均迭代次數的變化趨勢如圖6所示。

由圖6可以看出，在改進遺傳算法中，參數v的取值與問題解的優度呈正相關關系，而與收斂速度呈負相關關系，與理論分析結果是吻合的，因此，本文所提出的改進遺傳算法中，較大的v值有利于提高解的優度，較小的v值有利于提高算法的收斂速度，在實際應用時可根據具體要求來合理選取參數v的值。

圖4 標準遺傳算法最優解調度甘特圖

圖5 改進遺傳算法最優解調度甘特圖

圖6 不同v值下的改進遺傳算法所求目標函數均值與平均迭代次數變化趨勢

4 結束語

本文針對以最小化最大完工時間為優化目標的作業車間調度問題，從個體適應度函數、染色體交叉方式以及交叉與變異概率三方面對標準遺傳算法進行了相應的改進，所設計的動態交叉概率與變異概率能夠根據個體的適應度值與算法迭代次數而自動調整，從而擴大迭代初期的搜索范圍，使算法在前期具有較強的尋優能力，而在后期以較小的交叉與變異概率使算法盡快收斂，同時，對動態概率調整函數的參數v取不同值時算法的性能進行了分析，為實際應用中v值的選取提供了參考。今后的研究可以從種群的初始化方式、個體的選擇規則以及遺傳算法與其他智能算法的融合等方面入手，從而使求解作業車間調度問題的算法變得更加高效和完善。