Paper Info
Title
A multiagent evolutionary algorithm for constraint satisfaction problems.
Abstract
With the intrinsic properties of constraint satisfaction problems (CSPs) in mind, we divide CSPs into two types, namely, permutation CSPs and nonpermutation CSPs. According to their characteristics, several behaviors are designed for agents by making use of the ability of agents to sense and act on the environment. These behaviors are controlled by means of evolution, so that the multiagent evolutionary algorithm for constraint satisfaction problems (MAEA-CSPs) results. To overcome the disadvantages of the general encoding methods, the minimum conflict encoding is also proposed. Theoretical analyzes show that MAEA-CSPs has a linear space complexity and converges to the global optimum. The first part of the experiments uses 250 benchmark binary CSPs and 79 graph coloring problems from the DIMACS challenge to test the performance of MAEA-CSPs for nonpermutation CSPs. MAEA-CSPs is compared with six well-defined algorithms and the effect of the parameters is analyzed systematically. The second part of the experiments uses a classical CSP, n-queen problems, and a more practical case, job-shop scheduling problems (JSPs), to test the performance of MAEA-CSPs for permutation CSPs. The scalability of MAEA-CSPs along n for n-queen problems is studied with great care. The results show that MAEA-CSPs achieves good performance when n increases from 10(4) to 10(7), and has a linear time complexity. Even for 10(7)-queen problems, MAEA-CSPs finds the solutions by only 150 seconds. For JSPs, 59 benchmark problems are used, and good performance is also obtained.
Year
DOI
Venue
2006
10.1109/TSMCB.2005.852980
IEEE Transactions on Systems, Man, and Cybernetics, Part B
Keywords
Field
DocType
n-queen problems.,constraint satisfaction problem,linear space complexity,multiagent evolutionary algorithm,index terms—constraint satisfaction problems,general encoding method,evolutionary algorithms,permutation csps,good performance,nonpermutation csps,linear time complexity,graph coloring problems,multiagent systems,benchmark problem,benchmark binary csps,job-shop scheduling problems,n-queen problem,evolutionary computation,constraint satisfaction problems,computational complexity,linear space,graph coloring problem,evolutionary algorithm,linear time,job shop scheduling,indexing terms,multi agent systems
Evolutionary algorithm,Computer science,Theoretical computer science,Artificial intelligence,Time complexity,Graph coloring,Mathematical optimization,Job shop scheduling,Permutation,Evolutionary computation,Constraint satisfaction problem,Machine learning,Computational complexity theory
Journal
Volume
Issue
ISSN
36
1
1083-4419
Citations 
PageRank 
References 
37
1.98
53
Authors
3
Name
Order
Citations
PageRank
Jing Liu11043115.54
Weicai Zhong238126.14
Licheng Jiao35698475.84