Loading…

Ant Population Meta-Heuristics for Binary Constraint Satisfaction Problems

To solve large-scale constraint satisfaction problems, CSPs, we propose an ant colony optimization based meta-heuristics to dynamically control the balance between convergence and diversity in the search. In our method, several groups with different control parameters by which the balance are determ...

Full description

Saved in:
Bibliographic Details
Main Authors: Mizuno, K, Nagasawa, Y, Sasaki, H, Nishihara, S
Format: Conference Proceeding
Language:English
Subjects:
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:To solve large-scale constraint satisfaction problems, CSPs, we propose an ant colony optimization based meta-heuristics to dynamically control the balance between convergence and diversity in the search. In our method, several groups with different control parameters by which the balance are determined are first created, in each of which the same number of artificial ants are stored. Then, the main process is repeated until the system comes to a certain convergence. The main process is composed of two phases: searching by using the Ant System and population tuning, or reorganizing ants' groups. As for the latter phase, after calculating the evaluation value for each ants' group, migration operations of some number of artificial ants from groups with lower evaluation values to groups with higher ones are induced. This method is applied to large-scale and hard binary CSP instances in phase transition regions, whose experimental simulations demonstrate that our meta-heuristics is more efficient than the Ant System.
ISSN:2376-6816
2376-6824
DOI:10.1109/TAAI.2010.58