The Coalition Formation Of Multi-agent Based On Genetic Algorithm

To perform tasks in Distributed Problem Solving (DPS) system, agents must form coalition when a single agent cannot perform tasks and tasks cannot be partitioned, or the partition is computationally too complex. Just like other optimization problem, coalition formation need search the optimal solution or quasi-optimal solution in a complex and huge space. If algorithm traverses the whole search space, search process will lead to combination explosion that make it impossible for algorithm to complete search in polynomial time. The common methods include exhaustive method, member-limited method and so on. But the efficiency of these methods is very low; even these methods cannot find feasible solution in some cases. Contraposing the shortage of these methods and the complexity of coalition formation problem, we use Genetic Algorithm (GA) to realize agents?coalition formation.Based on profound investigations and analyses of agents coalition structure and formation, coalition problems are separated into two types in this paper. The mathematical models of these two types of problem are also been founded. To perform simple and indivisible tasks, agents only need to form a single coalition and a GA-based single coalition formation algorithm is introduced in this paper. To perform divisible tasks and sub-tasks have no precedence order, agents need to form several coalitions (coalition structure) and a GA-based coalition structure formation algorithm is introduced in this paper. Aiming at the implicit parallelism of GA and the characteristic of DPS system, we study the parallelization of the former two algorithms. The basic idea is to put forward an agents-based model of parallel coalition formation algorithm on thebasis of Coarse-grained Parallel Genetic Algorithm.