You are here

A Study into Ant Colony Optimization, Evolutionary Computation and Constraint Programming on Binary Constraint Satisfaction Problems

TitleA Study into Ant Colony Optimization, Evolutionary Computation and Constraint Programming on Binary Constraint Satisfaction Problems
Publication TypeConference Paper
Year of Publication2004
Authorsvan Hemert, JI, Solnon, C
Conference NameSpringer Lecture Notes on Computer Science
PublisherSpringer-Verlag, Berlin
EditorGottlieb, J, Raidl, G
ISBN Number3-540-21367-8
Keywordsant colony optimisation; constraint programming; constraint satisfaction; evolutionary computation
Abstract

We compare two heuristic approaches, evolutionary computation and ant colony optimisation, and a complete tree-search approach, constraint programming, for solving binary constraint satisfaction problems. We experimentally show that, if evolutionary computation is far from being able to compete with the two other approaches, ant colony optimisation nearly always succeeds in finding a solution, so that it can actually compete with constraint programming. The resampling ratio is used to provide insight into heuristic algorithms performances. Regarding efficiency, we show that if constraint programming is the fastest when instances have a low number of variables, ant colony optimisation becomes faster when increasing the number of variables.

Full Text