Research On Coalition Formation Under Bounded Resources

Coalition formation (CF) problem is a very active research topic in MAS, autonomous agents how to form coalitions to improve system efficiency, is the difficulty of the research in CF. The current research on CF usually assumes that an agent’s resource is infinite, we still need to study CF under bounded resources. In addition, a lot of problems in CF are computationally difficult, which is hard to use the global search strategy. Some technologies in swarm intelligence provide a train of thought to solve the CF.In view of the above background, this paper focuses on the research based on swarm intelligence technology to solve the problem of overlapping coalition formation under bounded resources and successful coalition formation in coalitional resource games.Try to achieve agents form the coalitions flexiblely, efficiently and rapidly to complete tasks under bounded resources.This research can provide the theoretical guidance and technical support for the application of CF problem in a complex environment. The study contents and innovations of the dissertation are as follows:(1) Analyze some swarm intelligence algorithms for overlapping coalition formation. Through the analysis of the three algorithms, we put forward characteristics and disadvantages of these algorithms, which provide theoretical guidance for the latter study.(2) Propose a revision algorithm for invalid encodings. Through the analysis of the relationship between agents and coalitions in overlapping coalition formation, we put forward the concept of the real contribution and residual contribution of an agent. Design a row-check algorithm without considering the amounts of the contribution of agents in coalitions. Our algorithm can achieve that each agent joins in different coalitions freely and improve the efficiency of the system.(3) Present an algorithm based on one-dimensional binary coding strategy and discrete particle swarm optimization to search for successful coalitions in coaitional resource games. According to the different preferences of agents and goals in practice, we put forward two kinds of different revision strategies. Through the analysis of the complexity of the algorithms, the proposed algorithms can get optimal solutions in polynomial time by using the fast convergence of particle swarm optimization. The simulation results show that, compared to the global search algorithms, the proposed algorithms can guarantee the quality of solutions and reduce the time and resource cost.