Abstract:

We describe in this paper Ant-P-solver, a generic constraint solver based on the Ant Colony Optimization meta-heuristic. This approach takes inspiration on the observation of real ants collective foraging behaviour. The idea is to model the problem as the search of a best path in a graph. Artificial ants walk trough this graph, in a stochastic and incomplete way, searching for good paths. Artificial ants communicate in a local and indirect way, by laying a pheromone trail on the edges of the graph.

Ant-P-solver has been designed to solve a general class of combinatorial problems: permutation constraint satisfaction problems, the goal of which is to find a permutation of n known values, to be assigned to n variables, under some constraints. Many constraint satisfaction problems involve such global permutation constraints. Ant-P-solver capabilities are illustrated, and compared with other approaches, on three of these problems, i.e., the n-queens, the all-interval series and the car-sequencing problems.
 
Full paper (postscript)