协作成本与完成质量联合优化的任务分配方法研究

论文摘要

任务分配乃社交网络的重要研究问题之一。一般地,任务的完成质量主要由参与人员的技能水平决定。但是,仅考虑技能水平的任务分配,可能引起各自为战,导致完成质量不高。因此,综合考虑技能水平与协作成本的任务分配方法,能为任务的完成质量提供有效保障。由于执行目标的不同,任务分为协作型任务与竞争型任务。协作型任务需要参与人员精诚合作,为实现一个共同的目标而努力,如嫦娥四号的发射;而竞争型任务需要参与各方既斗争又合作,为了结果的公平性而权衡多种影响因素。显而易见,协作型任务的分配应考虑参与人员的技能水平,并最小化参与人员间的协作成本;竞争型任务的分配不但考虑参与人员的技能水平,还应同时考虑参与人员的代表性,最大化参与人员间的协作成本,高的协作成本保证结果的公平性。本文以社交网络为研究背景,重点关注协作成本与任务完成质量,对社交网络的任务分配问题展开了较为系统的研究,主要的工作成果体现在以下几个方面:1)完成质量最优化的协作型任务分配算法:基于概念格理论,发现超大规模在线社交网络中的小团体,利用小团体成员间的强联系属性,结合协作型任务的内在需求,提出一个完成质量最优化的协作型任务分配算法。将协作型任务分配问题建模为一个组合优化问题,并证明了该优化问题具有NP-hard特性,进而提出一个启发式算法进行求解,算法的时间复杂度为t。2)成员影响力与协作成本联合优化的竞争型任务分配方法:综合考虑候选成员的代表性、技能水平与协作成本,提出面向竞争型任务的有效分配算法。考察基于概念格理论生成的小团体,每个小团体中影响力最大的成员作为最佳备选,并权衡候选人员的协作成本,以保证任务执行结果的公平性。将竞争型任务分配问题进行建模,形成了相应的组合优化问题,并证明该组合优化问题具有NP-hard特性,进而提出一个成员影响力与协作成本联合优化的启发式算法对问题进行求解,算法的时间复杂度为。3)为证实所提算法的有效性,本文使用真实数据集进行验证,并与贪心算法进行比较,本文所提算法在组内协作成本,组内最小协作成本、成员规模、运行时间等方面具有更佳性能。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   1.1 研究背景与意义
•   1.2 国内外研究现状
•   1.3 研究内容
•   1.4 论文组织结构
• 第二章 社交网络与任务分配理论基础
•   2.1 社交网络
•   2.2 任务分配
•     2.2.1 任务分配问题
•     2.2.2 组内成员之间的协作成本
•   2.3 社交网络中任务分配问题相关理论
•     2.3.1 协作型任务分配
•     2.3.2 竞争型任务分配
•   2.4 本章小结
• 第三章 完成质量最优化的协作型任务分配方法
•   3.1 任务分配内涵与数学建模
•     3.1.1 问题描述
•     3.1.2 数学模型的建立
•     3.1.3 问题复杂性分析
•   3.2 协作型任务分配最优解算法思路及其分析
•   3.3 协作型任务分配算法
•     3.3.1 概念格理论
•     3.3.2 基于概念格理论的小团体发现
•     3.3.3 算法灵感与系统目标
•     3.3.4 完成质量最优化的协作型任务分配算法
•     3.3.5 算法复杂度分析
•   3.4 实验结果与性能分析
•     3.4.1 实验环境与数据集介绍
•     3.4.2 对比算法
•     3.4.3 实验结果与分析
•   3.5 本章小结
• 第四章 成员影响力与协作成本联合优化的竞争型任务分配方法
•   4.1 任务分配内涵与数学建模
•     4.1.1 问题描述
•     4.1.2 数学模型的建立
•     4.1.3 问题复杂性分析
•   4.2 竞争型任务分配最优解算法思路与分析
•   4.3 竞争型任务分配算法
•     4.3.1 算法灵感
•     4.3.2 成员影响力与协作成本联合优化的竞争型任务分配算法
•     4.3.3 算法复杂度分析
•   4.4 实验结果与性能分析
•     4.4.1 实验环境与数据集介绍
•     4.4.2 对比算法
•     4.4.3 实验结果与分析
•   4.5 本章小结
• 总结与展望
• 参考文献
• 攻读硕士学位期间取得的科研成果
• 致谢

文章来源

类型: 硕士论文

作者: 王倩倩

导师: 尹小燕

关键词: 概念格,社交网络,任务分配,协作成本,小团体

来源: 西北大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 西北大学

基金: 国家自然科学基金项目“异构无线网络透明共存机制优化方法研究(项目编号:61872295)”

分类号: TP301.6;O157.5

总页数: 67

文件大小: 2406K

下载量: 26