基于多目标贪心策略的增益最大化团队构建算法
|
摘要
研究了满足一定约束条件的协同作业团队的构建。针对传统构建忽略了团队成员在协作过程中个体技能可增加这一因素,提出了团队构建的统一优化目标函数问题,并在综合考虑协同作业任务所需技能集合覆盖约束和团队成员之间交流代价最小化约束的基础上,引入了团队成员增益最大化约束。针对该多目标优化问题,提出了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).
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).
引文
[1]Wi H,Oh S,Mun J,et al.A team formation model based on knowledge and collaboration[J].Expert Systems with Applications,2012,40(1):9121-9134
[2]Stranad D,Guid N.A fuzzy-genetic decision support system for project team formation[J].Journal of Applied Soft Computing,2010,10(4):1178-1187
[3]Agrawal R,Golshan R,Terzi E.Grouping students in educational settings[C].In:Proceedings of the 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,New York,USA,2014.1017-1026
[4]Yang Y,Chen W J,Yang J.Team formation in business process context[C].In:Proceedings of the 21th IEEE International Conference on Computer Supported Cooperative Work in Design,Wellington,New Zealand,2017.73-78
[5]Budak G,Kara,9 Y T,et al.New mathematical models for team formation of sports clubs before the match[J].Central European Journal of Operations Research,2017(1):1-17
[6]Lappas T,Liu K,Terzi E.Finding a team of experts in social networks[C].In:Proceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,Paris,France,2009.467-475
[7]Kargar M,An A.Discovering top-k teams of experts with/without a leader in social networks[C].In:Proceedings of the 20th International Conference on Information and Knowledge Management(CIKM),Scotland,UK,2011.985-994
[8]Kargar M,An A,Zihayat M.Efficient bi-objective team formation in social networks[C].In:Proceedings of European Conference on Machine Learning and Knowledge Discovery in Databases,Bristol,UK,2012.483-498
[9]Juang M C,Huang C C,Huang J L.Efficient algorithms for team formation with a leader in social networks[J].Journal of Supercomputing,2013,66(2):721-737
[10]Datta S,Majumder A,Naidu K.Capacitated team formation problem on social networks[C].In:Proceedings of the 18th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,Beijing,China,2012.1005-1013
[11]Anagnostopoulos A,Becchetti L,Castillo C.Online team formation in social networks[C].In:Proceedings of the21th International Conference on World Wide Web,Lyon,France,2012.839-848
[12]Nikolaev A,Gore S,Govindaraju V.Engagement capacity and engaging team formation for reach maximization of online social media platforms[C].In:Proceedings of the22th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,San Francisco,USA,2016
[13]Wang X Y,Zhao Z,Ng W.USTF:A unified system of team formation[J].Journal of IEEE transactions on big data,2016,2(1):70-84
[14]Tang S J.Profit-driven team grouping in social networks[C].In:Proceedings of the 31th AAAI Conference on Artificial Intelligence,San Francisco,USA,2017.45-51
[15]Garrett J,Gopalakrishna S.Sales team formation:the right team member helps performance[J].Journal of Industrial Marketing Management,2017.Doi:10.1016/j.indmarman.2017.06.007
[16]殷建平,徐云,王刚等译.算法导论[M].第三版.北京:机械工业出版社,2014.658
[17]Apache Organization.The apache commons mathematics library[EB/OL].http://commons.apache.org/proper/commons-math:Apache,2017
[2]Stranad D,Guid N.A fuzzy-genetic decision support system for project team formation[J].Journal of Applied Soft Computing,2010,10(4):1178-1187
[3]Agrawal R,Golshan R,Terzi E.Grouping students in educational settings[C].In:Proceedings of the 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,New York,USA,2014.1017-1026
[4]Yang Y,Chen W J,Yang J.Team formation in business process context[C].In:Proceedings of the 21th IEEE International Conference on Computer Supported Cooperative Work in Design,Wellington,New Zealand,2017.73-78
[5]Budak G,Kara,9 Y T,et al.New mathematical models for team formation of sports clubs before the match[J].Central European Journal of Operations Research,2017(1):1-17
[6]Lappas T,Liu K,Terzi E.Finding a team of experts in social networks[C].In:Proceedings of the 15th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,Paris,France,2009.467-475
[7]Kargar M,An A.Discovering top-k teams of experts with/without a leader in social networks[C].In:Proceedings of the 20th International Conference on Information and Knowledge Management(CIKM),Scotland,UK,2011.985-994
[8]Kargar M,An A,Zihayat M.Efficient bi-objective team formation in social networks[C].In:Proceedings of European Conference on Machine Learning and Knowledge Discovery in Databases,Bristol,UK,2012.483-498
[9]Juang M C,Huang C C,Huang J L.Efficient algorithms for team formation with a leader in social networks[J].Journal of Supercomputing,2013,66(2):721-737
[10]Datta S,Majumder A,Naidu K.Capacitated team formation problem on social networks[C].In:Proceedings of the 18th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,Beijing,China,2012.1005-1013
[11]Anagnostopoulos A,Becchetti L,Castillo C.Online team formation in social networks[C].In:Proceedings of the21th International Conference on World Wide Web,Lyon,France,2012.839-848
[12]Nikolaev A,Gore S,Govindaraju V.Engagement capacity and engaging team formation for reach maximization of online social media platforms[C].In:Proceedings of the22th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,San Francisco,USA,2016
[13]Wang X Y,Zhao Z,Ng W.USTF:A unified system of team formation[J].Journal of IEEE transactions on big data,2016,2(1):70-84
[14]Tang S J.Profit-driven team grouping in social networks[C].In:Proceedings of the 31th AAAI Conference on Artificial Intelligence,San Francisco,USA,2017.45-51
[15]Garrett J,Gopalakrishna S.Sales team formation:the right team member helps performance[J].Journal of Industrial Marketing Management,2017.Doi:10.1016/j.indmarman.2017.06.007
[16]殷建平,徐云,王刚等译.算法导论[M].第三版.北京:机械工业出版社,2014.658
[17]Apache Organization.The apache commons mathematics library[EB/OL].http://commons.apache.org/proper/commons-math:Apache,2017