一种考虑偏好和独立地点的众包任务匹配方法

摘要

本发明公开了一种考虑偏好和独立地点的众包任务匹配方法，包括如下步骤：众包平台发布工人信息给所有的任务请求者；每一个请求者向平台提交一个请求；根据众包场景的类型计算获得任务请求者‑众包工人‑地点匹配对的价值；形式化考虑偏好和独立地点的众包任务匹配模型的价值最大化问题；执行考虑偏好和独立地点的众包任务匹配机制；众包工人在分配地点执行已分配的任务并把结果反馈给众包平台；众包平台把服务提供给任务请求者。本发明考虑完成任务获得价值相同和价值不同两种情况，解决两种情况下带偏好考虑独立地点的众包任务匹配价值最大化问题，该方法的综合价值量能够得到提高，具有明显优势。

说明书

技术领域

本发明属于互联网和算法博弈论的交叉领域，涉及众包任务匹配技术，具体涉及一种考虑偏好和独立地点的众包任务匹配方法。

背景技术

众包通过整合互联网上未知用户来完成机器难以完成的任务，已成为许多互联网资源产生的主要实现机制。目前众包已经广泛应用于信息检索、人工智能、视频分析、知识挖掘、智慧城市、人机交互学习、图像质量评估等领域。

在空间众包的研究中，任务分配问题是其核心问题之一。然而大部分现有任务分配问题研究的假设过强，导致其存在不足。设计分配机制来最大化众包系统总价值的问题是非常具有挑战性的：请求者可以通过提交偏好集合来采取战略行动，以最大化自己的价值。机制应该激励自私和理性的请求者报告他们的偏好集合。请求者对工作者有偏好，我们不能将任务分配给不兼容的工作者。这意味着我们不仅应考虑分配的价值，还应考虑分配的兼容性。

现有研究均假设空间众包中的任务分配问题仅涉及众包工人和众包任务两类对象：众包工人移动到众包任务指定地点完成任务并获取报酬。然而目前还存在着大量其他类型的空间众包应用，其任务分配不仅涉及众包任务和众包工人，还受到第三方工作地点的影响。例如人们健身时，需要找到合适的健身教练和健身馆；理发时，需要找到合适的理发师和理发店；办宴席时，需要找到合适的司仪和酒店。人们发布的这一类任务被工人接受后，往往还需要到特定的一类独立的地点为他们提供场地设施才能完成，并且地点设施的质量对任务的完成效果有着重要的影响。然而现在大多数众包研究中并没有对地点进行独立研究。

发明内容

发明目的：为了克服现有技术中存在的不足，提供一种考虑偏好和独立地点的众包任务匹配方法，考虑完成任务获得价值相同和价值不同两种情况，解决两种情况下带偏好考虑独立地点的众包任务匹配价值最大化问题。

技术方案：为实现上述目的，本发明提供一种考虑偏好和独立地点的众包任务匹配方法，包括如下步骤：

S1：众包平台发布工人信息给所有的任务请求者；

S2：每一个请求者向平台提交一个请求；

S3：根据众包场景的类型计算获得任务请求者-众包工人-地点匹配对的价值；

S4：形式化考虑偏好和独立地点的众包任务匹配模型的价值最大化问题；

S5：执行考虑偏好和独立地点的众包任务匹配机制；

S6：众包工人在分配地点执行已分配的任务并把结果反馈给众包平台；

S7：众包平台把服务提供给任务请求者。

上述众包任务匹配方法包括考虑偏好和独立地点且价值相同和考虑偏好和独立地点且价值不相同两种情况，分别为一种考虑偏好和独立地点且价值相同的众包任务匹配方法和一种考虑偏好和独立地点且价值不相同的众包任务匹配方法。本发明解决应用于考虑偏好和独立地点的众包系统的任务分配问题，具有计算有效性以及常数因子近似比的特性。

一种考虑偏好和独立地点且价值相同的众包任务匹配方法，包括如下步骤：

A1：众包平台发布W给所有的任务请求者，其中W＝{1,2,…,m}表示众包工人集合；L＝{1,2,…,l}表示地点集合，L对众包平台已知；

A2：设请求者集合为R＝{1,2,…,n},每一个请求者i向平台提交一个请求B

A3：对众包工人k，k∈P

A4：形式化考虑偏好和独立地点且价值相同的众包任务匹配的价值最大化问题；

A5：执行考虑偏好和独立地点且价值相同的众包任务匹配机制；

A6：众包工人在分配地点执行分配的众包任务，并把执行结果反馈给众包平台；

A7：众包平台把结果提供给任务请求者。

进一步地，所述步骤A4中考虑偏好和独立地点且价值相同的众包任务匹配的价值最大化问题的形式化表达具体如下：

其中，

进一步地，所述步骤A5中执行考虑偏好和独立地点且价值相同的众包任务匹配机制包括如下步骤：

B1：把所有满足i∈R,k∈P

B2：初始化任务分配

B3：取出

B4：令

B5：重复执行步骤B3到步骤B4，直到匹配对序列

B6：初始化存储集合

B7：令degree

B8：取出

B9：令N(e)表示在图G'与匹配对e相连接的匹配对集合，对N(e)\S

B10：重复执行步骤B9，直到集合N(e)\S

B11：重复执行步骤B8到步骤B10，直到存储集合S

B12：构建辅助图G”(P,E

B13：如果路径存在，令

B14：返回分配

进一步地，所述步骤B12中辅助图G”(P,E

C1：初始化导入边集合

C2：令

C3：对

C4：对每个包集合bag

C5：对每个包集合bag

考虑偏好和独立地点且相同价值的众包任务匹配算法是一个多项式时间算法。因为在分配中至多有min(n,m,l)对任务-工作者-地点匹配对，置γ＝min(n,m,l)，所以步骤B3到步骤B5需要O(nml·γ)时间。步骤B7中采用排序算法求解，排序算法的时间复杂度为O(nml·log(nml))。因为在场景中至多有nml对任务-工作者-地点匹配对，每个包集合bag

考虑偏好和独立地点且相同价值众包分配算法的近似比为4/3+∈。

根据步骤A4中目标函数的定义，经过证明，考虑偏好和独立地点且相同价值的众包任务匹配问题可以在多项式时间内规约到最大三维匹配问题，由于最大三维匹配问题是NP-hard，所以考虑偏好和独立地点且相同价值的众包任务匹配问题也是NP-hard。另外，已经存在一个多项式时间内可以求解K-集合装箱问题的本地改进贪心算法，并且该算法的近似比为

一种考虑偏好和独立地点且价值不相同的众包任务匹配方法，包括如下步骤：

D1：众包平台发布一个二元组(W,I)给所有的任务请求者，其中W＝{1,2,…,m}表示众包工人集合，I＝{I

D2：设请求者集合为R＝{1,2,…,n}，每一个请求者i向平台提交一个请求B

D3：根据众包任务的类型，众包工人的努力指示器向量和地点热度指示器向量，获得任务请求者-众包工人-地点匹配对的价值量；令

D4：形式化考虑偏好和独立地点且价值不同的众包任务匹配的价值最大化问题；

D5：执行考虑偏好和独立地点且价值不同的众包任务匹配机制；

D6：众包工人在分配地点执行分配的任务，并把执行结果反馈给众包平台；

D7：众包平台把结果提供给任务请求者。

进一步地，所述步骤D4中考虑偏好和独立地点且价值不同的众包任务匹配的价值最大化问题的形式化表达具体如下：

其中，

进一步地，所述步骤D5中执行考虑偏好和独立地点且价值不同的众包任务匹配机制包括如下步骤：

E1：对所有i∈R,k∈P

E2：初始化任务分配

E3：置

E4：令

E5：重复执行步骤E3到步骤E4，直到序列集合

E6：新设一个临时匹配对集合

E7：对

E8：令N(j)表示在图G上与匹配对j相连接的匹配对集合，对N(j)中每一个任务-工作者-地点匹配对j'∈N(j)，置N(j)＝N(j)\{j'}，判断

E9：重复执行步骤E8，直到邻域集合N(j)为空；

E10：令w(j)表示匹配对j的价值量，w(Y)表示匹配对集合Y中所有匹配对的价值量总和；判断收益因子a＝w(Y)/w(j)是否大于1，如果是，置

E11：返回分配

考虑偏好和独立地点且价值不同的众包任务匹配算法是一个多项式时间算法。步骤E1中采用排序算法求解，排序算法的时间复杂度为O(nml·log(nml))。因为在分配中至多有min(n,m,l)对任务-工作者-地点匹配对，所以步骤E3到步骤E5需要O(nml·min(n,m,l))时间。因为在分配中至多有min(n,m,l)对任务-工作者-地点匹配对，且每个匹配对的领域范围最多为三个，所以，步骤E7到步骤E10需要花费min(n,m,l)的时间复杂度。因此，步骤D5的时间复杂度为O(nml·max(log(nml),min(n,m,l)))。

有min(n,m,l)个任务-工作者-地点匹配对待改进，步骤E8到步骤E9每轮迭代将至多添加三个任务-工作者-地点匹配对，所以考虑偏好和独立地点且价值不同的众包系统的真实任务分配方法算时间复杂度为O(nml·max(log(nml),min(n,m,l)))，即考虑偏好和独立地点且价值不同的众包任务匹配算法是一个多项式时间算法。

考虑偏好和独立地点且价值不同的众包任务匹配算法的近似比为8/3。

根据步骤D4中目标函数的定义，经过证明，考虑偏好和独立地点且价值不同的众包任务匹配问题可以在多项式时间内规约到最大加权三维匹配问题，由于最大加权三维匹配问题是NP-hard，所以考虑偏好和独立地点且价值不同的众包任务匹配也是NP-hard。另外，已经存在一个多项式时间内可以求解K-集合装箱问题的本地改进贪心算法，并且该算法的近似比为

有益效果：本发明与现有技术相比，将偏好和独立地点同时考虑进众包任务匹配方法中，并且包括了价值相同和价值不同两种情况，该众包任务匹配方法的综合价值量能够得到提高，具有明显优势，且探究众包环境下任务请求者和任务工作者以及地点的偏好关系，偏好对于合理治理网络众包环境、降低网络众包风险、防止市场垄断具有重要作用，能够兼顾分配价值和分配兼容性，另外本发明提供的分配算法步骤多为简单的循环体和经典多项式算法，时间复杂较低，所需要的时间比其他匹配算法要少的多，分配效率得到提升，更加适合大规模考虑偏好和独立地点的众包匹配算法问题。

附图说明

图1为本发明的考虑偏好和独立地点的众包任务匹配系统结构图；

图2为本发明的考虑偏好和独立地点且价值相同的众包任务匹配算法流程图；

图3为本发明的考虑偏好和独立地点且价值不同的众包任务匹配算法流程图。

具体实施方式

下面结合附图和具体实施例，进一步阐明本发明，应理解这些实施例仅用于说明本发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发明的各种等价形式的修改均落于本申请所附权利要求所限定的范围。

本发明提供一种考虑偏好和独立地点的众包任务匹配方法，参照图1，其包括如下步骤：

S1：众包平台发布工人信息给所有的任务请求者；

S2：每一个请求者向平台提交一个请求；

S3：根据众包场景的类型计算获得任务请求者-众包工人-地点匹配对的价值；

S4：形式化考虑偏好和独立地点的众包任务匹配模型的价值最大化问题；

S5：执行考虑偏好和独立地点的众包任务匹配机制；

S6：众包工人在分配地点执行已分配的任务并把结果反馈给众包平台；

S7：众包平台把服务提供给任务请求者。

参照图1，上述考虑偏好和独立地点的众包任务匹配模型的场景，考虑偏好和独立地点的众包系统包括任务请求者、众包工人和地点。本发明考虑完成任务价值相同和价值不同两种情况，价值不同的情况通过任务类型难度和众包工人的努力指标向量和工作地点的热度指标向量构成每个任务请求者-众包工人-地点匹配对的综合价值量，以最大化平台的价值量为目标，求解考虑偏好和独立地点的众包任务匹配模型的价值最大化方案。

基于上述技术方案，分别将考虑偏好和独立地点且价值相同的众包任务匹配方法和考虑偏好和独立地点且价值不同的众包任务匹配方法进行实例应用，具体如下：

实施例1：

本实施例提供一种考虑偏好和独立地点且价值相同的众包任务匹配方法，包括如下步骤：

A1：众包平台发布W给所有的任务请求者，其中W＝{1,2,…,m}表示众包工人集合；L＝{1,2,…,l}表示地点集合，L对众包平台已知；

A2：设请求者集合为R＝{1,2,…,n},每一个请求者i向平台提交一个请求B

A3：对众包工人k,k∈P

A4：形式化考虑偏好和独立地点且价值相同的众包任务匹配的价值最大化问题；

形式化表达具体如下：

其中，

A5：执行考虑偏好和独立地点且价值相同的众包任务匹配机制；

A6：众包工人在分配地点执行分配的众包任务，并把执行结果反馈给众包平台；

A7：众包平台把结果提供给任务请求者。

本实施例考虑偏好和独立地点且价值相同的众包系统，任务请求者的集合为R＝{1,2}，众包工人的集合为W＝{1,2}，地点的集合为L＝{1,2}，用i表示任务请求者，用k表示众包工人，用x表示地点。众包平台发布W给所有的任务请求者，L对众包平台已知。每个任务请求者i提交自己的请求B

表1任务请求者信息表

本实施例在步骤S3中，根据定义以及表1可得所有满足偏好条件的任务请求者-众包工人-地点匹配对价值量如表2。

表2任务请求者-众包工人-地点对的综合价值量

基于上述内容，如图2所示，步骤A5中执行考虑偏好和独立地点且价值相同的众包任务匹配机制，其包括如下步骤：

B1：把所有满足i∈R,k∈P

B2：初始化任务分配

B3：取出

B4：判断

B5：重复执行步骤B3到步骤B4，直到匹配对序列

B6：初始化存储集合S

B7：根据degree

B8：取出

B9：对N(e

B10：重复执行步骤B9，直到集合N(e

B11：重复执行步骤B8到步骤B10，直到存储集合S

B12：构建冲突图G”(P，E

辅助图G”(P，E

C1：初始化导入边集合

C2：令

C3：对

C4：对每个包集合bag

C5：对每个包集合bag

B13：存在路径bag

B14：返回分配

本实施例中最终得出考虑偏好和独立地点且价值相同的众包任务匹配系统的综合价值量为2，且为本实施例的最优解。

为了验证本实施例所提方案的效果，本实施例采用传统贪婪算法，首先按照它们在词典序列

可见，本实施例所提方法获取的综合价值量要明显高于传统贪婪算法。

实施例2：

本实施例提供一种考虑偏好和独立地点且价值不相同的众包任务匹配方法，包括如下步骤：

D1：众包平台发布一个二元组(W,I)给所有的任务请求者，其中W＝{1,2,…,m}表示众包工人集合，I＝{I

D2：设请求者集合为R＝{1,2,…,n}，每一个请求者i向平台提交一个请求B

D3：根据众包任务的类型，众包工人的努力指示器向量和地点热度指示器向量，获得任务请求者-众包工人-地点匹配对的价值量；令

D4：形式化考虑偏好和独立地点且价值不同的众包任务匹配的价值最大化问题；

形式化表达具体如下：

其中，

D5：执行考虑偏好和独立地点且价值不同的众包任务匹配机制；

D6：众包工人在分配地点执行分配的任务，并把执行结果反馈给众包平台；

D7：众包平台把结果提供给任务请求者。

本实施例考虑偏好和独立地点且价值不同的众包系统，任务请求者的集合为R＝{1,2,…,n}，众包工人的集合为W＝{1,2,…,m}，地点的集合为L＝{1,2,…,l}，用i表示任务请求者，用k表示众包工人，用x表示地点；每个众包的信息如表3所示，每个地点的信息如表4所示。

表3工人信息表

表4地点信息表

众包平台发布一个元组(W,I,)给所有的任务请求者，L和H对于众包平台是已知的。每个任务请求者i提交自己的请求B

表5任务请求者信息表

本实施例在步骤D3中，根据公式(6)以及表3，表4，表5可得所有满足偏好条件的任务请求者-众包工人-地点对价值量如表6。

表6任务请求者-众包工人-地点对的综合价值量

基于上述条件，如图3所示，执行考虑偏好和独立地点且价值不同的众包任务匹配机制包括如下步骤：

E1：根据v(i,k,x)的非递增顺序对所有的任务-工作者-地点匹配对(i,k,x)进行排序，获得序列用

E2：初始化任务分配

E3：对

E4：判断

E5：重复执行步骤E3到步骤E4，直到序列集合

E6：置

E7：对

E8：e

E9：重复执行步骤E8，直到领域集合N(j)为空；

E10：判断收益因子a＝w(Y)/w(j)是否大于1，如果是，置

E11：返回分配

本实施例最终得出考虑偏好和独立地点且价值不同的众包任务匹配系统的综合价值量为34，且为本实施例的最优解。

为了验证上述方案的效果，本发明采用传统贪婪算法，基于价值优先策略，即请求者会被分配给最大可能价值的偏好集合中的工作者和地点。首先计算每一个任务请求者-众包工人-地点匹配对的价值，并基于它们的价值以非递增顺序对任务请求者-众包工人-地点匹配对进行排序。然后，如

可见，本实施例所提方法获取的综合价值量要明显高于传统贪婪算法。