基于具有自適應(yīng)與自學(xué)習(xí)能力的粒子群優(yōu)化算法的車(chē)間調(diào)度算法

葉寒鋒，李占山，陳 超

（吉林大學(xué) 符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130012）

車(chē)間作業(yè)調(diào)度問(wèn)題（job shop scheduling problem，JSP）是一種典型的組合優(yōu)化問(wèn)題和NP難題，因此當(dāng)問(wèn)題的規(guī)模增大到一定程度時(shí)，很難找到一種完美的算法使其既能找到最優(yōu)解，又能保證消耗最少的時(shí)間.目前，人們主要利用近似算法和粒子群優(yōu)化算法（PSO）進(jìn)行相關(guān)問(wèn)題的求解［1－6］.本文基于粒子群優(yōu)化算法和模擬退火算法，通過(guò)在模擬退火算法中引入新的鄰域搜索機(jī)制——多粒度搜索，將問(wèn)題自身的信息作為啟發(fā)式信息，根據(jù)不同規(guī)模的問(wèn)題，使用不同的搜索方法，增加算法的自適應(yīng)性；在PSO中加入了自學(xué)習(xí)部分，受蟻群算法信息素公式的啟發(fā)，給出了粒子在搜索過(guò)程中動(dòng)態(tài)更新和淘汰的方法.實(shí)驗(yàn)結(jié)果表明，在獲得最優(yōu)解的個(gè)數(shù)和平均質(zhì)量上，本文提出的算法均有所提高.

1 車(chē)間調(diào)度問(wèn)題

JSP的形式化描述如下［7－8］：

1）每個(gè)作業(yè)由m個(gè)操作單元構(gòu)成，這些操作單元的先后順序預(yù)先確定，處理這些操作的機(jī)器及處理操作所需時(shí)間由實(shí)例給定；

2）一臺(tái)機(jī)器同時(shí)只能處理一個(gè)操作，且不可以被打斷；

3）優(yōu)化最終目的是最小化調(diào)度完工時(shí)間的值.

本文用Oij表示作業(yè)i的第j個(gè)操作.

2 ALPSO－JSP算法

文獻(xiàn)［5－6］使用PSO算法處理JSP問(wèn)題，證明了PSO是一種較好的處理算法.可當(dāng)問(wèn)題規(guī)模較大時(shí)，它們的處理能力十分有限，因?yàn)閭鹘y(tǒng)算法由于缺少對(duì)不同規(guī)模問(wèn)題的適應(yīng)和動(dòng)態(tài)學(xué)習(xí)，常會(huì)導(dǎo)致陷入局部最優(yōu).因此，本文在自適應(yīng)性和動(dòng)態(tài)學(xué)習(xí)上對(duì)PSO進(jìn)行改進(jìn).

2.1 粒子表示及random－key轉(zhuǎn)換 本文用實(shí)數(shù)數(shù)組 Array［n×m］表示粒子的空間位置.random－key［6］的作用是將算法搜索空間限制在可行解空間內(nèi)，random－key使用以下幾個(gè)數(shù)據(jù)元素：

4）Ops［n×m］：從0～（n×m－1）遍歷數(shù)組H 可獲取m 個(gè)作業(yè)序號(hào)同樣為i（1≤i≤n）的數(shù)，表示作業(yè)i的第m個(gè)操作，i的第j次出現(xiàn)用Oij替代，Ops［n×m］表示一個(gè)可行調(diào)度解.

2.2 模擬退火算法中鄰域的變化 在模擬退火［9］和領(lǐng)域搜索［10］中，選擇何種方法獲取鄰居是關(guān)鍵.鄰域概念中包含了鄰域半徑的概念，鄰域半徑并不一定是Euler距離.本文中鄰域半徑為對(duì)當(dāng)前解使用操作算子的次數(shù)，本文算法采用m／5作為粒度，解決了采用模擬退火算法時(shí)對(duì)鄰居解的獲取存在盲目性，對(duì)不同搜索空間大小采用相同鄰域搜索粒度缺乏必要的動(dòng)態(tài)學(xué)習(xí)能力的問(wèn)題.尤其當(dāng)解空間變大時(shí)，需要加大變化粒度，提高廣度探索的比例.

算法1 多粒度領(lǐng)域搜索算法.

S表示當(dāng)前位置，S′表示S的鄰居.

算法1為本文在使用模擬退火時(shí)采用的鄰域求解算法.采用4種常規(guī)操作算子：插入、交換、逆轉(zhuǎn)和變異.圖1為利用random－key方法將位置2的元素插入到位置4時(shí)的完整示例.

圖1 插入操作Fig.1 Insert operation

2.3 JSP改進(jìn)算法 在粒子群優(yōu)化算法中，下面兩式分別用于更新粒子速度和粒子位置［11－12］：

為了更好地使用粒子群優(yōu)化算法，主要采用動(dòng)態(tài)調(diào)整慣性系數(shù)［13－14］的方法：

其中：w（begin）和w（end）分別表示慣性系數(shù)的上限和下限；Niter表示迭代總數(shù)；t表示當(dāng)前迭代次數(shù).

為了避免粒子變化過(guò)快且過(guò)于分散，粒子群后續(xù)算法增加了速度控制［15］.令Vmax，j表示第j維允許的最大速度，粒子速度調(diào)整方法為

本文對(duì)PSO算法主要改進(jìn)了兩方面：1）淘汰更新.若一個(gè)粒子連續(xù)未得到改進(jìn)（說(shuō)明它趨向收斂的可能性增大）或一個(gè)粒子當(dāng)前的質(zhì)量不占優(yōu)，則它被淘汰的概率增大；2）選擇優(yōu)化.對(duì)優(yōu)秀的粒子進(jìn)行模擬退火處理，以提高獲得全局最優(yōu)解的概率.算法如下（N表示粒子個(gè)數(shù)，x和x′分別表示當(dāng)前和移動(dòng)后的粒子）：

算法2 ALPSO－JSP（adaptive and self－learning PSO for JSP）算法.

輸入：JSP的benchmark；

輸出：所能獲得的最優(yōu)解.

初始化每個(gè)粒子的位置和速度；

循環(huán)：

根據(jù)式（1）～（4）更新所有粒子的位置和速度；

更新每個(gè)粒子連續(xù)未更新的次數(shù)；

更新每個(gè)粒子的局部最優(yōu)和所有粒子的全局最優(yōu)位置；

根據(jù)每個(gè)粒子所代表的調(diào)度完工時(shí)間按照非遞減排序，對(duì)排名靠前的粒子進(jìn)行模擬退火優(yōu)化處理；

更新每個(gè)粒子的death數(shù)值并排序，計(jì)算公式為粒子i的淘汰權(quán)重公式：

其中：p，q設(shè)定為常數(shù)；Rank［i］表示粒子的質(zhì)量排名；consecutive［i］表示粒子連續(xù)沒(méi)有改進(jìn)的次數(shù).

將數(shù)值較大的粒子淘汰，并等數(shù)量初始化新的粒子；

循環(huán)結(jié)束（找到最優(yōu)解或達(dá)到循環(huán)最大次數(shù)）.

3 實(shí)驗(yàn)結(jié)果及分析

本文實(shí)驗(yàn)采用43個(gè)測(cè)試用例，其中LA系列40個(gè)，F(xiàn)T 3個(gè)；Microsoft Visual Studio 2008作為編程實(shí)驗(yàn)測(cè)試平臺(tái)，編程語(yǔ)言為C＋＋，CPU為Intel（R）Core（TM）2Duo CPU 2.10GHz，內(nèi)存為512Mb.算法涉及的參數(shù)值分如下三部分.

1）PSO部分：粒子總數(shù)設(shè)定30，C1＝2.0，C2＝2.0；慣性系數(shù)w（begin）＝1.4，w（end）＝0.4；Vmax，j＝0.15×m×n；迭代最大次數(shù)設(shè)為500；

2）模擬退火部分：初始溫度為粒子所表示的調(diào)度完工時(shí)間減去BKS所獲得的數(shù)值［6］；終止溫度為1.0；溫度遞減比例為0.95；

3）動(dòng)態(tài)適應(yīng)和學(xué)習(xí)部分：Limit＝10，p＝2.0，q＝n／10＋m／5.

HGA－Param［2］算法、HIA算法［5］及 MPSO算法［6］與本文算法對(duì)比的實(shí)驗(yàn)結(jié)果列于表1和表2.所能獲取的最優(yōu)解用BKS表示，n×m表示規(guī)模為n個(gè)作業(yè)和m臺(tái)機(jī)器.N表示測(cè)試用例個(gè)數(shù)，N－N表示未獲取最優(yōu)解的測(cè)試用例個(gè)數(shù)，Y－N 表示獲取最優(yōu)解的測(cè)試用例個(gè)數(shù)，得到的最優(yōu)解用best表示，能得到的最差解用worst表示，解的平均數(shù)值用average表示.

表1列出了4種算法在獲取最優(yōu)解性能上的對(duì)比.由表1可見(jiàn)：4種算法在LA01～LA19，LA21，LA23，LA26，LA30～LA35和3個(gè)FT測(cè)試上都達(dá)到了最優(yōu)解；ALPSO－JSP算法在38個(gè)測(cè)試用例上達(dá)到最優(yōu)解，而HGA－Param算法和HIA算法分別只能達(dá)到31和32；ALPSO－JSP算法的平均偏差為0.074 1%，小于HGA－Param算法和HIA算法.為了驗(yàn)證本文算法中改進(jìn)部分的效果，本文對(duì)MPSO算法和ALPSO－JSP算法進(jìn)行單獨(dú)對(duì)比.由表1可見(jiàn)：ALPSO－JSP算法達(dá)到最優(yōu)解的實(shí)例數(shù)是38，而MPSO算法只有35；ALPSO－JSP算法的平均偏差小于MPSO算法；在次優(yōu)解質(zhì)量上進(jìn)行比較，對(duì)于實(shí)例LA24，LA36，LA38和LA40，ALPSO－JSP算法比 MPSO算法好.在LA27，LA36，LA37，LA38，LA40等較大規(guī)模的實(shí)例上，ALPSO－JSP算法的表現(xiàn)優(yōu)于MPSO算法，但對(duì)測(cè)試用例LA29，MPSO算法的表現(xiàn)略好于ALPSO－JSP算法.

表1 不同算法對(duì)LA和FT實(shí)例的測(cè)試結(jié)果Table 1 Text results of benchmark for LA and FT with different algorithms

表2對(duì)比了本文算法和MPSO算法所能達(dá)到的平均解.本文選取各個(gè)問(wèn)題規(guī)模中具有代表性的實(shí)例進(jìn)行對(duì)比.由表2可見(jiàn)：對(duì)實(shí)例LA21，LA36和FT20最差解的比較表明，ALPSO－JSP算法表現(xiàn)更優(yōu)；在實(shí)例LA16，LA21，LA36及FT20上對(duì)比平均解表明，本文算法比MPSO算法表現(xiàn)好.但對(duì)比FT10實(shí)例上的平均解表明，本文算法比MPSO算法差.因此，在平均解質(zhì)量比較上，ALPSO－JSP算法優(yōu)于MPSO算法.

表2 ALPSO－JSP算法和MPSO算法的平均性能比較Table 2 Comparison of the average performance between ALPSO－JSP algorithm and MPSO algorithm

綜上所述，ALPSO－JSP算法是一種求解JSP算法的高效算法.

［1］Nowicki E，Smutnicki C.An Advanced Tabu Search Algorithm for the Job Shop Problem ［J］.Journal of Scheduling，2005，8（2）：145－159.

［2］Goncalves J F，Mendes J J D M，Resende M G C.A Hybrid Genetic Algorithm for the Job Shop Scheduling Problem ［J］.European Journal of Operational Research，2005，167（1）：77－95.

［3］Suresh R K，Mohanasundaram K M.Pareto Archived Simulated Annealing for Job Shop Scheduling with Multiple Objectives［J］.The International Journal of Advanced Manufacturing Technology，2005，29（1／2）：184－196.

［4］Udomsakdigool A，Kachitvichyanukul V.Multiple Colony Ant Algorithm for Job－Shop Scheduling Problem ［J］.International Journal of Production Research，2008，46（5）：4155－4175.

［5］GE Hong－wei，SUN Liang，LIANG Yan－chun，et al.An Effective PSO and AIS－Based Hybrid Intelligent Algorithm for Job－Shop Scheduling［J］.IEEE Transactions on Systems，Man and Cyberrnetics，Part A：Systems and Humans，2008，38（2）：358－368.

［6］LIN Tsung－lieh，HORNG Shi－jinn，KAO Tzong－wann，et al.An Efficient Job－Shop Scheduling Algorithm Based on Particle Swarm Optimization［J］.Expert Systems with Applications，2010，37（3）：2629－2636.

［7］Yamada T.Studies on Metaheuristics for Jobshop and Flowshop Scheduling Problems ［D］.Kyoto：Kyoto University，2003.

［8］YANG Sheng－xiang，WANG Ding－wei，CHAI Tian－you，et al.An Improved Constraint Satisfaction Adaptive Neural Network for Job－Shop Scheduling［J］.Journal of Scheduling，2010，13（1）：17－38.

［9］Kirkpatrick S，Gelatt C D，Vecchi M P.Optimization by Simulated Annealing［J］.Science，New Series，1983，220：671－680.

［10］Hansen P，Mladenovic N，Perez－Britos D.Variable Neighborhood Decomposition Search ［J］.Journal of Heuristics，2001，7（4）：335－350.

［11］Kennedy J，Eberhart R C.Particle Swarm Optimization ［C］／／Proceedings of IEEE International Conference on Neural Networks.Piscataway：IEEE Press，1995：1942－1948.

［12］SHI Yu－h(huán)ui，Eberhart R C.A Modified Particle Swarm Optimizer［C］／／Proceedings of the IEEE Congress on Evolutionary Computations.Piscataway：IEEE Press，1998：69－73.

［13］Naka S，Genji T，Yura T，et al.Practical Distribution State Estimation Using Hybrid Particle Swarm Optimization［J］.IEEE Power Engineering Society Winter Meeting，2001，2：815－820.

［14］WANG Gang，LIU Yuan－ning，ZHANG Xiao－xu.Novel Spam Filtering Method Based on Fuzzy Adaptive Particle Swarm Optimization ［J］.Journal of Jilin University：Engineering and Technology Edition，2011，41（3）：717－720.（王剛，劉元寧，張曉旭.基于模糊自適應(yīng)粒子群的垃圾郵件過(guò)濾新方法 ［J］.吉林大學(xué)學(xué)報(bào)：工學(xué)版，2011，41（3）：717－720.）

［15］Eberhart R C，Simpson P K，Dobbins R W.Computational Intelligence PC Tools［M］.San Diego：Academic Press Professional，1996.