基于多目标贪心策略的增益最大化团队构建算法  

Team formation algorithms with team gain maximization based on multi-objective greedy strategy

作　　者：宋永浩 史骁 胡斌[1] 金岩[1] 杜翠兰[3] 井雅琪 赵晓芳[1] Song Yonghao;Shi Xiao;Hu Bin;Jin Yan;Du Cuilan;Jing Yaqi;Zhao Xiaofang(Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190;School of Computer and Control Engineering,University of Chinese Academy of Sciences,Beijing 101408;National Computer Network Emergency Response Technical Team/Coordination Center of China,Beijing 100029)

机构地区：[1]中国科学院计算技术研究所,北京100190 [2]中国科学院大学计算机与控制学院,北京101408 [3]国家计算机网络应急技术处理协调中心,北京100029

出　　处：《高技术通讯》2018年第4期279-290,共12页Chinese High Technology Letters

基　　金：国家自然科学青年基金(No.61202413)资助项目

摘　　要：研究了满足一定约束条件的协同作业团队的构建。针对传统构建忽略了团队成员在协作过程中个体技能可增加这一因素,提出了团队构建的统一优化目标函数问题,并在综合考虑协同作业任务所需技能集合覆盖约束和团队成员之间交流代价最小化约束的基础上,引入了团队成员增益最大化约束。针对该多目标优化问题,提出了3种基于贪心策略的启发式团队构建算法,即基于最小集合覆盖贪心策略的团队构建算法——贪心集覆盖算法(GSCA)、基于团队增益最大化贪心策略的团队构建算法——贪婪团队增益算法(GTGA)和基于多路径(MR)贪心策略的团队构建算法——MRGTGA。大量实验证明,GSCA较适用于交流代价极高的远程协作环境,MRGTGA较适用于对算法运行效率要求不高、但对整体增益最大化要求极高的场景,GTGA构建的团队整体增益值接近精确解(其值达到暴力枚举算法的96.70%),同时该算法运行效率极高(其计算时间接近GSCA)。The formation of the collaboration teams meeting certain constraints is studied. Considering that traditional team formation ignores that team members can enhance their skills during the collaboration,the problem of unified objective function optimization for team formation is proposed,and based on the comprehensive consideration of cover constraints for skill sets required for collaborative tasks and minimization constraints of exchange costs among team members,a team gain maximization constraint is also introduced. To solve the multi-objective optimization problem,three heuristic team formation algorithms based on greedy strategies are proposed to maximize the unified objective function. They are the team formation algorithm based on minimum set cover： greedy strategy,the greedy set cover algorithm（ GSCA）; team gain maximization greedy strategy; the greedy team gain algorithm（ GTGA） and multi-route GTGA（ MRGTGA）,respectively. The extensive experimental results indicate that GSCA is more appropriate for the（ remote） collaboration scenario with extremely high communication cost,MRGTGA is more appropriate for the collaboration scenario where entirety team gain maximization is required,no matter how complexity of the algorithm,and the entirety gain of the team formed by GTGA is approximately close to optimum（ The value is96. 70% of the brute-force enumerate algorithm）,meanwhile GTGA has the extremely high algorithm efficiency（ The computation time is close to GSCA）.

关 键 词：团队构建 团队增益 交流代价 多目标优化 贪心策略 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]