粒子群算法在制造調度系統中的應用研究

王楚楚，臧海娟

（1.江蘇理工學院 機械學院，江蘇 常州 213001；2.江蘇理工學院 計算機工程學院，江蘇 常州 213001）

制造業在國家經濟、社會發展中占著重要地位，它直接體現了一個國家的生產力水平。在制造業中，調度問題關系到企業整個生產系統的正常運轉。制造調度系統的智能優化是現代制造和管理的核心[1]，它是針對制造系統中面臨的各種動態事件，在滿足約束條件的前提下，做出及時的響應，以實現生產的最優化[2]。粒子群算法是通過模擬鳥群搜捕食物的方法，找尋現實生活中問題的最優解。由于其實現簡單、可調參數少、尋找結果效率高等優點，被廣泛應用于制造領域調度問題，并取得了大量的成果。本文從算法在制造系統調度中的規劃、優化和應用方面進行綜述和分析。

1 粒子群算法及其演化

鳥類以群體為單位進行覓食，通過每只鳥不斷的分享信息，找到范圍未知的食物。受此過程的啟發，美國的 Kennedy 和 Eberhart博士提出了粒子群算法。在粒子群算法（Particle Swarm Optimization，PSO）中，鳥群個體抽象為無質量無體積的粒子，粒子的位置為候選解。每個粒子初始化都有兩個基本信息，即自身的位置和速度，通過信息基本交互得到個體和群體的最優位置，位置是否最優由適應度函數比較得出。

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

自粒子群算法提出以來，為解決其自身固有的缺點和獲得更好更快的結果，眾多研究者從參數修正、收斂性、混合PSO等角度對算法進行改進，讓其在諸多領域發揮重大的作用。

1.1 參數的修正

PSO的參數的不同選擇對算法性能有著不同的影響，對參數的改進有許多經典算法。

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

1.2 粒子群算法的收斂性

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

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

1.3 混合粒子群算法

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

2 制造系統中的粒子群算法

2.1 制造領域的研究現狀

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

智能制造的目的在于實現整個制造過程的智能化，包括智能技術與產品設計、制造、裝配、運輸等產業鏈的深度融合。基于大數據的智能生產調度與優化技術是實現智能制造的關鍵技術之一，為了解決生產調度問題，應用了多種的基于人工智能的智能算法。制造業重視數據共享、調度的全局性和可擴展性、事件的響應速度等調度問題，促使研究者不斷優化調度系統，改進調度方法。

2.2 粒子群算法與其他智能算法對比

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

2.3 粒子群算法在制造調度中應用

粒子群算法在制造調度中應用大致分為三種：一是將粒子群算法直接運用調度模型中；二是在粒子群算法的基礎上改進算法后運用；三是粒子群算法結合其他算法融合在運用。

在粒子群算法直接解決調度方向上，Muharni Y Irman A，Febianti E等[15]使用PSO算法解決并行機流水車間調度中的調度問題。Nouiri M，Bekrar A，Jemai A等[16]以最小化最大完工時間準則為目標，應用粒子群優化算法求解柔性作業車間調度問題。Liao， J.和Lin， C[17]提出基于粒子群算法的作業車間供應鏈調度優化方法，并通過實例證明了粒子群算法能有效克服生產調度中的不收斂問題，以獲得車間作業調度的最優解。Balaji A.N，Porselvi S，Jawahar N[18]使用粒子群算法解決多單元柔性制造系統中具有順序依賴批量建立時間的零件批調度問題。

針對粒子群算法易陷入局部最優，尋優精度低等問題，提出改進方法解決調度問題。黎書文、張成龍、周知進[19]針對離散制造車間柔性調度優化，提出一種慣性權重、學習因子自適應調整的粒子群算法，并基于改算法建立柔性調度多目標優化模型。此算法基于1－ω＞0且2ω+2－c1－c2＞0的粒子穩定條件改進，更新公式如式（3） 、（4）所示：

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

粒子群算法與其他算法結合進行優化是目前應用較廣泛的手段之一。Li X Y，Gao L，Wang W W等[24]采用遺傳算子重新定義粒子群算法，結合遺傳算法和粒子群優化算法的優點來求解不確定的IPPS問題。公式如（5）所示：

3 結論

研究工作在PSO算法基礎上，以獲取更合適的解決方案為目標設計了多種的優化改進策略，并應用于制造系統等相關領域。隨著智能化技術的不斷深入，所需算法的優化要不斷成熟，因此，對未來的粒子群算法的重點得出如下結論：

（1）混合算法可以結合不同算法的優點，彌補單一算法的不足。隨著粒子群算法在不同領域中的廣泛應用，其與更多算法的混合會涉及更多新的領域，帶動新領域的進展。

（2）多目標粒子群算法的基礎研究和靈活性的拓展。由于多目標粒子群算法相關的數學理論還不夠完備，算法的收斂性、多樣性、迭代公式和參數等研究有待深入開展。在不同的優化階段，需要算法的收斂和多樣性也有所不同。如王學武， 薛立卡，顧幸生[26]在算法中同實引入三種突變因子，并用隨機數來選擇策略，以增加所得解的多樣性。因此，算法在問題上的靈活調整機制不斷優化需進一步探究。

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