A population based cunning ant system for constraint satisfaction problems

To solve large-scale constraint satisfaction problems, CSPs, ant colony optimization, ACO, based meta-heuristics has been used. However, the naive ACO based method is sometimes inefficient because the method may require much search time due to ant´s reconstructing candidate solutions. We have applied an ant colony optimization based meta-heuristics with cunning ants in which artificial ants construct a candidate solution by partially using building blocks, or useful partial solutions, of the candidate solution constructed at the previous search generation to CSP instances. In this paper, we propose a cunning ant system with several ant colonies each of which has different search strategies, i.e., borrowing partial solutions generated at the previous cycle. We experimentally demonstrated that our method can be more efficient than the ant system.