A Coalition Generation Algorithm Based on Local Optimum

Su Shexiong; Hu Shanli; Lin Chaofeng; Zheng Shengfu

Journal of Computer Research and Development > 2007 > 44(2): 277-281.

Su Shexiong, Hu Shanli, Lin Chaofeng, Zheng Shengfu. A Coalition Generation Algorithm Based on Local Optimum[J]. Journal of Computer Research and Development, 2007, 44(2): 277-281.

Citation:

Su Shexiong, Hu Shanli, Lin Chaofeng, Zheng Shengfu. A Coalition Generation Algorithm Based on Local Optimum[J]. Journal of Computer Research and Development, 2007, 44(2): 277-281.

Citation:

Su Shexiong, Hu Shanli, Lin Chaofeng, Zheng Shengfu. A Coalition Generation Algorithm Based on Local Optimum[J]. Journal of Computer Research and Development, 2007, 44(2): 277-281.

PDF (305 KB)

A Coalition Generation Algorithm Based on Local Optimum

1(Department of Computer Science and Technology, Fuzhou University, Fuzhou 350002) 2(Key Laboratory for Computer Science, Chinese Academy of Sciences, Beijing 100080)

More Information

Published Date: February 14, 2007

Graphical Abstract

Abstract

Abstract

Coalition formation is a key topic in multi-agent systems. To solve the problem of the number of coalition structure increasing rapidly, OCS algorithm—formation of agent coalition structure based on local optimum is given. Based on local optimum, the graph of agent coalition structure can be shirt cut and the graph of agent coalition structure is pruned by using the upper bound of coalition structures referred to the partition, which decreases the searching space. Then it is proved that the time complexity of OCS is O(3\+n), but experimentally it is already close to O(23n/2). Finally, by contrasting the data, the efficiency of the OCS is indicated. This work can be seen as the improvement of Rothkopf and Liu Jinglei's related work.
- multi agent system,
- coalition structure,
- local optimum,
- OCS algorithm,
- partition

FullText(HTML)

References (0)

[1]	Shang Junlin, Zhang Zhenyu, Qu Wenwen, Wang Xiaoling. Survey of Graph Partitioning Techniques for Distributed Graph Computing[J]. Journal of Computer Research and Development, 2025, 62(1): 90-103. DOI: 10.7544/issn1000-1239.202330790
[2]	Shi Huikang, Wang Zesheng, Hu Kekun, Dong Gang, Zhao Youjian. An Algorithms of Distributed Buffered Streaming Graph Partitioning[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202330386
[3]	Li Qi, Zhong Jiang, Li Xue. DyBGP: A Dynamic-Balanced Algorithm for Graph Partitioning Based on Heuristic Strategies[J]. Journal of Computer Research and Development, 2017, 54(12): 2851-2857. DOI: 10.7544/issn1000-1239.2017.20160690
[4]	Zheng Lili, Wu Jigang, Chen Yong, Zhu Meixia. Balanced k-Way Partitioning for Weighted Graphs[J]. Journal of Computer Research and Development, 2015, 52(3): 769-776. DOI: 10.7544/issn1000-1239.2015.20131508
[5]	Li Yefeng, Le Jiajin, and Wang Mei. A Column-Store Based Bucket Partition Algorithm for Range Queries[J]. Journal of Computer Research and Development, 2013, 50(3): 594-601.
[6]	Rong Chuitian, Xu Tianren, Du Xiaoyong. Partition-Based Set Similarity Join[J]. Journal of Computer Research and Development, 2012, 49(10): 2066-2076.
[7]	Jia Yaocang, Wu Chenggang, Zhang Zhaoqing. Program’s Performance Profiling Optimization for Guiding Static Cache Partitioning[J]. Journal of Computer Research and Development, 2012, 49(1): 93-102.
[8]	Yao Yiping and Zhang Yingxing. An Optimized Partitioning Algorithm for Complex Network Based on Social Simulations on Cluster Computing Platform[J]. Journal of Computer Research and Development, 2011, 48(9): 1759-1767.
[9]	Zhu Lin, Wang Shitong, Deng Zhaohong. Research on Generalized Fuzzy C-Means Clustering Algorithm with Improved Fuzzy Partitions[J]. Journal of Computer Research and Development, 2009, 46(5): 814-822.
[10]	Wang Yiran, Chen Li, Feng Xiaobing, Zhang Zhaoqing. Global Partial Replicate Computation Partitioning[J]. Journal of Computer Research and Development, 2006, 43(12): 2158-2165.