A relationship between network topology and search performance of PSO
Tsujimoto Takahiro, Takuya Shindo, Takayuki Kimura, Kenya Jin’no · 2012
Particle swarm optimization (abbr. PSO) is one of the most effective optimization algorithms. The PSO contains many control parameters, therefore, the performance of the searching ability of the PSO is significantly alternated. In order to analyze the dynamics of such PSO system rigorously, we have analyzed a deterministic PSO (abbr. D-PSO) systems which does not contain any stochastic factors, and its coordinate of the phase space is normalized. The found global best information influences the dynamics. This situation can be regarded as the full-connection state. On the other hand, there is the case where the best information in a limited population. Such information is called as lbest. How to get the lbest information from any population is equivalent to a network structure. Such network structure influences the performance of searching ability. In order to clarify a relationship between network structures of the PSO and its performance, we pay attention to the degree and the average distance used in graph theory. We consider the two cases where the D-PSO has an extended cycle structure and a Small World network structure. Our numerical simulation results indicates the searching performance of the D-PSO is depended on the average distance of the node. Especially, the long average distance exerts the search performance on the D-PSO. We confirm that the search performance properties of the D-PSO and the conventional stochastic PSO are completely different to the average distance. The search performance of the D-PSO is improved according to the average distance. On the other hand, the search performance of the conventional stochastic PSO is deteriorated according to the average distance. We consider that the slow transmission of the beneficial information leads to the diversification of the particles of the D-PSO. Also, we clarify the small perturbation of the random range of the stochastic PSO is important.