Abstract: When solving the multi-task coalition problem(MTCP),the ant colony optimization(ACO) algorithm showed deficiencies such as too many iterations and low solution accuracy.For problems above,the ACO algorithm based on relative distance and association frequency was proposed,which adopted two strategies in view of search mechanism and pheromone increment model.First,in order to improve the utilization of resources,the concept of relative distance was introduced,based on which,a more effective search mechanism was proposed.Then,to strengthen the collaborations among ants and make full use of answer information obtained,a pheromone increment model based on association frequency was established.Experiment shows that the proposed algorithm can not only get much more optimal solutions but also greatly enhance convergence speed compared with related algorithms.