改進粒子群算法求解車間作業調度問題

葛 晶，高廣宇，王虔翔

（北京理工大學計算機學院，北京 100081）

0 引 言

（1）問題背景介紹

在企業生產當中存在著生產環節多、合作關系復雜以及生產的連續性強等特點，如果某一個生產的節點發生變化（例如某一臺機器發生故障，工件的處理工序改變）會影響到整個生產系統的運行，一般來說，企業會安排一個專門的部門來管理生產調度，這無疑耗費大量的人力物力。車間作業調度問題是很多實際生產調度問題的簡化模型，具有重大的理論價值和工程實踐價值，是目前研究廣泛的典型調度問題。

（2）問題數學描述

對于每個工件和每一個機器，令x作為在上的開始時間，目標函數為，問題可以表示為：

（3）解決方案及實驗效果

本文采用改進的粒子群優化算法來解決車間作業調度問題，算法的關鍵步驟如下：①初始化粒子的速度和位置；②將位置信息編碼為作業的調度順序并計算總完工時間；③更新粒子的個體最優解和所有粒子全局最優解；④利用個體和群信息更新粒子速度，利用速度更新粒子的位置。但是，即便很小的位置變化也容易引起編碼順序的巨大改變，因此該算法局部搜索能力很差。

為了解決這一問題，本文提出的方法在每次迭代中，每個粒子的更新一定概率上使用傳統粒子群位置、速度更新公式，同時以一定概率將其當前位置與其歷史最優位置進行交叉來更新。同時，為了提高歷史最優位置處的局部搜索能力，采用位置交換（變異）來代替傳統位置更新，即原始算法用于全局搜索，交叉變異用于細化局部搜索。實驗證明，本文提出的方法可以實現比標準PSO 更快更好的效果，同時可以在犧牲少量速度的前提下，進一步提升實驗效果，在給定用例上取得了最優的測試結果。

本文后續部分組織如下。第1節詳細陳述使用的方法，第2 節報告實驗結果，第3 節討論本文的方法并總結全文。

1 算法設計

1.1 算法簡介

對于車間作業調度問題（job shop scheduling problem, JSSP），啟發式算法可以在可接受的時間內得到近似的最優解。該算法主要包括兩類：構造性啟發式算法和元啟發式算法。盡管構造性啟發式算法可以在解空間中找到問題的解，但它依賴于問題的局部信息，得到的解一般是局部最優解；元啟發式算法是一種優化算法，它的靈感來自于自然原理，并以公式化的方式描述了自然界中的一些問題。元啟發式算法能在可接受的時間內得到最優或近似最優解，已成為解決各種調度問題的一種實用可行的算法。

元啟發式算法主要包括克隆選擇算法（clonal selection algorithm,CSA），模擬退火算法（simulated annealing,SA），遺傳算法（genetic algorithms, GA），基于生物地理學的優化算法（biogeography-based optimization, BBO），粒子群優化算法（particle swarm optimization,PSO），差分進化算法（differential evolution,DE），蟻群優化算法（ant clony optimization,ACO），等等。為了獲得良好的性能，元啟發式算法需要找到一些策略來平衡算法的局部搜索能力（利用）和全局搜索能力（探索）。元啟發式算法的優勢在于，它可以在理論上將兩者以最優方式結合起來。

Qiu 等將人工免疫系統（artificial immune system, AIS）理論和PSO 結合起來解決車間作業調度問題JSSP，該算法采用克隆選擇和免疫網理論來模擬免疫、克隆、超突變、抗體選擇等基本過程。Masood 等提出了一種混合的遺傳算法來解決多目標的JSSP。Zhang等提出了一種基于克隆選擇理論的新PSO，以避免過早收斂。Abdel-Kade在PSO 中引入了兩個基于鄰域的算子以解決JSSP 群體多樣性。Dao 等提出了一種具有混合通信策略的并行蝙蝠算法（bat algorithm, BA）來解決JSSP，該算法的每個子群通過通信策略相互聯系，并分擔處理器上的計算負荷，該算法有很好的準確性和收斂率。

與其他元啟發式群體智能算法類似，PSO是一種創新的全局優化算法，最早由Kennedy博士和Eber 博士提出。PSO 思想來源于鳥群的覓食行為，即每個粒子代表鳥群中的鳥，在搜索空間中進行單獨搜索，獲得的個體最優值作為個體極值，并將個體極值與其他粒子的個體極值進行信息共享。粒子群中所有粒子的最佳個體極值作為當前的全局最優解，每個粒子根據自身的個體極值和當前的全局最優解更新自己的速度和位置，通過不斷地更新迭代獲取更好的全局最優解。PSO 粒子群算法因為參數少，收斂速度快，已經成為一種非常成功的算法，并已被用于優化各種實際問題。同時，開發和探索對應算法的局部優化能力和全局優化能力，雖然PSO 算法有很強的開發能力，但其探索能力是非常差的。當初始解離全局最優解較遠時，PSO經常出現過早收斂和局部停滯。

考慮到越來越多的混合元啟發式算法被用于解決JSSP，并且從平衡算法的全局搜索能力和局部搜索能力的角度來分析算法的性能。因此，為了克服PSO 的上述缺點，有必要引入一些策略來有效地平衡開發和探索。針對車間作業調度問題，本文設計了編碼方案，同時添加了交叉變異的局部搜索功能。

1.2 算法關鍵操作

1.2.1 編碼和解碼

對于個工件，個機器的車間作業調度問題，粒子的維度為×，每個粒子位置代表一種處理順序。

編碼：首先每個粒子根據位置進行升序排序，然后進行分組，每個為一組，規定最小的一組為工件1，第二組為工件2，以此類推，第組為工件。將位置從連續的實數更改為工件號后還原回原來的粒子位置順序，這時每個粒子的位置就代表工件的調度順序。

解碼：每個工件的第一次出現代表該工件的第一道工序，第二次出現代表該工件的第二道工序，以此類推，我們可以得到完整的調度順序。

1.2.2 粒子狀態更新

對于每個粒子，更新的類型是概率確定的，q的概率執行標準速度、位置更新，其中∈[ -,]，∈[ -,]，公式如下：

1 - q的概率執行交叉變異，當前位置與其個體歷史最優位置進行交叉，由于部分交叉產生的變異依然是巨大的，不利于局部的搜索，因此這里選擇完全交叉，即將粒子位置重置為其歷史最優位置，同時隨機交換兩個位置的坐標來產生變異，更新公式如下：

1.2.3 全局最優位置的額外的變異搜索

為了進一步提高局部搜索能力，針對全局最優位置進行額外的變異搜索，借鑒常桂娟提出的局部搜索方法，對全局最優位置隨機交換兩個位置的坐標。如果得到更優結果則更新最優位置，否則保留原全局最優位置。在這里本文添加探索次數為s，即執行s次上述操作以尋找更優。由于這種方法得到新的最優位置不屬于任何一個粒子的歷史最優，無法利用本文提出的粒子的交叉變異進行更新，因此默認將第一個粒子的歷史最優位置更新為目前新得到最優位置。

1.2.4 自適應的慣性權重

當粒子的所有速度都等于最大速度時，粒子很難達到最優位置，因此引入慣性權重，大的值有利于粒子群的探索，小的值有利于局部的挖掘，由于本文提出的方法需要同時兼顧全局與局部搜索，因此我們設計動態變化的慣性權重來應對不同的情況，這里采用Nikabadi等提出的一種自適應的慣性權重方法，每個粒子基于它離局部最佳位置的距離得到自己的慣性權重，公式如下：

基于上述分析和描述，所述算法的基本流程如圖1所示。

圖1 算法流程示意圖

1.3 時間復雜度分析

給定算法的粒子個數為，每個粒子的維度為。

（1）用標準公式更新所有粒子的速度和位置。對每個粒子調用速度和位置更新公式，時間復雜度為(×)。

（2）編碼所有粒子的位置。排序默認使用快排，時間復雜度為(×log)。

（3）計算每個粒子總調度時間。定義兩個列表，一個列表記錄每個工件的累計加工時間，一個列表記錄每臺機器上的累計加工時間，只需要掃一遍粒子的編碼便可以更新兩個列表。最終機器上累計加工時間最長的為總調度時間，因此時間復雜度為(×)。

（4）更新所有粒子的慣性權重。每個粒子根據歷史最優值更新其慣性權重，因此時間復雜度為()。

（5）交叉變異。需要掃一遍每個粒子的歷史最優位置，因此時間復雜度為(×)。

2 實驗及分析

2.1 實驗設置

（1）實驗環境：Windows10 系統、JetBrains PyCharm軟件、Python3.6語言

（2）最大運行時間：未設置

（3）實驗參數：

迭代次數設置為2000，粒子數40 個，設置為1，位置初始化∈[ -,],設置為0.25，速度初始化為0。參數,都設置為0.5，( 0 )設置為0.9，(n)設置為0.4，執行標準更新的概率q初始值設為0.95。采用線性遞減的方式，在迭代1000 輪時遞減為0.05，即訓練的前期重點利用標準PSO 進行全局的搜索，后期重點利用交叉變異進行局部的搜索。全局最優的進一步探索次數s設置為10，該參數越大效果越好，同時用時也越長。

2.2 實驗結果

2.2.1 測試用例實驗結果及分析

算法執行均采用上述提到的參數，每個測試用例運行10 次，以找到的最優解作為用例的運行結果，同時輸出10 次運行的平均時間，作為該測試用例的運行時間。

實驗結果如表1 所示，由于用例0 的正確答案是已知的1234，從運行結果來看最小結果1251 已經很接近正確答案，說明了本文提出算法的有效性，同時平均結果1274 與最小結果相差不大，說明了算法的穩定性。

表1 運行結果與運行時間

從結果來看，對于小規模用例，例如用例3，最小結果和平均結果一樣，說明算法對于小規模用例具有較高的精準度和穩定性。對于大規模用例，例如用例8 和9，依然具有較好的穩定性。

從運行時間來看，最小的用例只需要16.9 s，最大的用例需要228.9 s，并不需要太多的時間便能得到較好的效果。但是單獨觀察該實驗結果很難得出更多有用的信息，因此接下來與標準PSO進行對比試驗，來說明算法的有效性。

2.2.2 對比試驗

首先進行本文所提出的改進粒子群算法與標準粒子群算法的對比試驗，標準粒子群算法使用的參數與實驗設置一致，以保證對比的真實性，同樣每個用例運行十次，運行時間取平均值。

如表2所示，改進的PSO算法無論是最小結果還是平均結果都明顯優于標準的PSO 算法。測試用例規模越大，其優勢也越明顯，改進PSO 算法保留了標準PSO 算法收斂速度快的優點。同時對于局部探索的改進彌補了PSO 局部搜索能力差、精度低、易發散的問題。

表2 標準PSO與改進PSO結果對比

從運行時間來看，改進PSO 算法用時比標準PSO 略大。從算法角度來講，如果只添加交叉變異的思想用時會更少，因為粒子交叉操作重置位置為歷史最優時間復雜度為()，變異操作隨機交換兩個位置，時間復雜度可以忽略不計。而標準PSO 速度和位置更新時間復雜度都是()，一共是(2)。那么改進PSO 算法多出來的時間消耗必然是由于全局最優位置的局部探索導致的。因為設置每次探索次數為10，雖然10 次隨機交換并不耗時，但是每次交換需要進行編碼求解，調度是很耗時的。為了驗證在相同的用時情況下改進PSO 能否取得更好的效果，我們將探索次數置為1，再一次進行對比。

如表3所示，只添加交叉變異操作不執行全局最優位置的局部探索，運行時間的確比標準PSO 的運行時間還少。同時算法的運行結果依舊在很大程度上優于標準PSO。也就是說，本文提出的算法不僅提高了PSO 的搜索速度，同時極大地改善了PSO的搜索精度。

表3 標準PSO與改進PSO（無全局最優的局部探索）結果對比

3 結語

本文提出了一種增強局部搜索能力的粒子群優化算法用于求解車間作業調度問題，算法保留了標準粒子群算法良好的全局搜索能力，同時解決了其局部搜索能力差的問題。改進算法局部搜索能力的增強主要體現在對于每個粒子按概率重置到其歷史最優位置，并進行進一步的變異搜索。同時，對于全局最優位置進行額外的變異探索，如果是好的變異便保留。除此之外，為了使粒子更好地進行探索，采用自適應的慣性權重使得粒子在全局搜索時慣性權重更大，局部搜索時慣性權重更小。實驗證明本文提出的方法可以實現更快的搜索速度和更高的精度，同時可以在犧牲少量速度的前提下，進一步提升實驗效果。本文方法也存在一定不足，例如，算法在一定程度上依賴標準粒子群優化算法的全局搜索能力，未來還可以進行諸多改進嘗試。例如，實驗證明全局最優位置的額外探索取得了很好的效果，那么次優位置應該也有很大的價值，設計更加精細的局部探索框架也能提高算法搜索最優解的能力。