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

周靜，董紅斌，郭田雨

哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001

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

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

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

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

1 相關工作

1.1 時空眾包

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

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

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

1.2 遺傳算法

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

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

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

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

2 問題描述

2.1 基本定義

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

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

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

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

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

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

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

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

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

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

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

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

2.2 問題復雜性

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

3 延遲貪心算法

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

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

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

輸出：全局任務匹配結果集M

For each 新出現的眾包對象vdo

更新任務完成情況

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

Mwait← {滿足所有約束的任務匹配}

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

end

returnM

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

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

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

4 改進算法

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

4.1 混合遺傳算法

4.1.1 編碼與解碼

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

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

圖1 任務森林結構

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

4.1.2 初始解的生成

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

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

圖2 模擬過程

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

4.1.3 遺傳算子

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

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

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

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

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

圖3 隨機部分初始機制

4.1.4 算法偽代碼

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

算法2混合遺傳算法

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

輸出：全局任務匹配結果集M

For each 新出現的眾包對象vdo

更新任務完成情況

初始化未匹配的在線任務集、工人集、地點集；初始化任務森林；初始化標記矩陣

生成初始解

fori=0:Emaxdo

p 變異

t 變異

隨機部分重啟機制

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

end

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

end

returnM

4.2 延遲閾值策略

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

算法3延遲閾值策略

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

輸出：全局任務匹配結果集M

for each 新出現的眾包對象vdo

使用遺傳算法或者貪心算法找到所有可行的任務匹配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

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

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

5 實驗分析

通過實驗在真實數據集和合成數據集上分別對算法的效用和效率進行評估。

5.1 實驗設置

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

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

表1 實驗數據參數表

本文還通過一組合成數據集測試算法的可擴展性。任務、工人和地點以10∶10∶1 的比例在[0，480] min 內均勻出現在10 000×10 000 的網格中，位置以二維坐標表示，對工人服務質量和任務報酬采用2 種分布情況。合成數據集的詳細信息見表2。

表2 合成數據集

評價算法有以下7 種：

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

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

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

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

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

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

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

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

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

5.2 實驗結果

5.2.1 對比NetGA 算法

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

圖4 對比NetGA 算法

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

5.2.2 消融實驗

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

圖5 消融實驗對比結果

5.2.3 改變閾值

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

圖6 改變閾值實驗對比結果

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

5.2.4 改變半徑

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

圖7 改變半徑實驗對比結果

5.2.5 改變工人容量

在這組實驗中，改變工人的容量，其他參數使用表1 中的默認值。改變工人容量的實驗結果如圖8 所示。

圖8 改變工人容量實驗對比結果

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

5.2.6 改變延遲時間

在這組實驗中，改變算法的延遲時間，其他參數使用表1 中的默認值。改變延遲時間的實驗結果如圖9 所示。

圖9 改變延遲時間實驗對比結果

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

5.2.7 改變任務工作時長

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

圖10 改變任務工作時長實驗對比結果

5.2.8 改變任務和工人的數量

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

圖11 改變任務數量實驗對比結果

圖12 改變工人數量實驗對比結果

5.2.9 改變等待時間

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

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

5.2.10 測試算法的可擴展性

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

圖14 改變對象數量（均勻分布)實驗對比結果

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

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

5.3 實驗總結

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

6 結論

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

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

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

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