* ，3

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

表2 星級(jí)評(píng)價(jià)與評(píng)價(jià)得分對(duì)應(yīng)表Tab.2 Correspondence table of star rating and evaluation score

1.3 空間眾包工作者評(píng)價(jià)得分更新機(jī)制

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

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

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

表3 工作者評(píng)價(jià)得分更新Tab.3 Update of workers’evaluation score

1.4 加入工作者服務(wù)質(zhì)量評(píng)價(jià)得分機(jī)制的任務(wù)分配模型

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

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

2 GSO算法及其改進(jìn)

2.1 基本GSO算法

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

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

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

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

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

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

2.2 基于工作者評(píng)價(jià)得分的改進(jìn)的離散型GSO算法

2.2.1 算法的離散化

通常GSO 算法被用于處理連續(xù)空間的問題，當(dāng)引入此算法來處理空間眾包任務(wù)分配問題時(shí)，需要進(jìn)行離散化，對(duì)算法的解及初始化進(jìn)行離散化處理，并采用適當(dāng)?shù)恼麛?shù)編碼機(jī)制和編碼更新規(guī)則，改進(jìn)算法的位置更新策略和鄰域搜索策略，從而讓該算法適用于處理本文問題，使其具有更好的收斂速度和尋優(yōu)能力。

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

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

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

2.2.3 算法的離散及改進(jìn)

1）算法與任務(wù)分配問題的對(duì)應(yīng)及初始化。

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

2）算法中距離計(jì)算公式。

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

其中1 ≤k≤m。

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

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

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

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

對(duì)螢火蟲i，隨機(jī)從它的m維中挑選兩個(gè)維度，第p維和第q維，將其對(duì)應(yīng)維度上的編碼交換。例如，對(duì)螢火蟲i，xi(t)=[5，3，9，12，7，1，8，15，4，6]，隨機(jī)產(chǎn)生兩維（3，7），即p=3，q=7，兩維度上對(duì)應(yīng)的數(shù)字分別為9 和8，將兩個(gè)維度上的數(shù)字9和8 位置交換，則執(zhí)行交換變化后螢火蟲i的編碼變?yōu)閤i(t)=[5，3，8，12，7，1，9，15，4，6]。

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

對(duì)螢火蟲i，隨機(jī)從它的m維中挑選兩個(gè)維度，第p維和第q維，將第q維上的編碼移動(dòng)到第p維上，第p維及之后維度上的編碼往后順延。例如，對(duì)螢火蟲i，xi(t)=[5，3，9，12，7，1，8，15，4，6]，隨機(jī)產(chǎn)生兩維（3，7），即p=3，q=7，兩維度上對(duì)應(yīng)的數(shù)字分別為9 和8，將第7 維上的數(shù)字8 移動(dòng)到第3維上，第3維上的數(shù)字9移動(dòng)到第4維上，后面維度上的數(shù)字往后順延，則執(zhí)行插入變化后螢火蟲i的編碼變?yōu)閤i(t)=[5，3，8，9，12，7，1，15，4，6]。

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

對(duì)螢火蟲i，隨機(jī)從它的m維中挑選兩個(gè)維度，第p維和第q維，將第p～q維上的編碼執(zhí)行反轉(zhuǎn)。例如，對(duì)螢火蟲i，xi(t)=[5，3，9，12，7，1，8，15，4，6]，隨機(jī)產(chǎn)生兩維（3，7），即p=3，q=7，兩維度上對(duì)應(yīng)的數(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í)行步驟

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

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

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

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

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

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

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

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

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

2.2.5 算法時(shí)間復(fù)雜度分析

假設(shè)在基于工作者評(píng)價(jià)得分的改進(jìn)的離散型螢火蟲群優(yōu)化（IDGSOBWES）算法中，步驟1 中最大迭代次數(shù)值為iter_max，螢火蟲的種群規(guī)模為N，每只螢火蟲（m維，從n個(gè)空閑工作者中選出m個(gè)來完成任務(wù)）表示一種任務(wù)分配組合。在每一次迭代中，算法時(shí)間復(fù)雜度如下：

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

2.2.6 算法空間復(fù)雜度分析

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

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

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

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

3.1 實(shí)驗(yàn)設(shè)置

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

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

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

3.2 結(jié)果分析

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

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

1）本文任務(wù)分配策略與其他策略的對(duì)比。

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

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

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

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

2）本文算法與其他算法的對(duì)比。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 實(shí)驗(yàn)總結(jié)

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

4 結(jié)語

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