基于市场权值的二阶段多agent任务分配算法

Two-Stage Multi-Agent Task Allocation Algorithm Considering Market Weight

摘要: 当前对于多Agent系统中比较热点问题是多agent的资源分配和多agent的任务分配，即如何将合适的任务分配给合适的agent，以优化整体任务分配结果。但是考虑到其中的agent具有自利性问题的研究却很少。为了有效的解决自利agent任务分配的问题，构造出一个包含最优竞争和市场协作的两阶段任务分配模型，在最优竞争的基础上，市场协作阶段进一步协调和优化最优任务的分配。考虑到候选人之间的关系可能最终影响市场的总体收益，提出“市场权值”的概念来描述更精确的合作关系。基于市场权值的两阶段分配模型，不仅能让任务候选人充分发挥自身优势参与竞争，保护任务候选人利益，而且能优化市场的总体收益。最后，通过仿真结果验证本文提出算法的有效性。

Abstract: At present, the hot issues in multi-agent system are multi-agent resource allocation and multi-agent task allocation, that is, how to allocate appropriate tasks to appropriate agents to optimize the overall task allocation results. However, considering the self-interest of the agent, there is little re-search on the problem. In order to effectively solve the problem of task allocation of self-interest agent, a two-stage task allocation model including optimal competition and market cooperation is constructed. On the basis of optimal competition, the market cooperation stage further coordinates and optimizes the optimal task allocation. Considering that the relationship between candidates may ultimately affect the overall income of the market, the concept of “market weight” is proposed to describe a more accurate cooperative relationship. The two-stage allocation model based on market weight can not only enable task candidates to give full play to their own advantages, participate in competition and protect the interests of task candidates, but also optimize the overall in-come of the market. Finally, the simulation results verify the effectiveness of the proposed algorithm.

1. 引言

当对多agent系统的中的个体进行任务分配时，需要考虑到Agent个体的思维状态是否受到感情、智慧、社会关系等方面因素的影响，Agent的思考能力不一定表现在某个人的智能行为中，更可能因为社会活动的影响而以各种形式展示出来。当前，多Agent系统的核心问题是如何使这些agent之间进行相互协作，从而进行问题的求解。与劳务市场中工人的合作行为相似，Agent能够相互合作的前提是多Agent系统中的每个个体agent都具有交互功能 [1]。Agent之所以被赋予意识观念，是因为多Agent系统本身就是一种用来研究现实世界的抽象工具 [2]。联盟可以为那些独立的agent提供富有弹性且便捷的就业空间与场景，使得这些agent在固定时间内组成一个团体，通力合作以实现协同发展和资源整合，从而能够更加智慧、灵活和便捷的完成特定目标。

随着参与者的持续增加，市场也因此变得更加复杂。参与者不再是纯粹的竞争或者合作关系。如国内最大电动汽车制造商比亚迪与特斯拉之间既有竞争关系又有合作关系 [3]。他们都在研发电车电池，这样他们就会互相竞争以获得市场份额。同时，比亚迪也是特斯拉在华市场最大合作伙伴之一。相较于传统电池而言，比亚迪为特斯拉提供的刀片电池可以将利用效率比传统电池包提高50%以上，同时可将成本降低了20%~30%，以供特斯拉用于开拓低端产品线。在这方面，它们又相互合作。在劳务市场任务分配的过程中，这种情况也是存在的。这意味着在竞争模式下，每个参与者可以相互竞争以获得最大利益，在其他的一些情况下，他们会相互合作，使自己的利益最好。近年来，人们对博弈决策者之间的合作问题进行了大量的研究，然而却很少去研究非合作博弈中自利agent的应对机制。本文在联盟技能博弈模型下 [4]，对自利agent任务分配问题进行了探讨。考虑到多自利agent系统是一组受自身利益驱使的参与者，他们对其他参与者的行为做出反应，加入使自己的个体成本函数最小化的联盟,但是传统的任务分配算法往往会忽视这些。

由于上述差异，现有的多agent任务分配算法无法直接解决自利agent背景下复杂任务的分配问题。本文通过一个自由的劳务市场中任务分配问题为研究对象，设计了一个包含最优竞争和协商合作的两阶段任务分配算法(two-stage multi-agent task allocation algorithm based on market weights)。与其他算法不同的是，基于市场协作的两阶段任务分配算法不仅充分保护了参与者的主体性、保障了市场参与者的利益，且保证了市场的整体收益。

本文的剩余部分组织如下。第2节总结分析了相关问题的国内外研究现状。第3节建立了市场中复杂任务效益分配和任务分配的问题模型。第4节描述了(TSABMW)算法的基本思想，并对其收敛性进行了分析。第5节的仿真结果表明，本文提出的算法能够有效地将复杂任务和所得收益合理有效地分配给理性用户。第6节对本文的工作进行了总结。

2. 相关工作

随着MAS的发展，研究人员在多agent任务分配方面取得了很多的成果。现行MAS的很多问题都与资源分配和约束条件有关 [5]，其中最主要的是地理位置限制。因此，在分布式多agent任务分配环境下，通过协商方式形成联盟进行任务的分配与完成的方法得到了广泛的研究，有很多方法可以解决这个问题，比如通过谈判分配任务，基于市场的方法和团队组件问题 [6]。文献 [7] [8] [9] [10] 在联盟形成问题上进行了深入研究，假设一项任务可以由一组agent完成，agent个体试图找到团队成员，系统将任务的适当部分分配给每个成员，以实现效率最大化。kara和Bektas [11] 提出的数学规划方法通常追求最优解，然而随着问题规模增长，计算成本呈指数增长。Wooldridge等人 [12] [13] 于2006年首次提出CRG (Cooperative Resource Games)，详细分析了合作伙伴问题的时间复杂度，并讨论CRG与QCG (Quality Coalition Games)的关系，特别是在什么情况下两者之间切换。针对代理资源和能力的流失，张国富等 [14] 提出了合作伙伴和代表的想法，对基于复杂联盟的连续生成算法进行了精密设计，提出了有效的多颗粒凝集，可以加入多个合作伙伴以进行任务处理。Sandholm等 [15] 研究了联盟形成产生的边界问题。得出该问题是NP-hard的结论。对双边联盟结构绘制的充要性进行了完整论证。文献 [16] 提出了一种联盟结构最优生成算法，通过对联盟上界的剪枝大大缩小了搜索面积。进化算法， [17] 提出了一种基于解的算法，多代进化和杂交蚁群遗传算法的低效率。对于单一代理联盟的创建， [18] 建设性地引入了“贡献量元素”来评估个体对联盟的贡献量 [19]。使用了记录该团体过去记录的高质量解决方案，并在最合适的粒子突变的基础上使用多组相互平行搜索，防止陷入局部最大值，并筛选粒子簇以加速收敛。这类进化算法虽然拥有比数学规划法更低的计算复杂度，但是得到解的质量会随着问题规模(agent个数与任务个数)的上升而迅速下降。参考文献 [20] 使用差分进化算法用于解决单一agent伙伴问题和粒子质量的速度，并肯定了建立单一工作伙伴关系结构的研究也很有意义，因为在MAS中，多个任务之间并不总是存在优先级，单一实体只允许参与一个联盟，它不能同时支持两个或多个操作。在多智能体系统中单个任务的最佳合作伙伴结构应该有尽可能多的合作伙伴来完成这项任务。在实际中拥有最适合特定任务的agent所组成的联盟被认为是最合适的合作伙伴结构。

3. 问题模型定义

本节给出问题模型的定义，所研究的模型是一个建立于联盟技能博弈模型之上的自由劳务市场。联盟技能博弈中的自立agent符合现实中市场参与者具有相互冲突的偏好。当参与者是自利的情况下，形成稳定的联盟的最为重要的条件是用恰当的合作方式和合理的收益分配。博弈论中的联盟机制考虑了收益如何分配的问题，并提供了若干解决的思路。一个核心的思路是联盟之间可以通过协商，通过任务选择权力之间的交换，达到所有参与者都没有异议的结果。

该联盟主要包括三个集合，用户集 $R:=\left\{r_1,r_2,\cdots ,r_n\right\}$，技能集 $S:=\left\{s_1,s_2,\cdots ,s_l\right\}$，和任务集

$T:=\left\{t_1,t_2,\cdots ,t_m\right\}$，其中 $n=\left|R\right|,l=\left|S\right|,m=\left|T\right|$。其中 $|\ast |$ 代表每一个集合中所包含元素的个数。当 $i=1,2,\cdots ,n$， $j=1,2,\cdots ,l$， $k=1,2,\cdots ,m$， $R{S}_{i,j}=1$ 表示用户 $r_i$ 拥有技能 $s_j$。 $S{T}_{j,k}=1$ 完成任务 $t_k$ 需要技能 $s_j$，否则不需要，任务相应的效益使用向量 $U:\left\{u_1,u_2,\cdots ,u_m\right\}$ 表示。TS表示所有任务的效益分配方案，当 $k=1,2,\cdots ,m$， $j=1,2,\cdots ,l$， $T{S}_{k,\tau }\left(\tau \right)$ 表示在 $\tau$ 时刻， $t_k$ 分配给 $s_j$ 的收益份额。如果 $S{T}_{i,j}=0$，则 $T{S}_{k,j}\left(\tau \right)=-2$。

用户的状态：在 $\tau$ 时，用户 $r_i$ 的状态用一个6元组表示：

$r_i\left(\tau \right):=\langle R{S}_{i,\cdot },cos{t}_{i,\cdot },w_i\left(\tau \right),R{T}_{i,\cdot }\left(\tau \right),provid{e}_{i,\cdot }\left(\tau \right),r{u}_{i,\cdot }\left(\tau \right),RInsy{s}_i\left(\tau \right)\rangle$，矩阵RS的第i行用 $R{S}_{i,\cdot }$ 表示，代表了用户 $r_i$ 拥有的技能。 $cos{t}_{i,\cdot }$ 为矩阵 $cost$ 的第i行，表示用户 $r_i$ 使用相应技能所需花费的成本。 $w_i\left(\tau \right)$ 表示在 $\tau$ 时刻该用户 $r_i$ 的市场权重。 $R{T}_{i,\cdot }\left(\tau \right)$ 为 $RT\left(\tau \right)$ 矩阵的第i行，代表用户 $r_i$ 的当前任务选择情况。 $provid{e}_{i,\cdot }\left(\tau \right)$ 代表技能分配矩阵 $provide\left(\tau \right)$ 第i行， $provid{e}_{i,\cdot }\left(\tau \right)$ 是一个包含l个元素的向量， $provid{e}_{i,j}\left(\tau \right)=1$ 代表用户 $r_i$ 为当前选择的任务提供了技能 $s_j$，否则不为其提供。 $r{u}_{i,\cdot }\left(\tau \right)$ 为一个包含m个元素的向量， $r{u}_i\left(\tau \right):=\left\{r{u}_{i,1}\left(\tau \right),\cdots ,r{u}_{i,k}\left(\tau \right),\cdots ,r{u}_{i,m}\left(\tau \right)\right\}$，其中 $r{u}_{i,k}\left(\tau \right)\ge 0\left(k\in \left\{1,2,\cdots ,m\right\}\right)$ 代表如果用户 $r_i$ 在时刻 $\tau$ 选择任务m将会获得的收益。 $RInsy{s}_i\left(\tau \right)$ 表示当前用户在系统中的存在状态， $RInsy{s}_i\left(\tau \right)=1$ ( $RInsy{s}_i\left(\tau \right)=0$)代表当前用户已经选定一个能够完成的任务并且退出市场(在系统中待选择任务)。

任务的状态：在 $\tau$ 时刻任务 $t_k\in T$ 的状态由一个5元组表示：

$t_k\left(\tau \right):=\langle S{T}_{\cdot ,k},TS{N}_k,u_k,R{T}_{\cdot ,k}\left(\tau \right),T_{k}InSys\left(\tau \right)\rangle$。其中 $S{T}_{\cdot ,k}$ 代表ST的的第k列，是一个包含l个元素的列向

量。 $j\in \left\{1,2,\cdots ,l\right\}$， $k\in \left\{1,2,\cdots ,m\right\}$， $S{T}_{i,k}=1\left(S{T}_{i,k}=0\right)$ 代表完成任务k需要(不需要)技能 $S_j$。 $TS{N}_k$ 代表任务k需要技能的个数。 $u_k$ 是任务 $t_k$ 对应的收益。

$R{T}_{\cdot ,k}\left(\tau \right)$ 代表任务分配矩阵 $RT\left(\tau \right)$ 的第k列，代表当前任务被哪些用户选择。 $T_{k}Insy{s}_i\left(\tau \right)=1$ 代表在时刻 $\tau$ 任务已经获得所有的技能，并且能被完成，下一步将该任务从市场中剔除。 $T_{k}Insy{s}_i\left(\tau \right)=-1$ 代表在时刻 $\tau$，任务 $t_k$ 没有找到全部所需技能或者完成该任务 $t_k$ 所需的用户的技能成本大于所能提供的收益，则将该任务从市场中删除。 $T_{k}Insy{s}_i\left(\tau \right)=0$ 表示在时刻 $\tau$，任务 $t_k$ 处于待完成状态。

任务分配本质上是一个多目标优化问题，而联盟技能博弈问题的目标是找到一个任务分配方式使系统总收益最高。故可设在时刻 ${\tau }_0$ 对n个用户 $\left\{r_1,r_2,\cdots ,r_n\right\}$ 和k个任务 $\left\{t_1,t_2,\cdots ,t_n\right\}$ 进行任务分配得到任务选择矩阵 $R{T}^{n\times k}$ 矩阵中元素为：

$R{T}_{ij}=\{\begin{array}{cc}1& r_i选择任务t_j\\ 0& r_i不选择任务t_j\end{array}$

对任务分配方案的比较在于其收益矩阵和Sum和代价矩阵C，如下所示：

$\{\begin{array}{l}Sum=\left[\begin{array}{ccc}su{m}_{11}& \cdots & su{m}_{1k}\\ ⋮& \ddots & ⋮\\ su{m}_{n1}& \cdots & su{m}_{nk}\end{array}\right]\\ Cost=\left[\begin{array}{ccc}cos{t}_{11}& \cdots & cos{t}_{1k}\\ ⋮& \ddots & ⋮\\ cos{t}_{n1}& \cdots & cos{t}_{nk}\end{array}\right]\end{array}$

$su{m}_{ij}$ 代表任务 $t_j$ 分配给用户agent $r_i$ 的份额。 $cos{t}_{ij}$ 代表用户agent $r_i$ 完成任务 $t_j$ 需要付出的技能成本。

技能提供矩阵 $provid{e}_i^{k\times j}$ 代表了参与者 $agent{r}_i$ 为任务提供技能的情况，技能收益矩阵 $revenu{e}_i^{k\times j}$ 代表了参与者 $agent{r}_i$ 为任务提供技能分别带来的收益。

$\{\begin{array}{l}provide\left[\begin{array}{ccc}provid{e}_{11}& \cdots & provid{e}_{1j}\\ ⋮& \ddots & ⋮\\ provid{e}_{k1}& \cdots & provid{e}_{kj}\end{array}\right]\\ revenue\left[\begin{array}{ccc}revenu{e}_{11}& \cdots & revenu{e}_{1j}\\ ⋮& \ddots & ⋮\\ revenu{e}_{k1}& ⋮& revenu{e}_{kj}\end{array}\right]\end{array}$

其中 $su{m}_{ij}={\displaystyle \underset{i=1}{\overset{k}{\sum }}{\displaystyle \underset{j=1}{\overset{j}{\sum }}provid{e}_{ij}revenu{e}_{ij}}}$，同理可得 $cos{t}_{ij}={\displaystyle \underset{i=1}{\overset{k}{\sum }}{\displaystyle \underset{j=1}{\overset{j}{\sum }}provid{e}_{ij}sigcos{t}_{ij}}}$。

以上两个指标用于衡量任务分配的效果，其对应的总收益和总代价仍如下：

$\{\begin{array}{l}SumRT={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{k}{\sum }}su{m}_{ij}R{T}_{ij}}}\\ SumCost={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{k}{\sum }}su{m}_{ij}}cos{t}_{ij}}\end{array}$

对于给定的 $provid{e}_i^{k\times j}\left(\tau \right)$ 和 $revenu{e}_i^{k\times j}\left(\tau \right)$ 则系统总收益定义为：

$SysRev\left(\tau \right)=SumRT\left(\tau \right)-SumCost(\; \tau \; )$

假设用户具有两种市场状态：调度和待调度状态。调度和待调度状态由该用户 $r_i$ 的市场权重 $w_i$ 在 $\tau$ 时刻的排序先后来决定。处于待调度状态下的用户在选择任务时，首先考虑当前能带来最大收益的任务，而不考虑任务的完成情况。处于待调度状态下的用户 $r_i$ 会放弃当前已获得的个体收益跟随调度者 $r_i$ 去选择共同完成一个可能会带来更大收益的任务。调度者和待调度者的关系以及数量会随着市场复杂情况产生动态的变换。

4. 基于市场协作的多agent任务分配模型

4.1. 阶段1的任务选择策略

为了算法描述方便，首先给出一些定义。

(1) $P\left(i,k,\tau \right)$ 代表在时刻 $\tau$，用户 $r_i$ 能为任务 $t_k$ 提供的技能的集合，记为 $P_{num}\left(i,k,\tau \right)$，其计算公式如下所示：

$p_{num}\left(i,k,\tau \right):=\{\begin{array}{l}{P}_{num}\left(i,k,\tau -1\right)+left\left(\tau \right),R{T}_{i,k}\left(\tau -1\right);\\ nee{d}_{i,k}-{\displaystyle \underset{j=1}{\overset{l}{\sum }}{I}_2\left(i,j,k,\tau \right),否则}\end{array}$

如果 $p_{num}\left(i,k,\tau \right)>0$，则在当前的任务分配情形之下，用户 $r_i$ 能为其选择的任务 $t_k$ 提供技能，若

$p_{num}\left(i,k,\tau \right)=0$，则代表任务 $t_k$ 所需的技能不能被用户 $r_i$ 提供。 ${\displaystyle \underset{i\text{'}\in \left\{1,\cdots ,n\right\},i\text{'}\ne i}{\sum }R{T}_{i\text{'},k}\left(\tau \right)\cdot provid{e}_{i\text{'},j}\left(\tau \right)=0}$ 代表当

用户 $r_i$ 在 $\tau$ 时刻选择任务时，任务 $t_k$ 所需技能 $s_j$ 不被 $R/\left\{r_i\right\}$ 中的用户提供。

${\displaystyle \underset{i\text{'}\in \left\{1,\cdots ,n\right\},i\text{'}\ne i}{\sum }R{T}_{i\text{'},k}\left(\tau -n\right)\cdot provid{e}_{i\text{'},j}\left(\tau -n\right)\ge 1}$ 则代表了用户 $r_i$ 在 $\tau$ 时刻选择任务时，任务 $t_k$ 所需技能 $s_j$ 已被

$R/\left\{r_i\right\}$ 中的一个用户提供。

(2) $N_i\left(\tau \right):=\left\{t_k\in T|P\left(i,k,\tau \right)\ne \varnothing \right\}$。

(3) $complete\left(i,k,\tau \right)$ 代表如果用户 $r_i$ 在时刻 $\tau$ 选择任务k，任务k能不能完成。

$complete\left(i,k,\tau \right):=\{\begin{array}{l}1,R{T}_{i,k}\left(\tau \right)=1\wedge {\displaystyle \underset{j=1}{\overset{l}{\sum }}{I}_1\left(i,k,\tau \right)=TS{N}_k}\\ 0,否则\end{array}$

在 $RT\left(\tau \right)$ 的任务分配情境下，若任务 $t_k$ 拥有所需的技能 $s_j$，则 $I_1\left(j,k,\tau \right)=1$，任务 $t_k$ 没有获得所需技能 $s_j$ 或所需技能在市场中所有用户 $r_i$ 都无法提供时，则 $I_2\left(j,k,\tau \right)=0$。

(4) $C_i\left(\tau \right):=\left\{t_k\in T|complete\left(i,k,\tau \right)=1\right\}$。

(5) $r{u}_{i,k}\left(\tau \right)$ 代表用户 $r_i$ 在时刻 $\tau$ 选择任务 $t_k$，则用户 $r_i$ 能获得个体收益，其计算公式如下：

$r{u}_{i,k}\left(\tau \right)=\{\begin{array}{l}\frac{u_k}{TS{N}_k}\cdot p_{num}\left(i,k,\tau \right),complete\left(t_k,i,\tau \right)\wedge p_{num}\left(i,k,\tau \right)\ne 1\\ 0,否则\end{array}$

其中 $u_k$ 为任务 $t_k$ 对应的收益，所有任务对应的收益用向量 $U:\left\{u_1,u_2,\cdots ,u_m\right\}$ 表示。 $TS{N}_k$ 代表完成任务 $t_k$ 总共需要技能的个数。

用户轮流进行任务选择的过程最优竞争如算法5.1所示。3~10行为单个用户 $r_i$ 在时刻 $\tau +1$ 的选择意向。1~12行为一轮任务选择。

4.2. 下面简单说明算法第一阶段的收敛性

对于任意的两个用户agent ${r^{\prime }}_a$ 和agent ${r^{\prime }}_b$ ( ${r^{\prime }}_a\in R$, ${r^{\prime }}_b\in R$)， ${r^{\prime }}_a$ 和 ${r^{\prime }}_b$ 只有拥有相同的技能和拥有不同的技能这二种情况。第1种情况下，对于双方来说，对方的技能是多余的，所以不会选择对方与其合作，转而去各自寻找能给自己带来最大收益的任务。在第2种情况中， ${r^{\prime }}_a$ 只能选择协助 ${r^{\prime }}_b$ 去完成某个任务，或是分别选择不同的任务。这是因为如果 ${r^{\prime }}_a$ 倾向与 ${r^{\prime }}_b$ 合作而 ${r^{\prime }}_b$ 不意愿与 ${r^{\prime }}_a$ 合作的话， ${r^{\prime }}_a$ 选择的任务将不能被完成， ${r^{\prime }}_a$ 所获得的收益就会为0。则在下一回合选择的过程中， ${r^{\prime }}_a$ 将不再愿意与 ${r^{\prime }}_b$ 合作，将会选择其他能够提供 ${r^{\prime }}_b$ 所拥技能的其他用户进行合作，故在下一回合， ${r^{\prime }}_a$ 也不再需要 ${r^{\prime }}_b$。

4.3. 阶段二的任务选择策略

4.4. 简单说明阶段二算法的有效性

由于任务分配是一个NP难问题，最优竞争阶段无法保证可以为用户分配到最优的任务。因为在最优竞争模型中，用户 $r_i$ 所作出的反应只依托于个体的效益追求，这就意味着可能存在用户agent不满意目前负责的任务。在竞相选择能给自己带来最大收益的任务后，任务参与者通常出现合作行为。例如，在劳务市场中，一个工程项目往往由几个部分组成，如家庭装修需要刷漆工，电工，水工等。拥有最强能力的工人往往拥有工程承办权(即有权力发起合作)。在赢得工程承包的机会后，会邀请要价最低的工人参与其合作以相互配合完成整个项目。各部分的参与者发挥自己的长处配合完成整个项目。在考虑工人愿意放弃当前收益较小任务以获得更高收益的情况下。

5. 实例分析

如图1所示是一个简单的联盟技能博弈模型。在图中 $R=\left\{r_1,r_2\right\}$ 代表2个用户agent， $S=\left\{s_1,s_2\right\}$ 表示两个技能的集合， $T=\left\{t_1,t_2,t_3\right\}$ 表示3个任务的集合。对于任务 $t_1$ 和服务 $t_3$，因为其被完成所需技能个数只有一个，所以任务收益将全部都分配给其唯一需要的技能。对于任务 $t_2$ 由于需要两个技能，则将收益在所需技能之间平均分配( $u_k/TS{N}_k$)。

Figure 1. Graphic representation of coalitional skill game model

图1. 联盟技能博弈的图形表示

对于“阶段1”，若 $r_1$ 和 $r_2$ 都选择任务 $t_2$，则 $r_1$ 和 $r_2$ 的收益均为4。因为用户agent是自利的，在下一回合任务选择中， $r_2$ 将优先选择能够给自己带来最大利益的任务 $t_3$。若 $t_2$ 没有获得所需全部技能的情况下， $r_1$ 也会选择能给自己带来最大收益的任务 $t_1$。所以对于阶段一来说，无论 $r_1$ 和 $r_2$ 在开始选择了哪个任务，最终得到的纳什均衡点都是 $r_1$ 选择 $t_1$， $r_2$ 选择 $t_3$，系统总收益为7。

在“阶段2”，用户权值为所拥有技能的出度的权重之合。 $s_1\to t_1$ 为2， $s_1\to t_2$ 为4， $s_2\to t_2$ 为4， $s_2\to t_3$ 为5，则 $w_{r_1}=0.4$， $w_{r_2}=0.6$。 $w_{r_2}>w_{r_{{}_1}}$，所以服务agnet $r_2$ 比 $r_1$ 更优先享有任务 $t_2$ 的合作发起权，任务 $t_2$ 所缺少技能恰好为 $r_1$ 所拥有，且系统总收益大于原来总收益，故用户 $r_1$ 选择任务 $t_2$。第二谈判的过程包括合作待参与者是否愿意参与合作以及参与合作以后所获得是效益如何分配。这里将系统增加的收入按照权值分配给参与合作的每个任务，则 $r_1$ 的收入为 $2+\left(Su{m}_2-Su{m}_1\right)\ast w_1=2.4$ ( $Su{m}_1=8,Su{m}_2=7$)， $r_2$ 的收入为 $4+\left(Su{m}_2-Su{m}_1\right)\ast w_2=5.6$，不仅系统收益增加，每个人收益也得到提升。

如图2所示的是在给定一个由合作发起者产生的联盟 $R^1=\left\{r_1,r_2,r_3,\cdots ,r_n\right\}$，联盟内成员由竞争状态转变为合作状态的过程。假设 $t_1$ 是一个未获得完成任务全部所需技能的待完成状态， $r_1$ 是合作发起者，不同的颜色代表着不同的选择意向。

Figure 2. The shift in Market conditions

图2. 市场状态转变

6. 仿真结果

仿真环境：内存8 GB；CPU，AMD Ryzen 5 4600U with Radeon；主频，3.6 GHz；操作系统，Win10。

在本节中，将TSABMW的运行结果同以下5种算法运行结果进行了比较：非自利的普通遗传算法(General Genetic Algorithm, GGA)、VAA算法(Vig & Adams’Algorithm, VAA) [21] 和SAA算法(Service and Adams’ Algorithm, SAA) [22]，以及具有自利性的组合拍卖算法(Combinatorial Bids based Algorithm, CBA) [23]、有效的虚拟对策算法(Computationally Efficient Sampled Fictitious Play, CESFP) [24]。仿真所用数据集为随机产生和基于iMPOSE [25] [26] 产生。

6.1. 普通遗传算法最优参数的选取

为了获得普通遗传算法的最佳参数，任意生成一组随机数据，生成方法为： $n=30$， $l=15$， $m=30$。用户具有的技能数量为 $random\left(1,5\right)$，任务需要的技能个数为 $random\left(1,5\right)$。对于该数据集，在不同的交叉概率(crossover probability, CP)和变异概率(mutation probality, MP)下，普通遗传算法运行30次，平均系统收益如表1所示。从实验结果可以看出，当交叉概率为0.1实，变异概率为0.4时，普通遗传算法的平均系统收益得到最大值在表2、表3、表4和表5所示实验结果中，普通遗传算法的参数设置均为：交叉概率为0.1，变异概率为0.4，种群规模为100。

6.2. 算法性能比较

从表2~5可以看出，在大多数情况下，TSABMW算法所得的平均系统收益大于其他自利和非自利算法。因为对于计算有效的采样虚拟对策中的用户agent只知道自己的历史行动和相应的收益，较其他算法中用户agent所获指导行动信息数量较少，其任务分配的效果相对其他算法来说较差。VAA算法中对于联盟形成适应性较为精准的把控，是其能在部分数据集中取得较好收益的保障。从以上表中可以看出TSABMW算法的运行时间小于GGA、VAA和CESFP算法，持平于CBA和SAA算法，其运行时间在多数情况下都是可以接受的。

Table 1. The average system returns of common genetic algorithms

表1. 普通遗传算法的平均系统收益

Table 2. The system revenue and uptime under randomly generated dataset 2

表2. 随机产生的数据集2下的系统收益和运行时间

Table 3. The system revenue and uptime under randomly generated dataset 3

表3. 随机产生的数据集3下的系统收益和运行时间

Table 4. The system revenue and runtime based on the data set 3 generated by iMPOSE

表4. 基于iMPOSE所产生的数据集3下的系统收益和运行时间

Table 5. The system revenue and runtime based on the data set 4 generated by iMPOSE

表5. 基于iMPOSE产生的数据集4下的系统收益和运行时间

7. 总结

本文提出了一种考虑市场权值的二阶段多agent任务分配优化算法。市场中的工人是理性的人，他们总是选择能给他们带来最大个人收益并且容易完成的任务。任务请求者的目标完成任务，即获得全部所需技能。对于理性的市场参与者，只有当效益合理分配并且任务分配达到Nash均衡时，才能保证任务分配结果的稳定性，但自利性必然影响市场总收入的提高。通过市场权值能让用户自发合作去完成为自己带来更大个体收益的任务。在根据最优反应策略选择任务的过程中，执行顺序将会在一定程度上影响威客的个体收益。根据这一特点，本文提出的基于市场权值的协商阶段，进一步调整了市场中复杂任务分配的效益分配不均衡、选择不合理的问题。最后的仿真结果验证了算法的有效性。未来的研究工作将进一步总结威客任务分配的动态特性，考虑威客的诚信度，技能水平等特性，完善动态任务分配模型。并在此基础上提出满足个体理性、预算有效性、隐私保护性、任务分配结果的稳定性等特性的任务分配算法。

NOTES

^*第一作者。

^#通讯作者。