论文部分内容阅读
随着互联网的兴起，互联网上的分布式群体协作也开始流行。人们通过发起和参与各种协作任务完成了很多事情，比如很多的开源软件由广大程序员通过互联网协作完成，比如维基百科这样一部庞大的网络百科全书也由分布在世界各地的参与者们通过互联网协作完成。 互联网上的分布式群体协作过程大致有建立协作任务、招募任务参与者、分配任务、执行任务这几个环节。其中的任务分配环节，把协作任务划分为相对独立的子任务，然后分配给各个参与者执行。任务分配需要考虑几个因素，一是总任务的完成时间要短，一是所有参与者的总的时间花费要小，另外，参与者们的时间花费应当尽量均衡。用传统的图论理论或者整数规划理论，难以寻求到多项式时间复杂度的任务分配算法。本文首先对协作任务进行抽象建模，然后提出一种基于遗传算法的任务分配方法。我们设计了分配方案的编码/解码方法，分配方案的交叉和变异操作，并确定了最适合的选择操作。为了让分配算法取得更好的结果，我们采用自适应的交叉和变异概率，并给出基于当前种群和当前个体的交叉概率和变异概率计算公式。对多个协作任务模型进行实验的结果表明，该算法效果良好，能够以可接受的空间和时间代价寻求到最优或者接近最优的任务分配方案。 而在任务执行环节，参与者们需要对自己的进度进行合理的安排，并且需要同其他参与者进行协调，保证整个协作任务有序高效地向前推进。这些工作可以由参与者本人来完成，但这增加了他们的负担。为了减少参与者们的负担，让参与者们可以更加专注于他们所承担的协作子任务本身，我们设计了本文的“任务指导和参与者协调机制”，帮助参与者们完成这些工作。该机制要求在参与者的工作机器上运行一个守护程序，称之为参与者代理。参与者代理在合适的时间提醒参与者开始或结束相应的工作（学习技能或者执行任务），并且负责同其它参与者进行协调。参与者本人只需要遵从其代理的安排，专注于自己所承担的子任务即可。本文首先借鉴petri网理论和自动机理论，定义一种图，称之为“代理行为图”(PBD)，用于描述参与者代理的行为过程。然后根据寻求到的最优任务分配方案，生成描述参与者代理行为过程的PBD，将其编码后，发送给参与者代理。参与者代理通过解码并模拟PBD运行，完成辅助参与者的工作。