Particle swarm optimization for solving constraint satisfaction problems

This research presents the design and evaluation of a variety of new constraint-solving algorithms based on the particle swarm optimization (PSO) paradigm. Constraint satisfaction problems (CSPs) can be applied to many practical problems but they are in general NP-hard, so developing new algorithms has been a major research challenge. PSO is a relatively new approach to AI problem solving and has just begun to be applied to CSPs. This research modifies and extends the traditional PSOs to solve n-ary CSPs. These new particle swarm algorithms are tested on practical configuration problems and the traditional n-queens problems. The effectiveness and efficiency of the new algorithms are experimentally compared to the traditional PSOs. The performance of the individual algorithms is also assessed. The algorithms that combine zigzagging particles and repair-based CSP-solving methods perform best among the algorithms studied.