Abstract
We describe a novel incomplete approach for solving constraint satisfaction problems (CSPs) based on the ant colony optimization (ACO) metaheuristic. The idea is to use artificial ants to keep track of promising areas of the search space by laying trails of pheromone. This pheromone information is used to guide the search, as a heuristic for choosing values to be assigned to variables. We first describe the basic ACO algorithm for solving CSPs and we show how it can be improved by combining it with local search techniques. Then, we introduce a preprocessing step, the goal of which is to favor a larger exploration of the search space at a lower cost, and we show that it allows ants to find better solutions faster. Finally, we evaluate our approach on random binary problems.
Keywords
Constraint satisfaction problemAnt colony optimization algorithmsComputer scienceMetaheuristicConstraint satisfactionMathematical optimizationBacktrackingGuided Local SearchPreprocessorLocal search (optimization)HeuristicArtificial intelligenceConstraint programmingAnt colonyMathematicsAlgorithm
Affiliated Institutions
Related Publications
Ant colony system: a cooperative learning approach to the traveling salesman problem
This paper introduces the ant colony system (ACS), a distributed algorithm that is applied to the traveling salesman problem (TSP). In the ACS, a set of cooperating agents calle...
Ant Colony Optimization
Swarm intelligence is a relatively new approach to problem solving that takes inspiration from the social behaviors of insects and of other animals. In particular, ants have ins...
Solving symmetric and asymmetric TSPs by ant colonies
We present ACS, a distributed algorithm for the solution of combinatorial optimization problems which was inspired by the observation of real colonies of ants. We apply ACS to b...
Ants can colour graphs
AbstractIn the last few years researchers have shown how insect colonies can be seen as a natural model of collective problem solving. The analogy between the behaviour of ants ...
A new version of ant system for subset problems
Early applications of Ant Colony Optimization (ACO) have been mainly concerned with solving ordering problems (e.g., traveling salesman problem). We introduce a new version of A...
Publication Info
- Year
- 2002
- Type
- article
- Volume
- 6
- Issue
- 4
- Pages
- 347-357
- Citations
- 193
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
193
OpenAlex
Cite This
Christine Solnon
(2002).
Ants can solve constraint satisfaction problems.
IEEE Transactions on Evolutionary Computation
, 6
(4)
, 347-357.
https://doi.org/10.1109/tevc.2002.802449
Identifiers
- DOI
- 10.1109/tevc.2002.802449