Ant Population Meta-Heuristics for Binary Constraint Satisfaction Problems

To solve large-scale constraint satisfaction problems, CSPs, we propose an ant colony optimization based meta-heuristics to dynamically control the balance between convergence and diversity in the search. In our method, several groups with different control parameters by which the balance are determined are first created, in each of which the same number of artificial ants are stored. Then, the main process is repeated until the system comes to a certain convergence. The main process is composed of two phases: searching by using the Ant System and population tuning, or reorganizing ants' groups. As for the latter phase, after calculating the evaluation value for each ants' group, migration operations of some number of artificial ants from groups with lower evaluation values to groups with higher ones are induced. This method is applied to large-scale and hard binary CSP instances in phase transition regions, whose experimental simulations demonstrate that our meta-heuristics is more efficient than the Ant System.