Modified probabilistic particle swarm optimization with local search for the traveling salesman problem

Combinatorial optimization is a genre of mathematics whereby the problem definitions are discrete and is often deal with the permutation of a set of objects. Although optimality has been reached for combinatorial problems of many sizes; as the set of objects increases exact algorithmic procedures become unpractical due to the computational effort required. A set of procedures called metaheuristics, including the Particle Swarm Optimization (PSO), have been developed to handle classes of large problem sizes and have been able to provide near optimal solutions in an efficient manner.;Kennedy and Eberhart developed upon the concepts of swarm intelligence to create PSO, an algorithmic procedure which transfers knowledge amongst a set of search agents through counsel of global and local best positions recorded. The information is transferred using a velocity updating equation developed for problems in the continuous vector space. Using the mathematical function of summation, the velocity update equation amalgamates three vectors (previous velocity, local best velocity, and global best velocity) to direct particles toward better solutions. The velocity updating equations require notions of distance, a relation that only applies to problem spaces that have the property of ordering. Because neither ordering nor relations exist within the combinatorial problem space domain, adaptation of the PSO algorithm is required.;This research develops a new methodology for adapting PSO to combinatorial optimization problems. Specifically, the PSO algorithm was applied in the inversion table search space, a novel concept yet to be found in the literature. Utilizing the encoding scheme of inversion tables permutation sequences can be transformed into a vector space domain through a one-to-one mapping. The newly encoded representation of inversion table rearranges the points in combinatorial space into a dimension with the property of ordering allowing for the use of PSO's traditional updating equations.;The mathematical summation utilized in PSO's velocity update equation exploits the property of ordering that is inherent in vector space problems. Because combinatorial problem spaces lack the property of ordering, directing of particles using traditional PSO velocity update equation does not have the same exploitative effect compared to the vector space domain. To address the black-box nature of combinatorial problems, a probabilistic velocity update procedure was used in this research. The new probabilistic procedure uses the traditional PSO parameters as probabilistic thresholds to move the position of the particle from one point to another. In addition a local neighborhood search procedure was augmented upon the new probabilistic PSO to better exploit the combinatorial problem space.;Although the developed PSO variations did not perform as anticipated, the heuristic does provide a new foundation for studying PSO's application in the combinatorial space domain. Using designs of experiments, parameters were adjusted to best suit the new PSO variant to the inversion table search space. Additional improvements were gained utilizing the shortest distance rule of thumb for initializing particles. It was found that, both the probabilistic velocity update procedure and local search augmentation improved the performance of the developed PSO algorithm for traveling salesman problem instances with up to 100 cities.