| A multiagent evolutionary algorithm for constraint satisfaction problems. | |
| | |
MedLine Citation:
|
PMID: 16468566 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
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. |
| | |
Authors:
|
Jing Liu; Weicai Zhong; Licheng Jiao |
Related Documents
:
|
10376756 - The pathogenesis of vascular thrombosis and its impact in microvascular surgery. 7996086 - Canal configuration in the mesiobuccal root of the maxillary first molar: a clinical st... 7517576 - The boundaries of the self and the unhealthy other: reflections on health, culture and ... 17319876 - Targeting of streptococci by zoocin a. 8304906 - An australian experience of transdermal oestradiol patches in a subtropical climate. 21558626 - Technologies and strategies for people with communication problems following brain inju... |
Publication Detail:
|
Type: Evaluation Studies; Journal Article; Research Support, Non-U.S. Gov't |
Journal Detail:
|
Title: IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society Volume: 36 ISSN: 1083-4419 ISO Abbreviation: IEEE Trans Syst Man Cybern B Cybern Publication Date: 2006 Feb |
Date Detail:
|
Created Date: 2006-02-10 Completed Date: 2006-03-07 Revised Date: 2006-11-15 |
Medline Journal Info:
|
Nlm Unique ID: 9890044 Medline TA: IEEE Trans Syst Man Cybern B Cybern Country: United States |
Other Details:
|
Languages: eng Pagination: 54-73 Citation Subset: IM |
Affiliation:
|
Institute of Intelligent Information Processing, Xidian University, Xi'an 710071, China. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Artificial Intelligence* Computer Simulation Decision Support Techniques* Evolution Models, Theoretical* Systems Theory |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Highly scalable and robust rule learner: performance evaluation and comparison.
Next Document: Interactive segmentation of the cerebral lobes with fuzzy inference in 3T MR images.