Particle Swarm Optimization for Solving Constraint Satisfaction Problems

Candidate: I-Ling Lin
Type: Master of Science (MSc), School of Interactive Arts and Technology
Date: August 30, 2005
Senior Supervisor: Dr. Marek Hatala, Associate Professor
Thesis: Download Thesis Document

Abstract

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 ma jor 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 repaired-based CSP-solving methods perform best.