劉 松 林

(中國科學技術大學 軟件學院，江蘇 蘇州 215123) (中國科學技術大學 蘇州研究院，江蘇 蘇州 215123)

1 引 言

眾包的概念最早于2006年6月由美國《連線》雜志記者杰夫·豪(Jeff Howe)提出，被定義為“一個公司或機構把過去由員工執(zhí)行的工作任務，以自由自愿的形式外包給非特定的(而且通常是大型的)大眾網(wǎng)絡的做法”[1].當前，這一概念已得到進一步的擴展，泛指將一個或多個大規(guī)模的復雜任務分解成許多個子任務，并分配給大量攜帶有智能終端的移動用戶，通過他們共同完成而形成的一種新型協(xié)作計算模式.空間眾包(Spatial Crowdsourcing)則特指外包任務與空間地理位置密切相關的一類眾包系統(tǒng).由于空間眾包能夠通過移動用戶的協(xié)作，完成單個用戶難以單獨應對的大規(guī)模復雜任務，如數(shù)據(jù)收集、物流運輸、乘車共享、交通信息采集、環(huán)境監(jiān)測等等，因而具有廣泛的應用價值和重要的研究意義[2-6].

典型的空間眾包系統(tǒng)主要包括位于云端的系統(tǒng)平臺和許多攜帶智能終端的移動用戶(通常被稱為工作者Worker).眾包服務請求者會通過云端系統(tǒng)平臺發(fā)布一個大規(guī)模的空間眾包工作需求，通常可以表示為一系列地理位置相關的數(shù)據(jù)收集、環(huán)境檢測、物流運輸或乘車共享等任務.系統(tǒng)平臺則將這些任務分配給合適的工作者，或者工作者自主申領感興趣的眾包任務.然后，工作者移動到指定位置，執(zhí)行并完成相應的任務，并通過隨身攜帶的智能終端將任務結果反饋給任務的發(fā)起方.

任務分配是空間眾包的核心問題.圍繞著任務分配及相關問題，國內外學者展開了廣泛深入的研究.早期的任務分配以Amazon Mechanical Turk系統(tǒng)為代表，采用了WST(Worker Selected Tasks)即工作者主動選擇任務的模式[7].近年來，為了提升任務分配的效用，國內外學者則重點對SAT(Server Assigned Tasks)即系統(tǒng)平臺服務器分配任務的模式進行了研究，針對不同的應用場景提出了大量的任務分配算法[8-17].進一步地，圍繞著任務分配，設計了一系列的激勵機制[18-20]、隱私保護機制[21-27]等等.

目前，已有的這些空間眾包研究大多基于兩層開放式系統(tǒng)架構，工作者可以自主進入或退出系統(tǒng)，系統(tǒng)平臺則直接向工作者分配任務或回收結果，如圖1(a)所示.而近年來，隨著空間眾包應用的發(fā)展，面向專業(yè)化、精細化服務的需求，真實的應用系統(tǒng)已經(jīng)出現(xiàn)了由系統(tǒng)平臺、服務網(wǎng)點和員工用戶(工作者)共同組成的三層系統(tǒng)架構，如圖1(b)所示.相比于兩層開放式系統(tǒng)架構，該三層架構在系統(tǒng)平臺和工作者之間引入了服務網(wǎng)點層，系統(tǒng)平臺通過(真實或虛擬的)服務網(wǎng)點來管理專業(yè)化的工作者并向其分派眾包任務，典型的系統(tǒng)如順豐快遞、美團外賣、曹操出行等等.

圖1 空間眾包系統(tǒng)架構Fig.1 Architecture of spatial crowdsourcing

本文則對基于三層架構的空間眾包系統(tǒng)服務網(wǎng)點選址問題進行了研究.在一個大范圍區(qū)域，可能出現(xiàn)眾多的空間眾包任務，我們需要先擇合適的位置建設一些服務網(wǎng)點，并部署一定數(shù)量的工作者，為這些空間眾包任務的執(zhí)行提供服務支持.這一問題本質上包含了非平凡集合覆蓋、0-1背包的資源分配問題，是一個NP難解問題.為此，本文采用遺傳算法來選址服務網(wǎng)點，結合Voronoi圖來分配工作者，在此基礎上提出了一個基于Voronoi圖的空間眾包服務網(wǎng)點選址遺傳算法，并通過仿真實驗驗證了該算法能取得近似最優(yōu)的性能.據(jù)我們調研所知，這是首個面向三層空間眾包系統(tǒng)的服務網(wǎng)點選址算法.

2 問題建模

不失一般性，本文考慮如下三層結構的空間眾包應用場景：

假設一個大范圍區(qū)域內，有n個地理位置可能出現(xiàn)空間眾包任務，記為集合J，集合的基數(shù)為|J|=n.其中，每一個任務j∈J都關聯(lián)一個地理位置，單位考察周期內(如每天、每周等)任務出現(xiàn)的概率則記為pj∈[0，1]，任務的平均工作量記為qj，該任務被完成后系統(tǒng)得到報酬記為rj.這里，任務的類型可以不同，但都可以用工作時長來表示其工作量.并且為了簡化模型，我們假設每個地理位置只關聯(lián)一個任務.如果在實際應用中，一個地理位置出現(xiàn)了多個任務，我們可以將這些任務合并為一個總任務，其工作量為多個任務的工作量之和，其報酬為各任務的報酬之和，其出現(xiàn)概率則取工作量為權重的加權平均概率，合并前后的期望工作量(即，總的概率加權工作量)維持不變.例如，某任務j實際上是兩個子任務j1和j2的和，則令pj=(pj1qj1+pj2qj2)/(qj1+qj2)，qj=qj1+qj2，rj=rj1+rj2.

另一方面，假設在這一區(qū)域中有m個候選地理位置可以用于建設眾包服務網(wǎng)點，稱為候選服務網(wǎng)點，記為集合I，集合的基數(shù)為|I|=m.其中，每一個候選服務網(wǎng)點i∈I都有一個建設成本，涵蓋了場地建設費用及工作者的基本報酬，記為Ci，并且每一個候選服務網(wǎng)點都對應一個最大工作量處理能力Qi.這里，Ci中的建設成本實際上是該服務網(wǎng)點總的建設成本分攤在單位考察周內(如每天、每周等)的單位成本，工作者報酬也是單位考察周期內的報酬.并且，為了簡化模型，我們假設每個候選服務網(wǎng)點的建設規(guī)模和成本是單一的.在實際應用中，如果同一個地理位置有多個不同建設規(guī)模的候選服務網(wǎng)點，我們則可以采用多個虛擬的候選服務網(wǎng)點，每一個用來代替一個可能的候選服務網(wǎng)點配置，不影響本文所提算法的正確性.

此外，每個候選服務網(wǎng)點i與任務j的地圖距離記為dij.由于網(wǎng)點i為任務j提供服務時需要工作者往返于兩地，往返兩地的工作時長(即工作量)和代價均與兩地的地圖距離成比例，分別記為αidij和βidij，其中αi和βi是與服務網(wǎng)點i中工作者相關的常系數(shù).這里，我們簡單地假設工作者總是直接往返于服務網(wǎng)點和任務地點，而不考慮工作者在同時服務多個任務時通過繞行而縮短總的移動距離這一情形.實際上，我們研究了基于車聯(lián)網(wǎng)的空間眾包系統(tǒng)繞路問題，雖然“繞行”蘊含了路徑規(guī)劃問題，本身是NP難解問題，但在實際應用中，當給定多個可同時服務的任務地點時，工作者往往會習慣性地按照固定的路線繞行，總的移動距離也是固定的[23].因此，我們只需對常系數(shù)αi和βi做適當修正即可.

上述空間眾包場景中，本文主要關注服務網(wǎng)點的選址問題，目標是從集合I中選擇k個合適的位置來建設實際的服務網(wǎng)點，并為每個服務網(wǎng)點確定其所需服務的任務集合，使得各個網(wǎng)點所服務的任務工作量不超過其最大處理能力，同時盡可能地最大化整個系統(tǒng)的純收益.這里，我們假設上述場景中定義的各項參數(shù)都是已知的.事實上，關于任務點的各項參數(shù)可以通過相關歷史數(shù)據(jù)估算確定下來，而候選服務網(wǎng)點的相關參數(shù)則可以通過市場調研獲得.

(1)

(2)

xij∈{0，1}，?i∈I ，?j∈J

(3)

(4)

上述問題形式化中，公式(1)為優(yōu)化目標即系統(tǒng)的純收益(單位考察周期內)，第1項是空間眾包系統(tǒng)在單位考察周期內完成任務的總收益，第2項為服務網(wǎng)點的建設成本及工作者基本報酬，第3項則為工作者執(zhí)行任務相關的移動成本及相關支付報酬，其中∨為析取運算符;公式(2)為工作量限制條件，即每個服務網(wǎng)點所服務的任務工作時長與往返兩地的工作時長之和不大于該網(wǎng)點的最大處理能力.

3 問題難度分析

本文的三層空間眾包系統(tǒng)服務網(wǎng)點選址問題蘊含了0-1背包問題，是一個NP難解問題，證明如下：

定理1.本文所提的時空眾包服務網(wǎng)點選址問題是NP難解問題.

證明：首先，考慮本服務網(wǎng)點選址問題的一個特例問題.假設|I|=1，即系統(tǒng)中已有一個候選服務網(wǎng)點，不妨設i=1，同時假設αi=βi=Ci=0.則問題的優(yōu)化目標，即公式(1)，變?yōu)镸AX：∑j∈Jpjrjx1j，而公式(2)的限制條件則簡化為∑j∈Jqjx1j≤Q1.這一特例問題實際上是以Q1為容量的0-1背包問題，是一個NP難解問題.因此，本服務網(wǎng)點選址問題作為該特例問題的擴展，必然是NP難解問題.證畢.

此外，當考慮多個候選服務網(wǎng)點時，本文的服務網(wǎng)點選址問題還包含了不相交的集合覆蓋問題，是一個復雜的NP難問題.

4 算法設計和實現(xiàn)

已知本文所提的時空眾包選址問題是NP難解問題，無法在多項式時間內獲得最優(yōu)解，只能通過一定的方式迭代逐漸逼近最優(yōu)解.為此，本文提出了結合Voronoi圖的遺傳算法對該問題進行求解.

算法的基本思想如下：首先，將0-1向量{y1，…，yi，…，ym}進行編碼，yi=1則表示第i個候選網(wǎng)點將會被選擇建設為實際的眾包服務網(wǎng)點;然后，基于被選中的服務網(wǎng)點，利用Voronoi圖將各個任務分配到為其提供服務能夠獲得最好效用的服務網(wǎng)點，從而確定出0-1矩陣{xij}m×n的值;當所有的xij和yi都確定下來后就可以根據(jù)公式(1)計算相應的總收益值，并在此基礎上計算種群的適應度并實施遺傳算法.算法的基本步驟如下：

1.設計遺傳編碼(解碼)規(guī)則，進行遺傳編碼(解碼).

2.生成初始種群.

3.計算適應度值.

4.While(未滿足迭代終止條件)Do

a)選擇操作

b)交叉操作

c)變異操作

d)計算適應度值

5.結束.

在此，對上述具體步驟規(guī)則進行詳細設計和補充說明.

1)編碼規(guī)則

本文采用二重結構對離散時空眾包服務網(wǎng)點選址模型進行染色體編碼，如表1所示.第1行為序號碼，表示候選點的序號;第2行為變量碼，表示與序號碼相對應的候選點是否被選中.yi為布爾值變量，其值為1，表示第i個候選網(wǎng)點將會被選擇建設為實際的眾包服務網(wǎng)點;反之，當yi的值為0時，表示第i個候選網(wǎng)點將不會被選擇建設為實際的眾包服務網(wǎng)點.按照此規(guī)則進行染色體編碼并隨機產(chǎn)生個體，組成初始種群.

表1 雙重結構編碼
Table 1 Dual-structure coding

ii1i2i3i4i5i6i7…yi00101100

例如，對于一個共有10個任務點、從8個候選點中挑選5個建設服務網(wǎng)點的時空眾包服務網(wǎng)點選址問題，如果隨機產(chǎn)生的雙重結構如表2所示，它表示了一個可行的選址方案(個體).在該方案中，選擇了5個候選點(i2、i3、i4、i6、i8)覆蓋所有的10個時空眾包任務點.

表2 雙重結構編碼示例
Table 2 An example of dual-structure coding

ii1i2i3i4i5i6i7i8yi01110101

以被選中的候選點(例中為i2、i3、i4、i6、i8)為中心，將該區(qū)域劃分為若干個相應的區(qū)塊，針對每一個任務點，計算各個被選中的候選點到當前任務點所須的代價βidij，將此代價看作是各服務網(wǎng)點到當前任務點的虛擬距離，結合Voronoi圖，根據(jù)該虛擬距離對任務點進行劃分：根據(jù)每一個任務點j，取βidij的最小值，將其相對應的xij賦值為1;否則，xij=0.從而確定該任務點在Voronoi圖中所屬的區(qū)塊(例中任務點劃分如圖2所示)，同時也得到各xij的值.

2)生成初始種群

采用隨機的方式生成初始種群，具體規(guī)則為：

將已知的先驗規(guī)則轉化為必須滿足的約束條件，對隨機生成的染色體個體進行判斷：若不滿足上述問題模型已知的約束條件，則重新生成一個個體，直至產(chǎn)生足夠多的滿足種群規(guī)模的個體.

圖2 任務點劃分示例Fig.2 Example of task point division

本文以上述方式隨機生成初始種群.

3)計算適應度值

已知時空眾包選址問題的目標函數(shù)式(1)：

(5)

(6)

其中，K為種群規(guī)模.

4)選擇操作

采用優(yōu)選方法與輪盤賭方法相結合的方式進行選擇：首先將種群中適應度值最大的個體(最優(yōu)個體)，直接遺傳到子代;然后，再用進化以來所產(chǎn)生的最優(yōu)個體替換子代中最差的個體;其余的個體，采用輪盤賭的方法進行選擇.

輪盤賭選擇方法的基本思路是：第s個個體的適應度值Fit(s)在當前種群適應度值總和Fit(x)中占比的大小，即是其被選擇的概率ps的大小.這樣個體的適應度越大，越容易被選擇，保證了個體被選擇的概率與其適應度值成正比.

(7)

5)交叉操作

本文使用的方法是在目標個體的染色體片段中隨機產(chǎn)生兩個交叉點，將這兩個交叉點所對應的行元素(為同一任務點提供服務的候選點)進行互換操作，從而生成新的子代個體.

6)變異操作

變異操作的前提是比較目標函數(shù)值發(fā)現(xiàn)，上代種群中的最優(yōu)個體優(yōu)于交叉操作之后的.具體方法是依照預先設置好的變異概率pMutation，對一部分個體進行變異，改變?yōu)槟橙蝿拯c提供服務的候選點.

本文結合Voronoi圖，根據(jù)時空眾包服務網(wǎng)點選址問題模型的特點，設計了遺傳算法，并編寫了該類問題的種群、編碼、適應度、選擇、交叉、變異等規(guī)則.通過這些規(guī)則，我們比較每一代染色體的適應度值，尋找最優(yōu)個體和最優(yōu)目標函數(shù)值，盡可能接近最優(yōu)解，從而得出最優(yōu)選址方案，實現(xiàn)收益最大化的目標.

5 算法實驗

5.1 仿真實驗

本文針對具體案例進行仿真實驗：在某區(qū)域內，共有25個時空眾包任務點j和10個候選點i.各任務點的工作量如表3所示.各候選點的固定成本Ci(元/天)、單位距離移動成本βi(元/公里)和最大工作量Qi(工時)均為已知，如表4所示.現(xiàn)準備在該區(qū)域10個候選點i中建設6個時空眾包服務網(wǎng)點，要求滿足本文問題的所有約束條件.

表3 各任務點工作量
Table 3 Workload of task points

j12345678910qi1232112321j11121314151617181920qi1232112321j2122232425qi12321

表4 各候選點參數(shù)
Table 4 Parameters of candidate points

i12345678910Ci65402030503545202530βi5664365665Qi87610887897

5.2 實驗設置

本文采用遺傳算法求解上述案例，設遺傳算法參數(shù)為：交叉概率pCross=0.6;變異概率pMutation=0.1;種群數(shù)量為100;最大進化代數(shù)為100.在4G內存@2.60GHz的Intel(R)Core(TM)i5-4210M電腦上，使用Matlab軟件運行計算.

5.3 實驗結果

因為本文所研究的時空眾包服務網(wǎng)點選址問題，是NP難解問題，所以只能通過遺傳算法求得近似最優(yōu)解.每次實驗所選中的候選點和實驗結果未必相同.圖3、圖5、圖7給出了多次實驗中的3次不同結果，3次結果所對應的收斂曲線如圖4、圖6、圖8所示.

比較3種選擇方案可知，圖7所示方案總成本更小，收益更大.

5.4 實驗結論

遺傳算法常有的缺陷是過早收斂和陷入局部最優(yōu).這兩種缺陷分別出現(xiàn)在進化初期和進化后期：進化初期，往往有個別適應度突出的個體，導致過早收斂(早熟現(xiàn)象).而到了進化后期，又往往因為個體之間的差異較小，導致種群的多樣性受限，從而陷入局部最優(yōu).綜合實驗數(shù)據(jù)和圖形來看，本文所設計的遺傳算法，較好的規(guī)避了上述兩種常見的缺陷，使結果盡可能接近全局最優(yōu)解，進而使得收益最大化.

圖3 候選點選擇方案1Fig.3 Candidate point selection scheme 1圖4 遺傳算法收斂曲線1Fig.4 Convergence curve of genetic algorithm 1圖5 候選點選擇方案2Fig.5 Candidate point selection scheme 2圖6 遺傳算法收斂曲線2Fig.6 Convergence curve of genetic algorithm 2圖7 候選點選擇方案3Fig.7 Candidate point selection scheme 3圖8 遺傳算法收斂曲線3Fig.8 Convergence curve of genetic algorithm 3

6 總 結

本文引入了一種三層架構并構建了的空間眾包模型，適用于多種現(xiàn)實場景(如物流、外賣、數(shù)據(jù)采集等).相比于原有的空間眾包，本空間眾包模式在系統(tǒng)平臺和任務執(zhí)行者之間，新增了服務網(wǎng)點這一層級.在此模型下，本文介紹了此類空間眾包系統(tǒng)的一種服務網(wǎng)點選址問題，并提出了一個基于Voronoi圖的遺傳算法，設計了其編碼、生成種群、選擇、交叉、變異等操作的具體規(guī)則，在每一步迭代中，采用優(yōu)選法與輪盤賭法相結合的辦法，以此來盡可能接近最優(yōu)解.最后，本文通過仿真實驗，驗證了其可靠性和有效性.