A discrete stereotyped particle swarm optimization algorithm for quadratic assignment problems

Particle swarm optimization (PSO) is an optimization technique introduced in 1995 that is based on the behavior of natural creatures. It is a stochastic population-based algorithm where the particles are affected by their trust in themselves, their experiences, and their neighbors. Quadratic assignment problem (QAP), on the other hand, is a classic combinatorial optimization problem that was first introduced in 1957. The model was formulated to study the assignment of economic activities to a set of locations based on cost functions. QAP is a benchmark problem among researchers due to its practical and theoretical importance along with its inherent complexity; to date, the optimum solution for numerous problems has not yet been found and no PSO algorithm has solved problem instances that are greater than size fifty.;This research attempts to solve QAPs with the PSO model. Thirty different QAP instances that range in size from 12 to 150 locations were selected, essentially covering the entire collection of available problems. A baseline PSO model was created in order to provide a foundation with which to compare results. The concepts of clustering and stereotyping were introduced to the baseline model to form the Discrete Stereotyped PSO (DSPSO) model. A set of values were determined for the various parameters within the two algorithms and random numbers were synchronized in order to provide valid comparisons. The objective was to test whether the DSPSO algorithm yielded better results based on the addition of the clustering and stereotyping techniques.;Statistical comparisons of the two models showed that the DSPSO algorithm performed better with respect to the selected QAP instances. The DSPSO model found better solutions in fewer iterations with the same amount of computational time. The DSPSO algorithm also had competitive results when compared to other authors who solved the same QAP instances with different methods. The significant gains in performance from the DSPSO model proves that the addition of clustering and stereotyping to the PSO algorithm yields better results allowing large-scale QAPs to be solved in an efficient manner. The results of this research justify the use of the DSPSO model on other test problems as well as the application of clustering and stereotyping to other heuristics.