考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解

* ，3

（1.合肥工业大学管理学院，合肥 230009；2.过程优化与智能决策教育部重点实验室（合肥工业大学），合肥 230009；3.北方民族大学，银川 750021）

0 引言

众包（Crowdsourcing）是Howe［1］提出来的，即把以前需要特定员工完成的工作发布在一个公开的平台上，外包给那些自愿来完成这些工作的非特定的群众志愿者的做法。由于互联网技术和共享经济模式［2］的飞速发展，新的众包模式逐渐产生并发展，若要完成这类新的众包任务往往要求要在指定时间前到达指定任务地点。这种自传统众包技术发展而来且融合了时空信息的新模式被称为时空众包（Spatio-temporal Crowdsourcing），也被称为空间众包（Spatial Crowdsourcing）。空间众包采用一种集合群体智慧的方式完成带有时空信息的任务，在近年来被广泛推广，其应用领域也在不断扩展，目前在交通、物流等领域都有所涉及。日常使用的滴滴出行、百度外卖、饿了么等软件都属于空间众包平台。

空间众包中包含三个关键问题［2］，分别是任务分配、质量控制和隐私保护，本文的研究重点是任务分配。任务分配指的是，充分考虑任务请求者和空间众包工作者的时间和空间属性，以及众包任务的特点，由空间众包平台为每个任务请求者匹配最佳众包工作者来完成任务。国内外众多学者均有对空间众包任务分配问题进行研究。文献［3］从全局最优的角度最大化总任务数目，并考虑了工人需要在完成任务后于截止时间前返回出发点的约束，设计了一种启发式深度优先搜索算法；文献［4］为了提高空间众包中多类型任务的完成数量和质量，设计了一种多类型任务分配方法；文献［5］将任务分解成可高效完成的子任务，以提高任务完成概率；文献［6］为了解决一种空间众包中的在线任务分配问题，提出先采用k近邻算法选择候选工作者，再采用一种阈值选择算法；文献［7］为了减少进行任务分配的随机性同时提升效用值，设计了一种基于统计预测的自适应阈值算法；文献［8］为了解决在设定的一定预算条件下最大化可靠性分配，以及在一定可靠性要求下最小化成本分配两种优化问题，提出了一种贪婪策略；文献［9］为了选择效用值更大的工人和任务之间的组合，设计了一种贪婪策略；文献［10］建立了一种质量敏感的应答模型，并设计了众包数据分析系统，可以更准确地满足用户需求；文献［11］将质量控制的目标定为每个匹配的众包任务和众包参与者之间的时空距离，进行在线实时任务分配。上述国内外学者对任务分配的研究既包括静态任务分配也包括在线任务分配，但大多从工作者角度尽可能提高任务完成概率、最大化任务完成数量、最小化任务成本等，将其作为空间众包质量控制的考虑指标，缺少从任务请求者对工作者评价高低的角度考虑其对一定的时空环境下任务分配质量的影响的研究，而本文致力于从这个角度出发考虑空间众包任务分配问题。

群智能优化算法主要模拟自然界中生物的群体行为，通过个体间信息交流、学习与合作，将有限的个体经验与智能通过相互作用达到整体远大于个体之和的效果，实现寻优的目的。经典的群智能优化算法有遗传算法（Genetic Algorithm，GA）［12］、粒子群优化（Particle Swarm Optimization，PSO）算法［13］、人工鱼群算法、萤火虫群优化（Glowworm Swarm Optimization，GSO）算法等，许多学者在研究最优化问题时经常使用。但部分算法也存在一些缺陷，如遗传算法通常效率比较低下、易出现过早收敛；PSO 算法容易产生早熟、局部寻优能力差；人工鱼群算法也收敛较慢。而GSO 算法具有便于操作、实现简单且具有较好的全局寻优能力等优点，所以本文重点研究此种算法。GSO 算法由Krishnanand 等［14］于2005 年第一次提出，该算法通常被应用于解决连续性问题，文献［15］为了丰富种群的多样性，设计了一种基于混合变异的GSO 算法；文献［16］使用Spark 框架实现了GSO 算法，并利用几种多模态基准函数对不同维数的Spark-GSO 算法进行了评价，验证了算法的有效性。对于离散性问题，例如组合优化问题，研究者们通常改进算法，以使其适用于解决该类问题。文献［17］改进GSO 算法来处理烟草香级集成分类问题，提高了分类准确度；文献［18］为了求解旅行推销员问题，改进萤火虫的编码和解码方式以及个体间距离计算方式，并引入局部路径优化算子；文献［19］重新定义了离散型人工萤火虫算法中的距离，且使用了一种新的扰动机制增加了萤火虫种群的多样性，用于解决旅行商问题；文献［20］为了解决复杂的组合优化个性化推荐问题，改进GSO 算法，设计了一种混合的多目标模型，并构造深度神经网络来分析候选服务并提供个性化推荐；文献［21］改进了离散型萤火虫群优化（Discrete Glowworm Swarm Optimization，DGSO）算法用于处理飞行器三维路径规划问题；文献［22］为了提高带有时间窗的多目标车辆路径规划问题的求解质量，先对带有不同时间窗的用户进行分类，有效提升了时间效率。上述国内外学者的研究将改进后萤火虫群算法应用在求解连续性问题和离散型问题时算法性能均有一定的提升，但在算法的收敛速度和全局寻优能力方面还有待提高。而本文所提出的在一定时空环境下的空间众包任务分配问题可以采用此算法进行求解，并对算法的初始化策略、位置移动策略、邻域搜索策略等进行改进和优化，提高算法的收敛速度和全局寻优能力，也就可以提高空间众包任务分配的效率和质量。

鉴于实际生活中用户每次使用“滴滴出行”软件后会为司机服务进行评价，本文将司机所得到的星级等级评价转化为服务质量评价得分，并将该要素加入到影响整体任务分配总得分的条件约束中；同时，提出空间众包工作者评价更新机制，即工作者每成功接单一次，将根据当前服务质量评价得分和历史评价得分更新工作者得分；考虑空间众包工作者的服务质量评价得分和时空成本，将任务分配质量总得分最高作为优化目标，并采用改进的离散型萤火虫群优化（Improved Discrete Glowworm Swarm Optimization Based on Worker ' s Evaluation Score，IDGSOBWES）算法来解决。

1 考虑工作者服务质量的任务分配策略

1.1 问题描述及所包含要素的描述

下面给出具体问题描述：本文设定一个类似于“滴滴出行”中选择打出租车需求的场景，空间众包任务被任务请求者发布在空间众包平台上，空间众包工作者待命，平台实时进行空间众包任务和空间众包工作者之间的任务分配。本文基于实际问题，生活中每次打车结束，用户会根据司机的服务给出评价，评价结果反映在软件上，于是考虑将司机所得到的星级评价经处理转化为数字化的服务质量评价得分，并将此项业务要素加入到任务分配策略中，以任务分配质量总得分最高为优化目标，找到任务与工作者之间的最佳匹配。同时本文采用批处理的方式，将所研究的时空区域划分为多个连续区域，每个区域由一个时间戳和一定的地理面积组成，作为一个时空环境，每个时空环境下的任务分配周期性不断进行，形成动态任务分配。

本文所设定的问题情境包含以下要素：任务请求者、空间众包任务、空间众包工作者、空间众包平台、任务分配总得分、时空环境。表1给出上述所提及的要素的具体描述。

表1 空间众包任务分配所包含要素Tab.1 Elements included in spatial crowdsourcing task allocation

1.2 工作者的服务质量星级评价转化为数字化评价得分

在实际生活中，使用“滴滴出行”之后，乘客（任务请求者）需要给提供服务的司机（空间众包工作者）在“滴滴出行”软件上进行评价，本文将此星级评价信息通过数据处理转化为数字化评价得分，数值范围是（0，100］分。每个空间众包工作者的评价得分高低与他的服务质量成正比。表2 给出空间众包工作者的星级评价及其对应的数字化评分范围。

表2 星级评价与评价得分对应表Tab.2 Correspondence table of star rating and evaluation score

1.3 空间众包工作者评价得分更新机制

在引入工作者的服务质量评价得分要素后，为了更真实地反映该要素对任务分配质量的影响，设置空间众包工作者评价得分更新机制，及时更新工作者的评价得分，评价得分高的工作者将被优先考虑安排任务。空间众包工作者目前评价得分大小是由历史完成任务后所得评价转化得到的评价得分，每次成功地完成任务分配后，应该根据当前任务完成之后任务请求者给工作者的评价，实时更新工作者评价得分。每当空间众包工作者成功完成当前分配的任务后，空间众包平台使用加权平均更新空间众包工作者评价得分，对历史得分和当前完成任务后所获得的新的得分加权，从而得到最新得分。空间众包工作者为了能顺利接单，将致力于提升自身服务质量以获得更高的得分；由此，一方面可以改善任务分配质量，另一方面也在一定程度上达到了激励工作者的效果。假设由历史数据处理得到的工作者评价得分用grade_now表示，每成功完成接单任务后新的得分用grade_new表示，则每次任务分配结束并完成任务后，更新当前工作者评价得分为：

其中：k表示工作者的第k次分配；α表示权重系数，α的大小不同，表示历史得分对当前得分的影响大小不同。根据式（1）可得，空间众包工作者想要成功分配到任务，需要持续高质量完成任务以获得更高的评价得分，这样可以实现高质量的任务分配同时激励工作者认真完成任务。

如表3 所示，这是在一次成功的任务分配后工作者当前评价得分的更新情况，其中加黑的数字表示该工作者成功接单并更新了当前数字得分。15个工作者中有10个成功接单，每个工作者完成质量不同，得到的新的得分也不同，完成质量高的工作者评价得分会升高，评价得分高且距离近的工作者下次将被优先分配任务，或距离相等评价得分高的工作者也将被优先分配任务。

表3 工作者评价得分更新Tab.3 Update of workers’evaluation score

1.4 加入工作者服务质量评价得分机制的任务分配模型

在某一时空环境下，任务请求者在空间众包平台上发布了数量为m的待完成空间众包任务，此时待命的空间众包工作者数量为n（由于本文在空间众包任务分配中加入了空间众包工作者的服务质量评价业务要素，故假设m小于n，由此可以根据空间众包工作者评价得分高低优先考虑分配哪个工作者），只考虑当前所处时空环境，对空间众包任务和工作者进行匹配，空间众包任务数量为m，考虑从n个工作者中选择m个，共有种可能，在一次空间众包任务分配后有m个任务与工作者的组合，共有m！种组合，所以归类为NP难问题，而本文是将任务分配总得分最高作为最终的优化目标，因而可以整理为如下模型，即加入空间众包工作者服务质量评价得分机制的任务分配模型，具体如下：

其中：∑G表示所有被选择匹配的空间众包工作者的服务评价得分总和；∑L表示所有被匹配的工作者总旅行成本之和；∑LT表示在指定的匹配结果中工作者未能在指定时间内到达任务位置的消耗总和；m表示某个时空环境下的新发布的空间众包任务的数量；n表示某个时空环境下的正处于空闲的空间众包工作者的数量（m，n为正整数，由于要考虑按工作者评价得分挑选工作者，故假设m＜n）；在此模型中，由于假设的前提条件是m＜n的，说明在一个时空环境中，所有的空间任务都将被分配给相应工作者去完成，而每个工作者想要接单必须满足一定条件，这在一定程度上充分调用了工作表现比较优秀的工作者，对优秀工作者的利用率将达到比较高的水平，相对来说，表现较差的工作者将得到平台较低的调用机会，而上述1.3 节中设置的工作者评价得分更新机制，具有鼓励工作者努力提高评价得分来达到接单目的的效果，激励每个工作者都成为优秀的工作者，所以这说明此模型对平台方进行任务分配来说，优秀工作者的资源利用率是较高的；M表示某个时空环境下所有m个空间众包任务的集合；NM表示某个时空环境下m个（从n个工作者中选出m个）空间众包工作者的集合，集合中共有m个元素，且集合共有种可能；i表示集合M中的第i个任务；j表示集合NM中的第j个工作者；jmin表示集合NM中最小元素，jmax表示集合NM中最大元素；Li，Lj在面积S范围内；Li=(xi，yi)表示第i个空间众包任务的位置数据；Lj=(xj，yj)表示第j个空间众包工作者的位置数据；ManhaDis()表示以曼哈顿距离计算方式计算；Lij表示某成功的任务分配中第i个任务匹配第j个工作者，其中，第i个空间众包任务与第j个空间众包工作者之间的距离；Gij表示与第i个空间众包任务匹配的第j个空间众包工作者的评价得分，vj表示第j个工作者行驶速度，在此模型中，将每个工作者的行驶速度设置为定值，是为了保证面对同一距离的任务，其他条件一致的情况下，每个工作者完成任务需要的时间是一致的；表示任务请求者所能接受的任务工作者赶到任务地点最多所用时间。

2 GSO算法及其改进

2.1 基本GSO算法

基本GSO 算法是依据萤火虫个体及群体的行为动作设计的算法。算法中，每个可行解由每只萤火虫所处的位置表示，越亮的萤火虫其所处位置越好。对每只萤火虫而言，低亮度的萤火虫会向比自身亮度高的萤火虫靠近，来搜索更佳的位置，而萤火虫越亮，它吸引其他萤火虫的可能性也越高。GSO算法寻优过程大致如下：

1）变量初始化：N（N表示种群规模）个萤火虫随机置于可行域内，初始荧光素为l0，荧光素消失率ρ，荧光素更新率γ，固定步长s，邻域阈值nt，初始感知半径rs，初始决策半径rd，决策半径更新率β，最大迭代次数iter_max，每次迭代控制变量t。

2）更新荧光素：li(t)代表在第t次迭代时萤火虫i的荧光素值，J(xi(t))代表在第t次迭代时萤火虫i所处位置的目标函数值。

3）寻找萤火虫i的邻居集合：Ni(t)代表在第t次迭代时萤火虫i寻找的邻居集合代表在第t次迭代时萤火虫i的决策半径。

4）采用轮盘赌的方式判断萤火虫i接下来的移动方向：j=max(pi)表示其根据邻域确定的移动方向，其中pi=(pi1(t)，pi2(t)，…，pij(t)，…(t))，pij(t)表示萤火虫i以多大概率向萤火虫j方向移动。

5）更新位置：xi(t+1)代表第t+1 次迭代时萤火虫i的位置。

2.2 基于工作者评价得分的改进的离散型GSO算法

2.2.1 算法的离散化

通常GSO 算法被用于处理连续空间的问题，当引入此算法来处理空间众包任务分配问题时，需要进行离散化，对算法的解及初始化进行离散化处理，并采用适当的整数编码机制和编码更新规则，改进算法的位置更新策略和邻域搜索策略，从而让该算法适用于处理本文问题，使其具有更好的收敛速度和寻优能力。

2.2.2 算法的优化目标

考虑空间众包工作者服务评价的任务分配，优化目标是使任务分配质量总得分尽可能高，既考虑所有匹配了的空间众包工作者评价得分总和，又考虑相互匹配的工作者到任务地点旅行成本总和，另外还考虑工作者是否能在任务要求最迟开始时间之前开始执行任务，因此，在目标函数中加入惩罚因子，利用线性加权变多目标为单目标，优化目标为使任务分配总得分最高，表示如下：

其中：0 ＜r1，r2＜1，r1+r2=1，r1，r2表示所占权重；c1、c2表示为了统一量纲的常数；TD表示任务分配结果总得分；G表示当前任务分配中所有被分配的空间众包工作者评价得分总和；L表示任务分配中所有工作者完成指定任务消耗的总旅行成本；LT表示工作者到任务地点的距离成本总和，能够在任务最迟开始时间之前到达任务地点的工作者才属于符合要求的工作者，将不计成本，但不符合要求的工作者需要再加上额外的距离成本。

2.2.3 算法的离散及改进

1）算法与任务分配问题的对应及初始化。

在改进的算法中，将任务分配的组合设置为：xi(t)=[xi1(t)，xi2(t)，…，xim(t)]，表示在第t次迭代时第i个萤火虫的一种任务分配组合。其中，m表示待完成的空间任务的数量。为了清楚地表示一组空间任务与空间众包工作者之间的任务分配，将每只萤火虫初始化为一个m维的向量，每只萤火虫的位置代表一种m个空间任务和m个众包工作者之间的匹配。在进行初始化时采用随机的方式。例如：某一时空环境下，有10个新发布的空间任务（序列号1～10），15位空闲的空间众包工作者（序列号1～15），那么其中一个初始化的随机解为xi(t)=[5，3，9，12，7，1，8，15，4，6]，表示从15个工作者中随机选择10 个来执行任务，每一维度的数字即表示任务序列号，而每一维度上对应的数字即表示工作者的序列号。因此，此解表示，第5 个工作者分配了第1 个任务，第3 个工作者分配了第2 个任务，第9 个工作者分配了第3 个任务，…，第6 个工作者分配了第10个任务。

2）算法中距离计算公式。

萤火虫i与萤火虫j之间距离以汉明距离公式计算。因此，萤火虫i的第k维与萤火虫j的第k维之间的距离，萤火虫i与萤火虫j之间的距离，分别表示为：

其中1 ≤k≤m。

3）算法中更新位置公式。

得到初始解后，萤火虫i将与邻域内最优萤火虫的每一维对比，以概率p1保持第k维编码不变，以p2-p1的概率变为与最优萤火虫相同，以1-p2的概率随机变化；如果出现了编码重复的情况（即一个工作者同时被分配了多个空间众包任务，这显然不符合“空闲工作者同一时间只能接受一个众包任务”的约束条件），则找出与最优萤火虫相同维度上不同编码及其维度，将不同编码重新以随机的顺序排列并按序放入刚刚的维度上。如下所示：随机一只萤火虫i的初始解xi(t)=[12，8，5，7，2，11，15，9，3，6]，萤火虫i的邻域内最优萤火虫xj(t)=[1，9，4，10，3，15，7，8，2，13]，萤火虫i根据式（3）～（9）靠近邻域内最优萤火虫，进行第一次位置更新，得到xi(t)=[12，8，4，7，3，11，7，9，10，13]，当中出现了重复编码情况，按前面所述规则重新进行编码更新，萤火虫i更新当前位置为xi(t)=[10，9，4，2，3，8，7，15，1，13]，此时编码不再有重复。

4）算法中邻域搜索优化策略。

第一种：引入交换变异算子策略。

对萤火虫i，随机从它的m维中挑选两个维度，第p维和第q维，将其对应维度上的编码交换。例如，对萤火虫i，xi(t)=[5，3，9，12，7，1，8，15，4，6]，随机产生两维（3，7），即p=3，q=7，两维度上对应的数字分别为9 和8，将两个维度上的数字9和8 位置交换，则执行交换变化后萤火虫i的编码变为xi(t)=[5，3，8，12，7，1，9，15，4，6]。

第二种：引入插入变异算子策略。

对萤火虫i，随机从它的m维中挑选两个维度，第p维和第q维，将第q维上的编码移动到第p维上，第p维及之后维度上的编码往后顺延。例如，对萤火虫i，xi(t)=[5，3，9，12，7，1，8，15，4，6]，随机产生两维（3，7），即p=3，q=7，两维度上对应的数字分别为9 和8，将第7 维上的数字8 移动到第3维上，第3维上的数字9移动到第4维上，后面维度上的数字往后顺延，则执行插入变化后萤火虫i的编码变为xi(t)=[5，3，8，9，12，7，1，15，4，6]。

第三种：引入反演变异算子策略。

对萤火虫i，随机从它的m维中挑选两个维度，第p维和第q维，将第p～q维上的编码执行反转。例如，对萤火虫i，xi(t)=[5，3，9，12，7，1，8，15，4，6]，随机产生两维（3，7），即p=3，q=7，两维度上对应的数字分别为9和8，将第3～7维上的数字9、12、7、1、8反转变为8、1、7、12、9，重新置于第3～7维上，则执行反演变化后萤火虫i的 编码变为xi(t)=[5，3，8，1，7，12，9，15，4，6]。

2.2.4 算法的执行步骤

本文所提出的基于工作者评价得分的改进的离散型GSO算法的具体执行步骤如下：

步骤1 将各参数值初始化，包括种群规模、荧光素更新率、荧光素消失率、感知半径、决策半径、最大迭代次数等。

步骤2 根据新发布的任务数m，空闲工作者数n(m＜n)，确定萤火虫维度m，根据2.2.3 小节中1）生成初始任务分配组合。

步骤3 根据式（4）计算荧光素值，并标记初始最亮萤火虫到公告板。

步骤4 根据式（10）、（11）计算距离，并根据式（5）、（6）寻找移动方向；若未找到邻域萤火虫，即式（5）求得结果为空集合，则以随机概率执行2.2.3 节4）中所述策略中的某一种再进行新的邻域搜索。

步骤5 不再使用式（7）更新位置，而采用式（12）位置更新公式更新萤火虫每一维度上的编码。

步骤6 根据式（8）更新决策半径。

步骤7 计算萤火虫新的荧光素值，并与公告板标记的值相比，若比该值大，则更新公告板的值。

步骤8 当达到最大迭代次数或最优目标时，终止算法，否则转至步骤4。

2.2.5 算法时间复杂度分析

假设在基于工作者评价得分的改进的离散型萤火虫群优化（IDGSOBWES）算法中，步骤1 中最大迭代次数值为iter_max，萤火虫的种群规模为N，每只萤火虫（m维，从n个空闲工作者中选出m个来完成任务）表示一种任务分配组合。在每一次迭代中，算法时间复杂度如下：

步骤2 中为N个萤火虫个体生成初始解，时间复杂度为O(N)；步骤3 中计算N个萤火虫的荧光素值，时间复杂度为O(N)；步骤4 中计算距离，寻找邻居集合，时间复杂度为O(N2*m)，若未找到要进行新的邻域搜索，时间复杂度为O(N*m)；步骤5 中计算萤火虫个体位置更新的时间复杂度为O(N*m)；步骤6 中萤火虫决策半径更新的时间复杂度为O(N)；步骤7中计算新的荧光素值，时间复杂度为O(N)，计算工作者得分，时间复杂度为O(m)，计算任务分配总得分，时间复杂度为O(N*m)；步骤8 中控制循环迭代次数，时间复杂度为O(1)。由于迭代次数为iter_max，那么算法的时间复杂度为O(N2*m*iter_max)。

2.2.6 算法空间复杂度分析

假设在IDGSOBWES 算法中，最大迭代次数值为iter_max，萤火虫的种群规模为N，每只萤火虫（m维）代表一种任务分配组合。在每一次迭代中，算法空间复杂度如下：

在步骤1和步骤2设置初始参数和生成初始解时，空间复杂度为O(N*m)；步骤3 中要存储每个萤火虫的荧光素值，空间复杂度为O(N)；步骤4 中计算距离，寻找邻居集合，空间复杂度为O(N*m)；步骤5 中计算萤火虫个体位置更新的空间复杂度为O(N*m)；步骤6 中萤火虫决策半径更新的空间复杂度为O(N)；步骤7 中要存储荧光素值和总得分，空间复杂度为O(N)。由于迭代次数为iter_max，那么算法的空间复杂度为O(N*m*iter_max)。

3 实验及结果分析

本文实验部分主要分为两部分：第一部分在模拟数据上进行测试，第二部分对经过处理的真实数据进行测试，验证算法的有效性。

3.1 实验设置

实验环境：本文使用Matlab R2016a 软件编写代码并绘图，代码编译运行所使用的计算机参数：操作系统为64 位Windows10、处理器为Intel Core i5-8400 CPU（2.8 GHz），运行内存为8.0 GB。根据Krishnanand 等［23］和倪志伟等［24］的研究，算法参数值设置如表4所示.

算法中参数荧光素消失率、更新率以及决策半径更新率依据文献［23］和文献［24］中的实验研究结果设置，参数邻域阈值、决策半径、感知半径、种群规模、迭代次数则是依据3.2.1 节中的3）参数对算法性能影响的实验所设置，参数工作者的初始速度以及两个统一量纲系数的设置是为了不让结果出现负数，加权系数的设置是依据工作者服务质量和工作者的旅行成本的重要性。

表4 设置实验初始化参数Tab.4 Setting of initialization parameters of experiment

3.2 结果分析

3.2.1 在模拟数据集上测试

模拟数据集设置如下：任务的地理位置信息，在［0，100］范围上随机生成两组位置数据；任务开始最多所需时间、工作者的地理位置信息和工作者当前评价得分，采用上述同样方法随机生成。假设某时空环境下共有10 个空间众包任务（这些任务的时间信息都处于当前时空环境下）和15 个空间众包工作者（此时的工作者的状态恰好都是空闲），随机生成两组空间任务位置数据和两组工作者位置数据，将任务和工作者的地理位置数据组合，形成两组位置信息数据集，同时随机生成一份工作者当前评价得分表，一份任务最迟开始所需时间表。

1）本文任务分配策略与其他策略的对比。

对上述两组空间任务和工作者模拟位置数据分别进行独立重复的20次实验，对比贪婪策略［9］、随机匹配策略及本文所提策略所得到的任务分配总得分。

图1 是分别对两组模拟数据进行20 次实验所得到的结果。

由图1 可以观察到，尽管两组模拟数据集位置信息不同，但对实验结果影响不大，由图1 两组实验图像可知，本文所提出的任务分配策略比随机匹配策略对任务分配总得分的提高具有明显效果，且结果比较稳定，而随机匹配策略得到的任务分配总得分结果则比较跳跃，有高有低，比较分散。对比本来效果就比较好的贪婪策略来讲，本文所提策略在大多数实验次数上表现较优。实验表明本文所提出的任务分配策略和IDGSOBWES算法完全可以用于处理空间众包任务分配问题，具有一定的稳定性和有效性。

图1 两组不同模拟数据集上三种不同策略对比Fig.1 Comparison of three different strategies on two different simulated datasets

2）本文算法与其他算法的对比。

对上述第一组数据，进行20 次独立重复实验，将本文算法IDGSOBWES 与文献［17］中离散型萤火虫群优化（DGSO）算法、文献［18］中离散型萤火虫算法（Discrete Firefly Algorithm，DFA）以及PSO、GA 进行对比实验，分别计算几种算法根据目标函数迭代500 次每一次所得到的平均值，几种算法之间的比较可通过图2展现。

图2 几种算法计算得到的总得分对比结果Fig.2 Comparison results of total scores calculated by several algorithms

从图2 可以观察到，随着迭代次数的增加，五种算法中任务分配总得分均慢慢稳定下来，但本文所提出的IDGSOBWES算法相较其他几种算法的收敛速度明显更快，达到稳定值的速度更快，且任务分配总得分平均值更高，即任务分配质量更高。

再设置几组不同模拟数据集下的实验，模拟数据集的产生方法依然同上述方法相同，设置的模拟数据规模大小分别是：在同一个时空环境下，空间任务20 单，空闲工作者25 个；空间任务50单，工作者60个；空间任务100单，工作者120个；再结合上一组空间任务10 单，空闲工作者15 个的实验，得到各算法间的对比结果如表5所示。

根据上述实验结果分析，在一定规模的模拟数据集上，本文算法计算得到的任务分配总得分总是优于其他四种算法，如在（50，60）的空间任务和工作者匹配结果中，本文算法比DGSO 算法得到的任务分配总得分提高了3.8%，比DFA 提高了20.2%，比PSO 算法提高了4.7%，比GA 提高了5.6%；随着维度的变大，实验效果有减弱趋势，表明本文算法在一定的维度上对解决空间众包任务分配问题具有较优效果。

表5 各算法在不同规模数据集上的实验对比结果Tab.5 Experimental comparison results of different algorithms on datasets with different scales

3）参数对算法性能的影响。

用第一组数据进行实验，对参数感知半径、决策半径、邻域阈值、种群规模以及迭代次数分别进行分析，实验结果如图3所示。

图3 不同参数对实验中任务分配总得分的影响Fig.3 Effect of different parameters on total score of task assignment in experiment

对各参数的分析可知：在图3（a）表明，当感知半径取值12 时，总得分效果最优，因而在规定范围内感知半径取12；图3（b）表明，决策半径为12 时，总得分达到最高，因而在规定范围内决策半径取12。图3（c）表明，总得分先随邻域阈值波动，当阈值达到5 时，总得分开始下降，因而在规定范围内，邻域阈值取5。图3（d）表明，当种群规模到100 左右时，总得分趋于稳定，因而种群规模取100。图3（e）表明，总得分随着迭代次数一起增加，当迭代次数增加到100 左右时，总得分基本不再增加，可知当迭代次数达到100 之后算法性能基本稳定，故迭代次数取100。

3.2.2 在真实位置数据集上测试

真实数据是由 http：//www.dataju.cn/Dataju/web/datasetInstanceDetail/364 地址上获取的纽约出租车管理委员会官方的乘车数据。对该数据集进行处理，去除其中无效值、缺失值，取出实验所需的500 条空间众包任务的位置数据（一个时间戳内取500 条任务数据规模足够），并通过数据归一化处理，将空间任务的位置坐标映射到［0，100］区间，得到用于实验的真实空间任务位置数据，空间众包工作者的位置信息、当前评价得分数据以及任务最迟开始所需时间数据依然采用随机方法生成。分别采用3.2.1 节中的2）中提到的几种算法，解决如下几种情况的任务分配：在一个时空环境下，发布空间任务50 单，存在空闲工作者60 个；空间任务100 单，工作者120个；空间任务200单，工作者250个；空间任务500单，工作者600 个。进行任务分配后，任务分配质量总得分结果如表6所示。

表6 几种算法在不同空间任务和空间众包工作者数目时的总得分对比Tab.6 Comparison of the total scores of several algorithms with different number of spatial tasks and spatial crowdsourcing workers

根据上述实验结果可知，无论考虑任务分配质量总得分的均值还是最大值，在大部分情况下，本文提出的IDGSOBWES算法的结果都比其他四种算法高一些，也存在个别不如其他算法的地方，这表明本文算法具有一定程度的稳定性；当实验数据的维度越来越高，算法的效果会有一定程度的下降；然而直到数据达到500 维，IDGSOBWES 算法求得的任务分配质量总得分还是比DGSO 算法高约6%，故本文所提出的算法对解决空间众包任务分配中问题具有较优效果。

3.3 实验总结

依据上述实验结果分析，发现本文所提出的IDGSOBWES算法在解决考虑空间众包工作者服务质量的空间众包任务分配问题时比贪婪算法和随机匹配算法具有更高有效性，有更大的概率获得更高任务分配总得分，同时在中低维度上表现得比DGSO 和DFA 算法收敛更快，寻优能力更强，同时也比PSO和GA的结果更优，表明本文所提出的算法用于解决空间众包任务分配问题既具备可行性又具有有效性。

4 结语

本文重点研究空间众包任务分配，将空间众包工作者的服务质量评价得分要素考虑到其中，并建立得分更新机制，实现在一定时空环境下更高质量的空间众包任务分配；同时，改进了离散型萤火虫群优化算法，既加快了其收敛速度，也提高了其寻优能力。通过设定的几组实验，既表明本文提出的考虑工作者服务质量的任务分配模型可以提高任务分配总体质量得分，又验证了IDGSOBWES 算法具有较好的收敛性和寻优能力。接下来考虑从任务请求者和工作者两个角度出发继续研究空间众包任务分配问题，并将隐私保护相关内容加入其中。