时空众包中多目标优化任务分配 Multi-Objective Task Assignment in Spatio-Temporal Crowdsourcing

doi:10.12677/CSA.2021.113056

Computer Science and Application
Vol. 11 No. 03 ( 2021 ), Article ID: 41006 , 12 pages
10.12677/CSA.2021.113056

时空众包中多目标优化任务分配

吴胜男

●How to Cite this Article

烟台大学计算机与控制工程学院，山东烟台

收稿日期：2021年2月16日；录用日期：2021年3月11日；发布日期：2021年3月18日

摘要

随着移动网络的快速发展以及配备各种内部传感器的移动设备的普及，时空众包已成为解决基于位置的传感任务的新兴范例。在现有研究中，时空众包系统主要最大化平台效用。为了最大化社会福利，本文提出了一种多目标优化任务分配(MOO-TA)模型，以最大化平台和众包工人的效用，激励众包工人执行偏远地区任务，扩大数据覆盖率。本文提出一种组合算法LWS_NSGA_II，结合传统的线性加权求和(LWS)算法和带精英策略的快速非支配排序遗传算法(NSGA_II)算法，以搜索针对多目标优化任务分配问题的所有可选择的帕累托最优解供平台选择。通过在真实数据集上进行比较实验，评估了该方法的有效性和可行性。

关键词

时空众包，任务分配，多目标优化，帕累托最优解

Multi-Objective Task Assignment in Spatio-Temporal Crowdsourcing

Shengnan Wu

School of Computer and Control Engineering, Yantai University, Yantai Shandong

Received: Feb. 16^th, 2021; accepted: Mar. 11^th, 2021; published: Mar. 18^th, 2021

ABSTRACT

With the rapid development of mobile networks and the popularity of mobile devices equipped with various internal sensors, spatio-temporal crowdsourcing has become an emerging paradigm for solving location-based sensing tasks. In the existing research, the spatio-temporal crowdsourcing system mainly maximizes the utility of the platform. In order to maximize social welfare, this paper proposes the Multi-Objective Optimization Task Assignment (MOO-TA) model to maximize the utility of the platform and crowds workers. It encourages crowds workers to perform crowds tasks in remote areas, and expands data coverage. In this paper, the combination algorithm LWS_NSGA_II is proposed, which combines the traditional linear weighted Summation (LWS) algorithm and the Fast Non-dominated Sorting Genetic Algorithm (NSGA_II) algorithm to search for all selectable Pareto optimal solutions for multi-objective optimization task assignment problems for system selection. Through comparison experiments on real data sets, the effectiveness and feasibility of the proposed method are evaluated.

Keywords:Spatio-Temporal Crowdsourcing, Task Assignment, Multi-Objective Optimization, Pareto Optimal Solutions

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

通过内置在移动设备中的传感器来收集传感数据的时空众包服务已逐渐发展成为一种新颖的分布式问题解决范例。移动设备用于通过收集时空数据来完成众包任务。它要求众包工人移动到指定位置，以根据相关属性离线或在线完成任务。时空众包具有更广泛的覆盖范围，更低的部署成本和更高的可扩展性 [1]。近年来，O2O (在线到离线)领域出现了许多时空众包应用，例如灾难监控，交通管理，公共安全，物流管理和社交媒体 [2]。时空众包系统的结构与传统的众包结构相同，它由任务请求者，众包平台和众包工人组成。他们通过众包平台建立联系，如图1所示。该平台将任务请求者发布的众包任务发送给众包工人。众包工人完成已发布的任务，并将收集的数据上传到平台。时空众包是传统众包的延伸。移动设备用于通过收集时空数据来完成众包任务。因此，时空众包是时空维度上传统众包的一种新形式。

Figure 1. The workflow of a spatio-temporal crowdsourcing platform

图1. 时空众包平台的工作流程

本文主要研究时空众包中最大化社会福利的多目标任务分配。同时，为了吸引更多的众包工人，调动众包工人的积极性，并激励众包工人提供高质量的数据，设计了激励机制。在现有的研究中，大多数任务分配方法都集中在最大化平台的效用上。通常，平台效用的最大化主要取决于以下几个方面：1) 最大化任务覆盖率 [3] [4]；2) 尽量减少预算 [4]；3) 最大化任务的可靠性 [5] [6]。但是，这些研究都是针对最大化平台方面的效用，很少有研究最大化众包工人的效用。在本研究中，我们同时考虑了平台的效用最大化和众包工人的效用最大化，以最大化社会福利。

与位置相关的时空众包任务(例如Gigwalk，Field Agent，Didi Travel和Hungry)需要众包工人移动到指定位置才能完成任务。但是，有些任务位于偏远和不受欢迎的地区，众包工人不愿执行此类任务。为了提高数据覆盖率，有必要扩大感知范围，因此我们鼓励一些众包工人在不受欢迎的地区执行任务。首先，考虑到众包工人的信誉和能力，在两个因素上对众包工人进行评分。本文根据分数的高低设计了众包工人的额外奖励。然后，本文还考虑了位于不受欢迎的区域中的众包任务的执行任务难度值，任务难度值越高，给予的额外奖励越多。此外，本文还考虑了任务执行时间的惩罚和隐私敏感度的补偿。超过正常任务执行时间范围的众包工人将受到惩罚。在一定的隐私敏感度范围内的众包工人将得到补偿，而隐私敏感度范围之外的众包工人将不被雇用，这样做的目的是确保工人按时完成任务的保证收集数据的质量。考虑到上述因素，本文采用传统线性加权求和(LWS)算法和带精英策略的快速非支配排序遗传算法(NSGA_II)的组合算法(LWS_NSGA_II)来找到帕累托最优解集，以最大化平台的效用和众包工人效用。

本文的主要贡献概括如下：

—提出了LWS_NSGA_II算法来解决多目标优化问题，以最大化平台的效用和众包工人的效用。

—根据任务难度值，通过激励策略鼓励众包工人执行位于不受欢迎地区的众包任务，以改善感测数据的覆盖范围。

—真实数据的实验表明，该算法在多目标优化问题上实现社会福利最大化是有效可行的。

本文的其余部分安排如下。在第2节中，讨论了相关工作。第3部分介绍了系统模型和任务分配机制。提议的激励机制将在第4节中介绍。在第5节中，将讨论对比实验和实验结果。最后，第6节总结了结论和说明了未来将要研究的工作。

2. 相关工作

当前，许多关于任务分配的研究涉及多个优化目标。张等 [5] 使用遗传算法研究了最大化查询任务的可靠性和最大化感知任务的覆盖范围的双目标优化问题。王等 [7] 设计了一个工人运动预测模型来研究最大化任务覆盖率和最小化激励成本的问题。在 [8] 中，作者研究了多目标优化激励问题，以最大化数据准确性并最大化数据时空分布。尽管这些是多目标优化问题，但它们的主要目的是最大化平台的效用，而没有同时考虑最大化平台的效用和最大化众包工人的效用。段等 [9] 提出了一个新的分布式MCS框架，通过找到Walras均衡来最大化社会福利。但是，没有考虑众包工人和任务的实际属性，例如众包工人的信誉和完成任务的难度等。在当前的大多数任务分配研究中，要优化的两个目标是矛盾的。如果一个目标得到改善，另一目标将相应减少。换句话说，没有可以同时改善多目标的有效最优解，而是一组帕累托最优解 [10]。当前的研究要么努力优化一个目标，另一个目标作为固定边界约束 [11] [12]，或者基于这两个目标之间的既定权衡确定一种分配方案 [13] [14] [15]。

基于多目标优化的激励机制大多是在固定目标边界约束后优化其中一个目标，或者在多目标优化之前预先指定多目标权衡约束。无论它们是边界约束还是折衷约束，都假定它们是由平台预先定义的。但是，这种假设是不现实的，因为平台无法在众包工人执行任务之前获得众包工人与任务之间的匹配程度以及执行信息。因此，要求平台确定多个目标之间的令人满意的折衷是不现实的。因此，一种实用的方法是针对平台涉及的多目标提供所有帕累托最优解(即帕累托集)，以做出合理的决策。本文的研究是为该平台找到适当的帕累托最优分配解决方案。

3. 问题定义

在本节中，将介绍MOO-TA问题的定义。表1总结了主要符号。

Table 1. Frequently used notations

表1. 常用符号

在本文中，众包工人可以选择多个众包任务来执行，也可以由多个众包工人来执行众包任务。 $W = {w_{1}, w_{2}, \dots, w_{i}, \dots, w_{n}}$ 代表一组众包工人，其中 $w_{i} (1 \leq i \leq n)$ 表示第i个众包工人。一个时隙中的一组众包任务用 $T = {t_{1}, t_{2}, \dots, t_{j}, \dots, t_{m}}$ 表示，其中 $t_{j} (1 \leq j \leq m)$ 表示第j个任务。具体定义如下所示。

3.1. 众包工人

定义1：众包工人。 $W = {w_{1}, w_{2}, \dots, w_{i}, \dots, w_{n}}$ 为n个多属性众包工人的集合。每个众包工人 $w_{i} (1 \leq i \leq n)$ 都是由六个元素组成的元组： $((l o c_{w_{i}}^{x}, l o c_{w_{i}}^{y}), t r_{i}, a b_{i}, p r_{i}, n u m_{i}, n u m_{w_{i}}^{\max})$ 。平台选择一组合格的众包工人S来执行众包任务。众包工人可以选择在一个时隙中执行一组任务 $φ_{i} (φ_{i} \subset T)$ ， $0 < | φ_{i} | \leq n u m_{w_{i}}^{\max}$ 。

在本文中，我们使用Gompertz函数 [16] 来更新信任度 $t r_{i}$ 和能力值 $a b_{i}$ 。Gompertz函数是一种增长曲线函数模型，描述了事物发生，发展和成熟的三个阶段。不同阶段的发展速度是不同的。我们选择此函数来更新信任度 $t r_{i}$ 和能力值 $a b_{i}$ 值，因为它更适合于在人类交互中对信任度和能力值的概念进行建模。Gompertz函数由公式(1)定义。

$f (x) = ω \cdot e^{α \cdot e^{γ \cdot x}}$ (1)

其中 $ω$ 指定此函数的上渐近线， $α$ 控制沿x轴的位移，并 $γ$ 调整函数的增长率。

1) 信任度：在公式(1)中，x是Gompertz函数的变量。本文通过将x替换为 $x_{i}$ 获得 $t r_{i}$ 。 $x_{i}$ 由式(2)计算。

$t r_{i} (x_{i}) = ω \cdot e^{α \cdot e^{γ \cdot x_{i}}}$ (2)

在本文中，让 $t r_{i}$ 反映 $w_{i}$ 执行一组众包任务 $φ_{i} (φ_{i} \subset T)$ 时诚实和可靠的可能性。式(2)的输入需要反映历史信息，包括以前完成的任务的质量 $Q_{i} = {q_{1}^{i}, q_{2}^{i}, \dots, q_{j}^{i}, \dots, q_{n u m_{i}}^{i}}$ 以及承诺完成度 $p r o_{i}$ 和角色影响因素 $R I F_{i}$ 。承诺完成度 $p r o_{i}$ 来自现实生活中同事和朋友的评价，具体数据一般通过填写调查表获得。角色影响因子 $R I F_{i}$ 反映了其专业领域的影响程度，取值范围为[0,1] [17]。另外，受时间因素的影响，完成的任务质量与当前任务越接近，对众包工人的信任度的影响越大。我们根据心理学中的Ebbinghaus遗忘曲线 [18] 来表示这种时间延迟。式(2)的输入由式(3)确定。

$x_{i} = \frac{p r o_{i} + R I F_{i} + \sum_{j = 1}^{n u m_{i}}_{q_{j}^{i} \in Q_{i}} q_{j}^{i} \cdot δ_{j}}{1 + \sum_{j = 1}^{n u m_{i}} δ_{j}}$ (3)

其中，Ebbinghaus遗忘曲线表示第j个任务的时间衰减因子，这是人脑忘记新事物时的规律。随着时间的流逝，执行的历史任务的影响逐渐减小，直到趋向于0，如式(4)所示。

$δ_{j} = {\begin{array}{l} 1, & j = n u m_{i} \\ e^{- \frac{1}{j}}, & 1 \leq j < n u m_{i} \end{array}$ (4)

2) 能力值：我们获得 $a b_{i}$ 通过将等式(1)中的x替换为 $y_{i}$ 。 $y_{i}$ 由式(5)计算。

$a b_{i} (y_{i}) = ω \cdot e^{α \cdot e^{γ \cdot y_{i}}}$ (5)

$y_{i}$ 是等式(5)的输入，并且 $a b_{i}$ 随着 $y_{i}$ 增长而增长。 $y_{i}$ 可以通过公式(6)计算。

$y_{i} = \frac{p o s_{i j} + \sum_{j = 1}^{n u m_{i}}_{q_{j}^{i} \in Q_{i}} q_{j}^{i} \cdot δ_{j}}{1 + \sum_{j = 1}^{n u m_{i}} δ_{j}}$ (6)

其中 $p o s_{i j}$ 表示 $w_{i}$ 成功完成众包任务 $t_{j} (t_{j} \in φ_{i})$ 的可能性。

3) 众包工人的得分：本文根据众包工人的信任度 $t r_{i}$ 和能力值 $a b_{i}$ 来计算。得分 $s c o_{i}$ 代表 $w_{i}$ 的综合得分。它由公式(7)计算。

$s c o_{i} = ε_{1} \cdot t r_{i} + ε_{2} \cdot a b_{i}$ (7)

其中 $ε_{1}$ 和 $ε_{2}$ 代表相应的权重，和 $ε_{1} + ε_{2} = 1$ 。

3.2. 众包任务

定义2：众包任务。 $T = {t_{1}, t_{2}, \dots, t_{j}, \dots, t_{m}}$ 为m个任务。每个任务 $t_{j} (1 \leq j \leq m)$ 都是三个元素的元组： $((l o c_{t_{j}}^{x}, l o c_{t_{j}}^{y}), B_{j}, d i f_{i j})$ 。让我们指出的位置。 $d i f_{i j}$ 表示 $w_{i}$ 完成 $t_{j}$ 的难度值。它由公式(8)计算。

$d i f_{i j} = ω_{1} \cdot d t_{i j} + ω_{2} \cdot s e v_{j}$ (8)

其中 $d t_{i j}$ 表示 $w_{i}$ 从当前位置 $(l o c_{w_{i}}^{x}, l o c_{w_{i}}^{y})$ 到任务位置 $(l o c_{t_{j}}^{x}, l o c_{t_{j}}^{y})$ 的行驶时间。 $s e v_{j}$ 是所在区域的环境恶劣程度。例如，此任务位于偏远的郊区或高山。 $ω_{1}$ 和 $ω_{2}$ 并代表相应的权重， $ω_{1} + ω_{2} = 1$ 。

4. 激励机制

4.1. 系统模型

在本节中，首先给出了MOO-TA问题的系统模型。在我们的时空众包系统中，主要激发了众包工人在偏远的地区执行任务以扩大感知数据范围的能力。最终目标是最大程度地发挥众包工人和平台的效用。如果 $w_{i} (w_{i} \in S)$ 选择执行 $t_{j}$ ，则由公式(9)计算 $w_{i}$ 的效用。

$u_{i j} = p_{i j} - c_{i j} + ρ \cdot R o P_{i j}$ (9)

$R o P_{i j}$ 是 $w_{i}$ 执行 $t_{j}$ 时的额外奖励或惩罚。参数 $ρ$ 表示系统参数，并且在我们的模型中

${\begin{matrix} 0 < ρ < \frac{v_{i j} - p_{i j}}{R o P_{i j}}, & R o P_{i j} > 0 \\ 0 < ρ < \frac{c_{i j} - p_{i j}}{R o P_{i j}}, & R o P_{i j} < 0 \end{matrix}$

$p_{i j}$ 由公式(10)计算。

$p_{i j} = θ \cdot e^{\frac{- 1}{q_{i j}}} \cdot B_{j}$ (10)

$θ$ 是系统参数，其中 $\frac{c_{i j}}{B_{j}} \cdot e^{\frac{1}{q_{i j}}} < θ \leq e^{\frac{1}{q_{i j}}}$ 。

$w_{i}$ 执行 $t_{j} (t_{j} \in φ_{i})$ 的成本由公式(11)给出。

$c_{i j} = c_{i j}^{m} + c_{i j}^{s}$ (11)

其中表示 $c_{i j}^{m}$ 移动成本，表示 $c_{i j}^{s}$ 感测成本。令 $c_{i j}^{m} = k_{i} \cdot d_{i j}$ ， $c_{i j}^{s} = τ_{i} \cdot p t_{i j}$ 。在等式(9)中， $w_{i}$ 执行 $t_{j}$ 时的额外奖励或惩罚 $R o P_{i j}$ 由等式(12)给出。

$R o P_{i j} = S u b_{i j}^{s c o} + S u b_{i j}^{p r} + S u b_{i j}^{d i f} - F i n e_{i j}^{p t}$ (12)

在系统模型中，我们考虑了众包工人和任务的多个属性，并基于多个属性计算了众包工人的额外奖励。例如，为了激励众包工人更积极和负责任地执行任务，该平台会根据其得分和隐私敏感度为众包工人计算额外的奖励。 $S u b_{i j}^{s c o}$ 是根据等式(13)获得的 $w_{i}$ 执行 $t_{j}$ 时的得分计算出的额外奖励。

$S u b_{i j}^{s c o} = σ \cdot e^{\frac{- 1}{s c o_{i}}} \cdot p_{i j}$ (13)

$S u b_{i j}^{p r}$ 是根据公式(14)表示的隐私敏感度值计算出的额外奖励。

$S u b_{i j}^{p r} = {\begin{array}{l} β \cdot e^{\frac{- 1}{| p r_{i} - p r_{\min} |}} \cdot p_{i j}, & p r_{\min} < p r_{i} \leq p r_{\max} \\ 0, & p r_{i} = p r_{\min} \end{array}$ (14)

此外，为了激励众包工人在不受欢迎的(偏远，恶劣的环境)区域执行任务，该平台根据任务的难度值计算众包工人的额外奖励，类似于补贴，其表示为式(15)。

$S u b_{i j}^{d i f} = η \cdot e^{\frac{- 1}{d i f_{i j}}} \cdot c_{i j}$ (15)

另一方面，为了确保众包工人以高质量和高数量完成任务，该平台严格要求众包工人执行任务的时间长度。在平台给定的执行时间范围内未完成任务的众包工人将被罚款。 $F i n e_{i j}^{p t}$ 由公式(16)计算。

$F i n e_{i j}^{p t} = {\begin{array}{l} 0, & p t_{i j}^{\min} \leq p t_{i j} \leq p t_{i j}^{\max} \\ λ \cdot e^{\frac{- 1}{| p t_{i j} - p t_{i j}^{\min} |}} \cdot p_{i j}, & p t_{i j} < p t_{i j}^{\min} \\ λ \cdot e^{\frac{- 1}{| p t_{i j} - p t_{i j}^{\max} |}} \cdot p_{i j}, & p t_{i j} > p t_{i j}^{\max} \end{array}$ (16)

$\bar{u_{i j}}$ 是 $w_{i} (w_{i} \in S)$ 执行 $t_{j}$ 时带给平台的实际效用，由公式(17)计算。

$\bar{u_{i j}} = v_{i j} - p_{i j} - ρ \cdot R o P_{i j}$ (17)

$v_{i j}$ 表示 $w_{i} (w_{i} \in S)$ 通过感测 $t_{j}$ 为平台带来的贡献。 $ρ$ 参数表示系统参数 ${\begin{matrix} 0 < ρ < \frac{v_{i j} - p_{i j}}{R o P_{i j}}, & R o P_{i j} > 0 \\ 0 < ρ < \frac{c_{i j} - p_{i j}}{R o P_{i j}}, & R o P_{i j} < 0 \end{matrix}$

4.2. 多目标优化任务分配

在系统模型中，两个优化目标是在执行任务分配时最大化众包工人的效用U和最大化平台的效用 $\bar{U}$ ，从而实现最大化社会福利的目标。U和 $\bar{U}$ 由式(18)和式(19)计算。

$U = \sum_{w_{i} \in S} \sum_{t_{j} \in T} u_{i j}$ (18)

$\bar{U} = \sum_{w_{i} \in S} \sum_{t_{j} \in T} \bar{u_{i j}}$ (19)

LWS_NSGA_II算法用于解决多目标优化任务分配(MOO-TA)问题。它是传统的线性加权求和(LWS)算法和带精英策略的快速非支配排序遗传算法(NSGA_II)算法的组合算法。LWS算法的输出用作NSGA_II算法的输入，以便找到尽可能多的帕累托最优解。

平台给出了可行的解决方案空间PM (即，概率矩阵)，代表了所选众包工人完成每个任务的概率矩阵。如果有 $p m_{i j} > 0$ ， $w_{i} (w_{i} \in S)$ 就有可能完成 $t_{j}$ 。否则，这是不可能的。PM的计算方法不是本文的研究内容。AM (即，分配矩阵)是分配解决方案。如果 $t_{j}$ 分配给 $w_{i} (w_{i} \in S)$ ，相应的条目 $a m_{i j} = 1$ ; 否则， $a m_{i j} = 0$ 。

4.2.1. 线性加权求和(LWS)算法

这种线性加权求和LWS算法的主要思想是通过点乘预定义的目标将多目标集成到单个综合目标中。具体来说，我们构建一个集成的效用函数，该函数涉及最大化众包工人的效用U和平台的效用 $\bar{U}$ 。效用函数可以表述为：

$U F = μ \cdot U + (1 - μ) \cdot \bar{U}$ , (20)

$μ$ 权重因子的作用是平衡这两个目标，U以及 $\bar{U}$ 。

算法1显示了LWS算法的过程。在该算法中，我们将权重因子 $μ$ 从0更改为1，并获得相应的分配矩阵AM。基于贪婪的算法会根据等式(20)计算效用(表2)。

Table 2. The traditional linear weighted Summation (LWS) algorithm

表2. 传统的线性权重求和算法

我们选择不同的可变步长(例如：0.025、0.05、0.1)来更改权重因子 $μ$ 的值。例如，我们以0.1的增量将权重因子 $μ$ 从0更改为1，然后它将产生11个首选项组合，例如(0.1,0.9)，(0.3,0.7)，(0.6,0.4)等。对于每个优化组合，使用LWS算法来获得相应的分配解决方案。

4.2.2. LWS_NSGA_II算法

LWS算法直接将输出解决方案作为NSGA_II的初始种群的一部分，即为算法3：LWS_NSGA_II算法。通过LWS算法获得的解并不是全部的Pareto最优解，因为在每次迭代中，基于贪婪的线性加权求和算法可以实现接近最优的解，而不是最优解。此外，线性权重策略不能保证找到针对多目标优化问题的Pareto解，尤其是对于非凸解空间。相反，NSGA_II算法是一种启发式方法，可以实现尽可能多的帕累托最优解。通过LWS算法直接获得输出解决方案，作为NSGA_II算法初始种群的一部分。因此，它被称为LWS_NSGA_II算法。它可以有效地加速融合并获得满意的解决方案(表3)。

Table 3. LWS_NSGA_II algorithm

表3. LWS_NSGA_II算法

在迭代过程中，进行遗传算法操作：选择、交叉和变异，不断获得子代种群。然后通过非支配快速排序，比较两个适应度值即两个目标函数值U和 $\bar{U}$ ，从现有种群中选择Pareto解。直到达到进化轮数为止，输出Pareto解决方案。

5. 实验评估

5.1. 实验装置

我们所有的实验均在Windows 10操作系统上运行，该操作系统具有AMD Ryzen 5 3550H和Radeon Vega Mobile Gfx 2.10 Ghz CPU，16.00 GB内存以及PyCharm 2018.2.3平台。Yelp数据集 [19] 用于进行实验。Yelp是致力于本地企业目录服务和评论站点的社交网络，其中包括188,593家企业，1,518,169用户和5,996,997条评论。对于此数据集，我们将Yelp用户视为众包工人，将企业视为任务。在Yelp数据集中，没有提供众包工人的位置信息。在实验中，选择了众包工人的评论之一，并将所选评论的相应企业的位置视为众包工人的位置。因此，可以获得众包工人的位置属性。根据Yelp数据集的属性，还可以合理地映射众包工人和任务的其他属性。

5.2. MOO-TA的性能

我们从Yelp数据集中提取了50名人群工人和522个任务。众包工人可以执行的最大任务数设置为 $n u m_{w_{i}}^{\max} = 4$ ，一个任务最多有 $n u m_{t_{j}}^{\max} = 5$ 人执行。

在本文中，额外的奖励或惩罚RoP被添加到公式(9)和公式(17)中，以计算众包工人和平台的效用。RoP的常数参数 $ρ$ 用于确保激励机制的个体合理性。通过实验确定使LWS_NSGA_II算法更有效的常数参数 $ρ$ 的值。初始种群是通过LWS方法获得的输出解决方案。相应的实验结果如图2所示，其中RoP的常数参数 $ρ$ 分别设置为0.2、0.4、0.6、0.8、1.0和1.2。x坐标表示常量参数 $ρ$ 的值。左侧的y轴表示折线图的y坐标，右侧的y轴表示条形图的y坐标，指示Pareto解决方案的数量，以及Pareto解决方案中人群工作者和平台的效用的最小值。从图2可以看出，当时 $ρ = 1.0$ ，LWS_NSGA_II算法将获得更有效的结果，即，所获得的Pareto解的数量更多，众包工人和平台的效用的最小值较大。在图2中，当众包工人和平台的效用的最小值最大时，帕累托解决方案的数量却最小，因此不使用 $ρ = 0.8$ 。同样，尽管Pareto解决方案的数量在时 $ρ = 1.2$ 最大，但众包工人和平台的效用的最小值很小。因此，最后 $ρ$ 值取1.0。

Figure 2. Effect of different constant parameter ρ

图2. 不同常数参数ρ的影响

通过LWS_NSGA_II获得分配解决方案的结果如图3所示。初始种群大小设置为146，进化轮数设置为60。LWS_NSGA_II的帕累托最优解位于图3中这两个目标的二维空间的最外面。并且获得的分配解决方案数量为161 (即帕累托最优解)。

Figure 3. The result of LWS_NSGA_II

图3. LWS_NSGA_II结果

为了验证LWS_NSGA_II算法的有效性，我们将其与线性加权求和LWS算法和多目标粒子群MOPSO算法进行了比较。初始种群大小设置为146，迭代次数和进化轮数均设置为60。通过不同的优化方法获得的分配解决方案的结果如图4所示。LWS算法一次只能获得一个结果，并且不能保证是帕累托最优的解决方案。在每次迭代中，基于贪婪的线性加权求和方法可以实现接近最佳的解决方案，而不是最佳的解决方案。此外，线性加权求和策略不能保证找到多目标优化问题的Pareto解，尤其是对于非凸解空间。MOPSO算法获得了36个Pareto解，但众包工人和平台的实用性相对较低。与上述两种算法相比，LWS_NSGA_II算法，力求发现足够的帕累托最优解，获得了161个Pareto最优解，并且众包和平台的效用更大。该平台可以通过优势比较从161个Pareto解决方案中选择最合适的分配方案。

Figure 4. The allocation solution results of different algorithms

图4. 不同算法的分配结果

6. 总结

在本文中，我们研究了MOO-TA问题，以最大化平台的效用和众包工人的效用。为了解决多目标优化问题，提出了LWS_NSGA_II算法，以激励众包工人在偏远地区执行众包任务，并获得足够的帕累托最优解。对比实验结果证明了我们提出的方法在真实数据集上的有效性和适应性。

在未来的工作中，将研究边缘云移动众包系统中任务分配的超级多目标优化问题。

文章引用

吴胜男. 时空众包中多目标优化任务分配
Multi-Objective Task Assignment in Spatio-Temporal Crowdsourcing[J]. 计算机科学与应用, 2021, 11(03): 549-560. https://doi.org/10.12677/CSA.2021.113056

参考文献

1. Wen, Y., Shi, J., Zhang, Q., Tian, X., Huang, Z., Yu, H., Cheng, Y. and Shen, X. (2015) Quality-Driven Auction-Based Incentive Mechanism for Mobile Crowd Sensing. IEEE Transactions on Vehicular Technology, 64, 4203-4214. https://doi.org/10.1109/TVT.2014.2363842

2. Tong, Y., Yuan, Y., Cheng, Y., Chen, L. and Wang, G. (2017) Survey on Spatiotemporal Crowdsourced Data Management Techniques. Journal of Software, 28, 35-58.

3. Zhang, X., Yang, Z., Gong, Y.J., Liu, Y. and Tang, S. (2017) Spatial Recruiter: Maximizing Sensing Coverage in Selecting Workers for Spatial Crowdsourcing. IEEE Transactions on Vehicular Technology, 66, 5229-5240. https://doi.org/10.1109/TVT.2016.2614312

4. Wang, L., Yu, Z., Han, Q., Guo, B. and Xiong, H. (2017) Mul-ti-Objective Optimization based Allocation of Heterogeneous Spatial Crowdsourcing Tasks. IEEE Transactions on Mobile Computing, 17, 1637-1650. https://doi.org/10.1109/TMC.2017.2771259

5. Zhang, X., Yang, Z. and Liu, Y. (2018) Vehicle-Based Bi-Objective Crowdsourcing. IEEE Transactions on Intelligent Transportation Systems, 19, 3420-3428. https://doi.org/10.1109/TITS.2017.2766769

6. Zhang, X., Yang, Z., Liu, Y. and Tang, S. (2016) On Reliable Task Assignment for Spatial Crowdsourcing. IEEE Transactions on Emerging Topics in Computing, 7, 174-186. https://doi.org/10.1109/TETC.2016.2614383

7. Liang, W., Yu, Z., Qi, H., Guo, B. and Xiong, H. (2018) Mul-ti-Objective Optimization Based Allocation of Heterogeneous Spatial Crowdsourcing Tasks. IEEE Transactions on Mobile Computing, 17, 1637-1650.

8. Wang, Y., Jia, X., Jin, Q. and Ma, J. (2016) QuaCentive: A Quality-Aware Incentive Mechanism in Mobile Crowdsourced Sensing (MCS). The Journal of Supercomputing, 72, 2924-2941. https://doi.org/10.1007/s11227-015-1395-y

9. Duan, X., Zhao, C., He, S., Cheng, P. and Zhang, J. (2017) Dis-tributed Algorithms to Compute Walrasian Equilibrium in Mobile Crowdsensing. IEEE Transactions on Industrial Elec-tronics, 64, 4048-4057. https://doi.org/10.1109/TIE.2016.2645138

10. Deb, K. (2005) Multi-Objective Optimization. In: Burke, E.K. and Kendall, G., Ed., Search Methodologies, Springer, Berlin, Heidelberg, 273-316. https://doi.org/10.1007/0-387-28356-0_10

11. Ul Hassan, U. and Curry, E. (2016) Efficient Task Assignment for Spatial Crowdsourcing: A Combinatorial Fractional Optimization Approach with Semi-Bandit Learning. Expert Systems with Applications, 58, 36-56. https://doi.org/10.1016/j.eswa.2016.03.022

12. Wang, J., Wang, Y., Zhang, D., Wang, L., Xiong, H., Helal, A., et al. (2016) Fine-Grained Multi-Task Allocation for Participatory Sensing with a Shared Budget. IEEE Internet of Things Journal, 3, 1395-1405. https://doi.org/10.1109/JIOT.2016.2608141

13. Ben Messaoud, R. and Ghamri-Doudane, Y. (2016) Fair QoI and Energy-Aware Task Allocation in Participatory Sensing. 2016 IEEE Wireless Communications and Networking Conference, Doha, 3-6 April 2016, 1-6. https://doi.org/10.1109/WCNC.2016.7565025

14. Liu, Y., Guo, B., Wang, Y., Wu, W., Yu, Z. and Zhang, D. (2016) Taskme: Multi-Task Allocation in Mobile Crowd Sensing. Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing, Heidelberg, September 2016, 403-414. https://doi.org/10.1145/2971648.2971709

15. Liu, Y. and Li, X. (2015) Heterogeneous Participant Recruitment for Comprehensive Vehicle Sensing. PLoS ONE, 10, e0138898. https://doi.org/10.1371/journal.pone.0138898

16. Ma, X., Ma, J., Li, H., Jiang, Q. and Gao, S. (2016) RTRC: A Reputation-Based Incentive Game Model for Trustworthy Crowdsourcing Service. China Communications, 13, 199-215. https://doi.org/10.1109/CC.2016.7897544

17. Wang, Y., Li, L. and Liu, G. (2015) Social Context-Aware Trust Inference for Trust Enhancement in Social Network Based Recommendations on Service Providers. World Wide Web, 18, 159-184. https://doi.org/10.1007/s11280-013-0241-5

18. Peng, L., Yu, X.Y., Yang, L. and Zhang, T. (2014) Crowdsourcing Fraud Detection Algorithm Based on Ebbinghaus Forgetting Curve. International Journal of Security and Its Applications, 8, 283-290. https://doi.org/10.14257/ijsia.2014.8.1.26

19. Yelp Dataset (n.d.). https://www.yelp.com/dataset

期刊菜单