Abstract: In multi agent systems, it can improve agent’s abilities of problem solving to form coalition. So, coalition is an important cooperative method in multiagent systems. But the number of the possible coalitions is exponential since each agent can form coalition with others. Essentially, forming agent coalition is a combinatorial optimization problem. As a modern optimization method, differential evolution (DE) introduced by Storn and Price in 1997 is one of the most successful evolutionary algorithms which are adopted to solve this problem. The original differential evolution which is based on the individual differential reconstruction idea is designed for the global continuous optimization problem. In order to solve the combinatorial optimization problem by DE, in this paper, a novel binaryencoding differential evolution (BDE) algorithm is presented and applied to find out agent coalition fast and efficiently. By using a Sigmoid function, the new algorithm constrains the result of mutation operator in 0,1, so as to adopt the combinatorial optimization problem. Some simulations which include 30 agents have been achieved for the novel binaryencoding differential evolution, genetic algorithm (GA) and ant colony algorithm (ACA). The experimental results show that the new algorithm is feasible and efficient. It is superior to other related methods such as GA and ACA both on the quality of solution and on the convergence rate.