Advanced Search
    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.

    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.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return