基于準時化生產要求下改進型粒子群算法研究

(浙江工業大學 信息工程學院，浙江 杭州 310023)

在這個日新月異的市場環境下，競爭日益加劇，人們對個性化產品的追求與日俱增，越來越多的企業面臨升級轉型。由傳統粗放型、大規模批量生產轉向面對客戶個性化需求的小規模、多批次的以市場和客戶為導向的新型生產模式[1]。以下主要研究在此種新模式下，企業如何能按照訂單要求準時將產品送達客戶手中。為達到這一目標，企業生產過程中原材料、半成品的準時化配送就顯得十分重要。傳統的“領料式”配送方式，配送周期全憑經驗，以生產要料為主導，缺乏主動配送思想，配送效率低[2]。為實現對多目標條件下的準時化配送，通過研究改進型粒子群算法[3]，合理地安排物料配送方式，并將此算法與粒子群算法、遺傳算法和三段啟發式算法[4]進行比較驗證，分析算法的有效性。

1 多目標材料配送模型

1.1 配送時間點選取

生產制造工程中，材料的配送時間點選取至關重要，以往常由生產線工人的經驗決定，但在多樣化、面向訂單、個性化生產模式下，產品的種類變化多樣，經驗效應的可靠性受到很大影響，容易造成材料被過早或過遲配送到工位的情況，從而造成生產線旁材料的堆積或生產待料的情形[5]。因此為保證制造型企業準時化生產，合理地選擇配送點是先決條件。

現實生產中不能等到工位庫存消耗完畢才請求配送，因為材料的運輸、裝卸都需要時間，而此時工位處于閑置狀態，因此必須考慮到材料運輸的提前量。就此提出一個優化后的時間懲罰函數模型為

BTi=min(ZTi)+(NLi+KLi-SSi+S0)/Vi

(1)

LTi=min(ZTi)+(NLi+S0)/Vi

(2)

(3)

RTi=(Qi-S)/Vi

(4)

STi=BTi-RTi=min[(S-SSi)/Vi]

(5)

式中：S0為最初生產線旁庫存量；SSi為安全庫存量；min(ZTi)為最短配送提前量；KLi為工位邊的材料保有量；NLi為發送給管控中心的材料需求量；Vi為I材料的消耗速度[6]；Tα為材料的裝卸所消耗的時間；RTi為生產線發出材料需求的時間點；STi為最佳送達點的提前量；S為運送量；Tij為運輸時間。

對每次配送時間點進行分析，如圖1所示，根據優化后的時間懲罰函數進行分析，可較為準確地判定理想材料配送點。

圖1 材料配送時間點Fig.1 Material distribution point of time analysis

1.2 配送模型建立

傳統一對一或者定點式配送方式，成本高、周期長，缺點明顯。在一個制造型企業車間，需要的物料種類繁多，工位與工位之間變換頻繁，單一的配送方式極大影響生產。通過引入多目標配送概念，將配送方式優化，求解最優集，并根據實際要求從最優集中選擇配送方案[7]。

令目標函數F(x)為

F(x) =G{min[C(x),L(x),T(x)]}

(6)

(7)

(8)

minL(x)=Xi+Yi

(9)

(10)

(11)

minT(x)=ZTi+(NLi+
KLi-SSi+S0)/Vi

(12)

(13)

RTi=(Qi-S)/Vi

(14)

2 改進型粒子群算法的設計與優化

2.1 改進型粒子群算法的設計思路

粒子群算法最初來自于人工生命理論和復雜演化算法，其特點是利用在群體生活中個體間通過一定的交流且共享信息，通過運算反復迭代[8]在短時間內進行全局搜索，尋找出最優解的技術[9]。目前很多國內外專家為改進粒子群算法，常引入慣性權重、修正系數等方式改變初始粒子的速度和位置，以優化公式[10]。但在實際應用時，單一的粒子群算法不足以滿足需求，該算法收斂精度較差，容易陷入局部最優，為此提出將遺傳算法和模擬退火算法中利于尋優的部分揉合進粒子群算法中，以便提升算法優化準確性，提高搜索效率。

對粒子群算法優化如下：

1) 因為遺傳算法依照生物遺傳理論對算法中的決策變量進行編碼，能夠有效應對組合中的2 次分配問題，所以利用此特點將例子采用此方式進行編碼。

2) 為防止算法早熟，引入遺傳算法中的交叉策略和變異策略，以解決粒子初始位置和速度的不合理選擇產生的一系列問題。

3) 為避免在整體尋優過程中出現局部最優的情況，可以運用模擬退火算法中的Meteropolis準則[11]即重復對當前解進行迭代計算，以得到近似最優解。

2.2 改進型粒子群算法設計

根據設計思路，改進型粒子群算法針對實際生產過程中需要多目標工位實現準時材料配送過程的建模過程如下：

1) 以運送材料所需的花費、運送次數、運送所需消耗的時長為目標建立適應函數，并引入權重的系數進行優化評價，其表達式為

(15)

ωC+ωL+ωT=1

(16)

式中：x為個體粒子可行解；ωC，ωL，ωT分別為運送花費的權重、運送次數的權重和運送時長的權重，且3個權重系數之和為1。根據實際生產情況可按照需求分配權重，緊急情況下可側重時長，一般生產可側重成本。

2) 編碼。因為生產實際中考慮的多個因素作用的共同結果，所以在編碼時采用優化運算為

第1 次優化運算：

(17)

第2 次優化運算：

(18)

第S次優化運算：

(19)

式中：T1為第1 次材料運送到的時間；X11為1 號材料運送到1 號工位的數量；Y11為1 號材料運送到1 號位置所需要的車次。式(17～19)分別為改進型粒子群算法運算時第1 次、第2 次和第S次的粒子。

4) 交叉、變異策略。通過對遺傳算法中交叉變異策略的研究，采用單點交叉策略，并使用“父對染色體分段—比較選擇—復制替換—形成新粒子”的方法形成具有可行解的新粒子。具體操作如圖2所示。

圖2 交叉、變異策略框圖Fig.2 Cross, mutation strategy diagram

該變異策略通過基因突變的方法，使得粒子中的染色體部分片段得以改變，增強了粒子群算法從局部尋優的能力，通過此策略既改變了染色體的基因片段,增加了粒子群的多樣性,又可以防止算法早熟現象的出現。

此改進型粒子群算法是基于對全局最優解P的優化，其中新的初始粒子的產生是通過將變異操作前選取的隨機數與變異概率ρ進行比較，若隨機數大于等于ρ時，P不變，否則就改變P。此時全局最優解P就可以用變異策略產生的隨機初始種群粒子來代替。

如圖3所示，改進型粒子群算法具體流程如下：

步驟1選取初始粒子位置P和初速度V。

步驟2建立適應函數f(x)，選取合適權重并計算f(x)。

步驟3設計初始種群，確定C(x)，L(x)，T(x)。

步驟4更新個體極值Pi和群體極值Pg。

步驟5更新速度V和位置。

步驟6通過交叉與變異策略尋找全局最優解P。

步驟7計算適應度函數f(x)，得到最優的(C，L，T)。

步驟8判斷是否滿足終止條件，如滿足則迭代終止，輸出解，否則返回步驟3。

圖3 改進型粒子群算法流程框圖Fig.3 Improved particle swarm optimization flowchart

3 實驗仿真

通過選取湖州某重型機械公司的履帶式起重機的主臂生產線為加工實例，運用提出的改進型粒子群算法模型，并基于Matlab2014a仿真平臺來驗證其有效性。其中電腦主頻為2.30 GHz，內存為4.00 GB，CPU為i5-2410M。

表1 改進型粒子群算法、標準遺傳算法和三段啟發式算法計算結果

Table 1 Improved particle swarm optimization, standard genetic algorithm, three-section heuristic algorithm results

算法配送花費C/元 運送次數L/次 運送時長T/s改進型粒子群算法2719173標準遺傳算法36616341三段啟發式算法35614362

通過計算可以清楚地發現：相比于標準遺傳算法與三段啟發式算法，利用改進型粒子群算法能夠在配送花費C、運送次數L和運送時長T等3 個方面得到顯著改善。之后通過圖4比對改進型粒子群算法、粒子群算法和標準遺傳算法的收斂性，得出結論：改進型粒子群算法的收斂速度明顯優于粒子群算法和遺傳算法，且改進型粒子群算法相較于粒子群算法，它的收斂精度得到明顯改善。

圖4 改進型粒子群算法、粒子群算法和遺傳算法收斂性比較Fig.4 Improved particle swarm optimization, particle swarm optimization and genetic algorithm convergence comparison

通過計算：當ωC=1時，所對應的C=258，L=14，T=194；當ωL=1時，C=314，L=8，T=166；當ωT=1時，C=283，L=11，T=151?？梢园l現：3 項數據中任何1 項達到最優時，另外2 項都不能達到最優。對應在實際生產中，企業根據訂單狀況，對解(C，L，T)要求不一樣，因此可以相對應調整慣性權重的值來指導生產。

4 結 論

針對制造型企業在新形勢下面向訂單準時化生產問題，提出了一種改進型的粒子群算法，該算法采用遺傳算法的編碼方式和交叉變異策略，又通過模擬退火算法中的Meteropolis準則即重復對當前解進行迭代計算得到近似最優解。通過實驗發現改進型的粒子群算法增加了算法收斂速度和精度，能較快得到全局最優解，同時通過改變適應函數的慣性權重可以按照實際生產要求安排生產，由此證明了該改進型粒子群算法的有效性。