基于遗传算法的时空众包3 类对象任务分配

周静，董红斌，郭田雨

哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001

众包提供了一种汇集群体智慧求解问题的新思路，成为当前研究的热点问题[1]。近年来，随着移动互联网技术和线上到线下（online to offline，O2O）商业模式的兴起，时空众包逐步走进人们的视野。与传统众包如在线问答系统不同，时空众包需要人们实际在线下进行活动，因此受到了时空因素的约束。

目前针对工人、用户2 种角色的研究已经颇多[2-9]，然而，新的众包模式也带来了全新的挑战，平台需要将工人、用户、工作地点这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 类。趣运动是匹配教练进行教学或者匹配球员打球；在南瓜车中，理发师为顾客定制理发服务。这2 种任务完成时间一般至少以小时为单位，但是现有研究少有考虑到任务时长方面的问题。许多研究在一开始就假定了工人的最大匹配任务数，然后一次性完成匹配，工人依次完成这些任务，这对于微任务是可行的，但是对于长时间任务则不符合现实需求。如果一次性为工人分配多个任务，则后面的任务需要等待很久。

因此，本文假定了任务的工作时间st，它由任务指定，但是在工作过程中可由工人调节。对于趣运动，st是固定的，多为固定授课时长或者预约2 h 场地打球；而对于南瓜车，st无法立刻确定，可以首先生成最长st，在用户到达之后，工人再根据实际用户讲述的需求和自身经验预估st，这在实际应用中比较容易实现。

本文考虑到了工作时长对任务分配的影响，提出了在线3 类对象动态匹配(online dynamic assginment for three types of objects，ODAT)问题，并提出了基于混合遗传算法（genetic algorithm,GA）的延迟匹配算法和延迟阈值策略，旨在在满足多种约束的前提下平衡平台的利益和用户的满意度。

1 相关工作

1.1 时空众包

众包环境下在线匹配问题主要结合实际场景研究不同约束下的任务分配问题。在线二维匹配场景是工人前往任务地点完成工作。Kazemi 等[2]最早研究最大化任务匹配数问题。Tong 等[3]利用离线预测进行在线分配来最大化匹配数。Zheng等[4]考虑到了优化双边利益，不是单单优化平台利益，还应考虑工人偏好问题。Tong 等[5-6]研究双边在线微任务二维分配问题，将贪心算法和匈牙利算法结合，提出了两阶段模型使效用最大化。徐天乘等[7]利用深度学习方法设计了基于位置预测的任务分配方法。另外还存在一些复杂任务，如修理房屋、灾难恢复等，一个任务需要多个工人才能完成。Mizuhara 等[8]提出协同任务分配问题，需要所有工人都到达后才能开始工作。而Liu 等[9]提出了具有依赖性约束的多阶段匹配问题，工人需要依次完成任务。

在线三维匹配场景是工人和用户同时前往第三方地点，借助工作场所的工具来完成任务。Song 等[10]提出了众包环境下的3 类对象匹配问题。Li 等[11]和李博扬等[12]针对三维稳定匹配问题提出了求解算法。Li 等[13]确保工人和用户在给定的宽容时间内到达匹配的工作场所。

另外，任务规划问题也是时空众包研究的一个重要领域。潘庆先等[14]提出了一种自适应阈值的禁忌搜索算法，能减少任务分配中的移动成本。Deng 等[15]旨在为工人找到最大化执行任务数量的工作时间表。Tao 等[16]研究在用户能及时到达目的地的前提下完成众包任务并使效用最大化。Wu 等[17]基于遗传算法提出一种尺度自适应适应度评估方法，并解决计算成本较高的众包配送调度问题。

1.2 遗传算法

遗传算法[18]是借鉴大自然进化过程而提出的一种启发式搜索方法。其基本思想是采用优胜劣汰、适者生存的自然法则选择个体，通过交叉、变异等方式来产生新一代的种群，逐代进化，直到满足终止条件。

GA 最核心的问题就是编码。目前传统编码方法包括二进制编码、排列编码、值编码和树形编码等。其中树形编码中每个染色体是由多个对象组成的树，比如程序语言中的函数或者命令[19]。这些编码的相似点是每个基因都只涉及一个对象，且前后基因具有关联，因此易于实现。

目前也出现了许多GA 的变体，包括针对编码形式、交叉变异算子的改进等[20]。GA 还可以被应用到多目标优化问题中，如带精英策略的快速非支配排序遗传算法(nondominated sorting genetic algorithm II，NSGA-II)[21]。GA 可以很容易地与其他优化算法结合，达到更好的性能，如模拟退火算法、贪心算法等。

由于GA 的并行性、可扩展性等特点，被广泛应用于组合优化中的非确定性多项式(nondeterministic polynomial，NP)难问题，如运筹管理、多媒体和无线网络等领域。

2 问题描述

2.1 基本定义

定义1众包任务。众包任务定义为t=＜lt,rt,ut,bt,et,st＞，表示任务的位置为欧式空间中的一个点lt，其移动范围为以lt为圆心、以rt为半径的区域，报酬为ut，出现时间为bt，截止时间为et，工作时长为st。

定义2众包工人。众包工人定义为w=＜lw,rw,cw,qw,bw＞，表示工人的位置为lw，移动范围是以lw为圆心、以rw为半径的区域，容量为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]易知空间众包环境下的3 类对象在线任务匹配问题是NP 难问题，只能求得近似解。

3 延迟贪心算法

贪心算法每次一有新对象到来，就立即为其分配当前最优匹配。众所周知，在众包在线分配问题中，对象到达顺序的不同会直接影响匹配的效用。3 类对象在线分配问题在现实应用中对响应时间的要求不是很高，因此可以通过延长一定的任务匹配时间，等待尽量多的地点和工人加入到在线平台后再进行匹配，这样可以获得更好的效用。文献[12]提出了一种延迟匹配算法，仅仅当任务达到最长等待时间后才对任务进行稳定匹配，与本文场景不同。本文将其扩展到ODAT 问题中，延迟贪心算法的伪代码如算法1 所示。

算法1延迟贪心(delay greedy, DG)算法

输入：任务集T，工人集W，工作地点集P，效用函数U(.,.,.,)

输出：全局任务匹配结果集M

For each 新出现的众包对象vdo

更新任务完成情况

初始化未匹配的在线任务集、工人集、地点集

Mwait← {满足所有约束的任务匹配}

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

end

returnM

由于本文将工人动态分配给任务，所以每次任务完成后，需要释放工人和地点，使他们能够参与到下次的匹配。在每次新对象到来后先检查并更新任务完成情况，实际应用中可设置倒计时或者进行手动释放。

在大多数算法[5-6,10]中，会将多个容量的对象分解成多个单容量对象，但这样会增加算法量级。虽然地点有容量，但是在进行匹配时，只需将其作为一个对象，最后将所有可能的匹配按照效用排序，并依次安排到空的工位上，实验表明这样能大幅降低时间复杂度。注意每次加入匹配前需要再一次判断是否满足约束，因为候选匹配集中可能有一个任务和多个地点工人匹配的情况，每次一旦加入最大效用的一组匹配后，已经匹配的对象就不能再参与匹配了。排序的作用是防止小效用的任务占用了大效用的任务可匹配的工人或者地点。

算法复杂度：对于每个新出现的众包任务t∈T、众包工人w∈W和众包工作地点p∈P，时间复杂度是O(|T||W||P|)。算法需要记录所有可行匹配和3类对象的信息，空间复杂度是O(min(|T|,|W|,|P|×cp))。

4 改进算法

延迟贪心匹配算法可认为是在线3 类对象匹配中的局部最优算法。但是其复杂度过高，无法在短时间内得出结果，这违背了众包在线分配的实时性要求。因此本文提出了基于混合遗传算法的延迟匹配算法，可以大大减少复杂度，同时还提出了延迟阈值策略来增加效用。

4.1 混合遗传算法

4.1.1 编码与解码

本文将解直接设为1 个个体，每个染色体是1 组三维匹配，每对匹配是1 个基因。由于1 个基因又由3 个对象组合，每次生成新解和变化解都需要考虑到3 个对象的变化。最简单的方式是每次在未匹配的任务、工人、地点中随机选出3 个作为一对匹配，但是显然由于存在范围约束，这会导致大量无用解的产生，需要很多次迭代才可能成功产生一个可行匹配，收敛速度极慢。

通过对约束的分析可以发现，约束只存在任务与地点、工人与地点之间，任务与工人之间是无约束的，如果需要设置等待时间，则这个约束可以在产生新匹配的时候进行判断，因为它需要任务和工人的参与。因此本文将3 类对象构造为1 个任务森林结构，可以将有约束问题转化为无约束问题，能大概率保证解的成功产生。如图1所示，其中每个任务作为1 个树根，树的左子树是满足约束的地点，地点的右子树是满足约束的工人。树根的顺序以及左子树和右子树上的结点顺序直接按照到达顺序排列即可。同时，为了进一步优化后续搜索的速度，可对任务森林进行剪枝，将地点左子树为空的任务结点删除，如将图1 的26 号结点删除。任务森林类似树形编码方式，但是任务森林一旦确定，不可改变，因此无法通过交换部分子树等方法实现交叉操作。通过构造任务森林结构可以不断缩小可行解范围，这样任务森林的深度和广度都不会很大，可以提高随机生成初始解的成功概率和搜索速度。

图1 任务森林结构

本文使用随机方法产生新的基因，但在初始化和搜索过程中会导致优秀基因被重复挑选，相同基因重复会导致种群多样性下降。如果每次都与种群中的所有个体比较，判断是否产生重复匹配，每次需要比较3 个对象会耗费大量时间。为了保证每个个体中基因的无重复性，本文为每个个体设置3 个全局标记矩阵，可以保证个体中没有重复匹配。其中任务和工人每次只能匹配1 次，标记矩阵初始设为-1，匹配成功设为1；地点矩阵具有容量属性，初始化为未工作的工位数量，每次匹配成功则减1。

4.1.2 初始解的生成

由于是在线匹配问题，因此不固定种群规模，而是设置每轮最大种群规模数为未匹配任务的个数。借鉴蒙特卡罗树搜索[22]中模拟过程的思想，将每个未匹配任务作为起始节点，交替随机扩展任务和地点节点，直到没有节点可扩展。若地点结点上存在右子树，通过局部最优算子确定工人，此时确定一个匹配；若地点节点无可匹配工人，则更换地点节点重新扩展；若连续Smax次适应度不变，则停止模拟。

以图1 中的任务森林为例，当前有4 个未匹配任务，所以需要模拟4 次。从任务22 号出发，当前有2 个地点可扩展，随机选择一个4 号地点，并选择最大效用的工人，确定一次匹配。接下来扩展任务节点，当前有3 个任务可扩展，随机选择18 号任务，它有1 个8 号地点可扩展，以此类推直到22 号任务结点模拟结束。部分模拟过程如图2 所示。

图2 模拟过程

通过随机模拟生成初始解，可以给每个未匹配任务同等优先选择地点的权力，从而使初始解的多样性最大化。

4.1.3 遗传算子

使用局部最优算子、双重变异算子和随机部分重启机制逐代进化，同时融合贪心算法，只有搜索到比当前适应度更大的匹配时才变异基因。这种方式可以保证种群朝最优方向进化，加快收敛速度。

局部最优算子：确定好地点节点之后，遍历其右子树，找到当前未匹配且适应度最大的工人。

p 变异算子：在每个任务树的左子树上进行随机搜索其他地点节点。

t 变异算子：在任务森林中随机搜索，寻找新的任务节点。

随机部分重启机制：保留大于种群平均适应度的个体，具体如图3 所示。对于小于种群平均适应度的个体，在染色体上随机设置2 个重置点，将重置点中间的匹配进行释放，然后重新随机生成新的匹配，该算子有助于跳出局部最优解。

图3 随机部分初始机制

4.1.4 算法伪代码

设最大迭代次数Emax，同时若连续Tmax次种群最大适应度不变，则提前停止迭代。使用效用函数作为适应度函数，目标是找到适应度最高的种群。混合遗传算法的伪代码如算法2 所示。

算法2混合遗传算法

输入：任务集T，工人集W，工作地点集P，效用函数U(.,.,.,)

输出：全局任务匹配结果集M

For each 新出现的众包对象vdo

更新任务完成情况

初始化未匹配的在线任务集、工人集、地点集；初始化任务森林；初始化标记矩阵

生成初始解

fori=0:Emaxdo

p 变异

t 变异

随机部分重启机制

若连续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 实验设置

实验环境：处理器为2.9 GHz AMD Ryzen 7 4800H with Radeon Graphics，内存容量为2 GB，操作系统为CentOS Linux release 7.5.180 4 (Core)，编程语言为c++。

为验证本文算法的有效性，从时空众包平台gMission[23]收集真实数据。由于缺少预估工作时间和工人容量，采用合成数据，3 类对象匹配多是理发和运动，设置工作时间默认值为[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 个地点，需要在线实时分配，数据规模大，有效覆盖范围矩阵是稀疏矩阵，在进化过程中会产生大量失败匹配和重复匹配，需要迭代多次才能搜索成功；因而NetGA 算法无法应用到ODAT 问题中。

5.2.2 消融实验

在这组实验中，首先对比蒙特卡罗模拟初始化和随机初始化(GA-RI)的实验结果，然后验证去除随机部分重启机制(GA-NoRestart)后的实验结果，实验结果如图5 所示。算法的效用和匹配数如图5(a)和图5(b)所示，可见当使用随机生成初始解时效用小于使用模拟方法生成的初始解，这是因为随机生成需要确定种群规模大小，而每次匹配时在线的对象数都是不确定的，同时随机方法会导致部分优秀解的丢失，而去除随机部分重启机制后效用会有所降低；运行时间和内存占用如图5(c)和图5(d)所示，去除随机部分重启机制会降低运行时间，内存占用都一样。

图5 消融实验对比结果

5.2.3 改变阈值

在本组实验中，对比延迟阈值策略和固定阈值策略在DG 算法和GA 算法这2 种匹配方式上的结果，其他参数使用表1 中的默认值。改变阈值的实验结果如图6 所示。算法的效用和匹配数变化情况如图6(a)和图6(b)所示：显然使用延迟阈值策略的算法效用随阈值增大而增加，且能保持匹配任务数稳定；而使用固定阈值策略的算法效用则会在达到峰值后迅速下降，匹配数也会随之减少，DG 算法的效用略高于GA 算法。运行时间曲线如图6(c)所示，DG 算法的运行时间高于GA 算法，同时延迟阈值策略的运行时间高于固定阈值策略。内存占用变化曲线如图6(d)所示：DG 算法的内存占用明显高于GA 算法，因为DG 算法需要存储所有可行的匹配。

图6 改变阈值实验对比结果

由以上分析结果可以看出，延迟阈值策略在效用和匹配数上明显优于固定阈值策略。虽然运行时间较长，但是设置合适的阈值可以保证运行时长在可接受范围内。

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)所示，随着工人容量的提升，所有算法的效用先逐渐增加然后不变，这是因为每次会选择最优匹配的工人；运行时间和内存占用如图8(c)和图8(d)所示：DG 算法的运行时间和内存整体都高于GA算法。

5.2.6 改变延迟时间

在这组实验中，改变算法的延迟时间，其他参数使用表1 中的默认值。改变延迟时间的实验结果如图9 所示。

图9 改变延迟时间实验对比结果

算法的效用和匹配数如图9(a)和图9(b)所示，随着延迟时间的增加，所有算法的效用也会随之增加，因为可匹配的对象数量增多，可选择的范围也更大，其中使用DeFixed 策略的算法的效用和匹配数都始终优于其他算法；运行时间如图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)所示，随着任务数量的增加，所有算法的效用和匹配数都在增大，这是因为未匹配任务数量增加；随着工人数量的增加，算法的效用和匹配数会先增加后逐渐平缓，因为算法会优先选择高效用的工人，其中使用DeFixed 策略的算法效用最大。运行时间如图11(c)、图12(c)所示，所有算法的运行时间都随着数量增加而增加，其中DG-DeFixed 算法运行时间增长最快。内存占用如图11(d)、图12(d)所示：DG 算法逐渐增加且消耗最多，GA 算法稳定在较低水平。

图11 改变任务数量实验对比结果

图12 改变工人数量实验对比结果

5.2.9 改变等待时间

本组实验改变用户的可容忍等待时间，其他参数使用表1 中的默认值，实验结果如图13 所示。

如图13(a)和图13(b)所示，所有算法的效用随等待时间波动，特别在等待时间等于5 min 时，匹配数大多有所下降，这是因为限制的条件过小不满足的匹配较多；如图13(c)和(d)所示，使用DeFixed 策略算法的运行时间最长，在等待时间等于5 min 时运行时间骤增，DG 算法的内存占用均高于GA 算法。

5.2.10 测试算法的可扩展性

本组实验使用合成数据集测试在大规模数据量且服务质量和报酬具有不同分布下算法的效果，实验结果如图14 和图15 所示。

图14 改变对象数量（均匀分布)实验对比结果

图15 改变对象数量（正态分布）实验对比结果

算法的效用和匹配数如图14(a)和图14(b)、图15(a)和图15(b)所示，所有算法的效用和匹配数都随数量增加而增加，其中使用DeFixed 策略的算法效用高于其他算法；运行时间如图14(c)、图15(c)所示，DG-DeFixed 的运行时间过长，甚至可能无法满足在线匹配的实时性需求，但是GADeFixed 算法的运行时间远远小于DG-DeFixed 算法；内存占用如图14(d)、图15(d)所示，DG 算法的内存消耗远远多于GA 算法，因为随着数据规模的增长，其存储的匹配也增加。

5.3 实验总结

本文使用真实数据集和合成数据集对算法的效用和效率进行了实验。整体来看，GA-DeFixed算法的实验结果、运行速度和内存消耗均优于其他算法。实验首先对比了NetGA 算法，说明其无法应用于本文场景，同时对GA 算法做了消融实验；然后将DeFixed 策略和Fixed 策略进行对比，证明DeFixed 策略在效用和匹配数上优于Fixed策略；后续实验中，通过改变不同参数，可以发现DeFixed 策略的效用高于其他阈值策略，且GA 算法的运行时间和内存消耗少于DG 算法。通过在合成数据集上的可扩展性测试可以发现，虽然DG 算法能获得最优的效用，但是在数据规模较大的场景下，无法满足实时性，运行时间和内存消耗都远高于GA 算法；GA 算法虽然获得次优解，但是使用DeFixed 策略的GA 算法在效用上高于其他算法，并且运行时间和内存占用都较少。

6 结论

本文研究新型时空众包平台中3 类对象在线匹配问题，针对工人工作时长对后续匹配任务的影响，提出了考虑工作时长的在线3 类对象动态匹配问题。

1）通过分析3 类对象的结构和组合关系，提出了一种混合遗传算法对问题进行求解，并分析多种阈值策略的影响，提出了延迟阈值策略进一步提升效用。

2）对现有算法进行改造以适应本文场景，通过在真实数据集和合成数据集上的实验，验证了该算法在降低任务分配时间、提升分配效用上具有良好的表现。

在未来工作中，首先要进一步研究时间复杂度和效用之间的平衡；其次将探索更加广泛适用于众包场景的通用模型，考虑用户、工人和平台的多方利益，切合实际意义。