采用離散煙花算法的移動群智感知異構任務分配*

申曉寧，許 笛，宋麗妍，姚鋮濱，王玉芳

(1.南京信息工程大學自動化學院，江蘇 南京 210044；2.江蘇省大氣環(huán)境與裝備技術協(xié)同創(chuàng)新中心，江蘇 南京 210044； 3.江蘇省大數(shù)據(jù)分析技術重點實驗室，江蘇 南京 210044； 4.廣東省類腦智能計算重點實驗室(南方科技大學)，廣東 深圳 518055)

1 引言

自中國共產(chǎn)黨第十九屆中央委員會第五次全體會議上強調“推動綠色發(fā)展，促進人與自然和諧共生”這一理念以來，國家對環(huán)境質量的改善給予了持續(xù)的關注。當城市空氣中的污染物含量超標或噪聲分貝過大時，會使得環(huán)境承載能力下降，最終影響市民的身體健康[1]。近年來，隨著可手持設備和可穿戴設備的迅速普及，以及它們在物聯(lián)網(wǎng)和智能城市中的充分應用，移動群智感知MCS(Mobile Crowd-Sensing)已成為傳感和收集數(shù)據(jù)的一種高效的城市感知模式。MCS是指通過人們已有的移動設備形成參與式的感知網(wǎng)絡，并將感知任務發(fā)布給網(wǎng)絡中的個體或群體來完成，從而幫助專業(yè)人員或公眾收集數(shù)據(jù)、分析信息和共享知識。目前，MCS已應用于交通監(jiān)控、空氣質量檢測、流域條件檢測、健康感知和飲食感知等方面[2]。將MCS用于空氣污染和噪聲監(jiān)測，為城市管理提供了新的解決方案，可以在沒有額外花費的基礎上，擴大已部署的傳感系統(tǒng)的空間覆蓋范圍，從而顯著改善公民的日常生活。

目前，對MCS系統(tǒng)的研究主要集中在4個方面，分別為任務分配、激勵機制、數(shù)據(jù)收集和數(shù)據(jù)處理。其中,任務分配確定任務和參與者之間的分配關系，其合理性決定了參與者上傳的數(shù)據(jù)質量。近年來，MCS任務分配問題已成為社會計算、協(xié)作計算和智能計算領域的研究熱點[3]。文獻[4]指出，心理過程會指導參與者的行為，行為是心理的體現(xiàn)。如果參與者對平臺的任務分配方案不滿意，或執(zhí)行任務時的體驗感較差，將影響任務的感知質量甚至產(chǎn)生無效的感知行為，損害平臺利益，對系統(tǒng)產(chǎn)生負面影響。因此，平臺在分配任務時除了要考慮平臺效益外，還需顧及參與者的心理過程，即興趣偏好，以盡可能地提高參與者的滿意度。

在MCS任務分配問題中，學者主要從模型和求解算法2方面開展研究。在模型的研究中，針對任務類型，Zhao等[5]建立了同類型感知任務的分配模型，但忽略了系統(tǒng)中可能同時存在多種不同類型的異構任務。針對任務時間，袁姝等[6]考慮了參與者的彈性在線時間，忽略了參與者執(zhí)行任務的測量時間對數(shù)據(jù)的影響。針對任務分配方案的穩(wěn)定性,Zhou等[7]利用穩(wěn)定匹配理論將任務分配問題轉化為雙邊匹配問題。在算法設計方面，有分布式算法[8]、匹配算法[9]和多項式時間算法[5]等。然而，MCS任務分配已被證明為NP-hard問題[10]。上述傳統(tǒng)算法受到時間和空間復雜度的限制，大多只適用于小規(guī)模問題。部分算法雖可用于求解大規(guī)模問題，但對解的質量無法保證。元啟發(fā)式算法具有參數(shù)少、對問題信息依賴性小、全局優(yōu)化能力強的優(yōu)點，特別適用于求解NP-hard問題[11]。已有部分學者將MCS任務分配問題建模為基于搜索問題，采用元啟發(fā)式算法求解該問題的最優(yōu)解。Wang等[12]結合了蟻群優(yōu)化算法的正反饋機制與遺傳算法的快速收斂性，提出了MQC(Maximun Quality and minimun Cost)-遺傳算法；袁殊等[6]用鯨魚算法優(yōu)化感知數(shù)據(jù)質量；楊正清等[13]用布谷鳥算法優(yōu)化系統(tǒng)成本；Xi等[14]利用變異遺傳算法最大化任務完成效率。上述算法雖然取得了一定的效果，但仍存在啟發(fā)信息利用不足和未充分利用群體進化狀態(tài)信息等問題。

煙花算法FWA(FireWork Algorithm)[15]是模擬煙花在夜空中爆炸過程的一種元啟發(fā)式算法。目前已成功運用于物流配送[16]、隨機裝配線混流調度[17]等多種離散問題。本文針對上述已有MCS任務分配模型的不足，考慮參與者心理與行為過程，建立了MCS異構任務分配模型，并提出了引入預測信息的離散煙花算法DFWAPI(Discrete FireWorks Algorithm incorporating Predictive Information)求解該模型。設計了基于問題啟發(fā)信息的爆炸算子、爆炸振幅的分組線性預測策略和變異自適應競爭機制。與6種已有算法的對比實驗結果表明，所提算法在MCS異構任務分配模型上具有更高的求解精度。

2 考慮參與者心理與行為過程的空氣質量MCS任務分配模型

本節(jié)主要以最小化平臺成本為目標，考慮參與者的心理和行為過程及健康狀況，構建更加貼合實際的空氣質量MCS異構任務分配數(shù)學模型。

2.1 問題描述

任務發(fā)起者需要創(chuàng)建關于公民在不同污染環(huán)境等級中的個人暴露時間與位置信息。于是委托平臺發(fā)布了一組異構任務T，其中包括m個測量機動車尾氣任務和n個社會生活噪聲任務。假設在平臺上登記的候選參與者集合為U，U中參與者的數(shù)目l不少于任務數(shù)量。為了使上傳數(shù)據(jù)不存在冗余現(xiàn)象且盡可能減少平臺成本，需要進行合理的任務分配。本文采用單人單任務方式，即一個人只做一項任務，一項任務也只需被執(zhí)行一次。

2.2 心理與行為過程

本節(jié)從補償成本、參與者匹配度和數(shù)據(jù)損失成本三方面來闡述參與者心理過程對行為過程的影響。

2.2.1 補償成本

(1)

其中，amin、bmin和cmin分別為空氣質量為優(yōu)的PM2.5最小值、小雨雨量的最小值和輕風時風速的最小值，amax、bmax和cmax分別為重度污染的PM2.5最大值、暴雨雨量最大值和狂風風速最高值。

Cj=αj×BC

(2)

(3)

其中，BC為完成一項任務的最大補償成本，取值設定為5元；αj為等級系數(shù)。

2.2.2 參與者匹配度與數(shù)據(jù)損失成本

本文模型考慮參與者心理與行為過程的關系。通過匹配度反映參與者的心理狀態(tài)，行為過程由參與者對任務數(shù)據(jù)的測量時間來體現(xiàn)。

(1)興趣度HIij：為了使平臺在分配任務時更加人性化，考慮參與者對各項任務的興趣度。一般情況下，參與者與任務之間的距離及參與者是否能夠順路完成任務這2個因素對參與者的興趣度影響較大。在平臺發(fā)布任務之后，第i(i=1,2,…,l)個參與者對第j(j=1,2,…,m+n)個任務的興趣度HIij的計算如式(4)和式(5)所示：

(4)

(5)

其中，dij為參與者i與任務j之間的距離值，單位為km;γ為方向系數(shù)。由式(4)和式(5)可見，當某項任務與參與者距離較近，且參與者可順路完成該任務時，參與者對其興趣度較大；若某項任務位于參與者附近但不在其行進方向上時，參與者的興趣度將有所下降。由式(4)可知，HIij∈[0,100]。

Ri=100×[β×HDAi+(1-β)×OTUi]=

(6)

其中，l為參與者總人數(shù)，β為權重系數(shù)，r為參與者i參與歷史任務的總數(shù)。由于歷史數(shù)據(jù)感知質量對信譽度的影響更大，因此設置β=0.6。由式(6)可知，Ri∈[0,100]。

(3)匹配度Mij∈[0,100](i=1,2,…,l,j=1,2,…,m+n)定義為參與者i對任務j的興趣度和信譽度的平均值，如式(7)所示：

Mij=(Hij+Ri)/2

(7)

(8)

(9)

其中，η為單位測量時間的數(shù)據(jù)損失成本。

2.3 數(shù)學模型

MCS異構任務分配模型中，定義決策變量Xij如式(10)所示：

(10)

目標函數(shù)和約束條件如式(11)～式(15)所示。

(11)

(12)

s.t.

(13)

(14)

(15)

其中，式(11)表示平臺總成本,由補償成本Cj、數(shù)據(jù)損失成本Pij和距離成本Qij組成。綜合汽車、自行車和步行等不同出行方式的費用，估計得到參與者每千米的路程報酬約為g=5元。式(12)計算參與者與任務點的距離，(Uxi,Uyi)和(Txi,Tyi)分別為用戶和任務的地理坐標。式(13)～式(15)為約束條件，式(13)表示任一任務由且只由一個參與者完成；式(14)表示任一參與者至多只能完成一項任務；式(15)表示執(zhí)行測量尾氣任務的參與者呼吸系統(tǒng)健康系數(shù)需大于或等于60。

3 求解MCS異構任務分配模型的離散煙花算法DFWAPI

針對所建MCS異構任務分配模型，提出一種引入預測信息的煙花算法DFWAPI，設計了引入反向學習的初始化策略、利用啟發(fā)信息的煙花爆炸算子、爆炸振幅的分組線性預測策略及變異算子的自適應競爭機制，以提高算法的求解能力。

3.1 求解MCS異構任務分配模型的DFWAPI算法框架

DFWAPI求解MCS異構任務分配模型的框架如圖1所示。DFWAPI主要由4個模塊組成：(1)引入反向學習的初始化模塊；(2)煙花爆炸產(chǎn)生爆炸火花模塊；(3)煙花變異產(chǎn)生變異火花模塊；(4)選擇模塊。其中選擇模塊采用的是把每一代的核心煙花保留到下一代的精英保留策略和排序選擇策略[20]。

Figure 1 Framework of DFWAPI 圖1 DFWAPI算法框架

3.2 引入反向學習的初始化策略

本文對煙花個體采用整數(shù)編碼。一個個體表示參與者在平臺發(fā)布任務中的一套分配方案。個體長度為當前發(fā)布的任務數(shù)量，個體每一維上的整數(shù)對應分配給相應任務的參與者編號。由于平臺實際在線的參與者數(shù)量可能遠高于任務數(shù)量，常規(guī)的對所有參與者和任務進行0-1矩陣編碼的方式將產(chǎn)生大量全零行，因此本文采用的整數(shù)向量編碼可節(jié)約計算資源，提高算法搜索效率。為了便于計算個體目標值，個體編碼還引入了參與者屬性，如圖2所示。將參與者的匹配度依式(8)轉化為相應的預計測量時間后與距離值共同代入式(11)，求出該個體的目標值。個體目標值越小，說明其適應度越好。

Figure 2 Encoding of introducing the participant attribute圖2 引入?yún)⑴c者屬性的編碼方式

由于煙花算法的種群規(guī)模N較小，為了提高初始煙花種群中個體分布的多樣性，本文在初始化階段引入反向學習的思想[21]。首先隨機生成N個煙花后，再根據(jù)式(16)對各初始煙花的每一維進行反向調整：

ψ′=S+E-ψ

(16)

其中，S為參與者編號的起始值；E為參與者編號的終止值；ψ為初始生成的分配到某任務的參與者編號；ψ′為調整后的參與者編號。由式(16)得到的N個個體稱為反向煙花。若反向煙花的目標值優(yōu)于初始煙花，則用反向煙花替換初始煙花；若劣于初始煙花，則保留初始煙花，由此得到N個最終的初始煙花。

3.3 離散爆炸算子

本節(jié)設計了煙花爆炸振幅的分組線性預測策略和利用問題啟發(fā)信息的離散爆炸算子。

依據(jù)經(jīng)典煙花算法(FWA)[15]計算爆炸火花數(shù)量Sk，由于本文面向的MCS異構任務分配是離散優(yōu)化問題，F(xiàn)WA的爆炸振幅不再適用，因此本文將爆炸振幅定義為每個個體需要改變的維數(shù)。設每個個體煙花長度為len(len=m+n)，對于適應度值較優(yōu)的煙花，可在其附近進行精細地挖掘，因而它們可以取較小的爆炸振幅；反之，對于適應度值較差的煙花，應在其周圍進行大范圍搜索。因此，為它們選取較大的爆炸振幅。本文首先依據(jù)式(17)計算出第k個煙花的基本爆炸振幅Ak，其后在此基礎上對最終的爆炸振幅進行分組線性預測(見3.3.1節(jié))：

k=1,2,…,N

(17)

其中，M為控制爆炸振幅的參數(shù)，且M=round(λ*len)，λ為常數(shù)，取值為0.8，round為四舍五入操作；Ymin為當前種群中個體目標的最小值；ε為一個極小的常數(shù)，用來避免除零操作。為防止爆炸振幅過大或者過小，通過式(18)對Ak進行調整：

(18)

3.3.1 爆炸振幅的分組線性預測

(19)

所提分組線性預測策略的偽代碼如算法1所示。首先根據(jù)目標值排序將煙花種群分為2組，排名第2的煙花至中心煙花構成第1組，記為Poph，排名在中心煙花之后的煙花為第2組，記為Popl(第1～2行)。計算中心煙花和核心煙花的爆炸振幅(第3行)。動態(tài)調整核心煙花的爆炸振幅(第4行)。計算出中心煙花和核心煙花當前代與上一代爆炸振幅的改變幅度(第5～6行)。Poph中個體的爆炸振幅跟隨核心煙花爆炸振幅的變化趨勢進行調整(第7～9行)，Popl中個體的爆炸振幅跟隨中心煙花爆炸振幅的變化趨勢進行調整(第10～12行)。輸出為種群中各煙花的爆炸振幅(第13行)。

1：對Pop按目標值由小到大排序，排在首位和中間位的煙花分別記為核心煙花和中心煙花；

2：排名第2的煙花至中心煙花之間的煙花構成分組Poph,排名在中心煙花之后的煙花構成分組Popl;

7：forallu∈Pophdo{

8: 依據(jù)式(17)和式(18)計算煙花u的基本爆炸振幅At(u);

10:forallv∈Popldo{

11: 依據(jù)式(17)和式(18)計算煙花v的基本爆炸振幅At(v);

3.3.2 利用啟發(fā)信息的爆炸算子

3.4 變異算子的自適應競爭機制

FWA在連續(xù)優(yōu)化問題中采用高斯變異的方式增加種群多樣性，但在離散問題中并不適用。單一變異方式產(chǎn)生的變異火花無法控制其目標值的優(yōu)劣，較差的變異火花在迭代中被逐步淘汰，沒有對種群的進化起到促進的作用。而采用多種變異方式產(chǎn)生火花，雖然增加了火花的多樣性，但并不能保證每種變異方式均適用于當前進化階段，依舊可能產(chǎn)生較多劣解。為了解決該問題，本節(jié)設計變異算子的自適應競爭機制。該機制設置3種變異方式，每個煙花通過基于貢獻度Cw(w=1,2,3)的輪盤賭策略自適應選擇相應的變異方式，貢獻度越高的變異方式被選擇的概率越大，產(chǎn)生優(yōu)良變異火花的可能性也越大。

3種變異方式分別為單基因位變異、基因對變異和基因片段變異，具體操作分別為隨機替換、2點交換和片段逆序。隨機替換是指在煙花個體中隨機選一個基因位，對于尾氣測量任務，從未被選中的健康參與者中隨機選擇一名替換原參與者，對于噪聲測量任務，從未被選中的所有參與者中隨機選擇一名替換。2點交換是指隨機選擇2個基因位構成1個變異對，將2個參與者的位置交換。片段逆序是指隨機選擇2點作為片段的起始點與終止點，將選中的參與者片段逆序排列。對于2點交換和片段逆序后個體的前m個測量尾氣的任務，若變異后的參與者為不健康參與者，則從未被選中的健康參與者中隨機選擇一名替換。

(1)將產(chǎn)生的變異火花依次與當前種群所有煙花的適應度進行比較。

(2)記錄目標值劣于變異火花的煙花個數(shù)r。

(3)根據(jù)式(20)更新貢獻度：

(20)

(21)

變異算子自適應競爭機制的偽代碼如算法2所示。對第k個煙花采用基于貢獻度的輪盤賭策略選擇對應的變異方式(第6行)，其中index∈{1,2,3}，分別代表隨機替換、2點交換和片段逆序，其后，記錄第k個煙花產(chǎn)生第q個變異火花的變異方式reckq，并在集合Y中保存變異火花ykq(第7～17行)。接著，更新變異方式reckq的貢獻度和各變異方式的選擇概率(第18和第19行)。輸出所有煙花產(chǎn)生的變異火花集合和每種變異方式更新后的貢獻度(第20行)。

3:Y←?;

4:forallxk∈Popdo{

5:forq=1 toSkdo{

7:ifindex==1{

8:ykq←Stochastic(xk);//隨機替換

9:reckq=1;}

10:elseifindex==2{

11:ykq←Exchange(xk);//2點交換

12:reckq=2;}

13:elseifindex==3

14:ykq←Reverse(xk);//片段逆序

15:reckq=3;}

17:Y←[Y,ykq];

4 實驗仿真與結果分析

為了驗證所提算法和改進策略的有效性，采用Python3.7.6軟件進行仿真實驗，計算機處理器參數(shù)為Intel(R) Core(TM) i7-8565U CPU @ 1.80 GHz 1.99 GHz，8 GB運行內存。本文設計了2組實驗：(1)改進策略的有效性驗證；(2)將所提算法DFWAPI與文獻中6種具有代表性的算法進行對比，以驗證所提算法的性能。采用10個隨機生成的算例和1個包含南京市夫子廟周邊50個任務點的實例作為測試算例。所有對比算法均在各算例上分別進行30次獨立實驗，每次實驗的最大目標評價次數(shù)為50 000。DFWAPI的種群規(guī)模N設置為12。其中除了算法GGA_I采用原文獻的0-1編碼解碼方式外，其它對比算法均使用與所提算法DFWAPI相同的整數(shù)編碼解碼方式。其余參數(shù)設置均與原文獻相同。

隨機算例中，參與者和任務位置的橫縱坐標均在[0,1 000]內隨機均勻生成，參與者信譽度在[0,100]內隨機均勻生成，參與者的方向系數(shù)隨機取為1或0.5。為簡化問題，假設平臺中健康和不健康參與者的比例為4∶1。

4.1 改進策略有效性驗證

為了驗證第3.2～第3.4節(jié)所提各策略的有效性，分別將所提算法DFWAPI中的一個改進策略用另一種已有策略替換，得到4種對比算法：用隨機初始化代替引入反向學習初始化的算法DFWAPI-RI、僅通過式(17)和式(18)計算煙花基本爆炸振幅的算法DFWAPI-LP、在爆炸生成算子階段不引入啟發(fā)信息的算法DFWAPI-HI和將3種變異策略等概率隨機使用的算法DFWAPI-AV。將4種對比算法與DFWAPI在11個測試算例上分別獨立運行30次，計算各算法搜索到的式(11)所示成本目標的平均值Avg和最優(yōu)值Best，將Best和Avg的最好值加粗表示，如表1所示。為顯著對比4種策略的優(yōu)劣，采用顯著水平為0.05的Wilcoxon秩和檢驗對實驗結果進行統(tǒng)計測試，其中“+”“-”和“=”分別表示所提算法顯著優(yōu)于、顯著劣于對比算法和與對比算法無顯著差別。

Table 1 Comparison results of the proposed algorithm and the replace single strategy algorithms表1 所提算法和替換單一策略算法的對比結果 元

由表2可知，所提算法DFWAPI在絕大多數(shù)算例中取得了最優(yōu)的Best值，對于平均值Avg,在大中小規(guī)模的算例中均為最優(yōu)。同時，統(tǒng)計測試結果表明，在大多數(shù)算例中，在替換DFWAPI的單一改進策略后會導致求解性能顯著變差，以上實驗結果表明，所提各種改進策略是可行且有效的。產(chǎn)生以上結果的原因首先是引入反向學習的初始化降低了隨機初始化產(chǎn)生劣解的概率，同時增加了種群的多樣性。其次，采用線性預測的思想在基本爆炸振幅的基礎上，根據(jù)基準煙花的爆炸振幅改變量，調整了各煙花的爆炸方向和振幅。再次，在確定煙花的爆炸數(shù)量與爆炸范圍之后引入2種啟發(fā)信息對煙花進行爆炸，使得煙花在解空間中的爆炸過程具有較好的方向性和目的性，降低了原有爆炸方式的盲目性。最后，變異火花的產(chǎn)生采用自適應的思想，評價每種變異方式在不同進化階段對群體進化的貢獻度，并依據(jù)貢獻度選擇更適合當前進化狀態(tài)的變異方式，與等概率隨機選擇變異方式相比，所提策略能更有針對性地提高了算法的局部搜索精度。

Table 2 Comparative experimental results of FWAPI and contrast algorithms表2 FWAPI與對比算法的實驗結果 元

4.2 所提算法的性能驗證

為了驗證所提DFWAPI算法在求解MCS異構任務分配問題時的整體性能，選用4種具有代表性的求解MCS任務分配問題的已有算法(混合遺傳算法HGA(Hybrid Genetic Algorithm)[19]、貪婪增強遺傳GGA_I(Greedy-enhanced Genetic Algorithm for International)算法[23]、遺傳算法GA(Genetic Algorithm)[24]、鯨魚算法WOA(Whale Optimization Algorithm)[6])以及2種新型煙花算法(裸骨煙花算法BBFWA(Bare Bones FireWorks Algorithm)[25]和基于失敗者淘汰的煙花算法LoTFWA(Loser-out Tournament based FireWorks Algorithm)[26])，將它們分別應用于本文建立的模型，并與所提算法進行比較,實驗結果如表2所示。

由表2可見，所提DFWAPI算法與其余6種算法相比，在所有隨機算例和實例上均取得了最佳的最優(yōu)值Best和平均值Avg。顯著水平為0.05的Wilcoxon秩和檢驗結果表明，在大多數(shù)算例中DFWAPI顯著優(yōu)于6個對比算法。主要原因是4種改進策略的綜合使用和有效配合。在初始化階段，所提算法為后續(xù)煙花的爆炸操作提供了較好的起點；在煙花爆炸階段，引入不同類型基準煙花的信息對煙花的搜索范圍進行預測和調整，使得種群的搜索范圍隨著任務的推進自動地進行縮放，在進化前期強化了全局搜索能力，后期則提高了局部搜索能力；同時，根據(jù)問題不同類型的啟發(fā)信息生成多種爆炸火花，引導個體的收斂方向。在火花變異階段，利用自適應競爭機制進一步增強在煙花附近的局部搜索能力，提升了變異火花的質量。多種改進策略的協(xié)同合作，有效平衡了算法的全局搜索和局部挖掘能力，使算法獲得了較強的尋優(yōu)能力和求解精度。綜上，與6種對比算法相比，所提算法能夠更加有效地求解MCS異構任務分配問題，為平臺提供一套成本更低的分配方案。

5 結束語

本文以監(jiān)測空氣污染與生活噪聲為任務背景研究了MCS異構任務分配問題。本文工作和結論如下：(1)建立了考慮參與者心理與行為過程的MCS異構任務分配數(shù)學模型。(2)針對模型的特點，對初始化、爆炸振幅、爆炸算子和變異策略做出了改進。對策略有效性的驗證結果表明，所提策略是可行且有效的。(3)將所提算法與文獻中6種具有代表性的算法進行對比，實驗結果表明，所提算法在求解精度方面優(yōu)于所有對比算法，它在規(guī)模為小、中、大的隨機算例與實際算例中均能搜索到具有最低成本的MCS異構任務分配方案，說明它對問題規(guī)模具有較好的可擴展性。