ظهور پویایی های جستجوی قوانین مقیاس گذاری در بهینه سازی ازدحام ذرات

This paper investigates the search dynamics of a fundamental particle swarm optimization (PSO) algorithm via gathering and analyzing the data of the search area during the optimization process. The PSO algorithm exhibits a distinct performance when optimizing different functions, which induces the emergence of different search dynamics during the optimization process. The simulation results show that the performance is tightly related to the search dynamics which results from the interaction between the PSO algorithm and the landscape of the solved problems. The Lévy type scaling laws search dynamics emerges from the process in which the PSO algorithm shows good performance, while the Brownian dynamics appears after the algorithm has stagnated due to the premature convergence. The Lévy dynamics characterized by a large number of intensive local searches punctuated by long-range transfers is an indicator of good performance, which allows the algorithm to achieve an efficient balance between exploration and exploitation so as to improve the search efficiency.

The scaling laws strategy is widely applied by animals in nature when searching for food, which is referred to as Lévy flights, i.e., the search step lengths (ll) of these predators follow a power-law distribution (the so-called Pareto–Lévy distribution): the density function f(l)∝l−αf(l)∝l−α, where αα is the scaling exponent [1]. Quantities following power-law form are not well characterized by their typical or average values, and they have the scale invariance property, leading to the same distribution shape repeated across all scales. The flight lengths of many animals have been found to exhibit long-tailed power-law distributions (such as blue shark, mola, tuna, jackals, spider monkey, herbivores, soil amoebas, freshwater Hydra cells, mussels, etc.) [2], [3], [4], [5], [6], [7], [8] and [9]. Why Lévy flights as a foraging strategy are ubiquitous is still a secret to us, and some investigations think the Lévy motion is an efficient foraging method. The chance of returning to the same place in Lévy motion is less than in a normal diffusion process. Therefore, the Lévy motion especially optimizes the predator–prey encounter in a food scarce environment [10], [11] and [12]. Meanwhile, the analysis on the data obtained by bank notes, mobile phones and GPS also showed the emergence of scaling laws in human activity [13], [14], [15], [16] and [17]. The fat tail of jump size is thought to be the results of human decision processes with priority execution [17] and [18], which generates a strong heterogeneous distribution of waiting time and leads to the existence of scaling laws in human behavior. The main principle behind preferential choice is similar to ‘preferential attachment’ to generate a scale-free network [19]. Phase transitions and critical phenomena can also generate power-law distributions due to the divergence of some quantity [20]. The power-law distributions can also exist in the systems of self-organized criticality (SOC) [21]. However, the highly optimized tolerance (HOT) mechanism thinks the emergence of a power-law distribution is deliberately planted for optimization rather than self-organization [22]. In addition, some researchers believe the scaling laws of spatial networks can improve the performance of networked systems through optimizing the information entropy [23] and [24]. Therefore, understanding the emergence of scale laws is a crucial and challenging problem. Since systems with scaling properties exhibit good performance, it is interesting to incorporate the power-law property into heuristic optimization algorithms. Previous investigations focused on the improvement of performance through introducing the power-law property into the algorithms [25], [26] and [27]. However, the inherent searching dynamics of the algorithm is little addressed. More recently, the dynamic property of the optimization process of the genetic algorithm was investigated and the topology of the information flow network was found to own the scale-free property, which is probably due to the fitness preferential selection strategy [28]. Actually, the evolutionary dynamics reflects the key search pattern of an algorithm. Understanding the search pattern may provide direct insights of the optimization process, and furthermore offer new methods for the design of algorithms. In this paper, we investigate the search dynamics of a fundamental particle swarm optimization (PSO) algorithm by gathering and studying a process parameter, referred to search area. Similar to the jump length of foraging movement, the statistical property of the search area data characterizes the search pattern of the algorithm in the optimization process. The statistical analysis on the search area data shows that the scaling laws search pattern can inherently emerge from highly efficient optimization processes. The emergence of scale laws also confirms the assumption that the scaling laws are relevant to the state of high efficiency. In contrast, the Lévy search dynamics is replaced by a Brownian type behavior after the algorithm has been trapped by local minima. The Brownian search is characterized by intensive local scans around the local minimum that leads to a vicious circle. The trapped algorithm results in a slowly diffusive search which in turn prevents the algorithm from escaping out of the local optimum. The remainder of this paper is organized as follows. Section 2 introduces the PSO algorithm, the search area parameter, the benchmark functions, and the numerical experiment settings. Section 3 analyzes the statistical properties of the PSO evolution process, and gives the results. Section 4 summaries the paper.

In this paper we investigated the characteristic dynamics of the PSO. The statistical analysis shows that the search area data characterizing some efficient search movements obey a truncated Pareto distribution. We test the TP distribution, i.e., Lévy-type search hypothesis using the pp-value and the AICAIC methods. The PSO algorithm does not use any extrinsic scaling search strategy, such as introducing power-law random numbers or some mechanisms which can generate scaling laws’ behavior. The Lévy-type scaling laws’ dynamics emerges from the interaction between the algorithm and the solved problems. The PSO has distinct performances and dynamical properties when solving different problems. And the performance and the search dynamics of the PSO algorithm are interrelated. The Lévy-type search emerges from the efficient optimization process with good performance, while the Brownian dynamics occurs when the algorithm is stagnated due to the premature convergence. The investigation offers some insights of the PSO’s optimizing evolution and gives some clues on how to improve search efficiency. Perhaps the Lévy dynamics is an indicator rather than a strategy. Its emergence means an improvement of the algorithm, because it can properly balance between exploration and exploitation. And more importantly, this Lévy type search is a consequence of the interactions between the PSO and the landscape of the problem, therefore, the particles can move under the guidance of the landscape’s fitness information rather than in a random direction that is used in the foraging model [45]. The study on the dynamics seems to point out a new way to improve algorithms. That is to design some mechanisms or rules to induce the algorithm to self-organize into a state characterized by scaling search dynamics. In particular, for some complex problems which would likely trap the algorithm, the PSO algorithm requires some mechanisms related to generating long-range movements so as to escape from the local optimum and form an efficient Lévy search. The restarting mechanism often used to improve the diversity of the PSO algorithm would generate Lévy search dynamics by intermittently punctuating the intensive local search with long-range transfer produced by restarting.