考慮空間眾包工作者服務質量的任務分配策略及其螢火蟲群優化算法求解

* ，3

（1.合肥工業大學管理學院，合肥 230009；2.過程優化與智能決策教育部重點實驗室（合肥工業大學），合肥 230009；3.北方民族大學，銀川 750021）

0 引言

眾包（Crowdsourcing）是Howe［1］提出來的，即把以前需要特定員工完成的工作發布在一個公開的平臺上，外包給那些自愿來完成這些工作的非特定的群眾志愿者的做法。由于互聯網技術和共享經濟模式［2］的飛速發展，新的眾包模式逐漸產生并發展，若要完成這類新的眾包任務往往要求要在指定時間前到達指定任務地點。這種自傳統眾包技術發展而來且融合了時空信息的新模式被稱為時空眾包（Spatio-temporal Crowdsourcing），也被稱為空間眾包（Spatial Crowdsourcing）?？臻g眾包采用一種集合群體智慧的方式完成帶有時空信息的任務，在近年來被廣泛推廣，其應用領域也在不斷擴展，目前在交通、物流等領域都有所涉及。日常使用的滴滴出行、百度外賣、餓了么等軟件都屬于空間眾包平臺。

空間眾包中包含三個關鍵問題［2］，分別是任務分配、質量控制和隱私保護，本文的研究重點是任務分配。任務分配指的是，充分考慮任務請求者和空間眾包工作者的時間和空間屬性，以及眾包任務的特點，由空間眾包平臺為每個任務請求者匹配最佳眾包工作者來完成任務。國內外眾多學者均有對空間眾包任務分配問題進行研究。文獻［3］從全局最優的角度最大化總任務數目，并考慮了工人需要在完成任務后于截止時間前返回出發點的約束，設計了一種啟發式深度優先搜索算法；文獻［4］為了提高空間眾包中多類型任務的完成數量和質量，設計了一種多類型任務分配方法；文獻［5］將任務分解成可高效完成的子任務，以提高任務完成概率；文獻［6］為了解決一種空間眾包中的在線任務分配問題，提出先采用k近鄰算法選擇候選工作者，再采用一種閾值選擇算法；文獻［7］為了減少進行任務分配的隨機性同時提升效用值，設計了一種基于統計預測的自適應閾值算法；文獻［8］為了解決在設定的一定預算條件下最大化可靠性分配，以及在一定可靠性要求下最小化成本分配兩種優化問題，提出了一種貪婪策略；文獻［9］為了選擇效用值更大的工人和任務之間的組合，設計了一種貪婪策略；文獻［10］建立了一種質量敏感的應答模型，并設計了眾包數據分析系統，可以更準確地滿足用戶需求；文獻［11］將質量控制的目標定為每個匹配的眾包任務和眾包參與者之間的時空距離，進行在線實時任務分配。上述國內外學者對任務分配的研究既包括靜態任務分配也包括在線任務分配，但大多從工作者角度盡可能提高任務完成概率、最大化任務完成數量、最小化任務成本等，將其作為空間眾包質量控制的考慮指標，缺少從任務請求者對工作者評價高低的角度考慮其對一定的時空環境下任務分配質量的影響的研究，而本文致力于從這個角度出發考慮空間眾包任務分配問題。

群智能優化算法主要模擬自然界中生物的群體行為，通過個體間信息交流、學習與合作，將有限的個體經驗與智能通過相互作用達到整體遠大于個體之和的效果，實現尋優的目的。經典的群智能優化算法有遺傳算法（Genetic Algorithm，GA）［12］、粒子群優化（Particle Swarm Optimization，PSO）算法［13］、人工魚群算法、螢火蟲群優化（Glowworm Swarm Optimization，GSO）算法等，許多學者在研究最優化問題時經常使用。但部分算法也存在一些缺陷，如遺傳算法通常效率比較低下、易出現過早收斂；PSO 算法容易產生早熟、局部尋優能力差；人工魚群算法也收斂較慢。而GSO 算法具有便于操作、實現簡單且具有較好的全局尋優能力等優點，所以本文重點研究此種算法。GSO 算法由Krishnanand 等［14］于2005 年第一次提出，該算法通常被應用于解決連續性問題，文獻［15］為了豐富種群的多樣性，設計了一種基于混合變異的GSO 算法；文獻［16］使用Spark 框架實現了GSO 算法，并利用幾種多模態基準函數對不同維數的Spark-GSO 算法進行了評價，驗證了算法的有效性。對于離散性問題，例如組合優化問題，研究者們通常改進算法，以使其適用于解決該類問題。文獻［17］改進GSO 算法來處理煙草香級集成分類問題，提高了分類準確度；文獻［18］為了求解旅行推銷員問題，改進螢火蟲的編碼和解碼方式以及個體間距離計算方式，并引入局部路徑優化算子；文獻［19］重新定義了離散型人工螢火蟲算法中的距離，且使用了一種新的擾動機制增加了螢火蟲種群的多樣性，用于解決旅行商問題；文獻［20］為了解決復雜的組合優化個性化推薦問題，改進GSO 算法，設計了一種混合的多目標模型，并構造深度神經網絡來分析候選服務并提供個性化推薦；文獻［21］改進了離散型螢火蟲群優化（Discrete Glowworm Swarm Optimization，DGSO）算法用于處理飛行器三維路徑規劃問題；文獻［22］為了提高帶有時間窗的多目標車輛路徑規劃問題的求解質量，先對帶有不同時間窗的用戶進行分類，有效提升了時間效率。上述國內外學者的研究將改進后螢火蟲群算法應用在求解連續性問題和離散型問題時算法性能均有一定的提升，但在算法的收斂速度和全局尋優能力方面還有待提高。而本文所提出的在一定時空環境下的空間眾包任務分配問題可以采用此算法進行求解，并對算法的初始化策略、位置移動策略、鄰域搜索策略等進行改進和優化，提高算法的收斂速度和全局尋優能力，也就可以提高空間眾包任務分配的效率和質量。

鑒于實際生活中用戶每次使用“滴滴出行”軟件后會為司機服務進行評價，本文將司機所得到的星級等級評價轉化為服務質量評價得分，并將該要素加入到影響整體任務分配總得分的條件約束中；同時，提出空間眾包工作者評價更新機制，即工作者每成功接單一次，將根據當前服務質量評價得分和歷史評價得分更新工作者得分；考慮空間眾包工作者的服務質量評價得分和時空成本，將任務分配質量總得分最高作為優化目標，并采用改進的離散型螢火蟲群優化（Improved Discrete Glowworm Swarm Optimization Based on Worker ' s Evaluation Score，IDGSOBWES）算法來解決。

1 考慮工作者服務質量的任務分配策略

1.1 問題描述及所包含要素的描述

下面給出具體問題描述：本文設定一個類似于“滴滴出行”中選擇打出租車需求的場景，空間眾包任務被任務請求者發布在空間眾包平臺上，空間眾包工作者待命，平臺實時進行空間眾包任務和空間眾包工作者之間的任務分配。本文基于實際問題，生活中每次打車結束，用戶會根據司機的服務給出評價，評價結果反映在軟件上，于是考慮將司機所得到的星級評價經處理轉化為數字化的服務質量評價得分，并將此項業務要素加入到任務分配策略中，以任務分配質量總得分最高為優化目標，找到任務與工作者之間的最佳匹配。同時本文采用批處理的方式，將所研究的時空區域劃分為多個連續區域，每個區域由一個時間戳和一定的地理面積組成，作為一個時空環境，每個時空環境下的任務分配周期性不斷進行，形成動態任務分配。

本文所設定的問題情境包含以下要素：任務請求者、空間眾包任務、空間眾包工作者、空間眾包平臺、任務分配總得分、時空環境。表1給出上述所提及的要素的具體描述。

表1 空間眾包任務分配所包含要素Tab.1 Elements included in spatial crowdsourcing task allocation

1.2 工作者的服務質量星級評價轉化為數字化評價得分

在實際生活中，使用“滴滴出行”之后，乘客（任務請求者）需要給提供服務的司機（空間眾包工作者）在“滴滴出行”軟件上進行評價，本文將此星級評價信息通過數據處理轉化為數字化評價得分，數值范圍是（0，100］分。每個空間眾包工作者的評價得分高低與他的服務質量成正比。表2 給出空間眾包工作者的星級評價及其對應的數字化評分范圍。

表2 星級評價與評價得分對應表Tab.2 Correspondence table of star rating and evaluation score

1.3 空間眾包工作者評價得分更新機制

在引入工作者的服務質量評價得分要素后，為了更真實地反映該要素對任務分配質量的影響，設置空間眾包工作者評價得分更新機制，及時更新工作者的評價得分，評價得分高的工作者將被優先考慮安排任務。空間眾包工作者目前評價得分大小是由歷史完成任務后所得評價轉化得到的評價得分，每次成功地完成任務分配后，應該根據當前任務完成之后任務請求者給工作者的評價，實時更新工作者評價得分。每當空間眾包工作者成功完成當前分配的任務后，空間眾包平臺使用加權平均更新空間眾包工作者評價得分，對歷史得分和當前完成任務后所獲得的新的得分加權，從而得到最新得分?？臻g眾包工作者為了能順利接單，將致力于提升自身服務質量以獲得更高的得分；由此，一方面可以改善任務分配質量，另一方面也在一定程度上達到了激勵工作者的效果。假設由歷史數據處理得到的工作者評價得分用grade_now表示，每成功完成接單任務后新的得分用grade_new表示，則每次任務分配結束并完成任務后，更新當前工作者評價得分為：

其中：k表示工作者的第k次分配；α表示權重系數，α的大小不同，表示歷史得分對當前得分的影響大小不同。根據式（1）可得，空間眾包工作者想要成功分配到任務，需要持續高質量完成任務以獲得更高的評價得分，這樣可以實現高質量的任務分配同時激勵工作者認真完成任務。

如表3 所示，這是在一次成功的任務分配后工作者當前評價得分的更新情況，其中加黑的數字表示該工作者成功接單并更新了當前數字得分。15個工作者中有10個成功接單，每個工作者完成質量不同，得到的新的得分也不同，完成質量高的工作者評價得分會升高，評價得分高且距離近的工作者下次將被優先分配任務，或距離相等評價得分高的工作者也將被優先分配任務。

表3 工作者評價得分更新Tab.3 Update of workers’evaluation score

1.4 加入工作者服務質量評價得分機制的任務分配模型

在某一時空環境下，任務請求者在空間眾包平臺上發布了數量為m的待完成空間眾包任務，此時待命的空間眾包工作者數量為n（由于本文在空間眾包任務分配中加入了空間眾包工作者的服務質量評價業務要素，故假設m小于n，由此可以根據空間眾包工作者評價得分高低優先考慮分配哪個工作者），只考慮當前所處時空環境，對空間眾包任務和工作者進行匹配，空間眾包任務數量為m，考慮從n個工作者中選擇m個，共有種可能，在一次空間眾包任務分配后有m個任務與工作者的組合，共有m！種組合，所以歸類為NP難問題，而本文是將任務分配總得分最高作為最終的優化目標，因而可以整理為如下模型，即加入空間眾包工作者服務質量評價得分機制的任務分配模型，具體如下：

其中：∑G表示所有被選擇匹配的空間眾包工作者的服務評價得分總和；∑L表示所有被匹配的工作者總旅行成本之和；∑LT表示在指定的匹配結果中工作者未能在指定時間內到達任務位置的消耗總和；m表示某個時空環境下的新發布的空間眾包任務的數量；n表示某個時空環境下的正處于空閑的空間眾包工作者的數量（m，n為正整數，由于要考慮按工作者評價得分挑選工作者，故假設m＜n）；在此模型中，由于假設的前提條件是m＜n的，說明在一個時空環境中，所有的空間任務都將被分配給相應工作者去完成，而每個工作者想要接單必須滿足一定條件，這在一定程度上充分調用了工作表現比較優秀的工作者，對優秀工作者的利用率將達到比較高的水平，相對來說，表現較差的工作者將得到平臺較低的調用機會，而上述1.3 節中設置的工作者評價得分更新機制，具有鼓勵工作者努力提高評價得分來達到接單目的的效果，激勵每個工作者都成為優秀的工作者，所以這說明此模型對平臺方進行任務分配來說，優秀工作者的資源利用率是較高的；M表示某個時空環境下所有m個空間眾包任務的集合；NM表示某個時空環境下m個（從n個工作者中選出m個）空間眾包工作者的集合，集合中共有m個元素，且集合共有種可能；i表示集合M中的第i個任務；j表示集合NM中的第j個工作者；jmin表示集合NM中最小元素，jmax表示集合NM中最大元素；Li，Lj在面積S范圍內；Li=(xi，yi)表示第i個空間眾包任務的位置數據；Lj=(xj，yj)表示第j個空間眾包工作者的位置數據；ManhaDis()表示以曼哈頓距離計算方式計算；Lij表示某成功的任務分配中第i個任務匹配第j個工作者，其中，第i個空間眾包任務與第j個空間眾包工作者之間的距離；Gij表示與第i個空間眾包任務匹配的第j個空間眾包工作者的評價得分，vj表示第j個工作者行駛速度，在此模型中，將每個工作者的行駛速度設置為定值，是為了保證面對同一距離的任務，其他條件一致的情況下，每個工作者完成任務需要的時間是一致的；表示任務請求者所能接受的任務工作者趕到任務地點最多所用時間。

2 GSO算法及其改進

2.1 基本GSO算法

基本GSO 算法是依據螢火蟲個體及群體的行為動作設計的算法。算法中，每個可行解由每只螢火蟲所處的位置表示，越亮的螢火蟲其所處位置越好。對每只螢火蟲而言，低亮度的螢火蟲會向比自身亮度高的螢火蟲靠近，來搜索更佳的位置，而螢火蟲越亮，它吸引其他螢火蟲的可能性也越高。GSO算法尋優過程大致如下：

1）變量初始化：N（N表示種群規模）個螢火蟲隨機置于可行域內，初始熒光素為l0，熒光素消失率ρ，熒光素更新率γ，固定步長s，鄰域閾值nt，初始感知半徑rs，初始決策半徑rd，決策半徑更新率β，最大迭代次數iter_max，每次迭代控制變量t。

2）更新熒光素：li(t)代表在第t次迭代時螢火蟲i的熒光素值，J(xi(t))代表在第t次迭代時螢火蟲i所處位置的目標函數值。

3）尋找螢火蟲i的鄰居集合：Ni(t)代表在第t次迭代時螢火蟲i尋找的鄰居集合代表在第t次迭代時螢火蟲i的決策半徑。

4）采用輪盤賭的方式判斷螢火蟲i接下來的移動方向：j=max(pi)表示其根據鄰域確定的移動方向，其中pi=(pi1(t)，pi2(t)，…，pij(t)，…(t))，pij(t)表示螢火蟲i以多大概率向螢火蟲j方向移動。

5）更新位置：xi(t+1)代表第t+1 次迭代時螢火蟲i的位置。

2.2 基于工作者評價得分的改進的離散型GSO算法

2.2.1 算法的離散化

通常GSO 算法被用于處理連續空間的問題，當引入此算法來處理空間眾包任務分配問題時，需要進行離散化，對算法的解及初始化進行離散化處理，并采用適當的整數編碼機制和編碼更新規則，改進算法的位置更新策略和鄰域搜索策略，從而讓該算法適用于處理本文問題，使其具有更好的收斂速度和尋優能力。

2.2.2 算法的優化目標

考慮空間眾包工作者服務評價的任務分配，優化目標是使任務分配質量總得分盡可能高，既考慮所有匹配了的空間眾包工作者評價得分總和，又考慮相互匹配的工作者到任務地點旅行成本總和，另外還考慮工作者是否能在任務要求最遲開始時間之前開始執行任務，因此，在目標函數中加入懲罰因子，利用線性加權變多目標為單目標，優化目標為使任務分配總得分最高，表示如下：

其中：0 ＜r1，r2＜1，r1+r2=1，r1，r2表示所占權重；c1、c2表示為了統一量綱的常數；TD表示任務分配結果總得分；G表示當前任務分配中所有被分配的空間眾包工作者評價得分總和；L表示任務分配中所有工作者完成指定任務消耗的總旅行成本；LT表示工作者到任務地點的距離成本總和，能夠在任務最遲開始時間之前到達任務地點的工作者才屬于符合要求的工作者，將不計成本，但不符合要求的工作者需要再加上額外的距離成本。

2.2.3 算法的離散及改進

1）算法與任務分配問題的對應及初始化。

在改進的算法中，將任務分配的組合設置為：xi(t)=[xi1(t)，xi2(t)，…，xim(t)]，表示在第t次迭代時第i個螢火蟲的一種任務分配組合。其中，m表示待完成的空間任務的數量。為了清楚地表示一組空間任務與空間眾包工作者之間的任務分配，將每只螢火蟲初始化為一個m維的向量，每只螢火蟲的位置代表一種m個空間任務和m個眾包工作者之間的匹配。在進行初始化時采用隨機的方式。例如：某一時空環境下，有10個新發布的空間任務（序列號1～10），15位空閑的空間眾包工作者（序列號1～15），那么其中一個初始化的隨機解為xi(t)=[5，3，9，12，7，1，8，15，4，6]，表示從15個工作者中隨機選擇10 個來執行任務，每一維度的數字即表示任務序列號，而每一維度上對應的數字即表示工作者的序列號。因此，此解表示，第5 個工作者分配了第1 個任務，第3 個工作者分配了第2 個任務，第9 個工作者分配了第3 個任務，…，第6 個工作者分配了第10個任務。

2）算法中距離計算公式。

螢火蟲i與螢火蟲j之間距離以漢明距離公式計算。因此，螢火蟲i的第k維與螢火蟲j的第k維之間的距離，螢火蟲i與螢火蟲j之間的距離，分別表示為：

其中1 ≤k≤m。

3）算法中更新位置公式。

得到初始解后，螢火蟲i將與鄰域內最優螢火蟲的每一維對比，以概率p1保持第k維編碼不變，以p2-p1的概率變為與最優螢火蟲相同，以1-p2的概率隨機變化；如果出現了編碼重復的情況（即一個工作者同時被分配了多個空間眾包任務，這顯然不符合“空閑工作者同一時間只能接受一個眾包任務”的約束條件），則找出與最優螢火蟲相同維度上不同編碼及其維度，將不同編碼重新以隨機的順序排列并按序放入剛剛的維度上。如下所示：隨機一只螢火蟲i的初始解xi(t)=[12，8，5，7，2，11，15，9，3，6]，螢火蟲i的鄰域內最優螢火蟲xj(t)=[1，9，4，10，3，15，7，8，2，13]，螢火蟲i根據式（3）～（9）靠近鄰域內最優螢火蟲，進行第一次位置更新，得到xi(t)=[12，8，4，7，3，11，7，9，10，13]，當中出現了重復編碼情況，按前面所述規則重新進行編碼更新，螢火蟲i更新當前位置為xi(t)=[10，9，4，2，3，8，7，15，1，13]，此時編碼不再有重復。

4）算法中鄰域搜索優化策略。

第一種：引入交換變異算子策略。

對螢火蟲i，隨機從它的m維中挑選兩個維度，第p維和第q維，將其對應維度上的編碼交換。例如，對螢火蟲i，xi(t)=[5，3，9，12，7，1，8，15，4，6]，隨機產生兩維（3，7），即p=3，q=7，兩維度上對應的數字分別為9 和8，將兩個維度上的數字9和8 位置交換，則執行交換變化后螢火蟲i的編碼變為xi(t)=[5，3，8，12，7，1，9，15，4，6]。

第二種：引入插入變異算子策略。

對螢火蟲i，隨機從它的m維中挑選兩個維度，第p維和第q維，將第q維上的編碼移動到第p維上，第p維及之后維度上的編碼往后順延。例如，對螢火蟲i，xi(t)=[5，3，9，12，7，1，8，15，4，6]，隨機產生兩維（3，7），即p=3，q=7，兩維度上對應的數字分別為9 和8，將第7 維上的數字8 移動到第3維上，第3維上的數字9移動到第4維上，后面維度上的數字往后順延，則執行插入變化后螢火蟲i的編碼變為xi(t)=[5，3，8，9，12，7，1，15，4，6]。

第三種：引入反演變異算子策略。

對螢火蟲i，隨機從它的m維中挑選兩個維度，第p維和第q維，將第p～q維上的編碼執行反轉。例如，對螢火蟲i，xi(t)=[5，3，9，12，7，1，8，15，4，6]，隨機產生兩維（3，7），即p=3，q=7，兩維度上對應的數字分別為9和8，將第3～7維上的數字9、12、7、1、8反轉變為8、1、7、12、9，重新置于第3～7維上，則執行反演變化后螢火蟲i的 編碼變為xi(t)=[5，3，8，1，7，12，9，15，4，6]。

2.2.4 算法的執行步驟

本文所提出的基于工作者評價得分的改進的離散型GSO算法的具體執行步驟如下：

步驟1 將各參數值初始化，包括種群規模、熒光素更新率、熒光素消失率、感知半徑、決策半徑、最大迭代次數等。

步驟2 根據新發布的任務數m，空閑工作者數n(m＜n)，確定螢火蟲維度m，根據2.2.3 小節中1）生成初始任務分配組合。

步驟3 根據式（4）計算熒光素值，并標記初始最亮螢火蟲到公告板。

步驟4 根據式（10）、（11）計算距離，并根據式（5）、（6）尋找移動方向；若未找到鄰域螢火蟲，即式（5）求得結果為空集合，則以隨機概率執行2.2.3 節4）中所述策略中的某一種再進行新的鄰域搜索。

步驟5 不再使用式（7）更新位置，而采用式（12）位置更新公式更新螢火蟲每一維度上的編碼。

步驟6 根據式（8）更新決策半徑。

步驟7 計算螢火蟲新的熒光素值，并與公告板標記的值相比，若比該值大，則更新公告板的值。

步驟8 當達到最大迭代次數或最優目標時，終止算法，否則轉至步驟4。

2.2.5 算法時間復雜度分析

假設在基于工作者評價得分的改進的離散型螢火蟲群優化（IDGSOBWES）算法中，步驟1 中最大迭代次數值為iter_max，螢火蟲的種群規模為N，每只螢火蟲（m維，從n個空閑工作者中選出m個來完成任務）表示一種任務分配組合。在每一次迭代中，算法時間復雜度如下：

步驟2 中為N個螢火蟲個體生成初始解，時間復雜度為O(N)；步驟3 中計算N個螢火蟲的熒光素值，時間復雜度為O(N)；步驟4 中計算距離，尋找鄰居集合，時間復雜度為O(N2*m)，若未找到要進行新的鄰域搜索，時間復雜度為O(N*m)；步驟5 中計算螢火蟲個體位置更新的時間復雜度為O(N*m)；步驟6 中螢火蟲決策半徑更新的時間復雜度為O(N)；步驟7中計算新的熒光素值，時間復雜度為O(N)，計算工作者得分，時間復雜度為O(m)，計算任務分配總得分，時間復雜度為O(N*m)；步驟8 中控制循環迭代次數，時間復雜度為O(1)。由于迭代次數為iter_max，那么算法的時間復雜度為O(N2*m*iter_max)。

2.2.6 算法空間復雜度分析

假設在IDGSOBWES 算法中，最大迭代次數值為iter_max，螢火蟲的種群規模為N，每只螢火蟲（m維）代表一種任務分配組合。在每一次迭代中，算法空間復雜度如下：

在步驟1和步驟2設置初始參數和生成初始解時，空間復雜度為O(N*m)；步驟3 中要存儲每個螢火蟲的熒光素值，空間復雜度為O(N)；步驟4 中計算距離，尋找鄰居集合，空間復雜度為O(N*m)；步驟5 中計算螢火蟲個體位置更新的空間復雜度為O(N*m)；步驟6 中螢火蟲決策半徑更新的空間復雜度為O(N)；步驟7 中要存儲熒光素值和總得分，空間復雜度為O(N)。由于迭代次數為iter_max，那么算法的空間復雜度為O(N*m*iter_max)。

3 實驗及結果分析

本文實驗部分主要分為兩部分：第一部分在模擬數據上進行測試，第二部分對經過處理的真實數據進行測試，驗證算法的有效性。

3.1 實驗設置

實驗環境：本文使用Matlab R2016a 軟件編寫代碼并繪圖，代碼編譯運行所使用的計算機參數：操作系統為64 位Windows10、處理器為Intel Core i5-8400 CPU（2.8 GHz），運行內存為8.0 GB。根據Krishnanand 等［23］和倪志偉等［24］的研究，算法參數值設置如表4所示.

算法中參數熒光素消失率、更新率以及決策半徑更新率依據文獻［23］和文獻［24］中的實驗研究結果設置，參數鄰域閾值、決策半徑、感知半徑、種群規模、迭代次數則是依據3.2.1 節中的3）參數對算法性能影響的實驗所設置，參數工作者的初始速度以及兩個統一量綱系數的設置是為了不讓結果出現負數，加權系數的設置是依據工作者服務質量和工作者的旅行成本的重要性。

表4 設置實驗初始化參數Tab.4 Setting of initialization parameters of experiment

3.2 結果分析

3.2.1 在模擬數據集上測試

模擬數據集設置如下：任務的地理位置信息，在［0，100］范圍上隨機生成兩組位置數據；任務開始最多所需時間、工作者的地理位置信息和工作者當前評價得分，采用上述同樣方法隨機生成。假設某時空環境下共有10 個空間眾包任務（這些任務的時間信息都處于當前時空環境下）和15 個空間眾包工作者（此時的工作者的狀態恰好都是空閑），隨機生成兩組空間任務位置數據和兩組工作者位置數據，將任務和工作者的地理位置數據組合，形成兩組位置信息數據集，同時隨機生成一份工作者當前評價得分表，一份任務最遲開始所需時間表。

1）本文任務分配策略與其他策略的對比。

對上述兩組空間任務和工作者模擬位置數據分別進行獨立重復的20次實驗，對比貪婪策略［9］、隨機匹配策略及本文所提策略所得到的任務分配總得分。

圖1 是分別對兩組模擬數據進行20 次實驗所得到的結果。

由圖1 可以觀察到，盡管兩組模擬數據集位置信息不同，但對實驗結果影響不大，由圖1 兩組實驗圖像可知，本文所提出的任務分配策略比隨機匹配策略對任務分配總得分的提高具有明顯效果，且結果比較穩定，而隨機匹配策略得到的任務分配總得分結果則比較跳躍，有高有低，比較分散。對比本來效果就比較好的貪婪策略來講，本文所提策略在大多數實驗次數上表現較優。實驗表明本文所提出的任務分配策略和IDGSOBWES算法完全可以用于處理空間眾包任務分配問題，具有一定的穩定性和有效性。

圖1 兩組不同模擬數據集上三種不同策略對比Fig.1 Comparison of three different strategies on two different simulated datasets

2）本文算法與其他算法的對比。

對上述第一組數據，進行20 次獨立重復實驗，將本文算法IDGSOBWES 與文獻［17］中離散型螢火蟲群優化（DGSO）算法、文獻［18］中離散型螢火蟲算法（Discrete Firefly Algorithm，DFA）以及PSO、GA 進行對比實驗，分別計算幾種算法根據目標函數迭代500 次每一次所得到的平均值，幾種算法之間的比較可通過圖2展現。

圖2 幾種算法計算得到的總得分對比結果Fig.2 Comparison results of total scores calculated by several algorithms

從圖2 可以觀察到，隨著迭代次數的增加，五種算法中任務分配總得分均慢慢穩定下來，但本文所提出的IDGSOBWES算法相較其他幾種算法的收斂速度明顯更快，達到穩定值的速度更快，且任務分配總得分平均值更高，即任務分配質量更高。

再設置幾組不同模擬數據集下的實驗，模擬數據集的產生方法依然同上述方法相同，設置的模擬數據規模大小分別是：在同一個時空環境下，空間任務20 單，空閑工作者25 個；空間任務50單，工作者60個；空間任務100單，工作者120個；再結合上一組空間任務10 單，空閑工作者15 個的實驗，得到各算法間的對比結果如表5所示。

根據上述實驗結果分析，在一定規模的模擬數據集上，本文算法計算得到的任務分配總得分總是優于其他四種算法，如在（50，60）的空間任務和工作者匹配結果中，本文算法比DGSO 算法得到的任務分配總得分提高了3.8%，比DFA 提高了20.2%，比PSO 算法提高了4.7%，比GA 提高了5.6%；隨著維度的變大，實驗效果有減弱趨勢，表明本文算法在一定的維度上對解決空間眾包任務分配問題具有較優效果。

表5 各算法在不同規模數據集上的實驗對比結果Tab.5 Experimental comparison results of different algorithms on datasets with different scales

3）參數對算法性能的影響。

用第一組數據進行實驗，對參數感知半徑、決策半徑、鄰域閾值、種群規模以及迭代次數分別進行分析，實驗結果如圖3所示。

圖3 不同參數對實驗中任務分配總得分的影響Fig.3 Effect of different parameters on total score of task assignment in experiment

對各參數的分析可知：在圖3（a）表明，當感知半徑取值12 時，總得分效果最優，因而在規定范圍內感知半徑取12；圖3（b）表明，決策半徑為12 時，總得分達到最高，因而在規定范圍內決策半徑取12。圖3（c）表明，總得分先隨鄰域閾值波動，當閾值達到5 時，總得分開始下降，因而在規定范圍內，鄰域閾值取5。圖3（d）表明，當種群規模到100 左右時，總得分趨于穩定，因而種群規模取100。圖3（e）表明，總得分隨著迭代次數一起增加，當迭代次數增加到100 左右時，總得分基本不再增加，可知當迭代次數達到100 之后算法性能基本穩定，故迭代次數取100。

3.2.2 在真實位置數據集上測試

真實數據是由 http：//www.dataju.cn/Dataju/web/datasetInstanceDetail/364 地址上獲取的紐約出租車管理委員會官方的乘車數據。對該數據集進行處理，去除其中無效值、缺失值，取出實驗所需的500 條空間眾包任務的位置數據（一個時間戳內取500 條任務數據規模足夠），并通過數據歸一化處理，將空間任務的位置坐標映射到［0，100］區間，得到用于實驗的真實空間任務位置數據，空間眾包工作者的位置信息、當前評價得分數據以及任務最遲開始所需時間數據依然采用隨機方法生成。分別采用3.2.1 節中的2）中提到的幾種算法，解決如下幾種情況的任務分配：在一個時空環境下，發布空間任務50 單，存在空閑工作者60 個；空間任務100 單，工作者120個；空間任務200單，工作者250個；空間任務500單，工作者600 個。進行任務分配后，任務分配質量總得分結果如表6所示。

表6 幾種算法在不同空間任務和空間眾包工作者數目時的總得分對比Tab.6 Comparison of the total scores of several algorithms with different number of spatial tasks and spatial crowdsourcing workers

根據上述實驗結果可知，無論考慮任務分配質量總得分的均值還是最大值，在大部分情況下，本文提出的IDGSOBWES算法的結果都比其他四種算法高一些，也存在個別不如其他算法的地方，這表明本文算法具有一定程度的穩定性；當實驗數據的維度越來越高，算法的效果會有一定程度的下降；然而直到數據達到500 維，IDGSOBWES 算法求得的任務分配質量總得分還是比DGSO 算法高約6%，故本文所提出的算法對解決空間眾包任務分配中問題具有較優效果。

3.3 實驗總結

依據上述實驗結果分析，發現本文所提出的IDGSOBWES算法在解決考慮空間眾包工作者服務質量的空間眾包任務分配問題時比貪婪算法和隨機匹配算法具有更高有效性，有更大的概率獲得更高任務分配總得分，同時在中低維度上表現得比DGSO 和DFA 算法收斂更快，尋優能力更強，同時也比PSO和GA的結果更優，表明本文所提出的算法用于解決空間眾包任務分配問題既具備可行性又具有有效性。

4 結語

本文重點研究空間眾包任務分配，將空間眾包工作者的服務質量評價得分要素考慮到其中，并建立得分更新機制，實現在一定時空環境下更高質量的空間眾包任務分配；同時，改進了離散型螢火蟲群優化算法，既加快了其收斂速度，也提高了其尋優能力。通過設定的幾組實驗，既表明本文提出的考慮工作者服務質量的任務分配模型可以提高任務分配總體質量得分，又驗證了IDGSOBWES 算法具有較好的收斂性和尋優能力。接下來考慮從任務請求者和工作者兩個角度出發繼續研究空間眾包任務分配問題，并將隱私保護相關內容加入其中。