基于熵的混合粒子群算法在柔性調度中的應用＊

黃英杰，姚錫凡，古耀達

（1.華南理工大學 機械與汽車工程學院，廣東 廣州 510640；2.廣州計量檢測技術研究院，廣東 廣州 510030）

粒子群算法或粒子群優化（particle swarm opti mizer，PSO）算法是由Kennedy和Eberhart提出的源于群智能的一種智能優化算法[1］.它通過模擬鳥群的覓食行為來求解問題，初始產生一組隨機解，每個個體在搜索空間以一定的速度飛行，并根據自己和同伴的飛行經驗進行調整.PSO有著個體數目少、計算簡單、魯棒性好等優點，目前已廣泛應用于函數優化、神經網絡訓練、模糊系統控制等應用領域.而信息熵（Information entropy）則是一個數學上頗為抽象的概念，不妨把信息熵理解成某種特定信息的出現概率（離散隨機事件的出現概率）.一個系統越是有序，信息熵就越低；反之，一個系統越是混亂，信息熵就越高.信息熵可以說是系統有序化程度的一個度量.

柔性車間調度問題[2］（Flexible Job Shop Scheduling Problem，FJSP）是對經典Job Shop調度問題的擴展，它不僅是NP－Hard問題，而且與經典Job Shop問題相比，其可行解空間增大，問題的復雜性更高.盡管已經有很多算法用于求解這類調度問題，比如遺傳算法、粒子群算法、禁忌搜索算法等優化算法，然而單獨的一種算法求解的效果并不理想.為此，本文把粒子群算法、遺傳算法和模擬退火算法結合起來，并根據種群熵來調節自適應慣性系數和變異概率，提出一種應用于柔性車間調度優化的基于熵的混合粒子群算法.

1 問題描述

柔性車間調度問題是對經典Job Shop調度問題的擴展，不但繼承了Job Shop問題的所有特征，而且增加了新的求解難度.將柔性Job Shop調度問題描述為：將n個加工順序不同的工件在m（m＞2）臺機器上加工，其中，每道工序可以在多臺機器上加工，每臺機器也可以執行多種工序的加工任務.已知：工件集P＝ ｛p1，p2，…，pn｝，pi為第i個工件，i＝1，2，…，n；機器集M＝ ｛m1，m2，…，mn｝，mj為第j號機器，j＝1，2，…，m，機器集中存在加工能力相同、可以完成相同工序的機器稱為并行機；工序 序 列 集OP＝ ｛op1，op2，…，opn｝，而opi＝｛opi1，opi2，…，opin｝ 為工件pi的工序序列.與經典Job Shop調度問題不同，柔性Job Shop調度問題中，工件的工序數量不一定等于機器數，即在車間內可能存在并行機或可以加工兩種及以上工序的多功能機器；每個工件使用每臺機器的時間矩陣T，tij∈T為第i個工件pi使用第j個機器的時間.tij＝0表示工件pi不使用機器j.此外柔性Job Shop調度問題還需滿足以下條件：各工件在每臺機器上使用的次數可以多于1次；各工件使用每臺機器的順序可以不同，即可以有opi≠opd（i≠d）；各工件具有相同的加工優先權；各工件加工過程中沒有新工件加入，也不能臨時中斷加工.

2 用于柔性車間調度的粒子群算法

粒子群優化算法是一種由Kennedy和Eberhart于1995年提出的群智能進化算法.粒子群優化算法采用“群”和“進化”的概念，根據粒子的適應度值進行操作.每個粒子在n維搜索空間以一定速度飛行，且飛行速度由個體的飛行經驗和群體的飛行經驗共同進行動態調整.設種群的規模s，Xi＝（xi1，xi2，…，xin）為粒子i的當前位置；Vi＝ （vi1，vi2，…，vin）為粒子i的當前速度；Pi＝（pi1，pi2，…，pin）為粒子i的歷史最好位置，稱為個體最好位置.對于最小化問題，歷史最好位置就是指適應度函數值最小的位置，群體中所有粒子經歷過的最好位置為Pg（t），稱為全局最好位置，則基本粒子群優化算法的進化方程可以描述為：

式中：vij（t），xij（t），vij（t＋1），xij（t＋1）分別為第i個粒子在第t代和第t＋1代的飛行速度和位置；下標j為粒子的第j維；下標i為粒子i；t為第t代；w為慣性系數；c1和c2分別為個體粒子的加速常數和群體粒子的加速常數，通常取值0～2；r1，r2分別為（0，1）內的隨機數.從式（1）的速度更新公式可以看出，c1為調整粒子在歷史最優方向上的步長，c2為調整粒子在全局最優粒子方向上的步長.為了減少在進化過程中，粒子離開搜索空間的可能性，vij通常限定在 [－vmax，vmax］內，如果問題的搜索空間限定在 [－xmax，xmax］內，可以設定vmax＝k×xmax，0.1＜k＜1.0.

2.1 粒子的編碼和解碼

在求解柔性單車間調度優化問題的粒子群算法中，每個粒子對應一種調度方案.根據柔性車間調度的問題，這里用一個2L（L＝∑n j＝1nj為總工序數）維的向量來表示粒子的位置向量.實際上，這個位置向量由兩個L維的向量組成，即工序向量Xprocess[L］和機器向量Xmachine[L］，工序向量Xprocess[L］由L個非零且不大于n（工件數）的自然數組成，自然數的順序決定了工件工序的加工順序.在這里，借鑒遺傳算法中的基于操作的編碼方法，即每個工序向量用L個代表操作的位組成，是所有操作的一個排列.比如工序向量Xprocess[L］為[2 1 1 2 2 3 1 3 3］，其中的1表示工件1，2表示工件2，3表示工件3，第1次出現的1代表工件1的第1道工序，第2次出現的1代表工件1的第2道工序，第3次出現的1代表工件1的第3道工序，工件2和工件3的含義也由此類推.機器向量Xmachine[L］由L個非零且不大于m（機器數）的自然數組成，代表加工Xprocess[L］對應位置工序的機器號.

2.2 位置向量和速度向量的計算

粒子群算法是一種屬于連續空間的優化算法，而柔性作業車間調度問題是離散的非數值優化問題，因此在迭代計算過程中做如下修改：

1）對于Xmachine[L］，由于機器向量的取值為[1，m］的整數，如果按照公式（2）計算出來的是小數，則采取向下取整的辦法進行修正，如果按照公式（2）計算出的結果超出取值區間，則按照邊界取值.

2）對于Xprocess[L］，由于柔性車間調度優化問題為工序順序的排序問題，因此采用迭代運算.假設初始值為.

維數： 1 2 3 4 5 6 7 8 9.

Xprocess[L］：1 1 1 2 2 2 3 3 3（初始值）.經過某次迭代運算得到如下結果：

Xprocess[L］（按照公式（2）計算后的值）.

將計算后的數值按照由小到大進行排序，將與計算后的值所對應的初始值進行重新排列，得到如下結果.

這次迭代過后的結果為[1 2 1 1 3 2 3 3 2］，經過這樣轉化就可以得到一個滿足要求的可行解.

2.3 基于熵的混合粒子群算法

2.3.1 模擬退火算法

模擬退火算法[3］來源于固體退火原理，將固體加溫至充分高，再讓其逐漸冷卻，加溫時，固體內部粒子隨溫度升高變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最后在常溫時達到基態，內能減為最小.根據Metropolis準則，粒子在溫度T時趨于平衡的概率為e－ΔE/（λT），其中E為溫度T時的內能，ΔE為其改變量，λ為Boltzmann常數.用固體退火模擬組合優化問題，將內能E模擬為目標函數值f，溫度T演化成控制參數t，即得到解組合優化問題的模擬退火算法：由初始解i和控制參數初值t開始，對當前解重復“產生新解→計算目標函數差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優解，這是基于蒙特卡羅迭代求解法的一種啟發式隨機搜索過程.退火過程由冷卻進度表（Cooling Schedule）控制，包括控制參數的初值t及其衰減因子Δt，每個t值時的迭代次數L和停止條件S.2.3.2 混合粒子群算法

由于粒子群算法特有的粒子間單向信息流的影響，粒子群算法具有非常快的收斂速度，經過不太多次的迭代進化后，種群中的各粒子往往具有相同的特征.這樣，導致種群缺乏多樣性，難以跳出局部最優，往往很容易形成過早收斂.然而，模擬退火算法是在某一初溫下從某一起點開始鄰域搜索，伴隨溫度參數的不斷下降，結合概率性地突跳特性在解空間中隨機尋找目標函數的全局最優解，即在局部最優解能概率性地跳出并最終收斂于全局最優解[4］，但其計算時間長，效率低，因此把粒子群算法和模擬退火算法相結合能更好地解決優化問題.

選擇粒子群算法與模擬退火算法結合，主要有以下幾方面的原因：首先是優化機制的融合，SA通過賦予搜索過程一種隨時變化且最終趨于零的概率突跳性，從而可有效的避免陷入局部最小并最終趨于全局最優；PSO則通過全局最優粒子和個體最優粒子的飛行信息指導來實現優化，對選擇機制上如此差異的兩種算法進行混合，有利于豐富優化過程的搜索行為，增強全局和局部意義下的搜索能力和效率.其次是優化操作的結合，SA算法在每一時刻僅保留一個解，缺乏冗余和歷史搜索信息，而PSO的速度更新過程中繼承了種群中全局最優個體和歷史個體最優粒子的部分信息，使得粒子始終保持向好的方向進化.把這些作用不同的優化操作相結合，豐富了優化過程中鄰域搜索結構，增強了全局空間的搜索能力.再次是優化行為的互補，若粒子群算法收斂準則設計不好，PSO經常會出現進化緩慢或“早熟”收斂的現象；而算法SA的優化行為對退溫歷程具有很強的依賴性，而理論上的全局收斂對退溫歷程的限制條件很苛刻，因而SA優化時間性能較差.若將兩種算法相結合，則SA的兩準則可控制算法收斂性以避免出現“早熟”收斂現象，并行化的抽樣過程可提高算法的優化時間性能.

PSOSA混合算法在優化機制、結構和操作上結合了PSO和SA的特點，充分發揮了粒子群算法良好的搜索能力和模擬退火算法有效避免陷入局部最優并最終趨于全局最優的特性，使PSO和SA互相取長補短，提高算法尋優性能.

2.4 熵的引入

信息熵是信息論中用于度量信息量的一個概念.一個系統越是有序，信息熵就越低；反之，一個系統越是混亂，信息熵就越高[5－6］.所以，信息熵也可以說是系統有序化程度的一個度量.在此，我們把種群看作是一個系統，用種群中個體基因的信息熵來衡量種群中個體的差異程度，而粒子群算法的w取值就受種群信息熵的控制.在粒子群算法中，當w取值范圍較大時，有利于對解空間進行大范圍搜索，但這種情況下由于搜索過于粗略往往使得搜索的精度不高；而當w取值范圍較小時，會改善搜索精度，但算法卻可能陷入局部極值.因此，本文采用公式（3）對w進行自適應變換，使其在搜索過程中逐步減小.在迭代搜索的開始階段，w足夠大使得算法在較大搜索空間里具有更好的全局搜索能力；隨著迭代次數的增加，w的值自適應地減小，以提高算法搜索到最優解的精度.變異概率Pm用公式（4）進行自適應變換，當種群中個體差異程度較低時，表示種群中的個體趨于一致，Pm自動地變大以增加種群的多樣性，擺脫局部最優，而當種群中個體的差異程度較高時，表示種群中個體較分散，Pm自動地減小以保護優良個體的生存.

因此采用如下的方式調節慣性參數w：假設種群中有M個個體，每個個體由2n個基因組成，設Rj是M個個體第j位基因值的集合，bij表示第i個個體第j位基因值在Rj中的重復個數，Pij表示第i個個體第j位基因值在Rj中的占有率，那么種群中個體第j位基因的信息熵就可用下式計算[7］：

種群的多樣性就可用種群中所有個體n個基因位的平均信息熵H來表示[7］：

式中：w1為允許的最大慣性系數；w2為允許的最小慣性系數；Pm1為允許的最大變異概率；Pm2為允許的最小變異概率.

2.5 基于熵的混合粒子群算法（HPSO）

利用粒子群算法和模擬退火算法相結合來求解柔性車間調度問題，其采用步驟為：

1）設定粒子群算法的慣性系數、加速常數、種群數和模擬退火算法的退火速率、初始溫度和終止溫度，隨機初始化位置向量和速度向量.

2）對于每個粒子，用公式（1）計算速度向量Vprocess[L］和Vmachine[L］，用公式（2）計算位置向量Xprocess[L］和Xmachine[L］，并根據種群熵計算公式計算該代種群的種群熵.

3）對各粒子進行解碼，計算各個粒子的適應度函數值（加工完成時間的倒數），尋找各粒子的最優解Pi和全種群的最優解Pg.

4）對于某個粒子，如果其適應度值優于歷史最優位置的適應度值，則記當前的適應度為該粒子的最優適應度，當前的位置為該粒子的歷史最優位置.

5）尋找本代種群的最優解，判斷其是否優于全種群的最優解Pg，如果優于全種群的最優解，則用本代種群的最優解更新全種群的最優解.

6）判斷Metropolis準則是否滿足，如果是，則分別對最優解Pg的位置向量Xprocess[L］和Xmachine[L］進行模擬退火操作T（t＋1）＝λT（t），并存儲當前的最優狀態，轉9），如果否，則轉7）.

7）由當前的穩定狀態產生新狀態，并以概率min[1，exp（－Δt＇/T）］接受新狀態，并返回6）.

8）根據步驟2）中計算出的種群熵，用公式（3）更新慣性系數w，用公式（4）更新變異參數Pm，同時對各個個體最優粒子Pi以Pm的概率進行變異操作.

9）判斷迭代次數是否大于規定值，如果小于，則轉步驟2）.

10）優化結束，輸出最優解.

3 實例分析

以F46（4×6），F88（8×8），F1010（10×10），MK07（20×5）問題的數據為例，進行連續10次的優化計算，其中種群數為100，進化代數為50，ωmax＝1.2，ωmin＝0.2，c1＝c2＝2.0，λ＝0.9，變異概率Pm1＝0.4，Pm2＝0.05，連續10次運行的結果如表1所示.由仿真結果可以看出，用本文提出的混合粒子群算法每次都能求出最優解，其優化效果明顯優于標準粒子群算法，但優化時間大于標準粒子群算法的優化時間.圖1為F1010問題優化時的PSO算法、混合PSO算法收斂曲線圖.

表1 算例的優化結果Tab.1 Optimization results for the examples

圖1 PSO和混合PSO算法收斂曲線圖Fig.1 Convergence curves of PSO and hybrid PSO

4 結 論

本文針對較大規模的柔性車間調度問題，將粒子群算法、遺傳算法、模擬退火算法和種群熵相結合，提出一種應用柔性車間調度優化的混合粒子群算法.實例仿真結果表明，該算法能很好地求解各種規模的柔性車間調度問題，與傳統的優化算法相比，在優化精度上具有明顯的優越性.該算法對柔性車間調度優化的研究進行了有益的探索，為混合智能優化算法在調度問題中的應用提供了有益的借鑒.

[1]KENNEDY J，EBERHART R C.Particle swarm optimization[C］//Proceedings IEEE International Conference on Neural Networks，IV.Piscataway，NJ：IEEE Service Center，1995：1942－1948.

[2]谷峰，陳華平，盧冰原，等.粒子群算法在柔性工作車間調度中的應用[J］.系統工程，2005，23（9）：20－23.GU Feng，CHEN Hua－ping，LU Bing－yuan，etal.Particle swarm optimization for flexible job shop scheduling[J］.Systems Engineering，2005，23（9）：20－23.（In Chinese）

[3]顧元憲，項寶衛，趙國忠.一種改進的連續變量全局優化模擬退火算法[J］.系統工程理論與實踐，2005，4：103－109.GU Yuan－xian，XIANG Bao－wei，ZHAO Guo－zhong.An improved simulated annealing algorithm for global optimization problems with continuous variables[J］.Systems Engineering Theory ＆Practice，2005，4：103－109.（In Chinese）

[4]劉鑫朝，顏宏文.一種改進的粒子群優化RBF網絡學習算法[J］.計算機技術與發展，2006，16（2）：185－187.LIU Xin－chao，YAN Hong－wen.A RBF neural network learning algorithm based on improved PSO[J］.Computer Technology and Development，2006，16（2）：185－187.（In Chinese）

[5]PIPLANI R，WETJENS D.Evaluation of entropy－based dispatching in flexible manufacturing system[J］.European Journal of Operational Research，2007，176（1）：317－331.

[6]SARDIS G N.Entropy in control engineering[M］.Singapore：Word Scientific Publ Co Pte Ltd，2001.

[7]劉林.一類離散制造業生產過程中的優化問題研究[D］.合肥：合肥工業大學管理學院，2009.LIU Lin.Research on optimization problem of manufacturing process in a discrete manufacturing industry[D］.Hefei：College of Management，Hefei University of Technology，2009.（In Chinese）