基于改進(jìn)PSO算法的任務(wù)分配研究

曾文權(quán)，余愛(ài)民

廣東科學(xué)技術(shù)職業(yè)學(xué)院 計(jì)算機(jī)工程學(xué)院，廣東 珠海 519090

基于改進(jìn)PSO算法的任務(wù)分配研究

曾文權(quán)，余愛(ài)民

廣東科學(xué)技術(shù)職業(yè)學(xué)院 計(jì)算機(jī)工程學(xué)院，廣東 珠海 519090

1 引言

虛擬企業(yè)是一種企業(yè)經(jīng)營(yíng)模式，在獲得客戶訂單后，盟主企業(yè)首先將訂單任務(wù)分解和分類為若干個(gè)子任務(wù)，然后采用招投標(biāo)或協(xié)商等方式為每個(gè)子任務(wù)選擇合適的供應(yīng)商，該過(guò)程即虛擬企業(yè)中的任務(wù)分配或任務(wù)調(diào)度。

針對(duì)虛擬企業(yè)中的任務(wù)分配或調(diào)度問(wèn)題，已有研究大多基于多Agent的協(xié)商與協(xié)作能力，首先建立起任務(wù)分配或調(diào)度的數(shù)學(xué)模型，然后采用各種數(shù)學(xué)方法或智能優(yōu)化算法進(jìn)行模型的求解[1-3]；或者基于多Agent技術(shù)設(shè)計(jì)和開發(fā)任務(wù)的分配或調(diào)度系統(tǒng)[4-5]。任務(wù)的分配與調(diào)度是一個(gè)NP難題[6]，PSO算法由于其具有收斂速度快以及魯棒性好等優(yōu)點(diǎn)而得到了廣泛應(yīng)用，如針對(duì)多無(wú)人作戰(zhàn)飛機(jī)的協(xié)同控制[7-9]、雷達(dá)干擾[10]、多機(jī)器人系統(tǒng)[11]、網(wǎng)格系統(tǒng)[12]等領(lǐng)域的任務(wù)分配與調(diào)度。然而，PSO算法存在著易早熟收斂、后期搜索精度與迭代效率不高等缺陷[13-14]。因此，實(shí)際應(yīng)用中，對(duì)基于PSO求解任務(wù)分配與調(diào)度問(wèn)題大多需要進(jìn)行改進(jìn)。改進(jìn)的方法包括：引入聲搜索策略以克服陷入局部最優(yōu)[15]；采用自適應(yīng)慣性權(quán)重提高算法的收斂速度[7]；在算法中引入遺傳算法中的克隆和變異算子[11]；模擬生物免疫系統(tǒng)的特征和機(jī)制改進(jìn)PSO算法[9]基于網(wǎng)格的特性與PSO的混合粒子群的算法[16]等。由于虛擬企業(yè)中訂單任務(wù)的分配是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，盟主企業(yè)期望以最少的費(fèi)用、最短的交貨期、最高的供應(yīng)質(zhì)量和最小的風(fēng)險(xiǎn)等完成訂單任務(wù)。因此，本文首先建立起訂單任務(wù)分配的多目標(biāo)優(yōu)化決策模型，然后在分析傳統(tǒng)PSO算法的基礎(chǔ)上對(duì)其進(jìn)行改進(jìn)，并基于該方法求解任務(wù)的分配問(wèn)題，最后通過(guò)實(shí)際應(yīng)用實(shí)例和仿真實(shí)驗(yàn)來(lái)驗(yàn)證該方法的可行性和有效性。

2 任務(wù)分配的多目標(biāo)決策模型

2.1 模型假設(shè)

記n個(gè)待分配任務(wù)記為T={t1，t2，…，ti，…，tn}，則模型假設(shè)和參數(shù)描述為：

（1）任務(wù)ti之間相互獨(dú)立，任務(wù)ti的候選供應(yīng)商集合記為Pi={pi1，pi2，…，pij，…，pimi}；

（2）若任務(wù)ti分配給了供應(yīng)商pij，則狀態(tài)變量uij=1，否則uij=0；

（3）供應(yīng)商pij申請(qǐng)任務(wù)ti的信息中包括完成任務(wù)的費(fèi)用cij、交貨期限tij、質(zhì)量等級(jí)qij；

（4）盟主企業(yè)對(duì)供應(yīng)商pij的綜合信任度為rij；

（5）盟主企業(yè)期望以最少的費(fèi)用（C）、最短的交貨期限（T）、最高的質(zhì)量等級(jí)（Q）和最小的風(fēng)險(xiǎn)（R）完成訂單任務(wù)。

2.2 建立模型

任務(wù)分配的目標(biāo)即為每個(gè)ti(i=1，2，…，n)從Pi中選擇一個(gè)供應(yīng)商pij(i=1，2，…，n;j=1，2，…，mi)，以滿足盟主企業(yè)的期望。假設(shè)盟主企業(yè)對(duì)供應(yīng)商的信任度記為TR，則其任務(wù)分配的目標(biāo)函數(shù)為：

然而，上述目標(biāo)在實(shí)際中是不可能實(shí)現(xiàn)的，針對(duì)該目標(biāo)只能求得一組優(yōu)化解。在對(duì)cij、tij、qij以及trij按Min-Max方法歸一化處理后，建立任務(wù)分配目標(biāo)的決策優(yōu)化模型為：

3 PSO算法與改進(jìn)

3.1 PSO算法

PSO算法模擬鳥群的覓食行為，其基本思想是：粒子（一個(gè)候選解）從隨機(jī)的初始位置以隨機(jī)的初始速度開始搜索，并記錄下搜索過(guò)程中單個(gè)粒子所經(jīng)歷的最好位置（個(gè)體最優(yōu)解），以及整個(gè)粒子群體所經(jīng)歷過(guò)的最好位置（全局最優(yōu)解），一次搜索結(jié)束后各個(gè)粒子通過(guò)個(gè)體最優(yōu)解和全局最優(yōu)解更新自己的飛行速度和位置，并進(jìn)行下一輪的搜索，依此直至搜索次數(shù)達(dá)到設(shè)定值，則全局最優(yōu)解為搜索問(wèn)題的優(yōu)化解。

其中ω為速度慣性權(quán)重；c1和c2為加速度系數(shù)，分別為將粒子推向和的權(quán)重；r1和r2為區(qū)間[0，1]上的隨機(jī)數(shù)。

3.2 PSO算法的改進(jìn)

實(shí)踐證明，PSO算法具有收斂速度快和通用性強(qiáng)的優(yōu)點(diǎn)，但存在著易早熟收斂，搜索精度不高，以及后期迭代效率不高等缺陷[13-14]。因此，本文從PSO算法參數(shù)的調(diào)整，并引入遺傳算法中的變異操作對(duì)其進(jìn)行改進(jìn)，在保留其優(yōu)勢(shì)的同時(shí)克服其不足。

（1）速度慣性權(quán)重的調(diào)整

速度慣性權(quán)重ω取值較大時(shí)有利于克服算法陷入局部最優(yōu)，而取值較小時(shí)有利于算法收斂。因此，在算法的起初階段，由于粒子缺乏對(duì)搜索空間的認(rèn)識(shí)且沒(méi)有足夠的參照，ω應(yīng)取較大值以擴(kuò)大粒子群的搜索范圍，從而提高搜全率；而在算法的收斂階段，ω應(yīng)取較小值以盡可能搜索最優(yōu)解周邊的小范圍，從而提高搜準(zhǔn)率。因此，設(shè)定ω的自動(dòng)調(diào)整公式為：

其中ωk為第k(k=2，3，…，T)次搜索時(shí)的慣性權(quán)重，T為最大搜索次數(shù)，ω1為慣性權(quán)重的初始值。

（2）c1和c2的調(diào)整

c1和c2是分別用于調(diào)整個(gè)體最優(yōu)解與全局最優(yōu)解在粒子搜索過(guò)程中所起作用大小的兩個(gè)參數(shù)。對(duì)c1和c2的調(diào)整策略為：若粒子當(dāng)前位置的適應(yīng)度大于粒子群體適應(yīng)度的平均值，則增大c1且減小c2，以增加粒子沿自身方向飛行的速度，而減少向全局極值方向飛行的速度，反之采用相反策略。

c1和c2的自動(dòng)調(diào)整方式描述為：記第k次搜索時(shí)粒子位置的適應(yīng)度值為，而粒子群體適應(yīng)度的平均值為，則第k+1次搜索時(shí)c1和c2的調(diào)整公式如下：

（3）引入變異操作

為了避免粒子群陷入局部最優(yōu)，在算法中引入遺傳算法中的變異操作。若單個(gè)粒子的個(gè)體最優(yōu)解連續(xù)ξ（變異閾值）次沒(méi)有更新，則采用兩點(diǎn)變異策略對(duì)做變異操作。首先，產(chǎn)生[1，n]內(nèi)的兩個(gè)隨機(jī)數(shù)na和nb(1≤na≠nb≤n)，然后將中位置序號(hào)分別為na和nb的兩個(gè)元素交換位置后作為粒子新的個(gè)體最優(yōu)解。

4 基于改進(jìn)PSO算法求解任務(wù)分配模型

4.1 問(wèn)題與粒子的映射

針對(duì)模型（1），待分配的任務(wù)數(shù)n即粒子搜索空間的維度，則粒子i的位置為Xi=(xi1，xi2，…，xij，…，xin)，xij即為任務(wù)tj分配的候選供應(yīng)商序號(hào)，且xij取區(qū)間[1，mj]內(nèi)的整數(shù)，mj為申請(qǐng)任務(wù)tj的供應(yīng)商個(gè)數(shù)；粒子速度vij的取值范圍設(shè)定為[-(mj-1)，(mj-1)]。

由于xij取整數(shù)，當(dāng)采用式（3）更新粒子位置后，若其值在[1，mj]內(nèi)，則直接取結(jié)果的整數(shù)部分。否則，若xij＞mj，則xij=mj；若xij＜1，則xij=1。當(dāng)按式（4）更新粒子的速度后，若vij＞mj-1，則vij=mj-1；若vij＜-(mj-1)，則vij=-(mj-1)。

4.2 粒子位置適應(yīng)度值的計(jì)算

在計(jì)算粒子群中各粒子位置的適應(yīng)度值時(shí)，本文采用TOPSIS[17]方法進(jìn)行計(jì)算。設(shè)粒子群的粒子個(gè)體數(shù)m，則其計(jì)算方法描述為：

步驟1根據(jù)各粒子的位置Xi，得到粒子群的位置M= (xi1，…，xij，…，xin)m×n。

步驟2根據(jù)xij讀取出對(duì)應(yīng)的費(fèi)用信息cij、交貨期限tij、質(zhì)量等級(jí)qij和綜合信任度trij，則M變形為M′=[(ci1，ti1，qi1，tri1)，…，(cij，tij，qij，trij)，…，(cin，tin，qin，trin)]m×n。

步驟3針對(duì)M′中的(cij，tij，qij，trij)，首先對(duì)各個(gè)分量按列進(jìn)行歸一化處理后，然后計(jì)算M′中各行與正理想解和負(fù)理想解之間的距離，其計(jì)算公式分別為：

步驟4計(jì)算出各個(gè)粒子的位置適應(yīng)度值，公式為：

4.3 任務(wù)分配模型的求解算法

基于改進(jìn)的PSO算法求解任務(wù)分配模型（1）的算法步驟為：

步驟1設(shè)置算法的參數(shù)。設(shè)粒子群粒子個(gè)數(shù)為m，最大搜索次數(shù)（迭代次數(shù)）為T，粒子群慣性權(quán)重初始值和最后一次搜索時(shí)的值分別為ω1和ωT，設(shè)定c1和c2的初始值，以及變異閾值ξ。

步驟2隨機(jī)生成粒子群的初始位置和初始速度

步驟3計(jì)算出粒子群中各個(gè)粒子的位置適應(yīng)度值，進(jìn)而得到單個(gè)粒子的個(gè)體最優(yōu)解和粒子群的全局最優(yōu)解

步驟4采用式（2）和（3）更新粒子群的速度vij和位置xij，對(duì)vij和xij的取值按4.1節(jié)的方法進(jìn)行處理。

步驟5若搜索次數(shù)k=T，轉(zhuǎn)步驟7；否則轉(zhuǎn)步驟6。

步驟6對(duì)步驟3中連續(xù)ξ次未變化過(guò)的做變異操作，然后按（4）、（5）和（6）式更新慣性權(quán)重，c1和c2，并轉(zhuǎn)步驟3。

步驟7輸出步驟3中的，即為模型（1）的最優(yōu)解，算法結(jié)束。

5 應(yīng)用實(shí)例及仿真實(shí)驗(yàn)

5.1 應(yīng)用實(shí)例

某面向全球范圍從事機(jī)械類零部件產(chǎn)品加工定制的虛擬企業(yè)，盟主企業(yè)將4類待分配任務(wù)t1、t2、t3和t4向虛擬企業(yè)中的供應(yīng)商成員企業(yè)發(fā)布后，針對(duì)各個(gè)任務(wù)，收集到供應(yīng)商提交的任務(wù)申請(qǐng)信息包括費(fèi)用（萬(wàn)元）、交貨期限（天）、質(zhì)量等級(jí)，如表1所示。

表1 各供應(yīng)商對(duì)任務(wù)的申請(qǐng)信息

對(duì)表1中的信息加上盟主企業(yè)對(duì)各供應(yīng)商的信任度值后，按Min-Max方法進(jìn)行歸一化處理后的結(jié)果，如表2所示。

表2 歸一化后的任務(wù)申請(qǐng)信息

按照本文的任務(wù)分配求解算法，采用Matlab 7.0提供的PSO算法工具進(jìn)行求解。求解過(guò)程中，設(shè)置粒子群粒子的個(gè)數(shù)m=10，粒子搜索空間的維度n=4，最大搜索次數(shù)T=50，初始慣性權(quán)重和最后一次搜索的慣性權(quán)重分別為ω1=0.9和ωT=0.1，c1和c2的初始值分別設(shè)為2，變異閾值ξ=4，求解結(jié)果如表3所示。

表3 算法運(yùn)行結(jié)果

對(duì)表2中所有的240種任務(wù)分配組合分別進(jìn)行適應(yīng)度值計(jì)算后，其結(jié)果與算法的求解結(jié)果一致，均表明任務(wù)分配序列（2，3，3，3）為最優(yōu)解。

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

為了驗(yàn)證本文方法有效性，任務(wù)數(shù)分別設(shè)為10個(gè)、20個(gè)、50個(gè)、70個(gè)和100個(gè)，各個(gè)任務(wù)的候選供應(yīng)商個(gè)數(shù)假設(shè)都為10個(gè)，供應(yīng)商提交的任務(wù)申請(qǐng)信息以及盟主企業(yè)對(duì)供應(yīng)商的信任度值取[0，1]上隨機(jī)數(shù)的條件下，分別采用本文的方法和傳統(tǒng)PSO算法進(jìn)行求解。求解時(shí)：設(shè)定粒子群個(gè)數(shù)m=50，搜索空間維度為任務(wù)的個(gè)數(shù)，最大迭代次數(shù)T=1 000；針對(duì)本文改進(jìn)的PSO算法，設(shè)定ω1=0.9，ωT=0.1，c1和c2的初值均為2，ξ=4；PSO算法中ω=0.9，c1=2，c2=2。針對(duì)不同任務(wù)數(shù)的仿真結(jié)果分別如圖1～圖5所示，各任務(wù)數(shù)與收斂時(shí)的搜索次數(shù)關(guān)系如圖6所示。

圖1～圖5的實(shí)驗(yàn)結(jié)果表明，本文對(duì)PSO算法進(jìn)行改進(jìn)后，既提高了傳統(tǒng)PSO算法的收斂速度，也克服了其易陷入局部最優(yōu)解的缺陷。并且從圖6可看出，隨著求解問(wèn)題規(guī)模的擴(kuò)大，算法的收斂次數(shù)不是呈指數(shù)變化，進(jìn)一步說(shuō)明本文方法有較好的優(yōu)化特性。

6 結(jié)束語(yǔ)

為了提高PSO算法的收斂速度，盡量避免算法陷入局部最優(yōu)，通過(guò)PSO算法中可調(diào)節(jié)參數(shù)的自動(dòng)調(diào)整，并引入遺傳算法中的變異操作，進(jìn)而設(shè)計(jì)了基于改進(jìn)PSO算法求解任務(wù)分配多目標(biāo)優(yōu)化模型的方法。實(shí)驗(yàn)證明該方法既保留了PSO算法易實(shí)現(xiàn)和收斂速度快的優(yōu)點(diǎn)，同時(shí)克服了其容易陷入局部最優(yōu)的缺陷。本文的方法對(duì)類似多目標(biāo)組合優(yōu)化問(wèn)題的求解具有一定的參考意義。

圖1 10個(gè)任務(wù)的實(shí)驗(yàn)結(jié)果

圖2 20個(gè)任務(wù)的實(shí)驗(yàn)結(jié)果

圖3 50個(gè)任務(wù)的實(shí)驗(yàn)結(jié)果

圖4 70個(gè)任務(wù)的實(shí)驗(yàn)結(jié)果

圖5 100個(gè)任務(wù)的實(shí)驗(yàn)結(jié)果

圖6 任務(wù)個(gè)數(shù)不同時(shí)的搜索次數(shù)

[1]高陽(yáng)，周偉.基于多Agent的虛擬企業(yè)調(diào)度研究與實(shí)現(xiàn)[J].中國(guó)機(jī)械工程，2004，15（11）：978-982.

[2]趙強(qiáng)，肖人彬.基于多Agent的虛擬企業(yè)任務(wù)調(diào)度模型[J].控制理論與應(yīng)用，2009，26（4）：459-462.

[3]程方啟，王洪飛，葉飛帆.橫向虛擬企業(yè)訂單分配模型研究[J].機(jī)電工程，2009，26（4）：50-52.

[4]Kyung-Hyun C，Dong-Soo K，Yang-Hoi D.Multi-agent based taskassignmentsystemforvirtualenterprises[J].Robotics and Computer Integrated Manufacturing，2007，23：624-629.

[5]Shen Chenglin.Decision models of task assignment for virtual enterprise based on multi-agent theory[C]//Proceedings International Conference on Management and Service Science，2009.

[6]Lin W，Byrnes C.Control of discrete-time nonlinear system[J]. IEEE Transactions on Automatic Control，1996，41（4）：494-510.

[7]杜繼永，張鳳鳴，楊驥，等.多UCAV協(xié)同任務(wù)分配模型及粒子群算法求解[J].控制與決策，2012，27（11）：1751-1755.

[8]國(guó)博，王社偉，陶軍.基于改進(jìn)粒子群算法的多無(wú)人機(jī)任務(wù)分配研究[J].計(jì)算機(jī)仿真，2009，26（7）：62-65.

[9]有偉，王社偉，陶軍.基于免疫粒子群算法的多UCAV協(xié)同任務(wù)分配[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（32）：224-227.

[10]李俊，郝成民，劉湘?zhèn)?改進(jìn)PSO算法在雷達(dá)干擾任務(wù)分配中的應(yīng)用[J].計(jì)算機(jī)仿真，2008，25（12）：27-29.

[11]李濟(jì)澤.基于粒子群遺傳優(yōu)化算法的多機(jī)器人任務(wù)分配研究[J].機(jī)械與電子，2007（10）：45-48.

[12]王成昌，陳閎中，方鈺，等.基于混合粒子群算法的網(wǎng)格任務(wù)調(diào)度[J].計(jì)算機(jī)科學(xué)，2012，39（2）：18-21.

[13]Angeline P J.Evolutionary optimization versus particle swarm optimization：philosophyandperformancedifference[C]// Proc of the 7th Annual Conf on Evolutionary Programming，Germany，1998.

[14]劉衍民.粒子群算法的研究及應(yīng)用[D].濟(jì)南：山東師范大學(xué)，2011.

[15]陳大川，張榮國(guó)，黃付亮，等.PSO算法在子任務(wù)分配中的應(yīng)用[J].計(jì)算機(jī)工程，2011，37（24）：183-186.

[16]葉春曉，羅娟.基于網(wǎng)格的混合微粒群算法解決任務(wù)調(diào)度問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（12）：34-37.

[17]Ertuqrul I，Karakasoqlu N.Performance evaluation of Turkish cement firms withfuzzyanalytic hierarchyprocess and TOPSIS methods[J].Expert Systems with Application，2009，36（1）：702-715.

ZENG Wenquan,YU Aimin

School of Computer Engineering&Technology,Guangdong Institute of Science&Technology,Zhuhai,Guangdong 519090,China

To solve the task allocation in virtual enterprise,a multi-object decision-making optimization model on task allocation is constructed.The traditional Particle Swarm Optimization（PSO）algorithm is analyzed.It is improved by automatically adjusting the weight of speed inertia and acceleration coefficient,and by introducing the mutation operation in genetic algorithm.In process of solving the task allocation model by the improved PSO algorithm,the mapping between problems and particles and the computing method of particle position fitness value by Technique for Order Preference by Similarity to Ideal Solution（TOPSIS）are researched.Then,a task allocation algorithm based on the improved PSO algorithm is designed.Finally,the feasibility and validity of the method is verified by an application example and a simulation test.

virtual enterprise;Particle Swarm Optimization（PSO）;task allocation;Technique for Order Preference by Similarity to Ideal Solution（TOPSIS）

為了解決虛擬企業(yè)中的任務(wù)分配問(wèn)題，建立了任務(wù)分配的多目標(biāo)決策優(yōu)化模型。分析了傳統(tǒng)的PSO算法，通過(guò)設(shè)置算法中速度慣性權(quán)重和加速度系數(shù)的自動(dòng)調(diào)整，以及引入遺傳算法中的變異操作，實(shí)現(xiàn)了對(duì)該算法的改進(jìn)?；诟倪M(jìn)的PSO算法求解任務(wù)分配模型，研究了求解問(wèn)題與粒子的映射以及采用TOPSIS計(jì)算粒子位置適應(yīng)度的方法，進(jìn)而設(shè)計(jì)了一種基于改進(jìn)PSO算法的任務(wù)分配算法。通過(guò)應(yīng)用實(shí)例及仿真實(shí)驗(yàn)，證明了改進(jìn)的PSO算法應(yīng)用于任務(wù)分配的可行性和有效性。

虛擬企業(yè)；粒子群優(yōu)化算法；任務(wù)分配；逼近理想解排序

A

TP391

10.3778/j.issn.1002-8331.1211-0032

ZENG Wenquan,YU Aimin.Research on improved PSO algorithm based task allocation.Computer Engineering and Applications,2013,49（13）：51-55.

廣東省自然科學(xué)基金（No.S2011010002537）；廣東省科技計(jì)劃項(xiàng)目（No.2012A030400029）。

曾文權(quán)（1978—），男，副教授，主要研究方向：計(jì)算機(jī)應(yīng)用技術(shù)，圖像處理和分析；余愛(ài)民（1963—），男，博士，教授，主要研究方向：計(jì)算機(jī)應(yīng)用技術(shù)，圖像處理和分析。E-mail：bless365@126.com

2012-11-05

2012-12-31

1002-8331（2013）13-0051-05