Paper Info
Title
Ant Colony Optimization with Negative Feedback for Solving Constraint Satisfaction Problems
Abstract
As meta-heuristics to solve large-scale constraint satisfaction problems (CSPs), ant colony optimization (ACO) has recently been drawing attentions. In most of algorithms based on ACO, candidate assignments are constructed by taking account of data called pheromone graph. The pheromone graph is updated getting positive feedbacks from candidate assignments with the least number of constraint violations. However, it might be easy to get stuck in locally optimal solutions considering only a single perspective. In this paper, we propose a method that adopting new pheromone graph in addition to the original pheromone graph. This new pheromone graph is updated getting negative feedback from candidate assignments with the greatest number of constraint violations. This new pheromone graph, called a negative pheromone graph, is updated getting negative feedback from candidate assignments with the largest number of constraint violations. Also, the standard pheromone graph is updated by considering negative pheromones as well. By using pheromones updated from two perspectives, more effective search can be conducted. Moreover, in this paper, we conducted experiments on graph coloring problems. Graph coloring problem is one of CSPs. We demnonstrated that our model, which is applied to the cunning ant system, can be effective than other ACO-based methods for large-scale and hard graph coloring problems whose instance appears in the phase transition region.
Year
DOI
Venue
2018
10.1109/TAAI.2018.00041
2018 Conference on Technologies and Applications of Artificial Intelligence (TAAI)
Keywords
Field
DocType
constraint satisfaction,search,meta heuristics,ant colony optimization,graph coloring,phase transition
Ant colony optimization algorithms,Graph,Computer science,Negative feedback,Theoretical computer science,Constraint satisfaction problem,Graph coloring
Conference
ISSN
ISBN
Citations 
2376-6816
978-1-7281-1230-5
0
PageRank 
References 
Authors
0.34
3
3
Name
Order
Citations
PageRank
Takuya Masukane121.14
Kazunori Mizuno24210.55
Hiroto Shinohara300.34