群智感知系統(tǒng)中基于鯨魚(yú)優(yōu)化算法的任務(wù)分配

袁 姝，周朝榮,2+，楊正清，王婧柔

(1.四川師范大學(xué) 物理與電子工程學(xué)院，四川 成都 610101；2.成都信息工程大學(xué) 氣象信息與信號(hào)處理四川省高校重點(diǎn)實(shí)驗(yàn)室，四川 成都 610225)

0 引 言

群智感知(crowdsensing，CS)[1,2]利用智能設(shè)備收集數(shù)據(jù)，提供了靜態(tài)傳感器網(wǎng)絡(luò)難以支持的大規(guī)模應(yīng)用服務(wù)，比如ParkSense[3]等。為了更好地支持各類(lèi)應(yīng)用服務(wù)，群智感知系統(tǒng)要求在某些約束條件下將任務(wù)分配給合適的工人，工人移動(dòng)到對(duì)應(yīng)位置執(zhí)行任務(wù)，這樣的任務(wù)分配問(wèn)題是當(dāng)前群智感知相關(guān)研究領(lǐng)域中的熱點(diǎn)。

目前，已有學(xué)者針對(duì)群智感知系統(tǒng)中的任務(wù)分配問(wèn)題展開(kāi)研究。文獻(xiàn)[4,5]考慮到任務(wù)的執(zhí)行時(shí)長(zhǎng)分配任務(wù)，但忽略了工人的在線時(shí)間限制。因此，針對(duì)工人在線時(shí)間存在限制的情況，文獻(xiàn)[6,7]利用感知設(shè)備的可用時(shí)間代表工人的在線時(shí)間，從而分配任務(wù)。然而，工人的在線時(shí)間并非簡(jiǎn)單等同于感知設(shè)備的可用時(shí)間。為了避免此局限，文獻(xiàn)[8,9]分別用工人活躍時(shí)間與最晚工作時(shí)間來(lái)表示工人的在線時(shí)間，但忽略了工人在線時(shí)間的不確定性。此外，考慮到工人的在線時(shí)間，則不能忽視工人的時(shí)間成本。雖然文獻(xiàn)[10]考慮了預(yù)算對(duì)任務(wù)分配的影響，但預(yù)算中忽略了工人的延時(shí)成本與空閑成本。

為此，考慮工人在線時(shí)間為彈性時(shí)間的情況，采用模糊機(jī)會(huì)約束規(guī)劃方法[11]對(duì)工人的在線時(shí)間進(jìn)行建模，并引入延時(shí)成本與空閑成本。對(duì)應(yīng)的任務(wù)分配問(wèn)題為組合優(yōu)化問(wèn)題，屬于NP-hard問(wèn)題范疇，不存在時(shí)間有效的最優(yōu)算法，只能考慮次優(yōu)算法。鑒于鯨魚(yú)優(yōu)化算法(whale optimization algorithm，WOA)[12]具有全局搜索能力強(qiáng)等優(yōu)點(diǎn)，利用WOA設(shè)計(jì)了兩階段算法求解該任務(wù)分配問(wèn)題。仿真結(jié)果表明，所提出的算法與其它算法相比具有更好的搜索性能；同時(shí)，較之于固定在線時(shí)間，考慮彈性在線時(shí)間工人效率更高且工人成本更低。

1 問(wèn)題描述與系統(tǒng)模型

考慮一個(gè)存在t個(gè)感知任務(wù)以及w個(gè)注冊(cè)工人的群智感知系統(tǒng)。其中，T={T1,…,Tt} 以及W={W1,…,Ww} 分別表示任務(wù)集合與工人集合。對(duì)于任務(wù)i來(lái)說(shuō)，TTi為該任務(wù)執(zhí)行所需時(shí)間；對(duì)于工人j來(lái)說(shuō)，WTj為該工人在注冊(cè)時(shí)設(shè)定的預(yù)計(jì)在線時(shí)間。為便于問(wèn)題的描述，給出以下定義。

定義1 任務(wù)執(zhí)行時(shí)間MissionTime： 任務(wù)執(zhí)行時(shí)間為工人執(zhí)行系統(tǒng)所分配任務(wù)的總時(shí)間花費(fèi)，其定義如式(1)所示

(1)

其中，Vj表示分配給工人j的任務(wù)集合。

定義2 空閑時(shí)間IdleTime： 工人在預(yù)計(jì)在線時(shí)間內(nèi)未執(zhí)行任務(wù)的時(shí)間稱(chēng)作空閑時(shí)間，其定義如式(2)所示

ITj=WTj-MTj

(2)

此時(shí)，WTj≥MTj。

定義3 延時(shí)時(shí)間DelayTime： 工人任務(wù)執(zhí)行時(shí)間超過(guò)工人預(yù)計(jì)在線時(shí)間的情況下，工人實(shí)際在線時(shí)間即為工人任務(wù)執(zhí)行時(shí)間，而工人超出預(yù)計(jì)在線時(shí)間的部分則為延時(shí)時(shí)間，其定義如式(3)所示

DTj=MTj-WTj

(3)

根據(jù)工人存在空閑時(shí)間定義工人空閑代價(jià)如式(4)所示

ICj=α*ITj

(4)

其中，α為單位空閑時(shí)間代價(jià)。

此外，根據(jù)工人存在延時(shí)時(shí)間定義工人延時(shí)代價(jià)如式(5)所示

DCj=β*DTj

(5)

其中，β為工人單位延時(shí)代價(jià)。

在任務(wù)分配之前，由于工人還沒(méi)有開(kāi)始執(zhí)行任務(wù)，工人不能確定自己是否會(huì)在執(zhí)行任務(wù)之后選擇延長(zhǎng)在線時(shí)間，此時(shí)，系統(tǒng)考慮工人均不延長(zhǎng)在線時(shí)間，從而為工人初次分配任務(wù)。V′={V0′,V1′,V2′,V3′,…,Vw′} 表示此時(shí)感知任務(wù)的分配結(jié)果。其中，V0′為感知系統(tǒng)中未被分配的任務(wù)集合；V1′～Vw′分別表示感知系統(tǒng)為工人分配的任務(wù)集合。在這個(gè)階段，由于系統(tǒng)考慮工人均不延長(zhǎng)在線時(shí)間，工人的任務(wù)執(zhí)行時(shí)間均不超過(guò)工人預(yù)計(jì)在線時(shí)間。此時(shí)，若工人存在空閑時(shí)間，則會(huì)產(chǎn)生空閑代價(jià)ICj′， 確定此時(shí)工人總代價(jià)(TotalCost)為

(6)

在初次任務(wù)分配之后，工人能夠根據(jù)自身空閑情況以及后續(xù)安排決定是否考慮延長(zhǎng)在線時(shí)間。此時(shí)，利用工人時(shí)間約束可能性(即工人不選擇延長(zhǎng)時(shí)間的可能性)及置信水平大小來(lái)表示工人最終是否選擇延時(shí)。根據(jù)模糊機(jī)會(huì)約束規(guī)劃方法，當(dāng)工人時(shí)間約束可能性大于置信水平時(shí)，工人必須保證任務(wù)執(zhí)行時(shí)間不超過(guò)預(yù)計(jì)在線時(shí)間，此時(shí)工人不選擇延長(zhǎng)在線時(shí)間來(lái)執(zhí)行額外任務(wù)；而當(dāng)工人時(shí)間約束可能性小于置信水平時(shí)，工人選擇延長(zhǎng)在線時(shí)間來(lái)執(zhí)行額外任務(wù)，此時(shí)給工人分配額外任務(wù)。基于此，對(duì)初次任務(wù)分配的結(jié)果進(jìn)行調(diào)整。集合V={V0,V1,V2,V3,…,Vw} 表示最終任務(wù)分配結(jié)果。同理，V0為最終任務(wù)分配后未被分配的任務(wù)集合；V1～Vw表示工人最終的任務(wù)分配集合。分配完成后，根據(jù)工人是否選擇延時(shí)確定工人代價(jià)為延時(shí)代價(jià)或空閑代價(jià)

(7)

對(duì)應(yīng)的工人效率也分為兩種情況

(8)

基于上述定義，考慮工人彈性在線時(shí)間的任務(wù)分配模型給出如下

(9)

約束條件

(10)

V0∪V1∪…∪Vw=T

(11)

V0∩Vj=?,Wj∈W

(12)

Vk∩Vj=?,j≠k

(13)

|Vj|≥1,Wj∈W

(14)

Cr(WTj-MTj≥0)>τ,Wj∈W

(15)

TC≤TC′

(16)

?WTj,WTj-TTi≥0,Ti∈T,Wj∈W

(17)

其中，式(9)為優(yōu)化目標(biāo)即最大化工人總效率；式(10)與式(11)表示分配的任務(wù)為系統(tǒng)中發(fā)布的任務(wù)；式(12)與式(13)表示一個(gè)任務(wù)不能同時(shí)出現(xiàn)在工人任務(wù)集合以及未分配任務(wù)集合中；式(14)表示每個(gè)工人至少需要完成一個(gè)任務(wù)；式(15)為工人在線時(shí)間的模糊機(jī)會(huì)約束，其中τ為置信水平，采用模糊機(jī)會(huì)約束規(guī)劃模型建模，在一定程度上允許工人實(shí)際在線時(shí)間超過(guò)工人預(yù)計(jì)在線時(shí)間；式(16)表示引入彈性時(shí)間之后工人總代價(jià)不能超過(guò)未引入彈性時(shí)間的工人總代價(jià)；式(17)表明至少存在一個(gè)工人的預(yù)計(jì)在線時(shí)間超過(guò)所需執(zhí)行時(shí)間最長(zhǎng)的任務(wù)，保證執(zhí)行時(shí)間最長(zhǎng)的任務(wù)在初次分配時(shí)能夠有機(jī)會(huì)被執(zhí)行。由于考慮工人在線時(shí)間為彈性的任務(wù)分配問(wèn)題是組合優(yōu)化問(wèn)題，屬于NP-hard問(wèn)題的范疇，不存在時(shí)間有效的最優(yōu)算法，只能考慮次優(yōu)算法，所以在求解時(shí)考慮使用智能算法。相較于其它智能算法，鯨魚(yú)優(yōu)化算法能夠更好地平衡全局尋優(yōu)和局部尋優(yōu)階段且收斂速度更快，因此，在求解式(9)～式(17)所確定的任務(wù)分配問(wèn)題時(shí)考慮采用鯨魚(yú)優(yōu)化算法。

2 求解算法

鯨魚(yú)優(yōu)化算法[12]是由Mirjalili等提出，其思想源自座頭鯨的捕食行為。根據(jù)座頭鯨的捕食行為將算法分為3個(gè)階段：包圍獵物，氣泡網(wǎng)攻擊，搜索獵物。由于鯨魚(yú)優(yōu)化算法最初提出是為了求解連續(xù)問(wèn)題，而上述任務(wù)分配問(wèn)題為組合優(yōu)化問(wèn)題，因此，需要對(duì)鯨魚(yú)優(yōu)化算法進(jìn)行改進(jìn)，使之更加適合求解該任務(wù)分配問(wèn)題。

2.1 改進(jìn)鯨魚(yú)優(yōu)化算法

2.1.1 鯨魚(yú)優(yōu)化算法過(guò)程

包圍獵物階段：座頭鯨根據(jù)獵物的位置更新自身位置，從而接近獵物，稱(chēng)作包圍獵物階段。相關(guān)定義如式(18)所示

(18)

(19)

(20)

氣泡網(wǎng)攻擊階段：氣泡網(wǎng)攻擊階段座頭鯨螺旋移動(dòng)并吐出氣泡以包圍獵物。此時(shí)，座頭鯨的螺旋運(yùn)動(dòng)軌跡定義如式(21)所示

(21)

綜合上述兩個(gè)階段，此時(shí)座頭鯨處于已經(jīng)發(fā)現(xiàn)獵物并且向獵物移動(dòng)的過(guò)程，因此，這兩個(gè)階段也稱(chēng)作局部搜索階段。通過(guò)觀察發(fā)現(xiàn)，座頭鯨在獵物周?chē)蝿?dòng)行為同時(shí)包括了包圍獵物以及氣泡網(wǎng)攻擊兩種行為。因此，為了描述此時(shí)座頭鯨的行為，假設(shè)座頭鯨包圍獵物以及氣泡網(wǎng)攻擊的概率各為50%，此時(shí)，座頭鯨行為總結(jié)如下

(22)

其中，p為[0,1]之間的隨機(jī)數(shù)。

搜索獵物階段：在這個(gè)階段，座頭鯨還處于尋找獵物階段，它們根據(jù)彼此位置在空間內(nèi)進(jìn)行隨機(jī)搜索。因此，這部分也稱(chēng)作全局搜索階段，其定義如下

(23)

(24)

2.1.2 編碼及改進(jìn)

由于鯨魚(yú)優(yōu)化算法最初提出是為了求解連續(xù)優(yōu)化問(wèn)題，而工人彈性在線時(shí)間的任務(wù)分配為組合優(yōu)化問(wèn)題，其中涉及到任務(wù)和工人的配對(duì)問(wèn)題，因此需要對(duì)任務(wù)與工人序列進(jìn)行編碼并且對(duì)鯨魚(yú)優(yōu)化算法進(jìn)行改進(jìn)，使之能夠求解該任務(wù)分配問(wèn)題。

分別將任務(wù)和工人編碼成兩個(gè)序列。 [N1,N2,N3,…,Nt] 表示t個(gè)任務(wù)的排列，其中Ni∈{1,2,3,…,t}； [m1,m2,m3,…,mt] 表示任務(wù)對(duì)應(yīng)的執(zhí)行工人排列，其中mi∈{0,1,2,…,w}。 當(dāng)mj=0時(shí)，表明任務(wù)序列中Nj任務(wù)未被分配；而當(dāng)mj≠0時(shí)，表示對(duì)應(yīng)位置的任務(wù)分配給對(duì)應(yīng)位置的工人，從而確定任務(wù)分配結(jié)果。對(duì)應(yīng)的任務(wù)序列和工人序列相結(jié)合為一個(gè)鯨魚(yú)，此時(shí)，工人總效率即為鯨魚(yú)優(yōu)化算法的適應(yīng)度值。在利用鯨魚(yú)優(yōu)化算法進(jìn)行組合優(yōu)化問(wèn)題求解時(shí)，額外設(shè)計(jì)反轉(zhuǎn)模塊與局部搜索模塊以保證算法的搜索性能。為更好描述反轉(zhuǎn)模塊與局部搜索模塊，假設(shè)系統(tǒng)中存在9個(gè)任務(wù)和3個(gè)工人。初始化任務(wù)序列為[1 2 3 4 5 6 7 8 9]，隨機(jī)生成工人序列為[1 2 3 1 2 3 1 2 1]，相同位置的任務(wù)和工人構(gòu)成任務(wù)-工人對(duì)，表示該任務(wù)由該工人執(zhí)行。

反轉(zhuǎn)模塊：如圖1所示，選擇反轉(zhuǎn)起始點(diǎn)為4，反轉(zhuǎn)長(zhǎng)度為4，則需要反轉(zhuǎn)的任務(wù)序列為4 5 6 7；反轉(zhuǎn)之后該任務(wù)序列變?yōu)閇1 2 3 7 6 5 4 8 9]。根據(jù)優(yōu)化后的任務(wù)及工人序列可以發(fā)現(xiàn)任務(wù)分配發(fā)生了變化。

圖1 反轉(zhuǎn)模塊

圖2 局部搜索模塊

局部搜索：如圖2所示，選擇任務(wù)序列中的第5個(gè)元素進(jìn)行局部搜索優(yōu)化，因此，將第5個(gè)元素即任務(wù)6剔除，選擇第2個(gè)位置將該任務(wù)重新插入，則該任務(wù)序列變?yōu)閇1 6 2 3 7 5 4 8 9]。結(jié)合隨機(jī)生成的工人序列可知，任務(wù)分配發(fā)生了變化，使得任務(wù)分配的優(yōu)化結(jié)果跳出局部最優(yōu)。

2.2 兩階段任務(wù)分配算法

針對(duì)式(9)～式(17)所確定的任務(wù)分配模型，設(shè)計(jì)任務(wù)分配過(guò)程為兩個(gè)階段：初次分配與彈性調(diào)整。初次分配階段中群智感知系統(tǒng)首先將系統(tǒng)中所有任務(wù)初步分配給注冊(cè)工人，系統(tǒng)預(yù)評(píng)估感知系統(tǒng)所分配任務(wù)需花費(fèi)的總時(shí)間，當(dāng)發(fā)現(xiàn)某工人執(zhí)行完某個(gè)任務(wù)之后，執(zhí)行接下來(lái)的任務(wù)會(huì)使工人任務(wù)執(zhí)行時(shí)間超過(guò)工人預(yù)計(jì)在線時(shí)間，此時(shí)，系統(tǒng)確定分配給工人的任務(wù)為不超過(guò)預(yù)計(jì)在線時(shí)間的部分任務(wù)。沒(méi)有被執(zhí)行的任務(wù)聚集在一起為未分配任務(wù)，此時(shí)，工人的總代價(jià)中都只存在空閑代價(jià)，初次分配階段完成。其過(guò)程如算法1所示。

算法1： 初次分配

輸入： 工人信息W及任務(wù)信息T, 初始化工人任務(wù)執(zhí)行時(shí)間MTj’=0(j=1,2,…,w),工人空閑時(shí)間ITj’=0 (j=1,2,…,w)， 工人總代價(jià)TC’=0,單位空閑代價(jià)c。

系統(tǒng)將任務(wù)隨機(jī)分配給工人， 生成任務(wù)分配集Vj(j=1,2,…,w)

forj=1 towdo

forTvinVjdo

ifMTj’+TTv=

MTj’=MTj’+TTv

else

將該任務(wù)從該工人任務(wù)集中轉(zhuǎn)移到未分配任務(wù)中

endif

endfor

ITj’=WTj-MTj’

TC’=TC’+c*ITj’

endfor

輸出：工人最終任務(wù)集Vj’，未分配任務(wù)集V0’，總代價(jià)TC。

完成初次分配后，系統(tǒng)開(kāi)始彈性調(diào)整階段。在彈性調(diào)整階段中，根據(jù)每個(gè)工人的時(shí)間約束可能性以及預(yù)設(shè)的置信水平，確定工人是否選擇延時(shí)，從而確定是否為工人分配額外任務(wù)。當(dāng)工人的時(shí)間約束可能性大于置信水平時(shí)，說(shuō)明工人任務(wù)執(zhí)行時(shí)間不能超過(guò)工人預(yù)計(jì)在線時(shí)間，此時(shí)工人不選擇延長(zhǎng)時(shí)間；當(dāng)工人時(shí)間約束可能性小于置信水平時(shí)，此時(shí)工人選擇延長(zhǎng)時(shí)間，執(zhí)行額外任務(wù)，因此將未分配任務(wù)集中的某一個(gè)任務(wù)從未分配任務(wù)集中剔除，分配給該工人，在分配該任務(wù)時(shí)保證任務(wù)分配成功后的工人代價(jià)不能夠超過(guò)初次分配時(shí)的工人代價(jià)。其過(guò)程如算法2所示。

算法2： 彈性調(diào)整

輸入： 任務(wù)分配集合Vj’(j=0,1,…,w), 工人時(shí)間約束可能性Pbj(j=1,…,w)， 預(yù)設(shè)置信水平z, 初次分配分配階段工人總代價(jià)TC’, 初始化最終工人總代價(jià)TC=TC’。

forj=1towdo

ifPbj

未分配任務(wù)集中選擇一個(gè)任務(wù)預(yù)分配分配給工人j

計(jì)算TC

ifTC’

將該任務(wù)分配給工人j

endif

endif

更新工人任務(wù)集、 未分配任務(wù)集

endfor

輸出： 最終工人任務(wù)集合Vj(j=0,1,…,w)， 工人總代價(jià)TC。

綜合以上兩個(gè)階段，在基于鯨魚(yú)優(yōu)化算法設(shè)計(jì)的兩階段任務(wù)分配算法中,首先執(zhí)行初次分配，即根據(jù)工人、任務(wù)的相關(guān)信息隨機(jī)分配任務(wù)，然后利用改進(jìn)鯨魚(yú)優(yōu)化算法對(duì)隨機(jī)分配結(jié)果進(jìn)行優(yōu)化；接著執(zhí)行彈性調(diào)整，即根據(jù)初次分配結(jié)果以及工人時(shí)間約束可能性判斷工人是否選擇延長(zhǎng)時(shí)間，從而確定是否選擇額外任務(wù)分配給該工人，經(jīng)過(guò)多次迭代之后得到一個(gè)較優(yōu)的結(jié)果。完整的任務(wù)分配過(guò)程如算法3所示。

算法3： 離散鯨魚(yú)算法

輸入： 置信水平z， 工人集W， 任務(wù)集T， 工人時(shí)間約束可能性Pbj(j=1,2,…,w), 迭代次數(shù)maxIter

初始化種群Xi(i=1,2,…,n)

計(jì)算工人總效率

X*=工人總效率最高的任務(wù)分配方案

Whilet

fori=1tondo

更新鯨魚(yú)優(yōu)化算法中參數(shù)a,A,C,l和p

改進(jìn)鯨魚(yú)優(yōu)化算法優(yōu)化初次分配

彈性調(diào)整

endfor

計(jì)算每個(gè)個(gè)體適應(yīng)度值

更新X*

t=t+1

endwhile

2.3 算法的計(jì)算復(fù)雜性

假設(shè)算法的最大迭代次數(shù)為T(mén)，種群大小為P，工人數(shù)量為W。由算法3可知，完整算法中包含初次分配以及彈性調(diào)整兩個(gè)階段。在初次分配以及彈性調(diào)整中，算法的時(shí)間復(fù)雜度均只與工人數(shù)量有關(guān)，表示為O(W)。 由于兩部分都處于種群迭代優(yōu)化的內(nèi)層，因此，算法3的時(shí)間復(fù)雜度為O(TPW)。 可以看出，算法的時(shí)間復(fù)雜度是隨種群大小、迭代次數(shù)以及工人數(shù)量線性增長(zhǎng)的，這樣的復(fù)雜度是可以接受的。

3 仿真結(jié)果與分析

通過(guò)仿真實(shí)驗(yàn)驗(yàn)證所設(shè)計(jì)任務(wù)分配算法的性能，系統(tǒng)參數(shù)見(jiàn)表1。由于工人選擇延時(shí)會(huì)執(zhí)行額外任務(wù)，從而得到額外收益，使得工人延時(shí)成本降低；而工人空閑時(shí)，由于不執(zhí)行任務(wù)而沒(méi)有額外收益，不能降低空閑成本，因此，設(shè)置工人單位延時(shí)成本小于單位工人空閑成本?；诒?中的參數(shù)設(shè)置，我們首先分析置信水平對(duì)各算法中選擇彈性時(shí)間的工人數(shù)量的影響。然后，對(duì)比分析工人數(shù)量變化、置信水平變化以及彈性工人數(shù)量變化時(shí)，所提任務(wù)分配算法與基于遺傳算法(genetic algorithm，GA)[13]、貪婪算法(greedy algorithm，Greedy)以及隨機(jī)分配(random allocation，RA)的任務(wù)分配算法的性能比較。其中，基于遺傳算法的任務(wù)分配算法中，遺傳算法被用于優(yōu)化初步分配結(jié)果；基于貪婪算法的任務(wù)分配算法中，依次為工人分配使得當(dāng)前工人總效率達(dá)到最大的任務(wù)；基于隨機(jī)的任務(wù)分配算法中，根據(jù)工人是否選擇彈性時(shí)間將任務(wù)隨機(jī)分配給工人。最后，驗(yàn)證考慮工人彈性時(shí)間相較于不考慮工人彈性時(shí)間的優(yōu)勢(shì)。本文算法均以MATLAB R2014a為仿真平臺(tái)，所用機(jī)器配置為Intel?CoreTMi7-4710MQ 2.50GHz 8GB RAM，操作系統(tǒng)為Windows。

利用模糊機(jī)會(huì)約束方法對(duì)工人在線時(shí)間建模，工人能夠根據(jù)自身情況選擇是否延時(shí)以執(zhí)行額外任務(wù)，因此，每次仿真選擇彈性時(shí)間的工人數(shù)可能不同，從而影響優(yōu)化的結(jié)果。在仿真中預(yù)設(shè)置信水平，隨機(jī)生成工人的時(shí)間約束可能性，當(dāng)某個(gè)工人的該時(shí)間約束可能性大于置信水平時(shí)，判定該工人不選擇彈性時(shí)間，當(dāng)該工人的可能性小于置信水平時(shí)，則該工人選擇彈性時(shí)間，可以看出置信水平的大小會(huì)影響到選擇彈性時(shí)間的工人數(shù)，將選擇彈性時(shí)間的工人稱(chēng)作彈性工人。表2給出了經(jīng)過(guò)重復(fù)多次實(shí)驗(yàn)后在不同的置信水平下基于鯨魚(yú)優(yōu)化算法、遺傳算法、隨機(jī)分配以及貪婪算法的任務(wù)分配算法中彈性工人數(shù)量的平均值。從表2可以看出，隨著置信水平的增加，算法中的彈性工人數(shù)量也在增加，彈性工人數(shù)量在總工人數(shù)中所占比例大約等于置信水平。這說(shuō)明選擇彈性時(shí)間的工人數(shù)量會(huì)受到置信水平的影響，當(dāng)置信水平越大時(shí)，能夠滿(mǎn)足延時(shí)要求的工人數(shù)量就越多，此時(shí)，就有越多的工人選擇彈性時(shí)間。

表1 參數(shù)設(shè)置

表2 彈性工人數(shù)量隨置信水平變化的變化

為了驗(yàn)證置信水平對(duì)工人效率的影響，分別取置信水平為 [0.3,0.4,0.5,0.6,0.7] 時(shí)進(jìn)行多次仿真，從而得到圖3結(jié)果?？梢园l(fā)現(xiàn)在不同的置信水平下，相較于遺傳算法、隨機(jī)分配算法以及貪婪算法，鯨魚(yú)優(yōu)化算法得到的工人效率最高。此外，在不同算法中工人效率均會(huì)隨置信水平的增加而增加。

圖3 工人效率隨置信水平變化而變化

圖4給出了工人效率隨工人數(shù)變化而變化的趨勢(shì)?？梢钥闯鲭S著工人數(shù)量的增加，工人總效率也相應(yīng)增加，而基于鯨魚(yú)優(yōu)化算法制定的任務(wù)分配算法始終比其它算法所得工人效率好。

圖4 工人效率隨工人數(shù)變化而變化

由于選擇彈性時(shí)間的工人效率會(huì)得到提高，在相同單位代價(jià)、工人數(shù)量、任務(wù)數(shù)量以及置信條件下，不同的彈性工人數(shù)也會(huì)影響到工人總效率，記錄在工人、任務(wù)數(shù)量以及置信水平不變的情況下彈性工人數(shù)量分別為3、4、5、6、7時(shí)工人總效率的變化。如圖5所示，隨著彈性工人數(shù)的增加，不同算法中的工人的總效率均增加了。鯨魚(yú)優(yōu)化算法中工人總效率接近最高值，此后，工人總效率增長(zhǎng)變緩。此外，隨著彈性工人數(shù)量增長(zhǎng)，基于鯨魚(yú)優(yōu)化算法制定的任務(wù)分配算法的工人效率始終高于其它算法。

圖5 工人效率隨彈性工人數(shù)變化而變化

為了討論引入工人彈性時(shí)間的重要性，圖6展示了鯨魚(yú)優(yōu)化算法的最優(yōu)任務(wù)分配結(jié)果中各工人效率。可以看出有一半工人達(dá)到了最高效率1；圖7展示了工人任務(wù)執(zhí)行時(shí)間與預(yù)計(jì)在線時(shí)間的對(duì)比，可以看出工人2、4、6、9、10選擇了延長(zhǎng)時(shí)間執(zhí)行額外任務(wù)，所以他們達(dá)到了最高效率。因此，考慮工人彈性時(shí)間能夠提升工人效率。

圖6 工人效率

圖7 工人執(zhí)行任務(wù)時(shí)間與預(yù)計(jì)在線時(shí)間對(duì)比

為了進(jìn)一步展示彈性時(shí)間的效果，將考慮彈性時(shí)間與未考慮彈性時(shí)間的任務(wù)分配結(jié)果進(jìn)行對(duì)比。從圖8中可以看出未考慮彈性時(shí)間的工人總效率較低，相比來(lái)說(shuō)，考慮彈性時(shí)間的工人效率比不考慮彈性時(shí)間的工人效率高，其中工人2、4、6、9、10在考慮彈性時(shí)間之后均提高了工人效率。圖9展示了工人未考慮彈性時(shí)間以及考慮彈性時(shí)間之后工人任務(wù)執(zhí)行時(shí)間與工人預(yù)計(jì)在線時(shí)間的對(duì)比。可以看出，在未考慮彈性時(shí)間時(shí)，每個(gè)工人的任務(wù)執(zhí)行時(shí)間都不會(huì)超過(guò)工人預(yù)計(jì)在線時(shí)間，工人2、6、10即使空閑時(shí)間很多，也不會(huì)再執(zhí)行任務(wù)；而在考慮彈性時(shí)間之后，一部分工人選擇延長(zhǎng)在線時(shí)間執(zhí)行額外任務(wù)以達(dá)到更高的效率。圖10給出了未考慮彈性時(shí)間與考慮彈性時(shí)間后工人代價(jià)對(duì)比?？梢钥闯?，考慮彈性時(shí)間時(shí)工人代價(jià)均不會(huì)超過(guò)未考慮彈性時(shí)間時(shí)的工人代價(jià)，且總代價(jià)大幅度降低。因此，考慮工人彈性在線時(shí)間不但增加了工人效率，同時(shí)也降低了工人總代價(jià)，使得資源利用更為合理。

圖8 工人效率對(duì)比

圖9 任務(wù)執(zhí)行時(shí)間與預(yù)計(jì)在線時(shí)間對(duì)比

圖10 工人代價(jià)對(duì)比

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

任務(wù)分配問(wèn)題是群智感知相關(guān)研究中的重點(diǎn)。針對(duì)該任務(wù)分配問(wèn)題，本文考慮工人在線時(shí)間為彈性在線時(shí)間，采用模糊機(jī)會(huì)約束規(guī)劃方法進(jìn)行建模。由于該任務(wù)分配問(wèn)題為組合優(yōu)化問(wèn)題，不存在時(shí)間有效的最優(yōu)解，因此，基于鯨魚(yú)優(yōu)化算法設(shè)計(jì)了兩階段的任務(wù)分配算法進(jìn)行求解。仿真結(jié)果表明，所設(shè)計(jì)的任務(wù)分配算法相較于其它算法具有更高的工人效率；此外，相較于工人固定在線時(shí)間，在進(jìn)行任務(wù)分配時(shí)考慮工人彈性在線時(shí)間能夠提高工人效率同時(shí)降低工人成本。