劉軍馬超

（蘭州理工大學(xué)機(jī)電工程學(xué)院　蘭州　730050）

1　引言

緩沖區(qū)容量?jī)?yōu)化分配問題（Buffer Allocation Problem，BAP）是一個(gè)NP-hard組合優(yōu)化問題，也是設(shè)計(jì)制造系統(tǒng)中一個(gè)重要的研究方向。緩沖區(qū)容量分配問題是在生產(chǎn)線系統(tǒng)中找到最優(yōu)的緩沖區(qū)容量配置從而完成特定的目標(biāo)，根據(jù)目標(biāo)的不同，可以將該問題分為三類：緩沖區(qū)總量一定時(shí)，以最大化生產(chǎn)率為目標(biāo)對(duì)緩沖區(qū)容量進(jìn)行分配；生產(chǎn)線生產(chǎn)率一定時(shí)，以最小化緩沖區(qū)總量為目標(biāo)對(duì)緩沖區(qū)容量進(jìn)行分配；緩沖區(qū)總量和生產(chǎn)線生產(chǎn)率一定時(shí)，以生產(chǎn)線上平均在制品數(shù)量最少為目標(biāo)對(duì)緩沖區(qū)進(jìn)行分配。自1959年Koenigsberg［1］首次研究該問題以來，各國(guó)學(xué)者在該領(lǐng)域已進(jìn)行了逾50年的探索。主要通過兩步循環(huán)迭代法，即利用有關(guān)解生成方法進(jìn)行容量分配，然后利用生產(chǎn)線性能近似分析技術(shù)進(jìn)行性能評(píng)價(jià)，反復(fù)迭代直至獲得緩沖區(qū)容量分配最優(yōu)解。其中，解生成方法的發(fā)展尤為突出。最簡(jiǎn)單的生成方法就是Chow的遍歷空間法［2］，但只適用于小型系統(tǒng)，當(dāng)設(shè)備數(shù)和緩沖區(qū)容量增加時(shí)可行解數(shù)量呈指數(shù)增長(zhǎng)無法搜索到整個(gè)解空間。早期傳統(tǒng)搜索方法，如分支定界法［3］、梯度法［4］等作為解生成方法在緩沖區(qū)容量分配問題中得到廣泛應(yīng)用，但其主要缺陷是易于陷入局部最優(yōu)，同時(shí)難以觀察緩沖區(qū)容量微小變化對(duì)生產(chǎn)線系統(tǒng)性能造成的影響。因此近年來隨著人工智能、計(jì)算機(jī)技術(shù)的發(fā)展，研究者應(yīng)用元啟發(fā)式算法解決緩沖區(qū)容量分配問題。Nahas［5］利用遺傳算法作為解生成方法很好地解決了生產(chǎn)率一定總花費(fèi)最小目標(biāo)條件下的問題。ZhouBinghai［6］將蟻群算法用于解決生產(chǎn)率最大目標(biāo)函數(shù)下的緩沖區(qū)分配問題較DC算法、GA算法表現(xiàn)出更快的收斂速度和更好的精度。為更好地搜索解空間，將元啟發(fā)式算法與其它方法混合使用也成為主要的技術(shù)發(fā)展趨勢(shì)之一。Kose［7］提出一種遺傳模擬退火算法解決直線型生產(chǎn)線緩沖區(qū)分配問題，較單純遺傳算法、模擬退火算法具有更快的搜索速度和更好的搜索結(jié)果。Mohtashami［8］提出的基于線性搜索的混合遺傳算法在解決最小花費(fèi)和最大生產(chǎn)率目標(biāo)條件下的緩沖區(qū)分配問題時(shí)，表現(xiàn)出較好的搜索性能。

粒子群算法（particle swarm optimization，PSO）作為新一代群智能元啟發(fā)式算法，自1995年被James Kennedy和Russell Eberhart等［9］提出后，由于其概念簡(jiǎn)單，調(diào)整參數(shù)較少，易于編程，沒有復(fù)雜的數(shù)學(xué)操作，對(duì)計(jì)算機(jī)硬件的速度和存儲(chǔ)要求不高等特性，引起了許多學(xué)者的興趣和重視。但是由于粒子群算法出現(xiàn)的歷史較短，該算法用于解決BAP問題的研究尚不多，在理論基礎(chǔ)和應(yīng)用上還有一些急待解決的問題。2002年Elgallad和Fgee等用神經(jīng)網(wǎng)絡(luò)改進(jìn)粒子群算法第一次將其用于緩沖區(qū)分配問題［10］。2009年Can和Heavey將遺傳算法和粒子群算法相結(jié)合用于解決直線型生產(chǎn)線緩沖區(qū)容量分配問題，該方法對(duì)離散變量空間搜索時(shí)表現(xiàn)出較高的精度［11］。2014年 Narasimhamu和 Reddy等用平均值近似分析法作為評(píng)價(jià)算法，粒子群算法作為解生成算法，解決具有單一服務(wù)器的串行閉環(huán)排隊(duì)網(wǎng)絡(luò)模型［12］。2014年P(guān)hatak用PSO算法很好地解決了裝配線緩沖區(qū)容量分配問題［13］。但是上述研究都沒有克服粒子群算法局部搜索能力差以及早熟收斂的缺點(diǎn)。

基于此，針對(duì)受隨機(jī)故障等隨機(jī)事件影響的直線型生產(chǎn)線系統(tǒng)，提出一種多種群粒子群分析技術(shù)，解決生產(chǎn)線在緩沖區(qū)總量固定、生產(chǎn)率最大的目標(biāo)條件下的緩沖區(qū)容量?jī)?yōu)化分配技術(shù)問題。該技術(shù)將一定規(guī)模的粒子群平分成多個(gè)種群，分別按照ω線性遞減策略的粒子群算法的規(guī)則進(jìn)化，并對(duì)各種群中粒子群算法附以不同的慣性權(quán)重，通過“移民算子”實(shí)現(xiàn)各種群的協(xié)同進(jìn)化，并將各種群每代的最優(yōu)個(gè)體放入精華種群加以保存。既保持各子群進(jìn)化的獨(dú)立性，又保證子群間進(jìn)化的合作性。在同樣的實(shí)驗(yàn)參數(shù)設(shè)置下，本文方法與傳統(tǒng)經(jīng)典粒子群改進(jìn)算法進(jìn)行比較。結(jié)果表明，該技術(shù)用于小型、大型生產(chǎn)線系統(tǒng)較傳統(tǒng)算法具有收斂精度高、魯棒性好、局部搜索能力強(qiáng)等優(yōu)點(diǎn)，可以在較小的迭代次數(shù)內(nèi)搜索到全局最優(yōu)解，對(duì)克服早熟收斂有顯著效果，是對(duì)當(dāng)前緩沖區(qū)分配問題研究領(lǐng)域解生成技術(shù)的一個(gè)有效補(bǔ)充。

2　問題描述

本文所研究的受隨機(jī)故障等隨機(jī)事件影響的直線型生產(chǎn)線由 K臺(tái)設(shè)備(M1???Mk)，K-1個(gè)緩沖區(qū) (B1???Bk-1)串聯(lián)組成，如圖1所示。

圖1　直線型生產(chǎn)線模型

原材料從生產(chǎn)線外部進(jìn)入，在第一臺(tái)設(shè)備M1進(jìn)行加工，再進(jìn)入第一個(gè)緩沖區(qū)B1，并依次經(jīng)過后面各個(gè)設(shè)備和緩沖區(qū)，直到最后一臺(tái)設(shè)備Mk，最終離開該生產(chǎn)線。Ci為生產(chǎn)線中各個(gè)緩沖區(qū)的最大緩沖區(qū)容量，在任意時(shí)間t時(shí)，緩沖區(qū)Bi中產(chǎn)品總量為ni∈[0，Ci]，假設(shè)如下：

1）每臺(tái)設(shè)備具有正常工作與故障維修兩種狀態(tài)。令 αi∈{0，1} 表示設(shè)備狀態(tài)，i=1，2，…，K 為設(shè)備。αi=1表示正常運(yùn)行狀態(tài)，若αi=0則表示故障維修狀態(tài)。

2）Mi上游相鄰設(shè)備發(fā)生故障時(shí)，此設(shè)備與Mi之間的緩沖區(qū)中的原材料數(shù)量趨于減少，當(dāng)緩沖區(qū)為空時(shí)，設(shè)備Mi出現(xiàn)“饑餓”現(xiàn)象。Mi下游相鄰設(shè)備發(fā)生故障時(shí)，此設(shè)備與設(shè)備Mi之間緩沖區(qū)中的原材料數(shù)量趨于增加，當(dāng)緩沖區(qū)充滿時(shí)，設(shè)備Mi處于“阻塞”狀態(tài)。

3）假定設(shè)備故障為依靠操作型故障，即設(shè)備僅在操作時(shí)發(fā)生故障而與時(shí)間無關(guān)。當(dāng)設(shè)備既不出現(xiàn)“饑餓”又不出現(xiàn)“阻塞”且正常運(yùn)行時(shí)，其處于工作狀態(tài)。當(dāng)設(shè)備Mi正常工作時(shí)，產(chǎn)品以連續(xù)生產(chǎn)率U從上游緩沖區(qū)Bi-1流向下游緩沖區(qū)Bi，且其滿足Ui=1/Ti，Ti為設(shè)備加工時(shí)間。

4）假設(shè)M1不存在“饑餓”現(xiàn)象，而Mk不存在“堵塞”現(xiàn)象。當(dāng)設(shè)備工作時(shí)，令 pi為設(shè)備故障率，且服從指數(shù)分布，則1 pi表示兩故障之間的平均工作時(shí)間。令ri為設(shè)備維修率，且服從指數(shù)分布，則設(shè)備的平均維修時(shí)間記為1 ri，假設(shè)當(dāng)發(fā)生故障時(shí)，產(chǎn)品在設(shè)備中，經(jīng)維修，得以恢復(fù)正常時(shí)，生產(chǎn)加工仍然繼續(xù)進(jìn)行。

現(xiàn)令 f(ni)為生產(chǎn)線的平均生產(chǎn)率，N為生產(chǎn)線的緩沖區(qū)總量，解決直線型生產(chǎn)線在緩沖區(qū)總量固定、生產(chǎn)率最大的目標(biāo)條件下的緩沖區(qū)容量分配技術(shù)問題。目標(biāo)函數(shù)如下所示：

其中，ni(i=1???k-1)為正整數(shù)，代表為使生產(chǎn)率最大各個(gè)緩沖區(qū)需要配置的緩沖區(qū)容量；f(ni)為各個(gè)緩沖區(qū)容量為ni時(shí)整條生產(chǎn)線的生產(chǎn)率；N代表生產(chǎn)線的緩沖區(qū)總量，取值為正整數(shù)。這里需要注意的是：

生產(chǎn)線平均生產(chǎn)率由設(shè)備數(shù)K、每個(gè)設(shè)備的平均工作效率Ui、故障率 pi、維修率ri、分布類型以及各個(gè)緩沖區(qū)分配的容量ni所決定。本文先用分解法對(duì)生產(chǎn)線進(jìn)行評(píng)價(jià)從而得到平均生產(chǎn)率，然后利用多種群粒子群分析技術(shù)作為解生成方法進(jìn)行容量分配，反復(fù)迭代直至獲得緩沖區(qū)容量分配最優(yōu)解。如圖2所示。

圖2　解決BAP問題的方法

3　分解方法

分解方法基本思想是引入虛擬設(shè)備，將K臺(tái)設(shè)備組成的生產(chǎn)線L，分解成K-1條由上游設(shè)備Mu(i)和下游設(shè)備Md(i)構(gòu)成的雙設(shè)備生產(chǎn)線L(i)(i=1，2，3，???，k-1)通過反復(fù)迭代，不斷調(diào)整虛擬設(shè)備的參數(shù)使各雙設(shè)備生產(chǎn)線L(i)具有原始生產(chǎn)線的操作特性而最終獲得原系統(tǒng)的操作性能指標(biāo)。具體詳細(xì)的過程參照文獻(xiàn)［14］。

以如圖3所示的三臺(tái)設(shè)備生產(chǎn)線L為例，引入虛擬設(shè)備Mu(i)和Md(i)，將原生產(chǎn)線分解為子生產(chǎn)線L(i-2)和L(i-1)。分解后設(shè)備Mu(i-2)，Md(i-1)的參數(shù)保持為原設(shè)備參數(shù)值不變，通過往復(fù)式迭代求解虛擬設(shè)備Md(i-2)和Mu(i-1)的設(shè)備性能參數(shù)以保持原生產(chǎn)線操作特性為目標(biāo)，最終獲得系統(tǒng)性能指標(biāo)。

圖3　分解方法示例

4　多種群粒子群分析技術(shù)

4.1　粒子群算法

粒子群算法首先在可行解空間中初始化一群粒子，每個(gè)粒子都代表極值優(yōu)化問題的一個(gè)潛在最優(yōu)解，用位置、速度和適應(yīng)度三項(xiàng)指標(biāo)表示該粒子特征，適應(yīng)度值由適應(yīng)度函數(shù)計(jì)算得到，其值的好壞表示粒子的優(yōu)劣。粒子在解空間中運(yùn)動(dòng)，通過跟蹤個(gè)體極值Pbest和群體極值Gbest更新個(gè)體位置。粒子每更新一次位置，就計(jì)算一次適應(yīng)度值，并且通過比較新粒子的適應(yīng)度值和個(gè)體極值、群體極值的適應(yīng)度值更新個(gè)體極值和群體極值位置。其數(shù)學(xué)模型為：在D維目標(biāo)搜索解空間中，有n個(gè)粒子組成一個(gè)種群 X=(X1，X2，…，Xn)。 Xi=(Xi1，Xi2，…，Xin)代表第i個(gè)粒子的位置，也表示一個(gè)潛在的最優(yōu)解。每個(gè)粒子的速度用Vi=(Vi1，Vi2，…，ViD)表示。個(gè)體極值Pbest為第i個(gè)微粒所經(jīng)歷過的具有最好適應(yīng)值的位置，記為 Pi=(Pi1，Pi2，…，PiD)；群體極值Gbest為整個(gè)微粒群所經(jīng)歷過的最好位置，記為 Pg=(Pg1，Pg2，…，PgD)。根據(jù)目標(biāo)函數(shù)可以得出粒子位置對(duì)應(yīng)的適應(yīng)度值，以適應(yīng)度值大小衡量粒子的優(yōu)劣。粒子群中各個(gè)粒子的位置和速度不斷的進(jìn)化，其進(jìn)化方程為

其中，i=1，2，…，n為粒子數(shù)；d=1，2，…，D 為維數(shù)；k為當(dāng)前迭代次數(shù)；Xid第i個(gè)粒子第d維的位置；Vid為第i個(gè)粒子第d維的速度；Pid為個(gè)體極值；Pgd為群體極值；ω為慣性權(quán)重值；r1和r2為[0 ， 1]之間隨機(jī)數(shù)；c1和c2為加速度因子，是非負(fù)的常數(shù)。為防止粒子盲目的搜索，一般將速度限制在一定的范圍[-Vmax，Vmax] 。

在式（3）中，第一項(xiàng)為粒子當(dāng)前速度的影響，第二項(xiàng)為粒子個(gè)體最好位置的影響，第三項(xiàng)為群體最好位置的影響。第一項(xiàng)用來平衡全局和局部搜索能力；第二項(xiàng)反映粒子自身經(jīng)驗(yàn)的影響，使粒子具有全局搜索能力，避免陷入局部極值；第三項(xiàng)反映群體經(jīng)驗(yàn)的影響，體現(xiàn)了粒子間的信息共享。

4.2　多種群粒子群分析技術(shù)

多種群粒子群分析技術(shù)（multiple population Particle Swarm Optimization，MPPSO）的基本思想是將一定規(guī)模的粒子群平分成多個(gè)種群，分別按照ω線性遞減策略的粒子群算法的規(guī)則進(jìn)化，對(duì)各種群中粒子群算法附以不同的慣性權(quán)重，并在每一次迭代結(jié)束后進(jìn)行比較，從而得出相對(duì)于三個(gè)種群最優(yōu)個(gè)體的最優(yōu)個(gè)體，放入精華種群保存起來。既保持獨(dú)立性一面，即每一個(gè)子群按照不同的算法規(guī)則計(jì)算；又有合作性的一面，即通過“移民算子”實(shí)現(xiàn)各種群的協(xié)同進(jìn)化。

4.2.1多種群的算法

多種群粒子群分析技術(shù)突破傳統(tǒng)粒子群算法僅靠單個(gè)群體進(jìn)行搜索的框架，將一定規(guī)模的種群平分成多個(gè)子群，分別按照粒子群算法的規(guī)則進(jìn)行優(yōu)化搜索。各子群中的粒子群取不同的參數(shù)，同時(shí)進(jìn)行搜索，極大地增加了種群的多樣性，避免早熟收斂的發(fā)生，更快更好地搜索到整個(gè)解空間。

多種群是相對(duì)獨(dú)立的，相互之間通過“移民算子”聯(lián)系?！耙泼袼阕印睂⒏髯尤涸谶M(jìn)化過程中出現(xiàn)的最優(yōu)個(gè)體定期地引入其他子群中，實(shí)現(xiàn)種群之間的信息交換。具體的操作規(guī)則是，將目標(biāo)種群的最差個(gè)體用源種群的最優(yōu)個(gè)體代替?！耙泼袼阕印痹诙喾N群粒子群算法中至關(guān)重要，如果沒有“移民算子”，各種群之間就失去了聯(lián)系，將等同于用不同的控制參數(shù)進(jìn)行多次粒子群計(jì)算，從而失去了多種群的特色。

在進(jìn)化的每一代結(jié)束后對(duì)各個(gè)種群進(jìn)行比較，從而得出相對(duì)于多個(gè)種群最優(yōu)個(gè)體的最優(yōu)個(gè)體?！熬A種群保留算子”將最優(yōu)個(gè)體放入精華種群加以保存，保證進(jìn)化過程中各種群產(chǎn)生的最優(yōu)個(gè)體不被破壞和丟失。

4.2.2ω的線性遞減策略

多種群粒子群分析技術(shù)各子群均按照ω線性遞減策略的粒子群算法的規(guī)則進(jìn)化。ω是可變參數(shù)，如果ω取值較大，則全局搜索能力強(qiáng)，局部搜索能力弱，不易得到精確解；如果ω較小，則局部搜索能力強(qiáng)，全局搜索能力弱，粒子在局部徘徊，收斂速度慢且會(huì)陷入局部“最優(yōu)解”。為了使算法的全局搜索能力和局部搜索能力得到均衡，我們對(duì)ω進(jìn)行線性遞減的改進(jìn)，如式（5）所示。初期較大的ω使算法具有較強(qiáng)的搜索能力，而后期較小的ω又能夠得到相對(duì)精確的結(jié)果，從而提高了算法的性能。

式（5）中的ωstart為初始慣性權(quán)重，ωend為迭代至最大迭代次數(shù)時(shí)的慣性權(quán)重，k為當(dāng)前的迭代次數(shù)，T為最大的迭代次數(shù)。

為了使得各子群的參數(shù)不同，ωstart服從[0.70-0.95]的均勻分布，ωend服從[0.3-0.45]的均勻分布。通過多個(gè)采用線性遞減策略且慣性權(quán)重不同的種群協(xié)同進(jìn)化，很大程度上增大了種群的多樣性，避免早熟收斂的發(fā)生，使得算法更快更精確地搜索到最優(yōu)解。如下所示：

4.3　多種群粒子群分析技術(shù)的流程

1）確定種群規(guī)模且平分為M個(gè)種群進(jìn)行位置和速度的初始化，設(shè)置相關(guān)參數(shù)。

2）將分解法作為適應(yīng)度函數(shù)分別對(duì)各種群中的粒子進(jìn)行評(píng)價(jià)，得出適應(yīng)度值，記錄各種群的個(gè)體最優(yōu)和群體最優(yōu)。

3）根據(jù)式（5～6）計(jì)算出 ω ，再由式（3～4）對(duì)粒子的速度和位置進(jìn)行更新。

4）計(jì)算各種群中各個(gè)粒子的適應(yīng)度值，用各種群的最優(yōu)適應(yīng)度值更新個(gè)體最優(yōu)與群體最優(yōu)。

5）對(duì)控制參數(shù)不同的M個(gè)種群進(jìn)行移民操作，將目標(biāo)種群的最差個(gè)體用源種群的最優(yōu)個(gè)體代替。

6）在進(jìn)化的每一代，將所有種群的最優(yōu)個(gè)體放入精華種群加以保存。

7）如果達(dá)到終止條件則停止，否則轉(zhuǎn)到步驟2）。

5　仿真實(shí)驗(yàn)

仿真環(huán)境：主頻為2.4GHz，i5-2430的雙核英特爾第二代酷睿處理器（L700-T33B型號(hào)的東芝計(jì)算機(jī)）、W in7旗艦版32位系統(tǒng)以及Matlab R2011b軟件。

圖4　多種群粒子群分析技術(shù)的流程圖

為了驗(yàn)證算法的有效性，針對(duì)常用五設(shè)備小型串行生產(chǎn)線和二十設(shè)備大型串行生產(chǎn)線分別利用本文提出的多種群粒子群分析技術(shù)（MPPSO）、標(biāo)準(zhǔn)粒子群算法（WPSO）［15］與隨機(jī)慣性權(quán)重粒子群算法（MPSO）［15］的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行了比較。在實(shí)驗(yàn)中，假設(shè)每臺(tái)設(shè)備連續(xù)工作時(shí)間和出現(xiàn)故障后的修復(fù)時(shí)間都滿足指數(shù)分布，其平均正常工作時(shí)間（MTTF）和平均修復(fù)時(shí)間（MTTR）已經(jīng)給定。

參數(shù)設(shè)置：種群規(guī)模sizepop=20，學(xué)習(xí)因子c1=c2=0.5。WPSO算法的ω=0.9，MPSO算法的ωmax=0.9，ωmin=0.4。所有算法迭代次數(shù)100，每個(gè)實(shí)驗(yàn)設(shè)置運(yùn)行100次，將100次的平均值作為最終結(jié)果。五設(shè)備生產(chǎn)線的緩沖區(qū)總量B=31。二十設(shè)備生產(chǎn)線中，用于分配的總緩存容量B=100，其余參數(shù)設(shè)置如表1所示。

表1　五設(shè)備生產(chǎn)線的設(shè)備參數(shù)

表2　三種算法下五設(shè)備生產(chǎn)線的生產(chǎn)效率

表3　二十設(shè)備生產(chǎn)線的設(shè)備參數(shù)

表4　三種算法下二十設(shè)備生產(chǎn)線的緩沖區(qū)配置

表5　三種算法下二十設(shè)備生產(chǎn)線的生產(chǎn)效率

由表2、表4、表5可以看出對(duì)于五設(shè)備小型生產(chǎn)線MPPSO的最大生產(chǎn)效率、平均生產(chǎn)效率略高于WPSO和MPSO，對(duì)于二十設(shè)備大型生產(chǎn)線MPPSO的最大生產(chǎn)效率、平均生產(chǎn)效率遠(yuǎn)遠(yuǎn)優(yōu)于其他兩種算法。兩種生產(chǎn)線中MPPSO陷入局部最優(yōu)次數(shù)均遠(yuǎn)高于其他兩種算法，然而MPPSO的運(yùn)行時(shí)間均多于其他算法。

結(jié)合以上數(shù)值實(shí)驗(yàn)分析可知，隨著生產(chǎn)線復(fù)雜程度的增加，MPPSO的收斂精度和魯棒性較其他兩種算法更優(yōu)，可以在較小的迭代次數(shù)內(nèi)尋找到最優(yōu)解，更容易跳出局部最優(yōu)，搜索到全局最優(yōu)解，避免早熟收斂，然而需要的運(yùn)算時(shí)間較長(zhǎng)。

當(dāng)群體規(guī)模較小時(shí)，群體多樣性程度低，個(gè)體之間競(jìng)爭(zhēng)性較弱，隨著進(jìn)化的進(jìn)行，群體很快趨于單一化，比較容易陷入局部最優(yōu)，造成早熟收斂。然而群體規(guī)模過大將會(huì)導(dǎo)致計(jì)算時(shí)間大幅增加，計(jì)算效率受到影響，并且當(dāng)群體數(shù)目增長(zhǎng)至一定水平時(shí)，再增長(zhǎng)將不再有顯著的作用。MPPSO將一定規(guī)模的種群平分成多個(gè)子群，分別按照粒子群算法的規(guī)則進(jìn)行優(yōu)化搜索，通過增加種群個(gè)數(shù)來提高種群規(guī)模，并利用“移民算子”進(jìn)行聯(lián)系，將各子群在進(jìn)化過程中出現(xiàn)的最優(yōu)個(gè)體定期地引入其他的種群中，實(shí)現(xiàn)種群之間的信息交換，互相聯(lián)系，協(xié)同進(jìn)化，大大增加了種群的多樣性，很好地避免了早熟收斂的發(fā)生。然而種群規(guī)模的擴(kuò)大必然導(dǎo)致計(jì)算時(shí)間的增加，在后期學(xué)習(xí)中將致力于減少運(yùn)算時(shí)間的研究中。

較大的慣性權(quán)重將使粒子具有較大的速度，從而有較強(qiáng)的全局搜索能力；較小的慣性權(quán)重將使粒子具有較強(qiáng)的局部搜索能力。慣性權(quán)重的恰當(dāng)設(shè)定涉及粒子群算法全局搜索和局部搜索能力的均衡，進(jìn)化搜索的最終結(jié)果對(duì)慣性權(quán)重的取值相當(dāng)敏感，不同的值很可能會(huì)導(dǎo)致不同的計(jì)算結(jié)果。傳統(tǒng)粒子群算法采用經(jīng)驗(yàn)值慣性權(quán)重，極易造成早熟收斂的發(fā)生。本文提出的算法對(duì)各種群取不同的慣性權(quán)重，并且對(duì)慣性權(quán)重進(jìn)行了線性遞減的改進(jìn)，各種群前期ω變化相對(duì)較慢，取值較大，使得算法的全局收斂能力增強(qiáng)；后期ω變化相對(duì)較快，極大地提高了局部尋優(yōu)能力，種群間協(xié)調(diào)進(jìn)化，同時(shí)兼顧了算法的全局搜索和局部搜索能力，使得算法更快更精確地搜索到最優(yōu)解，很好地避免了早熟收斂的發(fā)生。

6　結(jié)語

針對(duì)受隨機(jī)故障等隨機(jī)事件影響的直線型生產(chǎn)線系統(tǒng)，提出一種多種群粒子群分析技術(shù)，解決生產(chǎn)線在緩沖區(qū)總量固定、生產(chǎn)率最大的目標(biāo)條件下的緩沖區(qū)容量?jī)?yōu)化分配技術(shù)問題。該技術(shù)將一定規(guī)模的粒子群平分成多個(gè)種群，分別按照ω線性遞減策略的粒子群算法的規(guī)則進(jìn)化，并對(duì)各種群中粒子群算法附以不同的慣性權(quán)重，通過“移民算子”實(shí)現(xiàn)各種群的協(xié)同進(jìn)化，并將各種群每代的最優(yōu)個(gè)體放入精華種群加以保存。既保持各子群進(jìn)化的獨(dú)立性，又保證子群間進(jìn)化的合作性。在同樣的實(shí)驗(yàn)參數(shù)設(shè)置下，本文方法與傳統(tǒng)經(jīng)典粒子群改進(jìn)算法在小型、大型生產(chǎn)線系統(tǒng)中進(jìn)行比較。結(jié)果表明，隨著生產(chǎn)線復(fù)雜程度的增加，該技術(shù)較傳統(tǒng)算法具有收斂精度高、魯棒性好、局部搜索能力強(qiáng)等優(yōu)點(diǎn)，可以在較小的迭代次數(shù)內(nèi)搜索到全局最優(yōu)解，對(duì)克服早熟收斂有顯著效果。然而需要較長(zhǎng)的運(yùn)算時(shí)間，如何提高收斂速度，降低運(yùn)算時(shí)間將會(huì)是今后研究中值得考慮的問題。另外，本文研究的主要模型為直線型生產(chǎn)線，但在實(shí)際生產(chǎn)中還有許多其他類型更加復(fù)雜的生產(chǎn)線比如平行線、裝配線、環(huán)線。希望在以后的研究中將本文的方法進(jìn)行擴(kuò)展，可以在更多類型生產(chǎn)線上得到應(yīng)用。

［1］Koenigsberg，E.Production lines and internal storage—A review［J］.ManagementScience，2007，59（5）：410-433.

［2］Chow W M.Buffer Capacity Analysis for Sequential Production Lines With Variable Process Times.［J］.International Journal of Production Research，1987，25（8）：1183-1196.

［3］DolguiA，Eremeev A V.HBBA：hybrid algorithm for buffer allocation in tandem production lines［J］.Journalof IntelligentManufacturing，2007，18（3）：411-420.

［4］Gershwin S B，Schor JE.Efficient algorithms for buffer space allocation［J］.Annals of Operations Research，2000，93（1）：117-144.

［5］Nahas N.Bufferallocation，machine selection and preventive maintenance optimization in unreliable production lines［J］.Journal of IntelligentManufacturing，2014，209（1）：1-9.

［6］ZhouBinghai，YuJiadi.Buffer allocation method of serial production lines based on improve dantcolony optimization algorithm［J］.高技術(shù)通訊（英文版），2016，22（2）：113-119.

［7］Kose SY，Kilincci O.Hybrid approach for buffer allocation in open serial production lines［J］.Computers&Operations Research，2015，60（C）：67-78.

［8］K?se SY，Demir L，Tunal?S，et al.Capacity improvement using simulation optimization approaches：A case study in the thermotechnology industry［J］.Engineering Optimization，2014，47（2）：1-16.

［9］Kennedy J，Eberhart R.Particle swarm optimization［C］//IEEEInternational Conference onNeural Networks，1995.Proceedings.IEEE，1995：1942-1948 vol.4.

［10］Elgallad A，El-Hawary M，Phillips W，et al.PSO-based neural network for dynamic bandwidth re-allocation［power system communication］［C］//Power Engineering 2002 Large Engineering Systems Conference on，LESCOPE 02.IEEE，2002：98-102.

［11］Can B，Heavey C.Sequentialmetamodelling with genetic programming and particle swarms［C］//Simulation Conference.IEEE，2009：3150-3157.

［12］Narasimhamu K L，Reddy V V，Rao CSP.Optimal Buffer Allocation in Tandem Closed Queuing Network with Single Server Using PSO ☆［J］.Procedia Materials Science，2014，5：2084-2089.

［13］Phatak S，Venkateswaran J，Pandey G，etal.Simulation based optimization using PSO in manufacturing flow problems：a case study［C］//SimulationConference.IEEE，2014：2136-2146.

［14］Liu J，Kong J，F(xiàn)an Q.Performance Analysis of Non-Homogeneous Hybrid Production Lines［J］.2014，4（5）：463-467.

［15］張志宇，白云霞.粒子群算法不同慣性權(quán)重之間的比較［J］.淮海工學(xué)院學(xué)報(bào)：自然科學(xué)版，2016，25（1）：1-6.WANG Zhiyu，BAIYunxia.Comparison ofDifferent Inertia Weight Based on Particle Swarm Optimization［J］.Journal of Huaihai Institute of Technology：Natural Science Edition，2016，25（1）：1-6.