Solving permutation constraint satisfaction problems with Artificial Ants
Christine Solnon · 2000
We describe in this paper Ant-P-solver, a generic constraint solver based on the Ant Colony Optimization (ACO) metaheuristic. The ACO metaheuristic 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, i.e., 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 allinterval series and the car sequencing problems.