Related Experiment Videos
A multiagent evolutionary algorithm for constraint satisfaction problems
Jing Liu1, Weicai Zhong, Licheng Jiao
1Institute of Intelligent Information Processing, Xidian University, Xi'an 710071, China.
Summary
A new multiagent evolutionary algorithm for constraint satisfaction problems (MAEA-CSPs) effectively solves both permutation and nonpermutation problems. This algorithm demonstrates linear space complexity and optimal convergence, achieving strong performance on benchmark instances.
Area of Science:
- Artificial Intelligence
- Constraint Satisfaction Problems
- Evolutionary Computation
Background:
- Constraint Satisfaction Problems (CSPs) are fundamental in AI.
- Existing methods face challenges with encoding and scalability.
- CSPs can be categorized into permutation and nonpermutation types.
Purpose of the Study:
- To introduce a novel Multiagent Evolutionary Algorithm for Constraint Satisfaction Problems (MAEA-CSPs).
- To address limitations of general encoding methods using minimum conflict encoding.
- To evaluate MAEA-CSPs on diverse benchmark problems.
Main Methods:
- Developed MAEA-CSPs with agent behaviors controlled by evolution.
- Proposed minimum conflict encoding to overcome general encoding disadvantages.
- Experimentally tested MAEA-CSPs on benchmark binary CSPs, graph coloring, n-queen, and job-shop scheduling problems.
Main Results:
- MAEA-CSPs exhibits linear space complexity and converges to global optima.
- Achieved strong performance on nonpermutation CSPs (benchmark binary CSPs, graph coloring).
- Demonstrated excellent scalability and performance on permutation CSPs (n-queen, job-shop scheduling), even for large instances.
Conclusions:
- MAEA-CSPs is a robust and scalable algorithm for various CSPs.
- The proposed minimum conflict encoding enhances performance.
- MAEA-CSPs offers a competitive approach to solving complex constraint satisfaction problems.