改進(jìn)粒子群算法求解車間作業(yè)調(diào)度問題

葛 晶，高廣宇，王虔翔

（北京理工大學(xué)計算機(jī)學(xué)院，北京 100081）

0 引 言

（1）問題背景介紹

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

（2）問題數(shù)學(xué)描述

對于每個工件和每一個機(jī)器，令x作為在上的開始時間，目標(biāo)函數(shù)為，問題可以表示為：

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

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

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

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

1 算法設(shè)計

1.1 算法簡介

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

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

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

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

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

1.2 算法關(guān)鍵操作

1.2.1 編碼和解碼

對于個工件，個機(jī)器的車間作業(yè)調(diào)度問題，粒子的維度為×，每個粒子位置代表一種處理順序。

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

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

1.2.2 粒子狀態(tài)更新

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

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

1.2.3 全局最優(yōu)位置的額外的變異搜索

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

1.2.4 自適應(yīng)的慣性權(quán)重

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

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

圖1 算法流程示意圖

1.3 時間復(fù)雜度分析

給定算法的粒子個數(shù)為，每個粒子的維度為。

（1）用標(biāo)準(zhǔn)公式更新所有粒子的速度和位置。對每個粒子調(diào)用速度和位置更新公式，時間復(fù)雜度為(×)。

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

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

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

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

2 實驗及分析

2.1 實驗設(shè)置

（1）實驗環(huán)境：Windows10 系統(tǒng)、JetBrains PyCharm軟件、Python3.6語言

（2）最大運行時間：未設(shè)置

（3）實驗參數(shù)：

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

2.2 實驗結(jié)果

2.2.1 測試用例實驗結(jié)果及分析

算法執(zhí)行均采用上述提到的參數(shù)，每個測試用例運行10 次，以找到的最優(yōu)解作為用例的運行結(jié)果，同時輸出10 次運行的平均時間，作為該測試用例的運行時間。

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

表1 運行結(jié)果與運行時間

從結(jié)果來看，對于小規(guī)模用例，例如用例3，最小結(jié)果和平均結(jié)果一樣，說明算法對于小規(guī)模用例具有較高的精準(zhǔn)度和穩(wěn)定性。對于大規(guī)模用例，例如用例8 和9，依然具有較好的穩(wěn)定性。

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

2.2.2 對比試驗

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

如表2所示，改進(jìn)的PSO算法無論是最小結(jié)果還是平均結(jié)果都明顯優(yōu)于標(biāo)準(zhǔn)的PSO 算法。測試用例規(guī)模越大，其優(yōu)勢也越明顯，改進(jìn)PSO 算法保留了標(biāo)準(zhǔn)PSO 算法收斂速度快的優(yōu)點。同時對于局部探索的改進(jìn)彌補(bǔ)了PSO 局部搜索能力差、精度低、易發(fā)散的問題。

表2 標(biāo)準(zhǔn)PSO與改進(jìn)PSO結(jié)果對比

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

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

表3 標(biāo)準(zhǔn)PSO與改進(jìn)PSO（無全局最優(yōu)的局部探索）結(jié)果對比

3 結(jié)語

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