Graph Theoretical Analysis in Particle Swarm Optimization Based on Random Topologies

Particle Swarm Optimization (PSO) is a swarm intelligence method which is employed frequently for solving real-world problems. After its inception, many variants of PSO devote to improving its performance by modifying the behavior of each particle, in which the population topologies of the particle swarm may alter. This paper investigates how population topology influences the performance of PSO. A random topology generation algorithm that adopts both the greedy strategy and randomized algorithm is proposed in the paper. The randomly generated topologies are applied in PSO-w, which introduces no modification to the population topology of the original PSO. Experimental results demonstrate that algorithms using topologies with more edges tend to converge faster and generally obtain a more accurate solution. Another major result in this paper is that how clustering coefficient affects PSO largely depends on the sparsity of the topology. A lower clustering coefficient in sparse topology conduces to faster convergence and a more precise result, but a higher clustering coefficient is preferred when the topology is dense.