  The coalition structure formation problem represents an active research area
in multi-agent systems. A coalition structure is defined as a partition of the
agents involved in a system into disjoint coalitions. The problem of finding
the optimal coalition structure is NP-complete. In order to find the optimal
solution in a combinatorial optimization problem it is theoretically possible
to enumerate the solutions and evaluate each. But this approach is infeasible
since the number of solutions often grows exponentially with the size of the
problem. In this paper we present a greedy adaptive search procedure (GRASP) to
efficiently search the space of coalition structures in order to find an
optimal one. Experiments and comparisons to other algorithms prove the validity
of the proposed method in solving this hard combinatorial problem.
