Abstract: Coalition is an important cooperative method in multi-agent system. It is a comp licated combinatorial optimization problem to search for the optimal, task-orien ted agent coalition. An ant colony algorithm is adopted to solve the problem. Du ring the process of solution, ants incline to select those agents who cooperate well before to form coalitions, which realizes the acquaintance mechanism perfec tly. A novel “second pheromone” is proposed to improve the ACA so as not to ge t in the premature convergence easily. The results of contrastive experiments sh ow that this algorithm is superior to other related methods both on the quality of solution and on the convergence rate.