面向異構(gòu)效用的移動群智感知多目標任務(wù)分配

傅彥銘 陸盛林 祁康恒 許勵強 陳嘉元

摘 要：當前移動群智感知（MCS）任務(wù)分配往往只考慮工人或平臺單方面的效用，并且效用的構(gòu)成也不夠全面。因此基于工人信譽指數(shù)和任務(wù)熟練指數(shù)，設(shè)計了工人和平臺兩方面的異構(gòu)效用機制，并提出一種雙種群競爭的多目標進化算法（DCMEA）來獲得最優(yōu)的工人和平臺異構(gòu)效用。該算法首先通過隨機貪婪初始化種群，然后使用二元競標賽算法將種群劃分為勝者種群和敗者種群，并針對每個種群采用不同的進化策略。最后，通過修復(fù)算子使進化過程中的無效個體滿足約束條件。在真實場景的數(shù)據(jù)集上進行實驗表明，與基線算法相比，DCMEA收斂速度更快，能夠找到精度更優(yōu)、穩(wěn)定性更好的任務(wù)分配解集，同時在更為復(fù)雜的場景中依然能夠保持其性能。

關(guān)鍵詞：移動群智感知；多任務(wù)分配；多目標優(yōu)化；雙種群競爭進化；信譽指數(shù)；任務(wù)熟練指數(shù)

中圖分類號：TP393.01?? 文獻標志碼：A?? 文章編號：1001-3695（2024）01-023-0159-06

doi：10.19734/j.issn.1001-3695.2023.04.0186

Multi-objective task assignment towards heterogeneous utilities in mobile crowdsensing

Abstract：Most of the existing MCS task allocation methods often only consider the unilateral utility of workers or platforms，and the composition of utility is not comprehensive enough.Therefore，this paper designed a heterogeneous utility mechanism for both workers and platforms based on the worker reputation index and task proficiency index.It proposed a dual-population competitive multi-objective evolutionary algorithm （DCMEA） to obtain the optimal worker and platform heterogeneous utilities.The algorithm firstly initialized the population using a stochastic greedy algorithm，then divided the population into a winner population and a loser population using a binary bidding tournament algorithm，and employed different evolutionary strategies for each population.Finally，this paper proposed the repair operator to make the invalid individuals in the evolution process satisfy the constraint.Experiments on real-world datasets show that DCMEA converges faster than the baseline algorithm，and can find more accurate and stable task allocation solution sets，while maintaining its performance in more complex scenarios.

Key words：mobile crowdsensing；multi-task allocation；multi-objective optimization；competitive evolution of two populations；reputation index；task proficiency index

0 引言

移動群智感知（MCS）來源于“眾包”，通過參與者持有移動設(shè)備相互合作完成眾多的任務(wù)，是一種新的感知范式［1，2］。移動互聯(lián)網(wǎng)、5G等技術(shù)的發(fā)展使任何具有微型傳感器的移動設(shè)備（如智能手機和平板電腦）攜帶者都可以成為MCS中的數(shù)據(jù)源。由于在收集感知數(shù)據(jù)方面具有高效性和擴展性，MCS在不同的領(lǐng)域中具有廣泛應(yīng)用，例如：環(huán)境監(jiān)測［3］、交通規(guī)劃［4］、公共安全［5］、醫(yī)療保?。?］。MCS包含任務(wù)發(fā)布、任務(wù)分配、任務(wù)執(zhí)行和數(shù)據(jù)收集四個階段。其中，任務(wù)分配是MCS的核心問題［7］。

從給每個工人分配的任務(wù)數(shù)角度，MCS任務(wù)分配可以分為單任務(wù)分配和多任務(wù)分配。單任務(wù)分配是每次只給可用工人分配單項任務(wù)。文獻［8］提出了一種沖突感知參與者招募機制，能夠有效提高平臺效用，同時保證在完成感知任務(wù)時無沖突。文獻［9］提出一種強大的隱私保護MCS方案，支持基于地理信息和移動用戶信用點的精確任務(wù)分配。然而，隨著MCS任務(wù)數(shù)量的增加，任務(wù)之間相互關(guān)聯(lián)，在有限的資源下，單任務(wù)分配會使工人完成任務(wù)的效率變低，MCS平臺無法獲得較好的整體效用。因此，多任務(wù)分配給一個工人同時分配多個任務(wù)來優(yōu)化平臺的整體效用。文獻［10，11］采用多任務(wù)分配方案，在任務(wù)共享有限的激勵預(yù)算時，使系統(tǒng)的整體效用最大化。文獻［12］提出了一個具有時間約束和平臺效用最大化的多任務(wù)分配問題，并設(shè)計了兩種遺傳算法來求解該問題。文獻［13］提出了一種以最大化平均感知質(zhì)量為目標的綜合空間覆蓋和感知精度的多任務(wù)分配方法，并引入改進的遺傳算法求解。

上述任務(wù)分配只考慮優(yōu)化一個目標［14，15］，屬于單目標優(yōu)化問題，而在分配過程中往往需要同時考慮優(yōu)化多個目標，以獲得符合多方利益的任務(wù)分配方案。文獻［16］設(shè)計了一種基于粒子群優(yōu)化的多目標任務(wù)分配算法，最大化感知質(zhì)量和預(yù)算的比值，同時最小化響應(yīng)時間。文獻［17］對單任務(wù)分配提出了一種改進的進化算法，通過平衡因子來選擇用戶，最大化參與者的總回報和感知質(zhì)量。文獻［18］同時考慮了最大化感知質(zhì)量和最小化激勵支付，通過帕累托最優(yōu)粒子群算法解決多目標多任務(wù)分配。文獻［19］建立了一種基于變速多任務(wù)分配的多目標優(yōu)化模型，并提出了一種三階段多目標洗牌蛙跳算法解決該模型。然而，在這些多目標分配模型中只考慮了工人的異質(zhì)性，例如工人的執(zhí)行意愿、信譽度、旅行速度等因素，而忽略了任務(wù)的異質(zhì)性。在實際分配中，不同類型的任務(wù)需要的感知數(shù)據(jù)并不相同，因此平臺需要匹配合適的工人以提高效用。

本文綜合考慮了工人和任務(wù)的異質(zhì)性，引入工人信譽指數(shù)和任務(wù)熟練指數(shù)，提出了一種優(yōu)化工人和平臺兩方面異構(gòu)效用的MCS多任務(wù)雙目標優(yōu)化任務(wù)分配方案。結(jié)合問題的特點，設(shè)計了一種雙種群競爭的多目標進化算法（DCMEA）來求解該問題。此外，在真實場景數(shù)據(jù)集上驗證了DCMEA求解本文的MCS任務(wù)分配方案能夠獲得優(yōu)于對比算法的精度和穩(wěn)定性。

1 異構(gòu)效用MCS多目標任務(wù)分配模型

1.1 模型描述

MCS包括一個中心平臺、多個任務(wù)發(fā)布者及參與工人，其工作流程可用圖1描述。首先，發(fā)布者將任務(wù)需求上傳到平臺，平臺在獲得任務(wù)信息后使用相關(guān)的任務(wù)分配算法將任務(wù)分配給工人。接著，工人完成任務(wù)后，將任務(wù)完成的結(jié)果或感知數(shù)據(jù)上傳到平臺。最后，平臺收到感知數(shù)據(jù)后將結(jié)果反饋給任務(wù)發(fā)布者，并獲得相應(yīng)報酬，同時給工人支付報酬。

若在MCS任務(wù)分配中有m名工人參與，W={w1，…，wi，…，wm}。工人wi包含以下信息：wi={lati， lngi，wnummaxi，Ri}。其中l(wèi)ati，lngi表示工人的經(jīng)緯度坐標；wnummaxi表示工人的最大完成任務(wù)數(shù)，工人不能重復(fù)完成相同的任務(wù)；Ri為工人的信譽值，表示工人歷史完成任務(wù)的質(zhì)量和性價比［20］。其中Ls≤Ri≤Lm，Lm為最大信譽值，Ls為最小信譽值。

任務(wù)發(fā)布者發(fā)布了n個任務(wù)T={t1，…，tj，…，tn}，任務(wù)tj包含以下信息：tj={latj，lngj，tnummaxj，bj，wrj，Skj}。其中：latj和lngj表示任務(wù)的經(jīng)緯度坐標；tnummaxj表示任務(wù)最多可以由多少名不同工人完成；bj為工人每次完成任務(wù)tj平臺所獲得的報酬。wrj為完成任務(wù)tj工人獲得的固定報酬。Skj={sk1j，…，skij，…，skmj}，skij表示工人wi對任務(wù)tj的熟練度，其中-1≤skij≤1，skij值越大說明工人對任務(wù)越熟悉。

wtij表示一個任務(wù)分配，若平臺將任務(wù)tj分配給了工人wi，則wtij=1，否則wtij=0。當wtij=1時，工人在完成任務(wù)后，分別產(chǎn)生相應(yīng)的工人異構(gòu)效用uwij和平臺異構(gòu)效用upij。當wtij=0時，uwij和upij的值為0。

1.2 異構(gòu)效用機制

為了充分考慮MCS中工人和任務(wù)的異質(zhì)性，從工人信譽和工人對任務(wù)的熟練程度兩個角度出發(fā)，定義了工人信譽指數(shù)和任務(wù)熟練指數(shù)兩個指標。

1）工人信譽指數(shù) 工人wi的信譽指數(shù)Hi用來描述工人信譽的良好程度。指數(shù)越高，其完成任務(wù)的質(zhì)量越高，反之亦然。Hi可用式（1）計算［20］。

2）任務(wù)熟練指數(shù)

任務(wù)熟練指數(shù)Tij用來描述工人wi對任務(wù)tj的熟悉程度。任務(wù)熟練指數(shù)越高，工人對任務(wù)越熟悉，完成任務(wù)的質(zhì)量越高且感知的數(shù)據(jù)也越準確。Tij可以用Gompertz函數(shù)來計算，如式（2）。Gompertz函數(shù)描述了事物的發(fā)生、發(fā)展和成熟三個階段，并已應(yīng)用于任務(wù)分配建模中［21］。

本文設(shè)計了異構(gòu)效用機制。工人在完成一個任務(wù)后會有一個固定的獎勵報酬RF，并通過信譽指數(shù)和任務(wù)熟練指數(shù)產(chǎn)生一個獎勵指數(shù)ηij，獎勵報酬和獎勵指數(shù)相乘得到工人完成任務(wù)后獲得的激勵報酬。將激勵報酬加入到工人效用和平臺效用中，更全面地反映了不同任務(wù)分配間的效用差異。

3）工人異構(gòu)效用

工人wi完成任務(wù)tj所產(chǎn)生的工人異構(gòu)效用由式（3）計算。由固定報酬wrj、激勵報酬ηij×RF和花費crij三部分組成。

uwij=wrj+ηij×RF-crij（3）

其中：ηij為獎勵指數(shù)，由信譽指數(shù)Hi和任務(wù)熟練指數(shù)Tij計算，如式（4）所示。

crij=p×dsij為工人到任務(wù)地點的旅行消耗，其中p為每米花費系數(shù)，dsij由Haversine formula計算得出：

4）平臺異構(gòu)效用

工人wi完成任務(wù)tj產(chǎn)生的平臺異構(gòu)效用upij由式（6）計算。由平臺報酬bj、固定報酬wrj和激勵報酬ηij×RF組成。

upij=bj-wrj-ηij×RF（6）

1.3 基于異構(gòu)效用的多目標任務(wù)分配模型

基于異構(gòu)效用的多目標任務(wù)分配即要尋找最優(yōu)任務(wù)分配方案，使得完成任務(wù)能夠獲得最大化的工人效用和平臺效用。該問題可以表示為如下的約束雙目標優(yōu)化模型。

其中：式（7）（8）分別表示最大化工人和平臺獲得的異構(gòu)效用；式（9）～（11）為任務(wù)分配的約束，分別表示每個工人wi完成的任務(wù)數(shù)不能超過wnummaxi、任務(wù)tj分配給不同工人的數(shù)量不能超過tnummaxj，wtij的取值為0或1表示同一個任務(wù)最多只能分配給同一工人一次。

2 異構(gòu)效用MCS多目標任務(wù)分配模型求解

MCS多任務(wù)分配的解集空間較大，是一個NP-hard問題，無法在多項式時間內(nèi)求解，因此考慮使用啟發(fā)式算法來解決。進化算法已應(yīng)用于MCS任務(wù)分配領(lǐng)域［12，13，17］，其特性也適合于本文的多任務(wù)分配問題。本文根據(jù)問題的特點設(shè)計了雙種群競爭的多目標進化算法（DCMEA）來求解模型，如算法1所示。

算法1根據(jù)工人集W和任務(wù)集T的信息，對個體進行序列編碼，并采用隨機加權(quán)貪婪策略生成初始化種群SP。接著，通過二元錦標賽算法將SP劃分為勝者種群WP和敗者種群LP。對這兩個種群執(zhí)行不同的交叉和變異操作，使WP注重局部搜索、LP注重全局搜索，實現(xiàn)競爭進化。之后，設(shè)計了修復(fù)算子對不滿足約束的無效解修復(fù)，以保留無效解中的有用信息。最后，將SP、WP和LP種群合并，根據(jù)任務(wù)分配解的UW和UP值，采用精英保留策略生成下一代種群SP。循環(huán)執(zhí)行上述雙種群進化過程，直至最大迭代次數(shù)，得到最優(yōu)的MCS任務(wù)分配方案集。

算法1 DCMEA

輸入：工人集W；任務(wù)集T；種群大小N；最大迭代次數(shù)times。

輸出：迭代后任務(wù)分配解集。

根據(jù)算法2初始化任務(wù)分配解集種群SP

for i=1：times do

根據(jù)算法3將種群SP劃分為勝者種群WP和敗者種群LP，并更新WP和LP使其朝著不同方向進化

根據(jù)算法4修復(fù)WP和LP中更新后產(chǎn)生的無效解

合并SP、WP、LP生成新的種群NewP

采用精英保留策略在NewP中選取前N個解生成子代種群NP

SP=NP

i=i+1

end for

return SP

2.1 個體編碼方式

通常MCS任務(wù)分配會采用0-1編碼的方式，用大小為m×n的數(shù)組表示種群個體［13］。行標為工人，列標為任務(wù)。數(shù)組元素為1表示分配給工人對應(yīng)的任務(wù)，否則為0。隨著任務(wù)和用戶數(shù)量的增加，0-1編碼會使矩陣包含大量元素“0”，變得稀疏。本文采用基于工人路徑的序列編碼，用一維數(shù)組表示一個可行的任務(wù)分配方案（種群個體Ci），如圖2所示。Ci由m個片段組成，每個片段的大小不超過工人可完成的最大任務(wù)數(shù)wnummaxi。每個片段中的數(shù)字表示任務(wù)的編號，工人根據(jù)編號按序完成任務(wù)，若沒有分配任務(wù)則用0表示。

2.2 隨機加權(quán)貪婪初始化

用隨機化的方式初始化種群容易生成無效解，也缺乏較優(yōu)的解來引導(dǎo)種群朝優(yōu)化的方向搜索。在多目標問題的求解中，線性加權(quán)法是一種常用的方法。對多個目標函數(shù)加權(quán)重，將多目標問題轉(zhuǎn)換為單目標問題，本文的兩個優(yōu)化目標可以轉(zhuǎn)換為

U=ε×UP+（1-ε）×UW（12）

算法2 隨機加權(quán)貪婪初始化

輸入：任務(wù)集合T，工人集合W。

輸出：初始種群SP

while i≤N do

生成沒有任務(wù)序號的個體Ci

創(chuàng)建候選工人集CWW

創(chuàng)建候選任務(wù)集CTT

隨機生成加權(quán)權(quán)重ε

repeat

從CW中隨機選擇一名工人wr

while j≤wnummaxr do

從CT中貪婪地選擇U值最大的任務(wù)ts

將任務(wù)ts的序號添加到Ci中wr的片段中

tnummaxs=tnummaxs-1

if tnummaxs≤0 do

CTCT-{ts}

end if

j=j+1

end while

CWCW-{wr}

until CW= or CT=

SP=SPU{Ci}

end while

return SP

上述初始化算法具有以下優(yōu)勢：a）基于實際問題約束的初始化方法可以避免生成無效初始解；b）基于貪婪策略的線性加權(quán)法獲得的解作為種群的初始化解可以引導(dǎo)種群朝優(yōu)化方向進化；c）通過隨機生成加權(quán)權(quán)重ε和工人的任務(wù)分配順序，可以保證初始種群的多樣性。

2.3 雙種群競爭進化

用二元錦標賽算法將種群劃分為勝者種群和敗者種群，并對兩個種群采用不同的更新策略，使兩個種群沿著不同方向進化。因此在進化過程中能夠增加種群的多樣性和隨機性，使得算法能夠跳出局部最優(yōu)，提升算法的收斂精度和速度。

1）二元錦標賽劃分種群

首先對種群的個體進行非支配排序、計算擁擠度距離。之后隨機選擇兩個個體，根據(jù)Pareto排序等級進行比較，等級高的為勝者，低的為敗者。若Pareto等級相同，進行擁擠度距離比較，擁擠度距離大的為勝者，小的為敗者。在進行N次比較后，將前N/2次比較的勝者構(gòu)成WP種群，后N/2次比較的敗者構(gòu)成LP種群。

2）勝者種群進化策略 WP種群在進化時注重局部搜索。首先采用多點交叉策略，選擇種群中C1和C2兩個個體，生成3～5個交叉點，交換C1和C2交叉點上的元素。如圖3所示，假設(shè)C1和C2有兩個工人，每個工人有三個任務(wù)，在個體C1和C2上生成三個交叉點，由豎線表示。將交叉點上的任務(wù)（2，1），（3，2），（9，8）交換后生成新的個體。

多點交叉后對新產(chǎn)生的個體采用兩點交換操作，在新個體上隨機生成兩個變異點，交換兩點上的任務(wù)生成新的個體。如圖4所示，將個體C1中虛線方框的任務(wù)（5，2）交換后生成新的個體。

勝者種群利用小范圍內(nèi)的交叉變異操作，保留原有個體的優(yōu)秀屬性，側(cè)重于在局部范圍內(nèi)搜索更優(yōu)解。

3）敗者種群進化策略

LP種群進化時注重全局搜索。選擇種群中個體C1和C2，采用順序交叉策略生成兩個新個體。如圖5所示，在個體C1和C2上生成兩個交叉點，由虛線表示。兩條虛線間的任務(wù)，即C1中的任務(wù)（5，6，3），C2中的任務(wù)（7，6，2）固定不變。在C1中去掉在C2固定部分（7，6，2）中出現(xiàn)的任務(wù)得到替換序列（5，3，1，9）。用該序列順序替換C2可變部分（1，10，8），更新C2得到（5，7，6，2，3，1）。在C2中去掉在C1固定部分（5，6，3）中出現(xiàn)的任務(wù)得到替換序列（1，7，2，10，8）。用該序列順序替換C1可變部分（2，1，9），更新C1得到（1，5，6，3，7，2）。

順序交叉后對新生成的個體采用Scramble變異的策略，在新個體上隨機生成3～5個變異點，將元素按新的順序隨機重新排列生成新的個體。如圖6所示，將個體C1中虛線方框內(nèi)的任務(wù)（5，3，7）隨機排序生成（3，7，5），交換任務(wù)后生成新的個體。

順序交叉和Scramble變異增大了個體中元素的改變幅度，擴大了種群的搜索空間，有利于生成新的優(yōu)秀個體。

雙種群競爭進化如算法3所示。由于選擇的概率導(dǎo)致雙種群中存在少量的相同解。在進化過程中，優(yōu)勢解局部搜索，劣勢解全局搜索，相同解則同時朝著兩個方向進化。種群沿著多個方向進化，增強了種群的多樣性和隨機性，能夠提高算法的尋優(yōu)能力。

算法3 雙種群競爭進化

輸入：種群SP。

輸出：進化后新種群WP、LP。

對SP采用二元錦標賽算法生成勝者種群WP和敗者種群LP

for i=1：（N/4」） do

在WP中選擇個體Cwi，Cw（i+N/4」）

采用多點交叉生成兩個新個體替換原有個體

在LP中選擇個體Cli，Cl（i+N/4」）

采用順序交叉生成兩個新個體替換原有個體

i=i+1

end for

for j=1：（N/2） do

對WP中個體Cwj采用兩點交換生成新個體替換原有個體

對LP中個體Clj采用Scramble變異生成新個體替換原有個體

j=j+1

end for

return WP，LP

2.4 修復(fù)算子

由于實際問題約束的特殊性，在進化過程中可能會產(chǎn)生無效的任務(wù)分配解。本文結(jié)合任務(wù)分配模型設(shè)計了修復(fù)算子，將無效解修復(fù)成有效解，并保留其中有用的信息。圖7展示了個體C1的修復(fù)過程。假設(shè)個體C1有三個工人，每個工人有三個任務(wù)，2號任務(wù)的最大分配數(shù)為2。首先將個體C1中工人w11中的2號任務(wù)替換成小于最大分配數(shù)的3號任務(wù)，使任務(wù)2不超過最大分配數(shù)。接著檢查每個工人是否有重復(fù)任務(wù)，并將工人w13中的5號任務(wù)替換成小于最大分配數(shù)的4號任務(wù)。

算法4是修復(fù)算子，首先統(tǒng)計個體中每個任務(wù)已分配的個數(shù)，計算每個任務(wù)剩余可分配的數(shù)量avnumj。接著將avnumj>0的任務(wù)替換掉avnumj<0的任務(wù)，使每個任務(wù)的avnumj≥0。最后對每個工人進行檢查，用avnumj>0的任務(wù)替換片段中重復(fù)任務(wù)。

算法4 修復(fù)算子

輸入：無效任務(wù)分配解Cinv。

輸出：有效任務(wù)分配解Cv。

統(tǒng)計無效解Cinv中每個任務(wù)tj分配給工人的個數(shù)

將最大分配數(shù)減去已分配數(shù)，計算出每個任務(wù)tj剩余可分配數(shù)avnumj

找出avnumj<0的任務(wù)tinv

按序號用 avnumj>0的任務(wù)tv替換解中的任務(wù)tinv

更新每個任務(wù)tj的avnumj，使所有的avnumj≥0

對每個工人wi的任務(wù)分配片段進行檢查，并記錄有重復(fù)分配的任務(wù)

按序號選擇avnumj>0的任務(wù)替換掉重復(fù)任務(wù)

return Cv

3 實驗分析

實驗在Windows 10操作系統(tǒng)、Intel Core i5-10200H 2.40 GHz CPU、16.0 GB內(nèi)存的機器上運行，用MATLAB R2020b編寫算法。本文選取三種多目標進化算法，分別為MOEADUR［22］、GFMMOEA［23］、DEAGNG［24］，來驗證DCMEA算法的性能。其中MOEADUR和DEAGNG是基于分解的多目標進化算法，類似算法已經(jīng)應(yīng)用于MCS任務(wù)分配領(lǐng)域中［17］，GFMMOEA是近年來提出的較為先進的多目標進化算法。算法參數(shù)按照原文獻設(shè)置，并添加了修復(fù)算子處理約束。

3.1 實驗數(shù)據(jù)集及參數(shù)設(shè)置

實驗采用Foursquare數(shù)據(jù)集［25］中紐約市9：00～12：00的簽到數(shù)據(jù)進行任務(wù)分配的測試。Foursquare數(shù)據(jù)集包含了大約十個月從紐約市和東京市收集的簽到記錄，每次簽到都包含以下記錄：user ID、venue ID 、venue category ID、venue category name、latitude、longitude、timezone offset in minutes、UTC time。由于紐約市中簽到地點存在較明顯的冷熱區(qū)，由此截取了經(jīng)緯度范圍為［-74.02，-73.92］、［40.68，40.8］，約15 km×10 km的長方形區(qū)域，并將數(shù)據(jù)集中簽到記錄的經(jīng)緯度視為MCS中任務(wù)集的地點，為每個任務(wù)生成隨機不同的tnummaxj數(shù)及skij值。此外選取不同ID工人初始簽到的地點作為工人的初始時間地點進行任務(wù)分配測試，根據(jù)文獻［20］隨機生成信譽值Ri，同時將Gompertz函數(shù)的參數(shù)分別設(shè)為a=e/2、b=-1、c=-1，使工人信譽指數(shù)和任務(wù)熟練指數(shù)取值范圍相近。為探尋在不同規(guī)模下算法的性能，選取了三組不同數(shù)量的工人任務(wù)實例集進行模擬，分別為data1：m=10，n=50；data2：m=20，n=100；data3：m=30，n=150。具體實驗參數(shù)的值和范圍見表1。

3.2 實驗結(jié)果分析

1）解集分布

圖8展示了DCMEA與對比算法在三個實例集上獲得的MCS任務(wù)分配解集所對應(yīng)的UW和UP值分布。結(jié)果顯示，DCMEA明顯優(yōu)于對比算法，能夠獲得更高的求解精度。DCMEA的UW和UP值分布也更加均勻和廣泛，因此能夠為平臺提供更加多元化的MCS任務(wù)分配方案。

2）IGD和HV指標

算法在實例上獨立運行30次，得到反向世代距離（IGD）［26］和超體積（HV）［27］的平均值和標準差，如表2、3所示。表中括號的數(shù)字為標準差。IGD評價指標可以綜合評價算法的收斂性和多樣性，IGD指標越小，算法的收斂性和多樣性越好。HV指標表示所獲得的非支配解集在目標空間上的覆蓋范圍，HV值越大，說明算法的解集覆蓋面越寬、分布越均勻，越接近真實Pareto前沿。

表2中，DCMEA的IGD平均值和標準差均優(yōu)于其他四種對比算法，表明DCMEA求解任務(wù)分配模型能夠獲得優(yōu)于對比算法的精度，同時在30次運行中得到的任務(wù)分配結(jié)果波動不大，因此具有更好的穩(wěn)定性。從數(shù)據(jù)集data1到data3，隨著實例復(fù)雜性增加，DCMEA的IGD值與其他算法的IGD差值越大。說明DCMEA隨著實例復(fù)雜增加能夠獲取比其他算法更優(yōu)的任務(wù)分配解集。表3顯示DCMEA的HV平均值均優(yōu)于對比算法，說明DCMEA得到的任務(wù)分配解集精度更高，且具有更好的多樣性。同樣，DCMEA隨著實例復(fù)雜增加能夠獲取比其他算法更優(yōu)的任務(wù)分配解集。

3）運行時間

算法在實例上獨立運行30次，得到運行時間的平均值和標準差，如表4所示。DCMEA在較為復(fù)雜的實例data2和data3上運行時間為最短，在data1上的運行時間只比DEAGNG略長。說明DCMEA總體上運行時間短于對比算法，在解決復(fù)雜問題上更能顯示其優(yōu)勢。

4）IGD和HV收斂曲線

圖9、10展示了算法在data1上迭代5萬次的IGD、HV的收斂曲線。DCMEA的收斂曲線在IGD上快速下降，并到達其他曲線下面，最終達到最小值。DCMEA的收斂曲線在HV上快速上升，并到達其他曲線上面，最終達到最大值。說明DCMEA的收斂速度明顯快于對比算法，在迭代早期能較快地找到優(yōu)秀的任務(wù)分配解集，且在迭代后期也不易陷入局部最優(yōu)，最終收斂精度也優(yōu)于其他算法。

上述實驗驗證了DCMEA在求解異構(gòu)效用MCS任務(wù)分配問題具有優(yōu)于對比算法的收斂精度、收斂速度和解的多樣性。DCMEA表現(xiàn)更優(yōu)的主要原因與算法設(shè)計所采用的技術(shù)有關(guān)。首先引入隨機加權(quán)貪婪初始化策略，生成優(yōu)勢解來初始化種群，從而能夠引導(dǎo)種群朝著最優(yōu)解的方向進化。此外，隨機的權(quán)重和任務(wù)分配順序保證了初始種群的多樣性。雙種群競爭機制把種群劃分為兩個子種群，每個子種群根據(jù)不同的策略更新種群個體。能夠在進化過程中保持種群的多樣性，使得種群不易陷入局部最優(yōu)，增加了種群的收斂性精度和速度。最后，算法中所設(shè)計的修復(fù)算子使無效解滿足實際問題的約束條件，保留了其中的有用信息，進一步提升了種群的收斂性和多樣性。

3.3 策略有效性分析

DCMEA結(jié)合本章MCS任務(wù)分配模型的特點，在進化算法的基礎(chǔ)上設(shè)計了隨機加權(quán)貪婪初始化、雙種群競爭搜索以及修復(fù)算子等策略。其中修復(fù)算子使個體能夠滿足約束條件，隨機加權(quán)貪婪初始化、雙種群競爭搜索增強了算法的求解性能。為驗證隨機加權(quán)貪婪初始化策略和雙種群競爭搜索策略對算法性能提升的有效性，將DCMEA中初始化策略改為隨機初始化得到DCMEAR算法，同時將DCMEA改為在單種群上采用順序交叉和兩點交換得到SMEA算法，并與DCMEA進行對比。

1）解集分布

圖11展示了在三個不同數(shù)據(jù)實例集上DCMEAR、SMEA和DCMEA獲得的MCS任務(wù)分配解集所對應(yīng)的UW和UP值分布。

結(jié)果顯示，DCMEA在迭代過程中可以找到更加優(yōu)越的解集。SMEA的解集分布差于另外兩種算法，說明雙種群競爭進化策略有效地改進了傳統(tǒng)進化算法種群單一、容易陷入局部最優(yōu)的問題。DCMEAR獲得解集的UW和UP值隨著數(shù)據(jù)實例集的增大越來越差，這表明隨著任務(wù)分配的復(fù)雜度的逐漸增加，較好的初始解能夠引導(dǎo)種群的搜索，增加算法的尋優(yōu)性能。

2）IGD和HV指標

表5、6展示了三種算法IGD、HV指標的平均值和標準差，每個算法運行30次，優(yōu)異的值加粗顯示?？梢钥闯?，DCMEA的IGD、HV值優(yōu)于其他對比算法，進一步表明DCMEA的改進策略有效地提升了求解任務(wù)分配模型的精度和性能。

3.4 模型有效性分析

本文綜合考慮了工人的信譽異質(zhì)性和不同工人對任務(wù)所需數(shù)據(jù)的熟練程度對任務(wù)分配的影響，結(jié)合信譽指數(shù)和任務(wù)熟練指數(shù)設(shè)計了異構(gòu)效用機制。為說明異構(gòu)效用機制對任務(wù)分配的影響，將本文模型與只考慮工人信譽和只考慮任務(wù)熟練程度的兩種模型進行對比。圖12展示了在data1上不同模型采用DCMEA算法生成的任務(wù)分配方案集的平均工人收益和平臺收益。由圖可知，本文模型能夠找到UW和UP平均值更為均衡的方案，同時UW與UP值的和也略高于其他模型，驗證了本文異構(gòu)效用機制的有效性。

4 結(jié)束語

本文引入了信譽指數(shù)和任務(wù)熟練指數(shù)來描述工人和任務(wù)的異質(zhì)性，構(gòu)建了最大化工人異構(gòu)效用和最大化平臺異構(gòu)效用的MCS多目標異構(gòu)效用任務(wù)分配模型。為了求解該模型，通過引入隨機貪婪初始化、雙種群競爭進化、修復(fù)算子等技術(shù)設(shè)計了一種雙種群競爭的多目標進化算法DCMEA。通過在解集分布、IGD和HV指標、運行時間上的實驗，證明DCMEA能夠在求解異構(gòu)效用MCS多目標任務(wù)分配問題中獲得良好的收斂精度、速度和穩(wěn)定性，并且在復(fù)雜的環(huán)境中依然能夠獲得較好的任務(wù)分配結(jié)果。在后面的工作中，可以考慮在任務(wù)分配中對工人的位置進行隱私保護，減少工人參與任務(wù)的顧慮、激發(fā)積極性，從而可以招募到更多優(yōu)質(zhì)的工人。

參考文獻：

［1］Guo Bin，Wang Zhu，Yu Zhiwen，et al.Mobile crowd sensing and computing：the review of an emerging human-powered sensing paradigm［J］.ACM Computing Surveys，2015，48（1）：1-31.

［2］Liu Yutong，Kong Linghe，Chen Guihai.Data-oriented mobile crowdsensing：a comprehensive survey［J］.IEEE Communications Surveys & Tutorials，2019，21（3）：2849-2885.

［3］Sun Wen，Li Qiang，Tham C K.Wireless deployed and participatory sensing system for environmental monitoring［C］//Proc of the 11th Annual IEEE International Conference on Sensing，Communication，and Networking.Piscataway，NJ：IEEE Press，2014：158-160.

［4］Coric V，Gruteser M.Crowdsensing maps of on-street parking spaces ［C］//Proc of IEEE International Conference on Distributed Computing in Sensor Systems.Piscataway，NJ：IEEE Press，2013：115-122.

［5］Guo Bin，Chen Huihui，Yu Zhiwen，et al.FlierMeet：a mobile crowdsensing system for cross-space public information reposting，tagging，and sharing［J］.IEEE Trans on Mobile Computing，2015，14（10）：2020-2033.

［6］Alemdar H，Ersoy C.Wireless sensor networks for healthcare：a survey［J］.Computer Networks，2010，54（15）：2688-2710.

［7］Capponi A，F(xiàn)iandrino C，Kantarci B，et al.A survey on mobile crowdsensing systems：challenges，solutions and opportunities［J］.IEEE Communications Surveys & Tutorials，2019，21（3）：2419-2465.

［8］Zhang Lichen，Ding Yu，Wang Xiaoming，et al.Conflict-aware participant recruitment for mobile crowdsensing［J］.IEEE Trans on Computational Social Systems，2020，7（1）：192-204.

［9］Ni Jianbing，Zhang Kuan，Xia Qi，et al.Enabling strong privacy pre-servation and accurate task allocation for mobile crowdsensing［J］.IEEE Trans on Mobile Computing，2020，19（6）：1317-1331.

［10］Song Zheng，Liu Chiharold，Wu Jie，et al.QoI-aware multitask-oriented dynamic participant selection with budget constraints［J］.IEEE Trans on Vehicular Technology，2014，63（9）：4618-4632.

［11］Wang Jiangtao，Wang Yasha，Zhang Daqing，et al.Fine-grained multi-task allocation for participatory sensing with a shared budget［J］.IEEE Internet of Things Journal，2016，3（6）：1395-1405.

［12］Li Xin，Zhang Xinglin.Multi-task allocation under time constraints in mobile crowdsensing［J］.IEEE Trans on Mobile Computing，2021，20（4）：1494-1510.

［13］Ji Jianjiao，Guo Yinan，Gong Dunwei，et al.Evolutionary multi-task allocation for mobile crowdsensing with limited resource［J］.Swarm and Evolutionary Computation，2021，63：100872.

［14］蔣偉進，張婉清，陳萍萍，等.基于IWOA群智感知中數(shù)量敏感的任務(wù)分配方法［J］.電子學報，2022，50（10）：2489-2502.（Jiang Weijin，Zhang Wanqing，Chen Pingping，et al.Quantity sensitive task allocation method based on IWOA in group intelligence perception［J］.Acta Electronica Sinica，2022，50（10）：2489-2502.）

［15］楊桂松，吳笑天，高麗，等.面向單任務(wù)質(zhì)量保障的移動群智感知任務(wù)分配［J］.計算機工程，2022，48（9）：45-54.（Yang Guisong，Wu Xiaotian，Gao Li，et al.Task allocation towards individual task quality assurance in mobile crowd sensing［J］.Computer Enginee-ring，2022，48（9）：45-54.）

［16］Estrada R，Mizouni R，Otrok H，et al.A crowd-sensing framework for allocation of time-constrained and location-based tasks［J］.IEEE Trans on Services Computing，2020，13（5）：769-785.

［17］Ji Jianjiao，Guo Yinan，Gong Dunwei，et al.MOEA/D-based participant selection method for crowdsensing with social awareness［J］.Applied Soft Computing，2019，87：105981.

［18］Li Mingchu，Gao Yuan，Wang Mingliang，et al.Multi-objective optimization for multi-task allocation in mobile crowd sensing［J］.Procedia Computer Science，2019，155：360-368.（下轉(zhuǎn)第169頁）

（上接第164頁）

［19］Shen Xiaoning，Chen Qingzhou，Pan Hongli，et al.Variable speed multi-task allocation for mobile crowdsensing based on a multi-objective shuffled frog leaping algorithm［J］.Applied Soft Computing，2022，127：109330.

［20］Ren Ju，Zhang Yaoxue，Zhang Kuan，et al.SACRM：social aware crowdsourcing with reputation management in mobile sensing［J］.Computer Communications，2015，65：55-65

［21］Wu Shengnan，Wang Yingjie，Tong Xiangrong.Multi-objective task assignment for maximizing social welfare in spatio-temporal crowdsour-cing［J］.China Communications，2021，18（11）：11-15.

［22］De Farias L R C，Araújo A F R.A decomposition-based many-objective evolutionary algorithm updating weights when required［J］.Swarm and Evolutionary Computation，2022，68：100980.

［23］Tian Ye，Zhang Xingyi，Cheng Ran，et al.Guiding evolutionary multi-objective optimization with generic front modeling［J］.IEEE Trans on Cybernetics，2020，50（3）：1106-1119.

［24］Liu Yiping，Ishibuchi H，Masuyama N，et al.Adapting reference vectors and scalarizing functions by growing neural gas to handle irregular pareto fronts［J］.IEEE Trans on Evolutionary Computation，2020，24（3）：439-453.

［25］Yang Dingqi，Zhang Daqing，Zheng V W，et al.Modeling user activity preference by leveraging user spatial temporal characteristics in LBSNs［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2015，45（1）：129-142.

［26］Bosman P，Thierens D.The balance between proximity and diversity in multi-objective evolutionary algorithms［J］.IEEE Trans on Evolutionary Computation，2003，7（2）：174-188.

［27］Zitzler E，Thiele L.Multi-objective evolutionary algorithms：a comparative case study and the strength pareto approach［J］.IEEE Trans on Evolutionary Computation，1999，3（4）：257-271.