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

傅彥銘 陸盛林 祁康恒 許勵(lì)強(qiáng) 陳嘉元

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

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

中圖分類號(hào)：TP393.01?? 文獻(xiàn)標(biāo)志碼：A?? 文章編號(hào)：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 引言

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

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

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

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

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

1.1 模型描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SP=NP

i=i+1

end for

return SP

2.1 個(gè)體編碼方式

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

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

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

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

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

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

輸出：初始種群SP

while i≤N do

生成沒(méi)有任務(wù)序號(hào)的個(gè)體Ci

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

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

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

repeat

從CW中隨機(jī)選擇一名工人wr

while j≤wnummaxr do

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

將任務(wù)ts的序號(hào)添加到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)勢(shì)：a）基于實(shí)際問(wèn)題約束的初始化方法可以避免生成無(wú)效初始解；b）基于貪婪策略的線性加權(quán)法獲得的解作為種群的初始化解可以引導(dǎo)種群朝優(yōu)化方向進(jìn)化；c）通過(guò)隨機(jī)生成加權(quán)權(quán)重ε和工人的任務(wù)分配順序，可以保證初始種群的多樣性。

2.3 雙種群競(jìng)爭(zhēng)進(jìn)化

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

1）二元錦標(biāo)賽劃分種群

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

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

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

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

3）敗者種群進(jìn)化策略

LP種群進(jìn)化時(shí)注重全局搜索。選擇種群中個(gè)體C1和C2，采用順序交叉策略生成兩個(gè)新個(gè)體。如圖5所示，在個(gè)體C1和C2上生成兩個(gè)交叉點(diǎn)，由虛線表示。兩條虛線間的任務(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）。

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

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

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

算法3 雙種群競(jìng)爭(zhēng)進(jìn)化

輸入：種群SP。

輸出：進(jìn)化后新種群WP、LP。

對(duì)SP采用二元錦標(biāo)賽算法生成勝者種群WP和敗者種群LP

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

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

采用多點(diǎn)交叉生成兩個(gè)新個(gè)體替換原有個(gè)體

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

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

i=i+1

end for

for j=1：（N/2） do

對(duì)WP中個(gè)體Cwj采用兩點(diǎn)交換生成新個(gè)體替換原有個(gè)體

對(duì)LP中個(gè)體Clj采用Scramble變異生成新個(gè)體替換原有個(gè)體

j=j+1

end for

return WP，LP

2.4 修復(fù)算子

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

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

算法4 修復(fù)算子

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

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

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

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

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

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

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

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

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

return Cv

3 實(shí)驗(yàn)分析

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

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

1）解集分布

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

2）IGD和HV指標(biāo)

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

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

3）運(yùn)行時(shí)間

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

4）IGD和HV收斂曲線

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

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

3.3 策略有效性分析

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

1）解集分布

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

結(jié)果顯示，DCMEA在迭代過(guò)程中可以找到更加優(yōu)越的解集。SMEA的解集分布差于另外兩種算法，說(shuō)明雙種群競(jìng)爭(zhēng)進(jìn)化策略有效地改進(jìn)了傳統(tǒng)進(jìn)化算法種群?jiǎn)我弧⑷菀紫萑刖植孔顑?yōu)的問(wèn)題。DCMEAR獲得解集的UW和UP值隨著數(shù)據(jù)實(shí)例集的增大越來(lái)越差，這表明隨著任務(wù)分配的復(fù)雜度的逐漸增加，較好的初始解能夠引導(dǎo)種群的搜索，增加算法的尋優(yōu)性能。

2）IGD和HV指標(biāo)

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

3.4 模型有效性分析

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

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

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

參考文獻(xiàn)：

［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］蔣偉進(jìn)，張婉清，陳萍萍，等.基于IWOA群智感知中數(shù)量敏感的任務(wù)分配方法［J］.電子學(xué)報(bào)，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ì)量保障的移動(dòng)群智感知任務(wù)分配［J］.計(jì)算機(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頁(yè)）

（上接第164頁(yè)）

［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.