Using binary particle swarm optimization to search for maximal successful coalition

Coalitional Resource Games (CRGs) are a natural and formal framework in which agents wish to form coalitions to pool their scarce resources in order to achieve a set of goals that satisfy all members of a coalition. Thus far, many computational questions surrounding CRGs have been studied, but to ou...

Full description

Saved in:
Bibliographic Details
Published in:Applied intelligence (Dordrecht, Netherlands) Netherlands), 2015-03, Vol.42 (2), p.195-209
Main Authors: Zhang, Guofu, Yang, Renzhi, Su, Zhaopin, Yue, Feng, Fan, Yuqi, Qi, Meibin, Jiang, Jianguo
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Associations
Computer Science
Cooperation
Encoding
Games
Intelligence
Machines
Manufacturing
Mechanical Engineering
Optimization
Performance evaluation
Processes
Repair
Searching
Strategy
Swarm intelligence
Wireless networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Coalitional Resource Games (CRGs) are a natural and formal framework in which agents wish to form coalitions to pool their scarce resources in order to achieve a set of goals that satisfy all members of a coalition. Thus far, many computational questions surrounding CRGs have been studied, but to our knowledge, a number of natural decision problems in CRGs have not been solved. Therefore, in this paper we investigate the possibility of using binary particle swarm optimization (BPSO) as a stochastic search process to search for Maximal Successful Coalition (MAXSC) in CRGs, which is a D P -complete problem. For this purpose, we develop a one-dimensional binary encoding scheme, propose strategies for encoding repair to ensure that each encoding in every iteration process is approximately valid and logicallsy consistent, and discuss some key properties of repair strategies. To evaluate the effectiveness of our algorithms, we compare them with the only other algorithm available in the literature for identifying MAXSC (due to Shrot, Aumann, and Kraus). The result shows that our algorithms are significantly faster especially for large-scale datasets.
ISSN:0924-669X
1573-7497
DOI:10.1007/s10489-014-0589-y