Ants with Limited Memory for solving constraint satisfaction problems

Ant colony optimization (ACO) metaheuristic-based algorithms have been successfully applied to solve large-scale constraint satisfaction problems (CSPs). In this paper, we present a novel algorithm, the Limited-Memory Ant-Solver, that extends the state-of-the-art ACO algorithm for solving random, binary CSPs, the Ant-Solver. The ants in our approach have limited memory, enabling them to recall partial assignments from their previous iteration while building new ones. We empirically show that our algorithm matches the Ant-Solver with respect to multiple performance criteria. When combined with local search techniques, our approach is again equally effective as Ant-Solver, but it is vastly superior in efficiency for solving large CSPs.