三层架构的空间众包服务网点选址遗传算法

刘 松 林

(中国科学技术大学 软件学院，江苏 苏州 215123) (中国科学技术大学 苏州研究院，江苏 苏州 215123)

1 引 言

众包的概念最早于2006年6月由美国《连线》杂志记者杰夫·豪(Jeff Howe)提出，被定义为“一个公司或机构把过去由员工执行的工作任务，以自由自愿的形式外包给非特定的(而且通常是大型的)大众网络的做法”[1].当前，这一概念已得到进一步的扩展，泛指将一个或多个大规模的复杂任务分解成许多个子任务，并分配给大量携带有智能终端的移动用户，通过他们共同完成而形成的一种新型协作计算模式.空间众包(Spatial Crowdsourcing)则特指外包任务与空间地理位置密切相关的一类众包系统.由于空间众包能够通过移动用户的协作，完成单个用户难以单独应对的大规模复杂任务，如数据收集、物流运输、乘车共享、交通信息采集、环境监测等等，因而具有广泛的应用价值和重要的研究意义[2-6].

典型的空间众包系统主要包括位于云端的系统平台和许多携带智能终端的移动用户(通常被称为工作者Worker).众包服务请求者会通过云端系统平台发布一个大规模的空间众包工作需求，通常可以表示为一系列地理位置相关的数据收集、环境检测、物流运输或乘车共享等任务.系统平台则将这些任务分配给合适的工作者，或者工作者自主申领感兴趣的众包任务.然后，工作者移动到指定位置，执行并完成相应的任务，并通过随身携带的智能终端将任务结果反馈给任务的发起方.

任务分配是空间众包的核心问题.围绕着任务分配及相关问题，国内外学者展开了广泛深入的研究.早期的任务分配以Amazon Mechanical Turk系统为代表，采用了WST(Worker Selected Tasks)即工作者主动选择任务的模式[7].近年来，为了提升任务分配的效用，国内外学者则重点对SAT(Server Assigned Tasks)即系统平台服务器分配任务的模式进行了研究，针对不同的应用场景提出了大量的任务分配算法[8-17].进一步地，围绕着任务分配，设计了一系列的激励机制[18-20]、隐私保护机制[21-27]等等.

目前，已有的这些空间众包研究大多基于两层开放式系统架构，工作者可以自主进入或退出系统，系统平台则直接向工作者分配任务或回收结果，如图1(a)所示.而近年来，随着空间众包应用的发展，面向专业化、精细化服务的需求，真实的应用系统已经出现了由系统平台、服务网点和员工用户(工作者)共同组成的三层系统架构，如图1(b)所示.相比于两层开放式系统架构，该三层架构在系统平台和工作者之间引入了服务网点层，系统平台通过(真实或虚拟的)服务网点来管理专业化的工作者并向其分派众包任务，典型的系统如顺丰快递、美团外卖、曹操出行等等.

图1 空间众包系统架构Fig.1 Architecture of spatial crowdsourcing

本文则对基于三层架构的空间众包系统服务网点选址问题进行了研究.在一个大范围区域，可能出现众多的空间众包任务，我们需要先择合适的位置建设一些服务网点，并部署一定数量的工作者，为这些空间众包任务的执行提供服务支持.这一问题本质上包含了非平凡集合覆盖、0-1背包的资源分配问题，是一个NP难解问题.为此，本文采用遗传算法来选址服务网点，结合Voronoi图来分配工作者，在此基础上提出了一个基于Voronoi图的空间众包服务网点选址遗传算法，并通过仿真实验验证了该算法能取得近似最优的性能.据我们调研所知，这是首个面向三层空间众包系统的服务网点选址算法.

2 问题建模

不失一般性，本文考虑如下三层结构的空间众包应用场景：

假设一个大范围区域内，有n个地理位置可能出现空间众包任务，记为集合J，集合的基数为|J|=n.其中，每一个任务j∈J都关联一个地理位置，单位考察周期内(如每天、每周等)任务出现的概率则记为pj∈[0，1]，任务的平均工作量记为qj，该任务被完成后系统得到报酬记为rj.这里，任务的类型可以不同，但都可以用工作时长来表示其工作量.并且为了简化模型，我们假设每个地理位置只关联一个任务.如果在实际应用中，一个地理位置出现了多个任务，我们可以将这些任务合并为一个总任务，其工作量为多个任务的工作量之和，其报酬为各任务的报酬之和，其出现概率则取工作量为权重的加权平均概率，合并前后的期望工作量(即，总的概率加权工作量)维持不变.例如，某任务j实际上是两个子任务j1和j2的和，则令pj=(pj1qj1+pj2qj2)/(qj1+qj2)，qj=qj1+qj2，rj=rj1+rj2.

另一方面，假设在这一区域中有m个候选地理位置可以用于建设众包服务网点，称为候选服务网点，记为集合I，集合的基数为|I|=m.其中，每一个候选服务网点i∈I都有一个建设成本，涵盖了场地建设费用及工作者的基本报酬，记为Ci，并且每一个候选服务网点都对应一个最大工作量处理能力Qi.这里，Ci中的建设成本实际上是该服务网点总的建设成本分摊在单位考察周内(如每天、每周等)的单位成本，工作者报酬也是单位考察周期内的报酬.并且，为了简化模型，我们假设每个候选服务网点的建设规模和成本是单一的.在实际应用中，如果同一个地理位置有多个不同建设规模的候选服务网点，我们则可以采用多个虚拟的候选服务网点，每一个用来代替一个可能的候选服务网点配置，不影响本文所提算法的正确性.

此外，每个候选服务网点i与任务j的地图距离记为dij.由于网点i为任务j提供服务时需要工作者往返于两地，往返两地的工作时长(即工作量)和代价均与两地的地图距离成比例，分别记为αidij和βidij，其中αi和βi是与服务网点i中工作者相关的常系数.这里，我们简单地假设工作者总是直接往返于服务网点和任务地点，而不考虑工作者在同时服务多个任务时通过绕行而缩短总的移动距离这一情形.实际上，我们研究了基于车联网的空间众包系统绕路问题，虽然“绕行”蕴含了路径规划问题，本身是NP难解问题，但在实际应用中，当给定多个可同时服务的任务地点时，工作者往往会习惯性地按照固定的路线绕行，总的移动距离也是固定的[23].因此，我们只需对常系数αi和βi做适当修正即可.

上述空间众包场景中，本文主要关注服务网点的选址问题，目标是从集合I中选择k个合适的位置来建设实际的服务网点，并为每个服务网点确定其所需服务的任务集合，使得各个网点所服务的任务工作量不超过其最大处理能力，同时尽可能地最大化整个系统的纯收益.这里，我们假设上述场景中定义的各项参数都是已知的.事实上，关于任务点的各项参数可以通过相关历史数据估算确定下来，而候选服务网点的相关参数则可以通过市场调研获得.

(1)

(2)

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

(3)

(4)

上述问题形式化中，公式(1)为优化目标即系统的纯收益(单位考察周期内)，第1项是空间众包系统在单位考察周期内完成任务的总收益，第2项为服务网点的建设成本及工作者基本报酬，第3项则为工作者执行任务相关的移动成本及相关支付报酬，其中∨为析取运算符;公式(2)为工作量限制条件，即每个服务网点所服务的任务工作时长与往返两地的工作时长之和不大于该网点的最大处理能力.

3 问题难度分析

本文的三层空间众包系统服务网点选址问题蕴含了0-1背包问题，是一个NP难解问题，证明如下：

定理1.本文所提的时空众包服务网点选址问题是NP难解问题.

证明：首先，考虑本服务网点选址问题的一个特例问题.假设|I|=1，即系统中已有一个候选服务网点，不妨设i=1，同时假设αi=βi=Ci=0.则问题的优化目标，即公式(1)，变为MAX：∑j∈Jpjrjx1j，而公式(2)的限制条件则简化为∑j∈Jqjx1j≤Q1.这一特例问题实际上是以Q1为容量的0-1背包问题，是一个NP难解问题.因此，本服务网点选址问题作为该特例问题的扩展，必然是NP难解问题.证毕.

此外，当考虑多个候选服务网点时，本文的服务网点选址问题还包含了不相交的集合覆盖问题，是一个复杂的NP难问题.

4 算法设计和实现

已知本文所提的时空众包选址问题是NP难解问题，无法在多项式时间内获得最优解，只能通过一定的方式迭代逐渐逼近最优解.为此，本文提出了结合Voronoi图的遗传算法对该问题进行求解.

算法的基本思想如下：首先，将0-1向量{y1，…，yi，…，ym}进行编码，yi=1则表示第i个候选网点将会被选择建设为实际的众包服务网点;然后，基于被选中的服务网点，利用Voronoi图将各个任务分配到为其提供服务能够获得最好效用的服务网点，从而确定出0-1矩阵{xij}m×n的值;当所有的xij和yi都确定下来后就可以根据公式(1)计算相应的总收益值，并在此基础上计算种群的适应度并实施遗传算法.算法的基本步骤如下：

1.设计遗传编码(解码)规则，进行遗传编码(解码).

2.生成初始种群.

3.计算适应度值.

4.While(未满足迭代终止条件)Do

a)选择操作

b)交叉操作

c)变异操作

d)计算适应度值

5.结束.

在此，对上述具体步骤规则进行详细设计和补充说明.

1)编码规则

本文采用二重结构对离散时空众包服务网点选址模型进行染色体编码，如表1所示.第1行为序号码，表示候选点的序号;第2行为变量码，表示与序号码相对应的候选点是否被选中.yi为布尔值变量，其值为1，表示第i个候选网点将会被选择建设为实际的众包服务网点;反之，当yi的值为0时，表示第i个候选网点将不会被选择建设为实际的众包服务网点.按照此规则进行染色体编码并随机产生个体，组成初始种群.

表1 双重结构编码
Table 1 Dual-structure coding

ii1i2i3i4i5i6i7…yi00101100

例如，对于一个共有10个任务点、从8个候选点中挑选5个建设服务网点的时空众包服务网点选址问题，如果随机产生的双重结构如表2所示，它表示了一个可行的选址方案(个体).在该方案中，选择了5个候选点(i2、i3、i4、i6、i8)覆盖所有的10个时空众包任务点.

表2 双重结构编码示例
Table 2 An example of dual-structure coding

ii1i2i3i4i5i6i7i8yi01110101

以被选中的候选点(例中为i2、i3、i4、i6、i8)为中心，将该区域划分为若干个相应的区块，针对每一个任务点，计算各个被选中的候选点到当前任务点所须的代价βidij，将此代价看作是各服务网点到当前任务点的虚拟距离，结合Voronoi图，根据该虚拟距离对任务点进行划分：根据每一个任务点j，取βidij的最小值，将其相对应的xij赋值为1;否则，xij=0.从而确定该任务点在Voronoi图中所属的区块(例中任务点划分如图2所示)，同时也得到各xij的值.

2)生成初始种群

采用随机的方式生成初始种群，具体规则为：

将已知的先验规则转化为必须满足的约束条件，对随机生成的染色体个体进行判断：若不满足上述问题模型已知的约束条件，则重新生成一个个体，直至产生足够多的满足种群规模的个体.

图2 任务点划分示例Fig.2 Example of task point division

本文以上述方式随机生成初始种群.

3)计算适应度值

已知时空众包选址问题的目标函数式(1)：

(5)

(6)

其中，K为种群规模.

4)选择操作

采用优选方法与轮盘赌方法相结合的方式进行选择：首先将种群中适应度值最大的个体(最优个体)，直接遗传到子代;然后，再用进化以来所产生的最优个体替换子代中最差的个体;其余的个体，采用轮盘赌的方法进行选择.

轮盘赌选择方法的基本思路是：第s个个体的适应度值Fit(s)在当前种群适应度值总和Fit(x)中占比的大小，即是其被选择的概率ps的大小.这样个体的适应度越大，越容易被选择，保证了个体被选择的概率与其适应度值成正比.

(7)

5)交叉操作

本文使用的方法是在目标个体的染色体片段中随机产生两个交叉点，将这两个交叉点所对应的行元素(为同一任务点提供服务的候选点)进行互换操作，从而生成新的子代个体.

6)变异操作

变异操作的前提是比较目标函数值发现，上代种群中的最优个体优于交叉操作之后的.具体方法是依照预先设置好的变异概率pMutation，对一部分个体进行变异，改变为某任务点提供服务的候选点.

本文结合Voronoi图，根据时空众包服务网点选址问题模型的特点，设计了遗传算法，并编写了该类问题的种群、编码、适应度、选择、交叉、变异等规则.通过这些规则，我们比较每一代染色体的适应度值，寻找最优个体和最优目标函数值，尽可能接近最优解，从而得出最优选址方案，实现收益最大化的目标.

5 算法实验

5.1 仿真实验

本文针对具体案例进行仿真实验：在某区域内，共有25个时空众包任务点j和10个候选点i.各任务点的工作量如表3所示.各候选点的固定成本Ci(元/天)、单位距离移动成本βi(元/公里)和最大工作量Qi(工时)均为已知，如表4所示.现准备在该区域10个候选点i中建设6个时空众包服务网点，要求满足本文问题的所有约束条件.

表3 各任务点工作量
Table 3 Workload of task points

j12345678910qi1232112321j11121314151617181920qi1232112321j2122232425qi12321

表4 各候选点参数
Table 4 Parameters of candidate points

i12345678910Ci65402030503545202530βi5664365665Qi87610887897

5.2 实验设置

本文采用遗传算法求解上述案例，设遗传算法参数为：交叉概率pCross=0.6;变异概率pMutation=0.1;种群数量为100;最大进化代数为100.在4G内存@2.60GHz的Intel(R)Core(TM)i5-4210M电脑上，使用Matlab软件运行计算.

5.3 实验结果

因为本文所研究的时空众包服务网点选址问题，是NP难解问题，所以只能通过遗传算法求得近似最优解.每次实验所选中的候选点和实验结果未必相同.图3、图5、图7给出了多次实验中的3次不同结果，3次结果所对应的收敛曲线如图4、图6、图8所示.

比较3种选择方案可知，图7所示方案总成本更小，收益更大.

5.4 实验结论

遗传算法常有的缺陷是过早收敛和陷入局部最优.这两种缺陷分别出现在进化初期和进化后期：进化初期，往往有个别适应度突出的个体，导致过早收敛(早熟现象).而到了进化后期，又往往因为个体之间的差异较小，导致种群的多样性受限，从而陷入局部最优.综合实验数据和图形来看，本文所设计的遗传算法，较好的规避了上述两种常见的缺陷，使结果尽可能接近全局最优解，进而使得收益最大化.

图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 总 结

本文引入了一种三层架构并构建了的空间众包模型，适用于多种现实场景(如物流、外卖、数据采集等).相比于原有的空间众包，本空间众包模式在系统平台和任务执行者之间，新增了服务网点这一层级.在此模型下，本文介绍了此类空间众包系统的一种服务网点选址问题，并提出了一个基于Voronoi图的遗传算法，设计了其编码、生成种群、选择、交叉、变异等操作的具体规则，在每一步迭代中，采用优选法与轮盘赌法相结合的办法，以此来尽可能接近最优解.最后，本文通过仿真实验，验证了其可靠性和有效性.