A Coalition Generation Algorithm Based on Local Optimum

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.