Ant Colony Optimization with Multi-Pheromones for Solving Constraint Satisfaction Problems

被引：0

作者：

Masukane, Takuya ^{[1
]}

Mizuno, Kazunori ^{[1
]}

机构：

[1] Takushoku Univ, Fac Engn, Dept Comp Sci, Tokyo, Japan

来源：

2016 CONFERENCE ON TECHNOLOGIES AND APPLICATIONS OF ARTIFICIAL INTELLIGENCE (TAAI) | 2016年

基金：

日本学术振兴会;

关键词：

constraint satisfaction; search; meta heuristics; ant colony optimization; graph coloring; phase transition;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

To solve large-scale constraint satisfaction problems, CSPs, ant colony optimization, ACO, based meta-heuristics has been effective. However, the naive ACO based method is sometimes inefficient because the method has only single pheromone trails. In this paper, we propose an ant colony optimization based meta-heuristics with multi pheromone trails in which artificial ants construct a candidate assignment by referring several pheromone trail graphs to solve CSP instances. We also implement the proposed model to some ACO based methods, demonstrating how our method is effective for solving graph coloring problems that is one of typical examples of CSPs.

引用

页码：110 / 115

页数：6

共 17 条

[1] Ant colony optimization techniques for the vehicle routing problem [J].

Bell, JE ;

McMullen, PR .

ADVANCED ENGINEERING INFORMATICS, 2004, 18 (01) :41-48

[2] An ant-based algorithm for coloring graphs [J].

Bui, Thang N. ;

Nguyen, ThanhVu H. ;

Patel, Chirag M. ;

Phan, Kim-Anh T. .

DISCRETE APPLIED MATHEMATICS, 2008, 156 (02) :190-200

[3]

Cheeseman P., 1991, P 12 INT JOINT C ART, V1, P331

[4] Ant system: Optimization by a colony of cooperating agents [J].

Dorigo, M ;

Maniezzo, V ;

Colorni, A .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 1996, 26 (01) :29-41

[5]

Dorigo M, 1999, NEW IDEAS OPTIMIZATI, P11

[6]

Dorigo M., 1996, NEW IDEAS OPTIMIZATI, P11

[7]

Hayakawa D., 2012, 2012 INT C TECHN APP, P205

[8] Phase transitions and the search problem [J].

Hogg, T ;

Huberman, BA ;

Williams, CP .

ARTIFICIAL INTELLIGENCE, 1996, 81 (1-2) :1-15

[9] MINIMIZING CONFLICTS - A HEURISTIC REPAIR METHOD FOR CONSTRAINT SATISFACTION AND SCHEDULING PROBLEMS [J].

MINTON, S ;

JOHNSTON, MD ;

PHILIPS, AB ;

LAIRD, P .

ARTIFICIAL INTELLIGENCE, 1992, 58 (1-3) :161-205

[10]

Mizuno K., 2001, Informatica, V25, P421

← 1 2 →