Using Computational Intelligence Algorithms to Solve the Coalition Structure Generation Problem in Coalitional Skill Games

作     者：Yang Liu Guo-Fu Zhang Zhao-Pin Su Feng Yue Jian-Guo Jiang 

作者机构：School of Computer and Information Hefei University of Technology Hefei 230009 China InteUigent Manufacturing Institute Hefei University of Technology Hefei 230009 China Department of Science and Technology Management Hefei University of Technology Hefei 230009 China 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2016年第31卷第6期

页      面：1136-1150页

核心收录：

学科分类：12[管理学] 03[法学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0837[工学-安全科学与工程] 0838[工学-公安技术] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 0306[法学-公安学] 

基　　金：This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 61573125 and 61371155  and the Anhui Provincial Natural Science Foundation of China under Grant Nos. 1608085MF131  1508085MF132  and 1508085QF129 

主　　题：coalitional skill game coalitional structure generation two-dimensional binary encoding heuristic individual repair 

摘      要：Coalitional skill games （CSGs） are a simple model of cooperation in an uncertain environment where each agent has a set of skills that are required to accomplish a variety of tasks and each task requires a set of skills to be completed, but each skill is very hard to be quantified and can only be qualitatively expressed. Thus far, many computational questions surrounding CSGs have been studied. However, to the best of our knowledge, the coalition structure generation problem （CSGP）, as a central issue of CSGs, is extremely challenging and has not been well solved. To this end, two different computational intelligence algorithms are herein evaluated： binary particle swarm optimization （BPSO） and binary differential evolution （BDE）. In particular, we develop the two stochastic search algorithms with two-dimensional binary encoding and corresponding heuristic for individual repairs. After that, we discuss some fundamental properties of the proposed heuristic. Finally, we compare the improved BPSO and BDE with the state-of-the-art algorithms for solving CSGP in CSGs. The experimental results show that our algorithms can find the same near optimal solutions with the existing approaches but take extremely short time, especially under the large problem size.