Design, Based On The Algebraic Properties Of The Optimal Coalition Structure Algorithm

With the development of internet's application towards the trend of distribution and interconnection, various means of communication and technology make the computer processing system more intelligent. The conflict of interest when computer systems that represent different interests interact with each other requires that systems must reach an agreement. This development led to the emergence of a new field of computer -multi agent system. Agent act as an entity which owns independence, reaction, sociality, they can be cooperation, consultation, and formed a coalition to complete tasks and benefit together.With the number of agent increasing, the coalition's numbers that agent forming increase exponentially, and the coalition structure's number is unpredictable. Therefore, it is impractical to search exhaustively in such a large number of coalition structures. The generated revenue is not same because of the different coalitions, so how to form coalitions to get the maximum benefit is a very import issue. This article summaries and analyzes coalition structure's properties from the view of algebraic structure, and uses key search set property to design an algorithm-LVAA (Lateral and Vertical Anytime Algorithm) through agent forming coalitions to get the maximum benefit. LVAA algorithm uses branch and bound technology to design a two-step pruning strategy-lateral and vertical pruning, and simplify the searching space. First, it uses a conception of integer split to establish a map between the coalition structure graph and integer split graph. In the lateral pruning, we compare the pruning function with the upper bound of coalition structure value, and prune some coalition structures; second, in vertical pruning, we compare the current optimal value with the upper bound of coalition structures which with the same type in the remaining subspaces. According to results of the comparison, the algorithm prunes some coalition structures of subspaces, and finally finds the optimal value furthermore.The input of the algorithm is coalition values. This paper discusses the cases of solving optimal coalition structure values when coalition values meet for different probability distribution, and the experiment results show that LVAA is more effective at the running time than other's algorithm.