基于遺傳算法的時空眾包3 類對象任務(wù)分配

周靜，董紅斌，郭田雨

哈爾濱工程大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001

眾包提供了一種匯集群體智慧求解問題的新思路，成為當(dāng)前研究的熱點問題[1]。近年來，隨著移動互聯(lián)網(wǎng)技術(shù)和線上到線下（online to offline，O2O）商業(yè)模式的興起，時空眾包逐步走進(jìn)人們的視野。與傳統(tǒng)眾包如在線問答系統(tǒng)不同，時空眾包需要人們實際在線下進(jìn)行活動，因此受到了時空因素的約束。

目前針對工人、用戶2 種角色的研究已經(jīng)頗多[2-9]，然而，新的眾包模式也帶來了全新的挑戰(zhàn)，平臺需要將工人、用戶、工作地點這3 類對象進(jìn)行組合匹配[10-13]。對于2 類對象的匹配問題，大多是微任務(wù)，即任務(wù)在短時間(幾分鐘)內(nèi)即可完成，如查看超市商品價格（Gigwalk, http://www.gigwalk.com）、收集停車場信息（Waze, http://www.waze.com）等。而對于3 類對象的匹配問題，目前涉及的應(yīng)用主要有趣運動（ InterestingSport,http://www.quyundong.com）和南瓜車（Nanguache,http://www.nanguache.com）2 類。趣運動是匹配教練進(jìn)行教學(xué)或者匹配球員打球；在南瓜車中，理發(fā)師為顧客定制理發(fā)服務(wù)。這2 種任務(wù)完成時間一般至少以小時為單位，但是現(xiàn)有研究少有考慮到任務(wù)時長方面的問題。許多研究在一開始就假定了工人的最大匹配任務(wù)數(shù)，然后一次性完成匹配，工人依次完成這些任務(wù)，這對于微任務(wù)是可行的，但是對于長時間任務(wù)則不符合現(xiàn)實需求。如果一次性為工人分配多個任務(wù)，則后面的任務(wù)需要等待很久。

因此，本文假定了任務(wù)的工作時間st，它由任務(wù)指定，但是在工作過程中可由工人調(diào)節(jié)。對于趣運動，st是固定的，多為固定授課時長或者預(yù)約2 h 場地打球；而對于南瓜車，st無法立刻確定，可以首先生成最長st，在用戶到達(dá)之后，工人再根據(jù)實際用戶講述的需求和自身經(jīng)驗預(yù)估st，這在實際應(yīng)用中比較容易實現(xiàn)。

本文考慮到了工作時長對任務(wù)分配的影響，提出了在線3 類對象動態(tài)匹配(online dynamic assginment for three types of objects，ODAT)問題，并提出了基于混合遺傳算法（genetic algorithm,GA）的延遲匹配算法和延遲閾值策略，旨在在滿足多種約束的前提下平衡平臺的利益和用戶的滿意度。

1 相關(guān)工作

1.1 時空眾包

眾包環(huán)境下在線匹配問題主要結(jié)合實際場景研究不同約束下的任務(wù)分配問題。在線二維匹配場景是工人前往任務(wù)地點完成工作。Kazemi 等[2]最早研究最大化任務(wù)匹配數(shù)問題。Tong 等[3]利用離線預(yù)測進(jìn)行在線分配來最大化匹配數(shù)。Zheng等[4]考慮到了優(yōu)化雙邊利益，不是單單優(yōu)化平臺利益，還應(yīng)考慮工人偏好問題。Tong 等[5-6]研究雙邊在線微任務(wù)二維分配問題，將貪心算法和匈牙利算法結(jié)合，提出了兩階段模型使效用最大化。徐天乘等[7]利用深度學(xué)習(xí)方法設(shè)計了基于位置預(yù)測的任務(wù)分配方法。另外還存在一些復(fù)雜任務(wù)，如修理房屋、災(zāi)難恢復(fù)等，一個任務(wù)需要多個工人才能完成。Mizuhara 等[8]提出協(xié)同任務(wù)分配問題，需要所有工人都到達(dá)后才能開始工作。而Liu 等[9]提出了具有依賴性約束的多階段匹配問題，工人需要依次完成任務(wù)。

在線三維匹配場景是工人和用戶同時前往第三方地點，借助工作場所的工具來完成任務(wù)。Song 等[10]提出了眾包環(huán)境下的3 類對象匹配問題。Li 等[11]和李博揚(yáng)等[12]針對三維穩(wěn)定匹配問題提出了求解算法。Li 等[13]確保工人和用戶在給定的寬容時間內(nèi)到達(dá)匹配的工作場所。

另外，任務(wù)規(guī)劃問題也是時空眾包研究的一個重要領(lǐng)域。潘慶先等[14]提出了一種自適應(yīng)閾值的禁忌搜索算法，能減少任務(wù)分配中的移動成本。Deng 等[15]旨在為工人找到最大化執(zhí)行任務(wù)數(shù)量的工作時間表。Tao 等[16]研究在用戶能及時到達(dá)目的地的前提下完成眾包任務(wù)并使效用最大化。Wu 等[17]基于遺傳算法提出一種尺度自適應(yīng)適應(yīng)度評估方法，并解決計算成本較高的眾包配送調(diào)度問題。

1.2 遺傳算法

遺傳算法[18]是借鑒大自然進(jìn)化過程而提出的一種啟發(fā)式搜索方法。其基本思想是采用優(yōu)勝劣汰、適者生存的自然法則選擇個體，通過交叉、變異等方式來產(chǎn)生新一代的種群，逐代進(jìn)化，直到滿足終止條件。

GA 最核心的問題就是編碼。目前傳統(tǒng)編碼方法包括二進(jìn)制編碼、排列編碼、值編碼和樹形編碼等。其中樹形編碼中每個染色體是由多個對象組成的樹，比如程序語言中的函數(shù)或者命令[19]。這些編碼的相似點是每個基因都只涉及一個對象，且前后基因具有關(guān)聯(lián)，因此易于實現(xiàn)。

目前也出現(xiàn)了許多GA 的變體，包括針對編碼形式、交叉變異算子的改進(jìn)等[20]。GA 還可以被應(yīng)用到多目標(biāo)優(yōu)化問題中，如帶精英策略的快速非支配排序遺傳算法(nondominated sorting genetic algorithm II，NSGA-II)[21]。GA 可以很容易地與其他優(yōu)化算法結(jié)合，達(dá)到更好的性能，如模擬退火算法、貪心算法等。

由于GA 的并行性、可擴(kuò)展性等特點，被廣泛應(yīng)用于組合優(yōu)化中的非確定性多項式(nondeterministic polynomial，NP)難問題，如運籌管理、多媒體和無線網(wǎng)絡(luò)等領(lǐng)域。

2 問題描述

2.1 基本定義

定義1眾包任務(wù)。眾包任務(wù)定義為t=＜lt,rt,ut,bt,et,st＞，表示任務(wù)的位置為歐式空間中的一個點lt，其移動范圍為以lt為圓心、以rt為半徑的區(qū)域，報酬為ut，出現(xiàn)時間為bt，截止時間為et，工作時長為st。

定義2眾包工人。眾包工人定義為w=＜lw,rw,cw,qw,bw＞，表示工人的位置為lw，移動范圍是以lw為圓心、以rw為半徑的區(qū)域，容量為cw，服務(wù)質(zhì)量qw∈(0,1]，出現(xiàn)時間為bw。

定義3眾包工作地點。眾包工作地點定義為p=＜lp,bp,cp＞，表示工作地點的位置為歐式空間中的一個點lp，出現(xiàn)時間為bp，容量為cp。

為了綜合平臺的利益和用戶的滿意度，參照文獻(xiàn)[16]擴(kuò)展到3 類對象匹配問題，定義眾包工人在眾包地點完成眾包任務(wù)的效用。

定義4效用。眾包工人w在眾包地點p完成眾包任務(wù)t的效用定義式為

即任務(wù)回報ut與工人服務(wù)質(zhì)量qw的乘積除以從匹配開始到正式開始工作需要的趕路時間，其中dis表示2 點之間的距離，max為取最大值。默認(rèn)速度為1，其中“+1”用于避免零分母。

定義5ODAT 問題。給定任務(wù)集T、工人集W、地點集P和效用函數(shù)U(.,.,.,)。求解目標(biāo)是找到T,W,P的任務(wù)分配M?T×W×P，并使總效用最大化max(M)=∑t∈T,w∈W,p∈P U(t,w,p)且滿足以下約束：

1)截止時間約束：任務(wù)需要在任務(wù)截止時間之前被分配。

2)空間約束：任務(wù)分配＜t,w,p＞需要滿足p在以lt為中心、以rt為半徑的范圍內(nèi)和以lw為中心、以rw為半徑的范圍內(nèi)。

3)容量約束：對于任務(wù)，每個任務(wù)t在M中最多出現(xiàn)一次；對于工人w，每次只能參與一種匹配，工人完成任務(wù)后才可再次參與匹配，總共最多出現(xiàn)cw次；對于地點p，其容量可認(rèn)為是多個工位，每次匹配只占用一個工位，每個地點正在工作的工位數(shù)不能超過cp，工人完成任務(wù)后該工位可被釋放，可再次參與匹配。

4)另外，Li 等[13]考慮到了工人和任務(wù)應(yīng)該同時到達(dá)的問題。本文由于設(shè)置了預(yù)估工作時長，可以直接保證工人和任務(wù)互相等待的時間Twait不超過給定的時間。即

式中 abs表示取絕對值。本文默認(rèn)未設(shè)置等待時間，這是一種提高用戶滿意度的方式，在實際應(yīng)用中可自行設(shè)置。

2.2 問題復(fù)雜性

根據(jù)文獻(xiàn)[10]易知空間眾包環(huán)境下的3 類對象在線任務(wù)匹配問題是NP 難問題，只能求得近似解。

3 延遲貪心算法

貪心算法每次一有新對象到來，就立即為其分配當(dāng)前最優(yōu)匹配。眾所周知，在眾包在線分配問題中，對象到達(dá)順序的不同會直接影響匹配的效用。3 類對象在線分配問題在現(xiàn)實應(yīng)用中對響應(yīng)時間的要求不是很高，因此可以通過延長一定的任務(wù)匹配時間，等待盡量多的地點和工人加入到在線平臺后再進(jìn)行匹配，這樣可以獲得更好的效用。文獻(xiàn)[12]提出了一種延遲匹配算法，僅僅當(dāng)任務(wù)達(dá)到最長等待時間后才對任務(wù)進(jìn)行穩(wěn)定匹配，與本文場景不同。本文將其擴(kuò)展到ODAT 問題中，延遲貪心算法的偽代碼如算法1 所示。

算法1延遲貪心(delay greedy, DG)算法

輸入：任務(wù)集T，工人集W，工作地點集P，效用函數(shù)U(.,.,.,)

輸出：全局任務(wù)匹配結(jié)果集M

For each 新出現(xiàn)的眾包對象vdo

更新任務(wù)完成情況

初始化未匹配的在線任務(wù)集、工人集、地點集

Mwait← {滿足所有約束的任務(wù)匹配}

將Mwait按照效用降序排序，依次加入到M

end

returnM

由于本文將工人動態(tài)分配給任務(wù)，所以每次任務(wù)完成后，需要釋放工人和地點，使他們能夠參與到下次的匹配。在每次新對象到來后先檢查并更新任務(wù)完成情況，實際應(yīng)用中可設(shè)置倒計時或者進(jìn)行手動釋放。

在大多數(shù)算法[5-6,10]中，會將多個容量的對象分解成多個單容量對象，但這樣會增加算法量級。雖然地點有容量，但是在進(jìn)行匹配時，只需將其作為一個對象，最后將所有可能的匹配按照效用排序，并依次安排到空的工位上，實驗表明這樣能大幅降低時間復(fù)雜度。注意每次加入匹配前需要再一次判斷是否滿足約束，因為候選匹配集中可能有一個任務(wù)和多個地點工人匹配的情況，每次一旦加入最大效用的一組匹配后，已經(jīng)匹配的對象就不能再參與匹配了。排序的作用是防止小效用的任務(wù)占用了大效用的任務(wù)可匹配的工人或者地點。

算法復(fù)雜度：對于每個新出現(xiàn)的眾包任務(wù)t∈T、眾包工人w∈W和眾包工作地點p∈P，時間復(fù)雜度是O(|T||W||P|)。算法需要記錄所有可行匹配和3類對象的信息，空間復(fù)雜度是O(min(|T|,|W|,|P|×cp))。

4 改進(jìn)算法

延遲貪心匹配算法可認(rèn)為是在線3 類對象匹配中的局部最優(yōu)算法。但是其復(fù)雜度過高，無法在短時間內(nèi)得出結(jié)果，這違背了眾包在線分配的實時性要求。因此本文提出了基于混合遺傳算法的延遲匹配算法，可以大大減少復(fù)雜度，同時還提出了延遲閾值策略來增加效用。

4.1 混合遺傳算法

4.1.1 編碼與解碼

本文將解直接設(shè)為1 個個體，每個染色體是1 組三維匹配，每對匹配是1 個基因。由于1 個基因又由3 個對象組合，每次生成新解和變化解都需要考慮到3 個對象的變化。最簡單的方式是每次在未匹配的任務(wù)、工人、地點中隨機(jī)選出3 個作為一對匹配，但是顯然由于存在范圍約束，這會導(dǎo)致大量無用解的產(chǎn)生，需要很多次迭代才可能成功產(chǎn)生一個可行匹配，收斂速度極慢。

通過對約束的分析可以發(fā)現(xiàn)，約束只存在任務(wù)與地點、工人與地點之間，任務(wù)與工人之間是無約束的，如果需要設(shè)置等待時間，則這個約束可以在產(chǎn)生新匹配的時候進(jìn)行判斷，因為它需要任務(wù)和工人的參與。因此本文將3 類對象構(gòu)造為1 個任務(wù)森林結(jié)構(gòu)，可以將有約束問題轉(zhuǎn)化為無約束問題，能大概率保證解的成功產(chǎn)生。如圖1所示，其中每個任務(wù)作為1 個樹根，樹的左子樹是滿足約束的地點，地點的右子樹是滿足約束的工人。樹根的順序以及左子樹和右子樹上的結(jié)點順序直接按照到達(dá)順序排列即可。同時，為了進(jìn)一步優(yōu)化后續(xù)搜索的速度，可對任務(wù)森林進(jìn)行剪枝，將地點左子樹為空的任務(wù)結(jié)點刪除，如將圖1 的26 號結(jié)點刪除。任務(wù)森林類似樹形編碼方式，但是任務(wù)森林一旦確定，不可改變，因此無法通過交換部分子樹等方法實現(xiàn)交叉操作。通過構(gòu)造任務(wù)森林結(jié)構(gòu)可以不斷縮小可行解范圍，這樣任務(wù)森林的深度和廣度都不會很大，可以提高隨機(jī)生成初始解的成功概率和搜索速度。

圖1 任務(wù)森林結(jié)構(gòu)

本文使用隨機(jī)方法產(chǎn)生新的基因，但在初始化和搜索過程中會導(dǎo)致優(yōu)秀基因被重復(fù)挑選，相同基因重復(fù)會導(dǎo)致種群多樣性下降。如果每次都與種群中的所有個體比較，判斷是否產(chǎn)生重復(fù)匹配，每次需要比較3 個對象會耗費大量時間。為了保證每個個體中基因的無重復(fù)性，本文為每個個體設(shè)置3 個全局標(biāo)記矩陣，可以保證個體中沒有重復(fù)匹配。其中任務(wù)和工人每次只能匹配1 次，標(biāo)記矩陣初始設(shè)為-1，匹配成功設(shè)為1；地點矩陣具有容量屬性，初始化為未工作的工位數(shù)量，每次匹配成功則減1。

4.1.2 初始解的生成

由于是在線匹配問題，因此不固定種群規(guī)模，而是設(shè)置每輪最大種群規(guī)模數(shù)為未匹配任務(wù)的個數(shù)。借鑒蒙特卡羅樹搜索[22]中模擬過程的思想，將每個未匹配任務(wù)作為起始節(jié)點，交替隨機(jī)擴(kuò)展任務(wù)和地點節(jié)點，直到?jīng)]有節(jié)點可擴(kuò)展。若地點結(jié)點上存在右子樹，通過局部最優(yōu)算子確定工人，此時確定一個匹配；若地點節(jié)點無可匹配工人，則更換地點節(jié)點重新擴(kuò)展；若連續(xù)Smax次適應(yīng)度不變，則停止模擬。

以圖1 中的任務(wù)森林為例，當(dāng)前有4 個未匹配任務(wù)，所以需要模擬4 次。從任務(wù)22 號出發(fā)，當(dāng)前有2 個地點可擴(kuò)展，隨機(jī)選擇一個4 號地點，并選擇最大效用的工人，確定一次匹配。接下來擴(kuò)展任務(wù)節(jié)點，當(dāng)前有3 個任務(wù)可擴(kuò)展，隨機(jī)選擇18 號任務(wù)，它有1 個8 號地點可擴(kuò)展，以此類推直到22 號任務(wù)結(jié)點模擬結(jié)束。部分模擬過程如圖2 所示。

圖2 模擬過程

通過隨機(jī)模擬生成初始解，可以給每個未匹配任務(wù)同等優(yōu)先選擇地點的權(quán)力，從而使初始解的多樣性最大化。

4.1.3 遺傳算子

使用局部最優(yōu)算子、雙重變異算子和隨機(jī)部分重啟機(jī)制逐代進(jìn)化，同時融合貪心算法，只有搜索到比當(dāng)前適應(yīng)度更大的匹配時才變異基因。這種方式可以保證種群朝最優(yōu)方向進(jìn)化，加快收斂速度。

局部最優(yōu)算子：確定好地點節(jié)點之后，遍歷其右子樹，找到當(dāng)前未匹配且適應(yīng)度最大的工人。

p 變異算子：在每個任務(wù)樹的左子樹上進(jìn)行隨機(jī)搜索其他地點節(jié)點。

t 變異算子：在任務(wù)森林中隨機(jī)搜索，尋找新的任務(wù)節(jié)點。

隨機(jī)部分重啟機(jī)制：保留大于種群平均適應(yīng)度的個體，具體如圖3 所示。對于小于種群平均適應(yīng)度的個體，在染色體上隨機(jī)設(shè)置2 個重置點，將重置點中間的匹配進(jìn)行釋放，然后重新隨機(jī)生成新的匹配，該算子有助于跳出局部最優(yōu)解。

圖3 隨機(jī)部分初始機(jī)制

4.1.4 算法偽代碼

設(shè)最大迭代次數(shù)Emax，同時若連續(xù)Tmax次種群最大適應(yīng)度不變，則提前停止迭代。使用效用函數(shù)作為適應(yīng)度函數(shù)，目標(biāo)是找到適應(yīng)度最高的種群。混合遺傳算法的偽代碼如算法2 所示。

算法2混合遺傳算法

輸入：任務(wù)集T，工人集W，工作地點集P，效用函數(shù)U(.,.,.,)

輸出：全局任務(wù)匹配結(jié)果集M

For each 新出現(xiàn)的眾包對象vdo

更新任務(wù)完成情況

初始化未匹配的在線任務(wù)集、工人集、地點集；初始化任務(wù)森林；初始化標(biāo)記矩陣

生成初始解

fori=0:Emaxdo

p 變異

t 變異

隨機(jī)部分重啟機(jī)制

若連續(xù)Tmax次種群最大適應(yīng)度不變，則停止迭代

end

選出適應(yīng)度最大的個體，依次取出每個基因，加入到M中

end

returnM

4.2 延遲閾值策略

現(xiàn)有研究對于在線3 類對象匹配問題一般使用閾值策略來增加效用，如固定閾值(fixed)、隨機(jī)閾值(random)[10]、自適應(yīng)隨機(jī)閾值(adaptive)[10]等。其中自適應(yīng)隨機(jī)閾值效果最好，固定閾值最差。本文針對固定閾值策略進(jìn)行改進(jìn)，提出一種延遲閾值策略(delay fixed, DeFixed)，主要思想是保留雖然適應(yīng)度未達(dá)到閾值但是任務(wù)已經(jīng)達(dá)到最長延遲時間的匹配。延遲閾值策略的偽代碼如算法3 所示。

算法3延遲閾值策略

輸入：任務(wù)集T，工人集W，工作地點集P，效用函數(shù)U(.,.,.,)

輸出：全局任務(wù)匹配結(jié)果集M

for each 新出現(xiàn)的眾包對象vdo

使用遺傳算法或者貪心算法找到所有可行的任務(wù)匹配Mwait

for each ＜t,w,p＞minMwaitdo

if m.t.tb+td＜tnowthen

ifUm＜qthen

continue

else

將m加入候選集C

else

將m加入候選集C

將C按照效用降序排序，依次加入到M

end

end

returnM

如果在當(dāng)前時間tnow時，任務(wù)t的開始時間tb加上延時時間td小于當(dāng)前時間tnow，而且其形成的任務(wù)分配的效用沒有達(dá)到閾值θ，則丟棄此次匹配；如果已經(jīng)到達(dá)最長延時時間，且它依舊能形成一個任務(wù)分配，則忽略閾值，認(rèn)定此次匹配成功。這樣的做法能夠在前期最大程度上保留可能的高效用匹配，在后期保留低效用的匹配，解決了固定閾值任務(wù)分配數(shù)降低的缺點。同時，最后一刻任務(wù)t依然能夠形成滿足約束的任務(wù)匹配，某種程度上也說明匹配的工人和地點對象其實也可能長時間無法與其他的對象形成高匹配。雖然也存在匹配的是新到來的工人和地點，在未來可以和其他任務(wù)形成高匹配的可能性，但是保留低效用匹配，讓工人盡快開始服務(wù)比無限時等待未來可能的高效用匹配更具有現(xiàn)實意義。

固定閾值策略和延遲閾值策略都會最大程度上過濾掉小于閾值的匹配，這會讓在線等待匹配的對象數(shù)量大大增加，運行時間也隨之增長。

5 實驗分析

通過實驗在真實數(shù)據(jù)集和合成數(shù)據(jù)集上分別對算法的效用和效率進(jìn)行評估。

5.1 實驗設(shè)置

實驗環(huán)境：處理器為2.9 GHz AMD Ryzen 7 4800H with Radeon Graphics，內(nèi)存容量為2 GB，操作系統(tǒng)為CentOS Linux release 7.5.180 4 (Core)，編程語言為c++。

為驗證本文算法的有效性，從時空眾包平臺gMission[23]收集真實數(shù)據(jù)。由于缺少預(yù)估工作時間和工人容量，采用合成數(shù)據(jù)，3 類對象匹配多是理發(fā)和運動，設(shè)置工作時間默認(rèn)值為[30,120] min，工人容量默認(rèn)為5，符合實際情況。實驗數(shù)據(jù)的參數(shù)設(shè)置見表1，加粗?jǐn)?shù)值為默認(rèn)參數(shù)。

表1 實驗數(shù)據(jù)參數(shù)表

本文還通過一組合成數(shù)據(jù)集測試算法的可擴(kuò)展性。任務(wù)、工人和地點以10∶10∶1 的比例在[0，480] min 內(nèi)均勻出現(xiàn)在10 000×10 000 的網(wǎng)格中，位置以二維坐標(biāo)表示，對工人服務(wù)質(zhì)量和任務(wù)報酬采用2 種分布情況。合成數(shù)據(jù)集的詳細(xì)信息見表2。

表2 合成數(shù)據(jù)集

評價算法有以下7 種：

1）采用延遲閾值的DG 算法(DG-DeFixed)。

2）采用隨機(jī)閾值的DG 算法(DG-Random)。

3）采用自適應(yīng)閾值的DG 算法(DG-Adaptive)。

由于延遲匹配，將DG-Adaptive 算法中的權(quán)重更新公式改為

式中：ut,k是一輪匹配中使用隨機(jī)閾值算法以ek為閾值獲得的總效用和，Nt,k是一輪匹配中被分配任務(wù)的總數(shù)。

4）采用延遲閾值的GA 算法(GA-DeFixed)。

5）采用隨機(jī)閾值的GA 算法(GA-Random)。

6）采用自適應(yīng)閾值的GA 算法(GA-Adaptive)。

7）NetGA 為文獻(xiàn)[24]提出的一種改進(jìn)遺傳算法。作者使用了遺傳算法解決通信領(lǐng)域中的資源配置問題，主要在用戶、基站、子信道三者之間進(jìn)行分配。其中1 個基站或子信道可以和多個用戶匹配，但是1 個用戶只能和1 個基站、1 個子信道匹配。使用映射矩陣解決有效覆蓋范圍的約束，染色體設(shè)計為用戶與基站的匹配加上用戶與子信道的匹配。

5.2 實驗結(jié)果

5.2.1 對比NetGA 算法

由于使用閾值的匹配方式運行時間比沒有閾值的長，僅使用無閾值的DG 算法和GA 算法與NetGA 算法進(jìn)行對比實驗。NetGA 算法的參數(shù)同GA 算法一致。實驗結(jié)果如圖4 所示。

圖4 對比NetGA 算法

可以看出NetGA 算法在長時間運行情況下依然無法獲得很好的結(jié)果，分析原因如下：NetGA 算法[24]的應(yīng)用場景是超密集異構(gòu)網(wǎng)絡(luò)下的離線分配問題，基站和子信道都有多個容量，有效覆蓋范圍矩陣是稠密矩陣，即使對象數(shù)量少也能生成多個匹配，在本實驗中3 類對象數(shù)量都不超過50，所以可以使用該方法。而本文場景每次任務(wù)和工人每次只能匹配1 個地點，需要在線實時分配，數(shù)據(jù)規(guī)模大，有效覆蓋范圍矩陣是稀疏矩陣，在進(jìn)化過程中會產(chǎn)生大量失敗匹配和重復(fù)匹配，需要迭代多次才能搜索成功；因而NetGA 算法無法應(yīng)用到ODAT 問題中。

5.2.2 消融實驗

在這組實驗中，首先對比蒙特卡羅模擬初始化和隨機(jī)初始化(GA-RI)的實驗結(jié)果，然后驗證去除隨機(jī)部分重啟機(jī)制(GA-NoRestart)后的實驗結(jié)果，實驗結(jié)果如圖5 所示。算法的效用和匹配數(shù)如圖5(a)和圖5(b)所示，可見當(dāng)使用隨機(jī)生成初始解時效用小于使用模擬方法生成的初始解，這是因為隨機(jī)生成需要確定種群規(guī)模大小，而每次匹配時在線的對象數(shù)都是不確定的，同時隨機(jī)方法會導(dǎo)致部分優(yōu)秀解的丟失，而去除隨機(jī)部分重啟機(jī)制后效用會有所降低；運行時間和內(nèi)存占用如圖5(c)和圖5(d)所示，去除隨機(jī)部分重啟機(jī)制會降低運行時間，內(nèi)存占用都一樣。

圖5 消融實驗對比結(jié)果

5.2.3 改變閾值

在本組實驗中，對比延遲閾值策略和固定閾值策略在DG 算法和GA 算法這2 種匹配方式上的結(jié)果，其他參數(shù)使用表1 中的默認(rèn)值。改變閾值的實驗結(jié)果如圖6 所示。算法的效用和匹配數(shù)變化情況如圖6(a)和圖6(b)所示：顯然使用延遲閾值策略的算法效用隨閾值增大而增加，且能保持匹配任務(wù)數(shù)穩(wěn)定；而使用固定閾值策略的算法效用則會在達(dá)到峰值后迅速下降，匹配數(shù)也會隨之減少，DG 算法的效用略高于GA 算法。運行時間曲線如圖6(c)所示，DG 算法的運行時間高于GA 算法，同時延遲閾值策略的運行時間高于固定閾值策略。內(nèi)存占用變化曲線如圖6(d)所示：DG 算法的內(nèi)存占用明顯高于GA 算法，因為DG 算法需要存儲所有可行的匹配。

圖6 改變閾值實驗對比結(jié)果

由以上分析結(jié)果可以看出，延遲閾值策略在效用和匹配數(shù)上明顯優(yōu)于固定閾值策略。雖然運行時間較長，但是設(shè)置合適的閾值可以保證運行時長在可接受范圍內(nèi)。

5.2.4 改變半徑

在本組實驗中，改變?nèi)蝿?wù)和工人的半徑，實驗結(jié)果如圖7 所示，其他參數(shù)使用表1 中的默認(rèn)值。算法的效用和匹配數(shù)如圖7(a)和圖7(b)所示，使用DeFixed 策略的算法效用和匹配數(shù)明顯高于另2 種策略算法，Adaptive 策略其次，Random 最低，DG 算法在同種策略上效用略大于GA 算法；運行時間如圖7(c)所示，所有算法的運行時間隨半徑增加而增大，因為可匹配的對象數(shù)量增多，DGDeFixed 算法的運行時間明顯高于其他算法，且DG 算法在同種策略上的運行時間也高于GA 算法。內(nèi)存占用如圖7(d)所示，DG 算法的內(nèi)存占用明顯高于GA 算法。

圖7 改變半徑實驗對比結(jié)果

5.2.5 改變工人容量

在這組實驗中，改變工人的容量，其他參數(shù)使用表1 中的默認(rèn)值。改變工人容量的實驗結(jié)果如圖8 所示。

圖8 改變工人容量實驗對比結(jié)果

算法的效用和匹配數(shù)如圖8(a)和圖8(b)所示，隨著工人容量的提升，所有算法的效用先逐漸增加然后不變，這是因為每次會選擇最優(yōu)匹配的工人；運行時間和內(nèi)存占用如圖8(c)和圖8(d)所示：DG 算法的運行時間和內(nèi)存整體都高于GA算法。

5.2.6 改變延遲時間

在這組實驗中，改變算法的延遲時間，其他參數(shù)使用表1 中的默認(rèn)值。改變延遲時間的實驗結(jié)果如圖9 所示。

圖9 改變延遲時間實驗對比結(jié)果

算法的效用和匹配數(shù)如圖9(a)和圖9(b)所示，隨著延遲時間的增加，所有算法的效用也會隨之增加，因為可匹配的對象數(shù)量增多，可選擇的范圍也更大，其中使用DeFixed 策略的算法的效用和匹配數(shù)都始終優(yōu)于其他算法；運行時間如圖9(c)所示，所有算法的運行時間都隨延遲時間增加而逐漸減少，其中DG-DeFixed 算法的運行時間不延遲時較高，這是因為DeFixed 策略會將不滿足閾值的任務(wù)延遲至最后一刻，增加了匹配時的復(fù)雜度，GA-DeFixed 算法的運行時間雖然僅次于DG-DeFixed 算法，但是保持在較低水平；內(nèi)存占用如圖9(d)所示，DG 算法的內(nèi)存占用均高于GA 算法。

5.2.7 改變?nèi)蝿?wù)工作時長

在這組實驗中，分別對比了算法在工作時間為10～30 min 的短時長任務(wù)、30～120 min 的中等時長任務(wù)和120～300 min 的長時長任務(wù)的實驗結(jié)果，其他參數(shù)使用表1 中的默認(rèn)值。改變?nèi)蝿?wù)的工作時間的實驗結(jié)果如圖10 所示。算法的效用和匹配數(shù)如圖10(a)和圖10(b)所示，隨著工作時長的增加，所有算法的效用都逐漸減少。這是因為每次都需要任務(wù)完成后才能釋放工人和地點，當(dāng)匹配時間點到達(dá)時，可匹配的對象也減少了，只能退而求其次，選擇相對較差的匹配。運行時間和內(nèi)存占用如圖10(c)和圖10(d)所示：算法的運行時長隨工作時長增加會有所減少，其中使用DeFixed 策略的算法運行時長最長，DG 算法的內(nèi)存占用高于GA 算法。

圖10 改變?nèi)蝿?wù)工作時長實驗對比結(jié)果

5.2.8 改變?nèi)蝿?wù)和工人的數(shù)量

本組實驗改變?nèi)蝿?wù)數(shù)量和工人的數(shù)量，其他參數(shù)使用表1 中的默認(rèn)值，實驗結(jié)果如圖11、12 所示。算法的效用和匹配數(shù)如圖11(a)和圖11(b)、圖12(a)和圖12(b)所示，隨著任務(wù)數(shù)量的增加，所有算法的效用和匹配數(shù)都在增大，這是因為未匹配任務(wù)數(shù)量增加；隨著工人數(shù)量的增加，算法的效用和匹配數(shù)會先增加后逐漸平緩，因為算法會優(yōu)先選擇高效用的工人，其中使用DeFixed 策略的算法效用最大。運行時間如圖11(c)、圖12(c)所示，所有算法的運行時間都隨著數(shù)量增加而增加，其中DG-DeFixed 算法運行時間增長最快。內(nèi)存占用如圖11(d)、圖12(d)所示：DG 算法逐漸增加且消耗最多，GA 算法穩(wěn)定在較低水平。

圖11 改變?nèi)蝿?wù)數(shù)量實驗對比結(jié)果

圖12 改變工人數(shù)量實驗對比結(jié)果

5.2.9 改變等待時間

本組實驗改變用戶的可容忍等待時間，其他參數(shù)使用表1 中的默認(rèn)值，實驗結(jié)果如圖13 所示。

如圖13(a)和圖13(b)所示，所有算法的效用隨等待時間波動，特別在等待時間等于5 min 時，匹配數(shù)大多有所下降，這是因為限制的條件過小不滿足的匹配較多；如圖13(c)和(d)所示，使用DeFixed 策略算法的運行時間最長，在等待時間等于5 min 時運行時間驟增，DG 算法的內(nèi)存占用均高于GA 算法。

5.2.10 測試算法的可擴(kuò)展性

本組實驗使用合成數(shù)據(jù)集測試在大規(guī)模數(shù)據(jù)量且服務(wù)質(zhì)量和報酬具有不同分布下算法的效果，實驗結(jié)果如圖14 和圖15 所示。

圖14 改變對象數(shù)量（均勻分布)實驗對比結(jié)果

圖15 改變對象數(shù)量（正態(tài)分布）實驗對比結(jié)果

算法的效用和匹配數(shù)如圖14(a)和圖14(b)、圖15(a)和圖15(b)所示，所有算法的效用和匹配數(shù)都隨數(shù)量增加而增加，其中使用DeFixed 策略的算法效用高于其他算法；運行時間如圖14(c)、圖15(c)所示，DG-DeFixed 的運行時間過長，甚至可能無法滿足在線匹配的實時性需求，但是GADeFixed 算法的運行時間遠(yuǎn)遠(yuǎn)小于DG-DeFixed 算法；內(nèi)存占用如圖14(d)、圖15(d)所示，DG 算法的內(nèi)存消耗遠(yuǎn)遠(yuǎn)多于GA 算法，因為隨著數(shù)據(jù)規(guī)模的增長，其存儲的匹配也增加。

5.3 實驗總結(jié)

本文使用真實數(shù)據(jù)集和合成數(shù)據(jù)集對算法的效用和效率進(jìn)行了實驗。整體來看，GA-DeFixed算法的實驗結(jié)果、運行速度和內(nèi)存消耗均優(yōu)于其他算法。實驗首先對比了NetGA 算法，說明其無法應(yīng)用于本文場景，同時對GA 算法做了消融實驗；然后將DeFixed 策略和Fixed 策略進(jìn)行對比，證明DeFixed 策略在效用和匹配數(shù)上優(yōu)于Fixed策略；后續(xù)實驗中，通過改變不同參數(shù)，可以發(fā)現(xiàn)DeFixed 策略的效用高于其他閾值策略，且GA 算法的運行時間和內(nèi)存消耗少于DG 算法。通過在合成數(shù)據(jù)集上的可擴(kuò)展性測試可以發(fā)現(xiàn)，雖然DG 算法能獲得最優(yōu)的效用，但是在數(shù)據(jù)規(guī)模較大的場景下，無法滿足實時性，運行時間和內(nèi)存消耗都遠(yuǎn)高于GA 算法；GA 算法雖然獲得次優(yōu)解，但是使用DeFixed 策略的GA 算法在效用上高于其他算法，并且運行時間和內(nèi)存占用都較少。

6 結(jié)論

本文研究新型時空眾包平臺中3 類對象在線匹配問題，針對工人工作時長對后續(xù)匹配任務(wù)的影響，提出了考慮工作時長的在線3 類對象動態(tài)匹配問題。

1）通過分析3 類對象的結(jié)構(gòu)和組合關(guān)系，提出了一種混合遺傳算法對問題進(jìn)行求解，并分析多種閾值策略的影響，提出了延遲閾值策略進(jìn)一步提升效用。

2）對現(xiàn)有算法進(jìn)行改造以適應(yīng)本文場景，通過在真實數(shù)據(jù)集和合成數(shù)據(jù)集上的實驗，驗證了該算法在降低任務(wù)分配時間、提升分配效用上具有良好的表現(xiàn)。

在未來工作中，首先要進(jìn)一步研究時間復(fù)雜度和效用之間的平衡；其次將探索更加廣泛適用于眾包場景的通用模型，考慮用戶、工人和平臺的多方利益，切合實際意義。