粒子群算法在制造調(diào)度系統(tǒng)中的應(yīng)用研究

王楚楚，臧海娟

（1.江蘇理工學(xué)院 機(jī)械學(xué)院，江蘇 常州 213001；2.江蘇理工學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 常州 213001）

制造業(yè)在國(guó)家經(jīng)濟(jì)、社會(huì)發(fā)展中占著重要地位，它直接體現(xiàn)了一個(gè)國(guó)家的生產(chǎn)力水平。在制造業(yè)中，調(diào)度問(wèn)題關(guān)系到企業(yè)整個(gè)生產(chǎn)系統(tǒng)的正常運(yùn)轉(zhuǎn)。制造調(diào)度系統(tǒng)的智能優(yōu)化是現(xiàn)代制造和管理的核心[1]，它是針對(duì)制造系統(tǒng)中面臨的各種動(dòng)態(tài)事件，在滿足約束條件的前提下，做出及時(shí)的響應(yīng)，以實(shí)現(xiàn)生產(chǎn)的最優(yōu)化[2]。粒子群算法是通過(guò)模擬鳥(niǎo)群搜捕食物的方法，找尋現(xiàn)實(shí)生活中問(wèn)題的最優(yōu)解。由于其實(shí)現(xiàn)簡(jiǎn)單、可調(diào)參數(shù)少、尋找結(jié)果效率高等優(yōu)點(diǎn)，被廣泛應(yīng)用于制造領(lǐng)域調(diào)度問(wèn)題，并取得了大量的成果。本文從算法在制造系統(tǒng)調(diào)度中的規(guī)劃、優(yōu)化和應(yīng)用方面進(jìn)行綜述和分析。

1 粒子群算法及其演化

鳥(niǎo)類(lèi)以群體為單位進(jìn)行覓食，通過(guò)每只鳥(niǎo)不斷的分享信息，找到范圍未知的食物。受此過(guò)程的啟發(fā)，美國(guó)的 Kennedy 和 Eberhart博士提出了粒子群算法。在粒子群算法（Particle Swarm Optimization，PSO）中，鳥(niǎo)群個(gè)體抽象為無(wú)質(zhì)量無(wú)體積的粒子，粒子的位置為候選解。每個(gè)粒子初始化都有兩個(gè)基本信息，即自身的位置和速度，通過(guò)信息基本交互得到個(gè)體和群體的最優(yōu)位置，位置是否最優(yōu)由適應(yīng)度函數(shù)比較得出。

假設(shè)粒子的位置和速度分別用向量Xi，j=（xi，1，xi，2，…，xi，d）和Vi=（vi，1，vi，2，…，vi，d）表示，其中i為粒子編號(hào)，d為空間維度，i=1，2，…，n。則粒子的方程公式如（1）、（2）所示：

自粒子群算法提出以來(lái)，為解決其自身固有的缺點(diǎn)和獲得更好更快的結(jié)果，眾多研究者從參數(shù)修正、收斂性、混合PSO等角度對(duì)算法進(jìn)行改進(jìn)，讓其在諸多領(lǐng)域發(fā)揮重大的作用。

1.1 參數(shù)的修正

PSO的參數(shù)的不同選擇對(duì)算法性能有著不同的影響，對(duì)參數(shù)的改進(jìn)有許多經(jīng)典算法。

Zhang L，Tang Y，Hua C C等[3]將貝葉斯技術(shù)引入粒子群算法中，根據(jù)粒子過(guò)去的位置來(lái)調(diào)整慣性權(quán)值，使算法具有更高的精度和更快的收斂速度。2020年，楊寶軍[4]從離散狀態(tài)空間表達(dá)式入手，在慣性權(quán)重矩陣的基礎(chǔ)上，提出一種提高收斂、跳出局部極數(shù)的自適應(yīng)粒子群算法（RDR-PSO），得到的算法穩(wěn)定性強(qiáng)、收斂精度有著一定的提升。同年，周旭和張業(yè)榮[5]對(duì)粒子群算法中的慣性權(quán)重ω和c1c2學(xué)習(xí)因子進(jìn)行調(diào)整，使ω在前期數(shù)值較大，迭代后期數(shù)值較小，提出一種非線性變化策略，使c1逐漸減小，c2逐漸增大。薛建彬，劉星星[6]提出了基于PD公式的慣性權(quán)重函數(shù)，進(jìn)行慣性權(quán)重的自適應(yīng)選擇。當(dāng)種群多樣性較好時(shí)，可通過(guò)減小慣性權(quán)重，使粒子找到更優(yōu)的個(gè)體極值和全體極值。否則增加粒子速度，增強(qiáng)全局尋優(yōu)的能力。

1.2 粒子群算法的收斂性

由于粒子群算法受隨機(jī)系數(shù)影響較大，因此，許多研究者對(duì)算法收斂性進(jìn)行了不同的分析、改進(jìn)，以進(jìn)一步提高算法的性能。

宋美、葛玉輝、劉舉勝[7]針對(duì)PSO算法易陷入局部最優(yōu)、發(fā)生早熟的缺點(diǎn)，提出一種動(dòng)態(tài)雙重自適應(yīng)PSO 改進(jìn)算法，文中采用Feigenbaum迭代構(gòu)造混沌序列初始化粒子位置和速度，引用協(xié)同進(jìn)化理論中的非線性調(diào)整策略來(lái)平衡c1、c2的關(guān)系，從而控制粒子的飛行方向和速度，提高收斂速度。Hao L，Zhang X W，Liang H等人[8]提出的基于人類(lèi)行為的粒子群優(yōu)化算法（HPSO），將全局最差的粒子引入到算法的速度方程中，該方程服從標(biāo)準(zhǔn)正態(tài)分布，具有隨機(jī)權(quán)重且消除了兩個(gè)加速度系數(shù)c1c2。HPSO通過(guò)上述方法降低已解決問(wèn)題的參數(shù)敏感性，并改變粒子的飛行模式，從而提高種群的多樣性、收斂速度和精度。

1.3 混合粒子群算法

在對(duì)PSO算法的改進(jìn)中，多數(shù)情況下，PSO通過(guò)混合其他算法或技術(shù)來(lái)補(bǔ)足自身缺點(diǎn)。盧志剛，申康[9]提出蟻群算法與粒子群算法綜合應(yīng)用的混合算法， 以更準(zhǔn)確更高效率地求解了供應(yīng)鏈合作伙伴選擇的問(wèn)題；Tetsuyuki、 Takahama、Setsuko Sakai[10]提出將EPC方法應(yīng)用于PSO，控制系數(shù)的擴(kuò)展目標(biāo)值相同，并將一個(gè)新的解與當(dāng)前最優(yōu)解比較；Chen M R，Li X，Zhang X等人[11]為了克服PSO的局限性，將PSO與極值優(yōu)化（EO）相結(jié)合。Jiang H，Kwong C，K，Chen Z Q等人[12]結(jié)合混沌優(yōu)化算法（COA）和PSO以得到更快的收斂速度及更高的迭代精度，對(duì)用于醫(yī)療的持續(xù)高溫腹腔灌注的溫度進(jìn)行了預(yù)測(cè)控制。

2 制造系統(tǒng)中的粒子群算法

2.1 制造領(lǐng)域的研究現(xiàn)狀

21世紀(jì)，大數(shù)據(jù)、人工智能、云計(jì)算等計(jì)算機(jī)技術(shù)的蓬勃發(fā)展，促使消費(fèi)行為、企業(yè)模式產(chǎn)生巨大轉(zhuǎn)變。德國(guó)工業(yè)4.0和國(guó)內(nèi)《中國(guó)制造2025》的提出使得制造領(lǐng)域煥發(fā)出勃勃生機(jī)，將制造技術(shù)與數(shù)字技術(shù)、網(wǎng)絡(luò)技術(shù)、智能技術(shù)等多種技術(shù)結(jié)合，打造智能化制造[13]。2010年，歐盟提出“歐洲2020的戰(zhàn)略”，為了實(shí)現(xiàn)制造業(yè)上智能化的進(jìn)一步發(fā)展。2011年，美國(guó)總統(tǒng)奧巴馬提出“先進(jìn)制造伙伴AMP”，在政府、企業(yè)、高校的合作基礎(chǔ)上，強(qiáng)化制造業(yè)，創(chuàng)新和發(fā)展關(guān)鍵制造行業(yè)、機(jī)器人戰(zhàn)略、先進(jìn)材料等方面，進(jìn)一步研發(fā)智能工廠、智能制造技術(shù)和智能制造平臺(tái)。2012年，英國(guó)經(jīng)濟(jì)學(xué)家發(fā)表智能制造技術(shù)發(fā)展會(huì)引起“第三地工業(yè)革命”的言論[14]。2014年，日本推行“再行戰(zhàn)略”，重點(diǎn)發(fā)展機(jī)器人、新能源汽車(chē)和3D打印等。近幾年，我國(guó)也加大對(duì)智能化制造的重視，發(fā)布相關(guān)政策，加大對(duì)智能制造技術(shù)研究、高校研究、人才培養(yǎng)的投資，使得智能制造技術(shù)取得快速的發(fā)展，在機(jī)器人技術(shù)、通信網(wǎng)絡(luò)技術(shù)、信息處理技術(shù)、傳感器等方面有了大幅度的提升。我國(guó)起步較晚，現(xiàn)在與歐美國(guó)家有一定的差距，我們?nèi)孕璨粩鄤?chuàng)新、不斷探索、不斷發(fā)展，在未來(lái)謀取一片天地。

智能制造的目的在于實(shí)現(xiàn)整個(gè)制造過(guò)程的智能化，包括智能技術(shù)與產(chǎn)品設(shè)計(jì)、制造、裝配、運(yùn)輸?shù)犬a(chǎn)業(yè)鏈的深度融合。基于大數(shù)據(jù)的智能生產(chǎn)調(diào)度與優(yōu)化技術(shù)是實(shí)現(xiàn)智能制造的關(guān)鍵技術(shù)之一，為了解決生產(chǎn)調(diào)度問(wèn)題，應(yīng)用了多種的基于人工智能的智能算法。制造業(yè)重視數(shù)據(jù)共享、調(diào)度的全局性和可擴(kuò)展性、事件的響應(yīng)速度等調(diào)度問(wèn)題，促使研究者不斷優(yōu)化調(diào)度系統(tǒng)，改進(jìn)調(diào)度方法。

2.2 粒子群算法與其他智能算法對(duì)比

制造系統(tǒng)中典型的智能算法包括遺傳算法、粒子群算法、蟻群算法等，此類(lèi)算法對(duì)問(wèn)題依賴性較弱，通過(guò)計(jì)算機(jī)迭代運(yùn)算完成搜索。遺傳算法模擬了自然生物界遺傳和進(jìn)化過(guò)程優(yōu)化方法，算法根據(jù)群體中個(gè)體的選擇、交叉和變異操作獲得更優(yōu)秀的個(gè)體，該算法高效、魯棒性強(qiáng)、全局搜索能力強(qiáng)，但實(shí)現(xiàn)較復(fù)雜，運(yùn)行效率低。蟻群算法是受螞蟻集體尋徑行為啟發(fā)而來(lái)，該算法形成一種正反饋機(jī)制，易于并行實(shí)現(xiàn)以及和其他算法結(jié)合，但參數(shù)較多，運(yùn)行效率較低并容易發(fā)生停滯現(xiàn)象，適用小規(guī)模、低維數(shù)據(jù)。粒子群算法易于實(shí)現(xiàn)，局部搜索能力強(qiáng)且運(yùn)行效率高，但易陷入局部最優(yōu)，尋優(yōu)精度低，適合較大規(guī)模數(shù)據(jù)。

2.3 粒子群算法在制造調(diào)度中應(yīng)用

粒子群算法在制造調(diào)度中應(yīng)用大致分為三種：一是將粒子群算法直接運(yùn)用調(diào)度模型中；二是在粒子群算法的基礎(chǔ)上改進(jìn)算法后運(yùn)用；三是粒子群算法結(jié)合其他算法融合在運(yùn)用。

在粒子群算法直接解決調(diào)度方向上，Muharni Y Irman A，F(xiàn)ebianti E等[15]使用PSO算法解決并行機(jī)流水車(chē)間調(diào)度中的調(diào)度問(wèn)題。Nouiri M，Bekrar A，Jemai A等[16]以最小化最大完工時(shí)間準(zhǔn)則為目標(biāo)，應(yīng)用粒子群優(yōu)化算法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題。Liao， J.和Lin， C[17]提出基于粒子群算法的作業(yè)車(chē)間供應(yīng)鏈調(diào)度優(yōu)化方法，并通過(guò)實(shí)例證明了粒子群算法能有效克服生產(chǎn)調(diào)度中的不收斂問(wèn)題，以獲得車(chē)間作業(yè)調(diào)度的最優(yōu)解。Balaji A.N，Porselvi S，Jawahar N[18]使用粒子群算法解決多單元柔性制造系統(tǒng)中具有順序依賴批量建立時(shí)間的零件批調(diào)度問(wèn)題。

針對(duì)粒子群算法易陷入局部最優(yōu)，尋優(yōu)精度低等問(wèn)題，提出改進(jìn)方法解決調(diào)度問(wèn)題。黎書(shū)文、張成龍、周知進(jìn)[19]針對(duì)離散制造車(chē)間柔性調(diào)度優(yōu)化，提出一種慣性權(quán)重、學(xué)習(xí)因子自適應(yīng)調(diào)整的粒子群算法，并基于改算法建立柔性調(diào)度多目標(biāo)優(yōu)化模型。此算法基于1－ω＞0且2ω+2－c1－c2＞0的粒子穩(wěn)定條件改進(jìn)，更新公式如式（3） 、（4）所示：

慣性權(quán)重余弦自適應(yīng)調(diào)整可提高算法初期的全局尋優(yōu)能力，運(yùn)行過(guò)程中的逐漸遞減有利于加速算法收斂。根據(jù)粒子穩(wěn)定條件調(diào)整學(xué)習(xí)因子，提高了粒子學(xué)習(xí)能力。實(shí)驗(yàn)表明自適應(yīng)調(diào)整的粒子群算法加快了收斂速度，增強(qiáng)了全局搜索能力，所以對(duì)車(chē)間調(diào)度的效率有著一定的提升。但自適應(yīng)機(jī)制增加了算法的復(fù)雜度，執(zhí)行時(shí)間較長(zhǎng)，且改進(jìn)算法只是和PSO算法、SA算法相比，缺乏更多算法的比較。溫海駿、劉從虎[20]通過(guò)在粒子群算法中引入積分控制器，使用控制器控制粒子運(yùn)行軌跡的方式解決不確定條件下再制造模糊加工時(shí)間的生產(chǎn)調(diào)度問(wèn)題。Marichelvam M.K，Geetha M，Tosun O[21]在考慮人為因素的基礎(chǔ)上，引入調(diào)度規(guī)則和建設(shè)性啟發(fā)式來(lái)改進(jìn)PSO算法的初始解，并混合變量鄰域搜索算法和PSO算法，應(yīng)用于各階段具有相同并行機(jī)的多級(jí)混合流水車(chē)間調(diào)度問(wèn)題。Chen S C，Cheng C F，Lin C C[22]提出了一種新穎的離散粒子群優(yōu)化算法來(lái)求解資源受限項(xiàng)目計(jì)劃問(wèn)題，即在資源約束和優(yōu)先約束的情況下，使項(xiàng)目的制造時(shí)間最小化。Anuar N I， Fauadi M H F M，Saptari A[23]為解決Job-shop調(diào)度問(wèn)題，提出使用離散粒子群算法模型求解。

粒子群算法與其他算法結(jié)合進(jìn)行優(yōu)化是目前應(yīng)用較廣泛的手段之一。Li X Y，Gao L，Wang W W等[24]采用遺傳算子重新定義粒子群算法，結(jié)合遺傳算法和粒子群優(yōu)化算法的優(yōu)點(diǎn)來(lái)求解不確定的IPPS問(wèn)題。公式如（5）所示：

3 結(jié)論

研究工作在PSO算法基礎(chǔ)上，以獲取更合適的解決方案為目標(biāo)設(shè)計(jì)了多種的優(yōu)化改進(jìn)策略，并應(yīng)用于制造系統(tǒng)等相關(guān)領(lǐng)域。隨著智能化技術(shù)的不斷深入，所需算法的優(yōu)化要不斷成熟，因此，對(duì)未來(lái)的粒子群算法的重點(diǎn)得出如下結(jié)論：

（1）混合算法可以結(jié)合不同算法的優(yōu)點(diǎn)，彌補(bǔ)單一算法的不足。隨著粒子群算法在不同領(lǐng)域中的廣泛應(yīng)用，其與更多算法的混合會(huì)涉及更多新的領(lǐng)域，帶動(dòng)新領(lǐng)域的進(jìn)展。

（2）多目標(biāo)粒子群算法的基礎(chǔ)研究和靈活性的拓展。由于多目標(biāo)粒子群算法相關(guān)的數(shù)學(xué)理論還不夠完備，算法的收斂性、多樣性、迭代公式和參數(shù)等研究有待深入開(kāi)展。在不同的優(yōu)化階段，需要算法的收斂和多樣性也有所不同。如王學(xué)武， 薛立卡，顧幸生[26]在算法中同實(shí)引入三種突變因子，并用隨機(jī)數(shù)來(lái)選擇策略，以增加所得解的多樣性。因此，算法在問(wèn)題上的靈活調(diào)整機(jī)制不斷優(yōu)化需進(jìn)一步探究。

（3）連續(xù)PSO和離散PSO的性能對(duì)比。PSO最初是解決連續(xù)問(wèn)題提出的，但離散化對(duì)于數(shù)據(jù)的緊湊會(huì)更好。但連續(xù)PSO可通過(guò)映射的方法解決離散問(wèn)題，所以它們的性能的對(duì)比和研究值得進(jìn)一步探討。如文獻(xiàn)[23]通過(guò)求解FT06和FT10實(shí)例的最小使程值，比較了連續(xù)粒子群算法和離散粒子群算法的性能。