* ，3

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

0 引言

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

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

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

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

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

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

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

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

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

1.2 工作者的服務質(zhì)量星級評價轉(zhuǎn)化為數(shù)字化評價得分

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

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

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

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

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

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

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

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

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

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

2 GSO算法及其改進

2.1 基本GSO算法

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

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

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

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

4）采用輪盤賭的方式判斷螢火蟲i接下來的移動方向：j=max(pi)表示其根據(jù)鄰域確定的移動方向，其中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 算法被用于處理連續(xù)空間的問題，當引入此算法來處理空間眾包任務分配問題時，需要進行離散化，對算法的解及初始化進行離散化處理，并采用適當?shù)恼麛?shù)編碼機制和編碼更新規(guī)則，改進算法的位置更新策略和鄰域搜索策略，從而讓該算法適用于處理本文問題，使其具有更好的收斂速度和尋優(yōu)能力。

2.2.2 算法的優(yōu)化目標

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

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

2.2.3 算法的離散及改進

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

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

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

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

其中1 ≤k≤m。

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

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

4）算法中鄰域搜索優(yōu)化策略。

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

對螢火蟲i，隨機從它的m維中挑選兩個維度，第p維和第q維，將其對應維度上的編碼交換。例如，對螢火蟲i，xi(t)=[5，3，9，12，7，1，8，15，4，6]，隨機產(chǎn)生兩維（3，7），即p=3，q=7，兩維度上對應的數(shù)字分別為9 和8，將兩個維度上的數(shù)字9和8 位置交換，則執(zhí)行交換變化后螢火蟲i的編碼變?yōu)閤i(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]，隨機產(chǎn)生兩維（3，7），即p=3，q=7，兩維度上對應的數(shù)字分別為9 和8，將第7 維上的數(shù)字8 移動到第3維上，第3維上的數(shù)字9移動到第4維上，后面維度上的數(shù)字往后順延，則執(zhí)行插入變化后螢火蟲i的編碼變?yōu)閤i(t)=[5，3，8，9，12，7，1，15，4，6]。

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

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

2.2.4 算法的執(zhí)行步驟

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

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

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

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

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

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

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

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

步驟8 當達到最大迭代次數(shù)或最優(yōu)目標時，終止算法，否則轉(zhuǎn)至步驟4。

2.2.5 算法時間復雜度分析

假設(shè)在基于工作者評價得分的改進的離散型螢火蟲群優(yōu)化（IDGSOBWES）算法中，步驟1 中最大迭代次數(shù)值為iter_max，螢火蟲的種群規(guī)模為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 中控制循環(huán)迭代次數(shù)，時間復雜度為O(1)。由于迭代次數(shù)為iter_max，那么算法的時間復雜度為O(N2*m*iter_max)。

2.2.6 算法空間復雜度分析

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

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

3 實驗及結(jié)果分析

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

3.1 實驗設(shè)置

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

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

表4 設(shè)置實驗初始化參數(shù)Tab.4 Setting of initialization parameters of experiment

3.2 結(jié)果分析

3.2.1 在模擬數(shù)據(jù)集上測試

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

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

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

圖1 是分別對兩組模擬數(shù)據(jù)進行20 次實驗所得到的結(jié)果。

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

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

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

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

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

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

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

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

表5 各算法在不同規(guī)模數(shù)據(jù)集上的實驗對比結(jié)果Tab.5 Experimental comparison results of different algorithms on datasets with different scales

3）參數(shù)對算法性能的影響。

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

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

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

3.2.2 在真實位置數(shù)據(jù)集上測試

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

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

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

3.3 實驗總結(jié)

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

4 結(jié)語

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