计算机科学 ›› 2019, Vol. 46 ›› Issue (2): 315-320.doi: 10.11896/j.issn.1002-137X.2019.02.048

• 交叉与前沿 • 上一篇    下一篇

模糊多目标进化的社会团队形成方法

金婷1, 谭文安1,2, 孙勇1, 赵尧1   

  1. 南京航空航天大学计算机科学与技术学院 南京2111061
    上海第二工业大学计算机与信息工程学院 上海2010292
  • 收稿日期:2017-12-07 出版日期:2019-02-25 发布日期:2019-02-25
  • 通讯作者: 金 婷(1994-),女,硕士生,主要研究方向为协同计算、团队形成;谭文安(1965-),男,博士,教授,主要研究方向为软件工程及其开发环境技术、智能信息系统等,E-mail:wtan@foxmail.com;谭文安(1965-),男,博士,教授,主要研究方向为软件工程及其开发环境技术、智能信息系统等,E-mail:wtan@foxmail.com
  • 作者简介:孙 勇(1977-),男,博士,主要研究方向为协同计算、跨组织工作流、软件工程等;赵 尧(1994-),女,硕士生,主要研究方向为服务计算和区块链。
  • 基金资助:
    本文受国家自然科学基金项目(61672022,61272036),上海第二工业大学重点学科(XXKZD1604),研究生创新项目(A01GY17F022),安徽省高校自然科学基金重点项目(KJ2017A414)资助。

Social Team Formation Method Based on Fuzzy Multi-objective Evolution

JIN Ting1, TAN Wen-an1,2, SUN Yong1, ZHAO Yao1   

  1. School of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China1
    School of Computer and Information Engineering,Shanghai Polytechnic University,Shanghai 201029,China2
  • Received:2017-12-07 Online:2019-02-25 Published:2019-02-25

摘要: 目前,基于社会网络的团队形成问题研究大多采取0-1规则度量专家技能。针对人们通常使用自然语言描述专家技能的情况,提出模糊多目标进化的社会团队形成方法。该方法研究模糊环境下如何从专家社会网络中查询出合适的个体并组成规模一定的团队,实现最小的通信代价和最优的团队绩效。其采用模糊语言变量代替以0-1规则为代表的精确参数来描述专家技能,使用团队绩效的概念衡量团队对任务P的技能表现力。鉴于标准SPEA2算法在进化初期收敛速度慢的缺点,引入档案精英学习策略生成优良个体。另外,考虑到专家技能的模糊性,文中提出了细粒度Dominance判断作为判断个体间支配关系的新准则。仿真实验结果证明,改进算法的收敛速度快,获得的近似Pareto前沿更加逼近真实解集,可有效求解团队形成问题。

关键词: 进化算法, 模糊语言变量, 社会网络, 团队形成

Abstract: The present team formation researches in social network mostly take 0-1 rule to measure expert skills.Aiming at the situation that people often utilize the natural language to describe expert skills,this paper proposed a social team formation method based on fuzzy multi-objective evolution.This method focuses on how to find out the appropriate individuals from the expert social network to form a team with certain size and achieves the optimization between communication cost and team performance under the uncertainty circumstances.In this method,the precise parameters represented by 0-1 rule are replaced by fuzzy language variables to describe expert skill.The concept of team performance is used to measure team capability.Because the standard SPEA2 algorithm has slow convergence at the initialevolutio-nary stage,this paper introduced AEL strategy to generate individuals with good characteristics.Considering the ambi-guity of expert skills,this paper also proposed a fine-grained Dominance judgment as the new rule of judging the dominance relationship of individuals.The simulation results show that the improved algorithm converges fast and obtains good quality approximate PF,which can be successfully applied to solve the team formation problem.

Key words: Evolutionary algorithm, Fuzzy language variables, Social network, Team formation

中图分类号: 

  • TP311
[1]LAPPAS T,LIU K,TERZI E.Finding a team of experts in social networks[C]∥Proceedings of the 15th ACM SIGKDD International Conf. on Knowledge Discovery and Data Mining.New York:ACM,2009:467-476.
[2]LI C T,SHAN M K.Team formation for generalized tasks in expertise social networks[C]∥Proceedings of IEEE International Conference on Social Computing.Piscataway,NJ:IEEE,2010:9-16.
[3]KARGAR M,AN A.Discovering top-k teams of experts with/without a leader in social networks[C]∥Proceedings of the 20th ACM International Conference on Information and Knowledge Management.New York:ACM,2011:985-994.
[4]KARGAR M,ZIHAYAT M,AN A.Finding affordable and collaborative teams from a network of experts[C]∥Proceedings of the 13th SIAM International Conference on Data Mining.2013:587-595.
[5]KARGAR M,AN A,ZIHAYAT M.Efficient Bi-objective Team Formation in Social Networks[C]∥Proceedings of 2012 European Conference on Machine Learning & Knowledge Discovery in Databases.Berlin:Springer-Verlag,2012:483-498.
[6]SUN Y,TAN W A,LI L,et al.A new method to identify colla- borative partners in social service provider networks[J].Information Systems Frontiers,2016,18(3):565-578.
[7]SUN Y,TAN W A.Cross-Organizational Workflow Task Allocation Algorithms for Socially Aware Collaborative Computing[J].Journal of Computer Research and Development,2017,54(9):1865-1879.(in Chinese)
孙勇,谭文安.支持社会协同计算的跨组织工作流任务分派算法[J].计算机研究与发展,2017,54(9):1865-1879.
[8]SUN H L,JIN M Y,LIU J L,et al.Methods for Team Formation Problem with Grouping Task in Social Networks[J].Journal of Computer Research and Development,2015,52(11):2535-2544.(in Chinese)
孙焕良,金洺宇,刘俊岭,等.社会网络上支持任务分组的团队形成方法[J].计算机研究与发展,2015,52(11):2535-2544.
[9]FARHADI F,SORKHI M,HASHEMI S,et al.An effective expert team formation in social networks based on skill grading[C]∥Proceedings of 2011 IEEE 11th International Conference on Data Mining Workshops (ICDMW).New York:IEEE,2011:366-372.
[10]SUN H L,FU S S,LIU J L,et.al.Team Formation with Weak Ties in Social Networks[J].Journal of Frontiers of Computer Science and Technology,2016,10(6):773-785.(in Chinese)
孙焕良,富珊珊,刘俊岭,等.社会网络中弱关系团队形成问题研究[J].计算机科学与探索,2016,10(6):773-785.
[11]XIE C W,WANG Z J,XIA X W.Multi-Objective Evolutionary Algorithm Based on Archive-Elite Learning and Opposition-Based Learning[J].Chinese Journal of Computers,2017,40(3):757-772.(in Chinese)
谢承旺,王志杰,夏学文.应用档案精英学习和反向学习的多目标进化算法[J].计算机学报,2017,40(3):757-772.
[12]BAYKASOGLU A,DERELI T,DAS S.Project team selection using fuzzy optimization approach[J].Cybernetics and Systems,2007,38(2):155-185.
[1] 刘宝宝, 杨菁菁, 陶露, 王贺应.
基于DE-LSTM模型的教育统计数据预测研究
Study on Prediction of Educational Statistical Data Based on DE-LSTM Model
计算机科学, 2022, 49(6A): 261-266. https://doi.org/10.11896/jsjkx.220300120
[2] 孙刚, 伍江江, 陈浩, 李军, 徐仕远.
一种基于切比雪夫距离的隐式偏好多目标进化算法
Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance
计算机科学, 2022, 49(6): 297-304. https://doi.org/10.11896/jsjkx.210500095
[3] 邵玉, 陈崚, 刘维.
独立级联模型下基于最大似然的负影响力源定位方法
Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model
计算机科学, 2022, 49(2): 204-215. https://doi.org/10.11896/jsjkx.201100190
[4] 李笠, 李广鹏, 常亮, 古天龙.
约束进化算法及其应用研究综述
Survey of Constrained Evolutionary Algorithms and Their Applications
计算机科学, 2021, 48(4): 1-13. https://doi.org/10.11896/jsjkx.200600151
[5] 周晟伊, 曾红卫.
进化算法与符号执行结合的程序复杂度分析方法
Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution
计算机科学, 2021, 48(12): 107-116. https://doi.org/10.11896/jsjkx.210200052
[6] 赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏.
基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法
Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform
计算机科学, 2021, 48(11A): 30-38. https://doi.org/10.11896/jsjkx.201200085
[7] 朱汉卿, 马武彬, 周浩浩, 吴亚辉, 黄宏斌.
基于改进多目标进化算法的微服务用户请求分配策略
Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms
计算机科学, 2021, 48(10): 343-350. https://doi.org/10.11896/jsjkx.201100009
[8] 张清琪, 刘漫丹.
复杂网络社区发现的多目标五行环优化算法
Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery
计算机科学, 2020, 47(8): 284-290. https://doi.org/10.11896/jsjkx.190700082
[9] 杨卓璇, 马源培, 严冠.
基于耦合强度的多项式时间社团探测算法
Polynomial Time Community Detection Algorithm Based on Coupling Strength
计算机科学, 2020, 47(6A): 102-107. https://doi.org/10.11896/JsJkx.190900170
[10] 董明刚, 弓佳明, 敬超.
基于谱聚类的多目标进化社区发现算法研究
Multi-obJective Evolutionary Algorithm Based on Community Detection Spectral Clustering
计算机科学, 2020, 47(6A): 461-466. https://doi.org/10.11896/JsJkx.191100215
[11] 富坤, 仇倩, 赵晓梦, 高金辉.
基于节点演化分阶段优化的事件检测方法
Event Detection Method Based on Node Evolution Staged Optimization
计算机科学, 2020, 47(5): 96-102. https://doi.org/10.11896/jsjkx.190400072
[12] 杨浩, 陈红梅.
基于量子进化算法的非平衡数据混合采样算法
Mixed-sampling Method for Imbalanced Data Based on Quantum Evolutionary Algorithm
计算机科学, 2020, 47(11): 88-94. https://doi.org/10.11896/jsjkx.191000102
[13] 王瑄, 毛莺池, 谢在鹏, 黄倩.
基于差分进化的推断任务卸载策略
Inference Task Offloading Strategy Based on Differential Evolution
计算机科学, 2020, 47(10): 256-262. https://doi.org/10.11896/jsjkx.190800159
[14] 谢腾宇,周晓根,胡俊,张贵军.
基于接触图残基对距离约束的蛋白质结构预测算法
Contact Map-based Residue-pair Distances Restrained Protein Structure Prediction Algorithm
计算机科学, 2020, 47(1): 59-65. https://doi.org/10.11896/jsjkx.181202395
[15] 李章维, 郝小虎, 张贵军.
蛋白质结构从头预测多级个体筛选进化算法
Multi-layer Screening Based Evolution Algorithm for De Novo Protein Structure Prediction
计算机科学, 2019, 46(6A): 80-84.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!