{'fraction_non_alphanumeric': 0.027660787523219245, 'fraction_numerical': 0.012542990086991706, 'mean_word_length': 4.729610115911486, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Random Drift Particle Swarm Optimization

The random drift particle swarm optimization (RDPSO) algorithm, inspired by the free electron model in metal conductors placed in an external electric field, is presented, systematically analyzed and empirically studied in this paper. The free electron model considers that electrons have both a thermal and a drift motion in a conductor that is placed in an external electric field. The motivation of the RDPSO algorithm is described first, and the velocity equation of the particle is designed by simulating the thermal motion as well as the drift motion of the electrons, both of which lead the electrons to a location with minimum potential energy in the external electric field. Then, a comprehensive analysis of the algorithm is made, in order to provide a deep insight into how the RDPSO algorithm works. It involves a theoretical analysis and the simulation of the stochastic dynamical behavior of a single particle in the RDPSO algorithm. The search behavior of the algorithm itself is also investigated in detail, by analyzing the interaction between the particles. Some variants of the RDPSO algorithm are proposed by incorporating different random velocity components with different neighborhood topologies. Finally, empirical studies on the RDPSO algorithm are performed by using a set of benchmark functions from the CEC2005 benchmark suite. Based on the theoretical analysis of the particle's behavior, two methods of controlling the algorithmic parameters are employed, followed by an experimental analysis on how to select the parameter values, in order to obtain a good overall performance of the RDPSO algorithm and its variants in real-world applications. A further performance comparison between the RDPSO algorithms and other variants of PSO is made to prove the efficiency of the RDPSO algorithms.


Introduction
Particle swarm optimization (PSO) is a population-based optimization method attributed to be originally developed by Kennedy and Eberhart (Kennedy and Eberhart, 1995;Eberhart and Kennedy, 1995). It is widely known that PSO is rooted in two paradigms . One obvious root is its ties with artificial life in general, and bird flocking, fish schooling, and swarm theory in particular. The other root is associated with evolutionary algorithms (EAs), such as genetic algorithms (GAs) and evolutionary programming (EP). However, unlike EAs, PSO has no evolution operators similar to crossover and selection.
PSO optimizes a problem by iteratively improving a population of candidate solutions with respect to an objective (fitness) function. The candidate solutions, called particles, move through the problem space according to simple mathematical formulae describing the particles' position and velocity. The movement of each particle is influenced by its own experiences, and is also guided towards the current best known position.
During the last decade, PSO has gained increasing popularity due to its effectiveness in performing difficult optimization tasks. The reason why PSO is attractive is that it gets better solutions, in a faster and cheaper way compared to other methods, whereas has fewer parameters to adjust. It has been successfully used in many research and application areas. An extensive survey of PSO applications can be found in (Poli, 2007;2008).
To gain insights into how the algorithm works, some researchers have theoretically analyzed the PSO algorithm. These analyses mainly aimed for the behavior of the individual particle in the PSO algorithm, which is essential to the understanding of the search mechanism of the algorithm and to the parameter selection (Kennedy, 1998;Ozcan, and Mohan, 1999;Clerc and Kennedy, 2002;van den Bergh, 2002;Eberhart and Shi, 1998;Trelea, 2003;Emara, and Fattah, 2004;Gavi and Passino, 2003;Kadirkamanathan, et al, 2006;Jiang, 2007;Solis and Wets, 1981). For example, Kennedy analysed a simplified particle behavior and demonstrated different particle trajectories for a range of design choices (Kennedy, 1998).
Clerc and Kennedy undertook the first formal analysis of the particle trajectory and its stability properties (Clerc and Kennedy, 2002). As for the algorithm itself, Van den Bergh proved that the canonical PSO is not a global search algorithm (van den Bergh, 2002), even not a local one, by using the convergence criterion provided by Solis and Wets (Solis and Wets, 1981).
In addition to the analyses mentioned above, there has been a considerable amount of work performed in improving the original version of the PSO through empirical studies. The original PSO proposed in  appeared to have weak local search ability, due to the slow convergence speed of the particles. It is universally known that the tradeoff between the local search (exploitation) and the global search (exploration) is vital for the performance of the algorithm. As such, the original PSO needs to accelerate the convergence speed of the particles in order to achieve a better balance between exploitation and exploration. The work in this area, first carried out by Shi and Eberhart, involves introducing an inertia weight into the update equation for velocities (Shi and Eberhart, 1998). Clerc proposed another acceleration method by adding a constriction factor in the velocity update equation, in order to release the restriction on the particle's velocity during the convergence history (Clerc, 1999). The acceleration techniques were shown to work well, and the above two variants of PSO have laid the foundation for further enhancement of the PSO algorithm.
In the original PSO, the PSO with inertia weight (PSO-In) and the PSO with constriction factor (PSO-Co), the search of the particles is guided by the global best position and their personal best positions.
In these versions of PSO, all particles are neighbors of each other so that their neighborhood topology is known as the global best topology or the global best model. Although the algorithm with this model is able to efficiently obtain the best approximate solutions for many problems, it is more prone to encounter premature convergence when solving harder problems. If the global best particle sticks to a local or suboptimal point, it would mislead the other particles to move towards that point. In other words, other promising search areas might be missed. This had led to the investigation of other neighborhood topologies known as the local best models, first studied by Eberhart and Kennedy (1995) and subsequently in depth by many other researchers (Suganthan, 1999;Kennedy, 1999;Liang and Suganthan, 2005;Mendes, et al., 2004;Parrott and Li, 2006;Bratton and Kennedy, 2007;Kennedy and Mendes, 2002;van den Bergh and Engelbrecht, 2004;Lane et al., 2004;Li, 2004). The objective there was to find other possible topologies to improve the performance of the PSO algorithm. In PSO, the particle essentially follows a semi-deterministic trajectory defined by a velocity update formula with two random acceleration coefficients. This is a semi-deterministic search, which restricts the search domain of each particle and may weaken the global search ability of the algorithm, particularly at the later stage of the search process. In view of this limitation, some researchers have proposed several probabilistic PSO algorithms, which simulate the particle trajectories by direct sampling, using a random number generator, or from a distribution of practical interests (Kennedy, 2003;Sun, et al., 2012;Krohling, 2004;Secrest and Lamon, 2003;Richer and Blackwell, 2006;Kennedy, 2006). The Bare Bones PSO (BBPSO) family is a typical class of probabilistic PSO algorithms (Kennedy, 2003). In BBPSO, each particle does not have a velocity vector, but its new position is sampled "around" a supposedly good one, according to a certain probability distribution, such as the Gaussian distribution in the original version (Kennedy, 2003). Several other new BBPSO variants used other distributions which seem to generate better results (Kennedy, 2004;2006).
Researchers also turned to hybrid algorithms that incorporate other search methods into the PSO algorithm, for the purpose of playing to the advantages of different optimization algorithms (Angeline, 1998;Løvbjerg et al., 2001;Zhang and Xie, 2003;Devicharan and Mohan, 2004;Chen et al., 2007;Settles and Soule, 2005;Higashi and Iba, 2003;Pant et al., 2008). Angeline undertook the first work in this area by introducing a tournament selection into the PSO, based on the particle's current fitness, so that the properties that make some solutions superior were transferred directly to some of the less effective particles (Angeline, 1998). Besides, some researchers introduced various efficient strategies into the PSO in order to enhance the search ability of the algorithm (Riget and Vesterstroem, 2002;Lovbjerg and Krink, 2002;Xie et al., 2002;Krink et al., 2002;Liang et al., 2006). For instance, Liang et al. proposed a PSO with a novel learning strategy, in which all other particles' historical best information is used to update a particle's velocity. It was shown that this strategy can diversify the swarm to avoid premature convergence (Liang et al., 2006).
In this paper, based on a random drift model, we present a new version of PSO, which is called the random drift particle swarm optimization (RDPSO). This PSO variant is inspired by the free electron model in metal conductors in an external electric field. The model considers that each electron in a conductor, which is situated in an external electric field, has both a thermal motion as well as a drift motion (Omar, 1993). The drift motion is caused by the electric field and is the directional movement of the electron in the opposite direction to the electric field. On the other hand, the thermal motion is random in essence, and it exists even in the absence of an external electric field. The two motions together bring the electron into a location with minimum potential energy, which is analogous to the process of searching for the optimal solution to an optimization problem. Our motivation of designing the RDPSO algorithm, based on this model, was to improve the search ability of the PSO algorithm by only modifying the update equation of the particle's velocity, instead of by revising the algorithm based on the update equation of the canonical PSO, which would probably increase the complexity of the algorithm and its computational cost.
The basics of the original concept of the random drift model for PSO were sketched in our previous work (Sun et al., 2010). In the initial limited version of the algorithm, the velocity of the particle's drift motion is simply expressed by the summation of the cognition part and the social part in the velocity update equation of the original PSO, which is not consistent with the physical meaning of the random drift model. This paper is to propose a more concise form for the drift velocity, which is more in line with the physical meaning of the model, and a novel strategy for determining the random velocity, and thus a new version of the RDPSO algorithm. In order to gain an in-depth understanding of how the RDPSO works, we make comprehensive theoretical analyses of the behavior of the individual particle in the RDPSO and the search behavior of the algorithm. Four variants of the RDPSO are proposed based on different random velocities and neighborhood topologies. Comprehensive empirical studies on the RDPSO algorithm by using the CEC2005 benchmark suite are performed to verify the effectiveness of the algorithm.
To this end, the paper firstly describes the principle of the RDPSO and analyzes the behavior of the single particle in the RDPSO. The motivations of the RDPSO from a trajectory analysis point of view together with the free electron model are formulated in detail, and the random drift model for the RDPSO is presented. Based on this model, the velocity of the particle is assumed to be the superimposition of the random velocity component and the drift velocity component, which reflect the global search as well as the local search of the particle, respectively. The mathematical expressions of the two velocity components and, subsequently, the update equation for the particle's velocity are given. After that, the conditions for the particle's position to be probabilistically bounded are theoretically derived, and are later verified by stochastic simulations on the particle's behavior.
Then, the search mechanism of the RDPSO algorithm is investigated. The effects of the thermal and drift motions on the particle's search behavior are analyzed. The drift velocity component leads the particle to move toward its personal best position and the global best position as well, and thus it essentially implements the local search of the particle. The random velocity component makes the particle more volatile and its position is pulled or pushed away from the global best position, reflecting the global search of the particle. The interactions between the particles in the swarm are also analyzed in order to show that the RDPSO algorithm may provide a good balance between the global and the local search. Next, four RDPSO variants are proposed based on the combination of the two topologies (i.e., the global best model, and the ring neighborhood topology for the local best model) with two strategies for the random velocity components (i.e., one that uses the mean best position to determine the random velocity component, and the other one that employs randomly selected personal best position to compute the random velocity component).
Finally, empirical studies on the RDPSO algorithm are undertaken by using the CEC2005 benchmark suite. The issues of the parameter control and selection with respect to the thermal and drift coefficients of the algorithm are addressed by testing the algorithm with different parameter settings on three benchmarks.
Then, the parameter settings that are identified to result in good algorithmic performance are further tested and compared on the first twelve functions of the CEC2005 benchmark suite. For each RDPSO variant, the parameter settings that yield good overall algorithmic performance are found out. The RDPSO variants with the identified parameter configurations and some other PSO variants are tested by all the twenty five problems of the benchmark suite in order to make a thorough performance comparison and verify the efficiency of the RDPSO algorithms.
The remainder of the paper is organized as follows. Section 2 gives a brief introduction to the PSO algorithm. Section 3 presents the motivation, the procedure and the analyses of the RDPSO algorithm as well as its variants. Empirical studies on the parameter selection for the RDPSO algorithm and the performance comparison are provided in Section 4. Finally, the paper is concluded in Section 5.

Particle Swarm Optimization
In a PSO with M individuals, each individual is treated as a volume-less particle in the N-dimensional space, with the current position vector and the velocity vector of particle i at the n th iteration represented as , , , respectively. The particle moves according to the following equations: is the best previous position (the position giving the best objective function value or fitness value) of particle i, called the personal best (pbest) position, and the vector is the position of the best particle among all the particles in the population and called the global best (gbest) position. Without loss of generality, we consider the following minimization problem: where ) ( X f is an objective function and S is the feasible space. Accordingly, n i P , can be updated by and n G can be found by The parameters j n i r , and j n i R , are sequences of two different random numbers distributed uniformly on (0, 1), which is denoted by The original PSO algorithm with equation (1) appears to have a weak local search ability. It should be noted that the tradeoff between the local search (exploitation) and the global search (exploration) is vital for the performance of the algorithm. Therefore, the original PSO needs to accelerate the convergence speed of the particles in order to achieve a better balance between exploitation and exploration. Work in this area, first carried out by Shi and Eberhart [16], involves introducing an inertia weight into equation (1), and the resulting update equation for velocities becomes: where w is the inertia weight. The PSO algorithm with equation (5) replacing equation (1) is known as the PSO with inertia weight (PSO-In). The inertia weight w can be a positive value chosen according to experience or from a linear or nonlinear function of the iteration number. When w is 1, the PSO-In is equivalent to the original PSO. The values of c 1 and c 2 in equation (5) are generally set to be 2 as originally recommended by Kennedy and Eberhart (1995), which implies that the 'social' and 'cognition' parts have the same influence on the velocity update. Clerc (1999) proposed another acceleration method by adding a constriction factor in the velocity update equation (1) where the constant χ is known as the constriction factor and is determined by This version of PSO is known as the PSO with constriction factor (PSO-Co). It was shown by Clerc and Kennedy (Clerc and Kennedy, 2002)   and c 1 =c 2 =2.05 (Clerc and Kennedy, 2002).
These two versions of the PSO algorithm collectively referred to as the canonical PSO algorithms accelerate the convergence speed of the swarm effectively and have better performance than the original PSO in general. They have laid the foundation for further enhancement of the PSO. There are many other versions of the PSO algorithm as have been mentioned in Section 1, but most of them are based on these two versions.

The Motivation and Procedure of RDPSO
In (Clerc and Kennedy, 2002), the trajectory analysis demonstrated that the convergence of the whole particle swarm may be achieved if each particle converges to its local focus, ) , In fact, as the particles are converging to their own local attractors, their current positions, pbest positions, local focuses and the gbest position are all converging to one point. This way, the canonical PSO algorithm is said to be convergent. Since n i p , is a random point uniformly distributed within the hyper-rectangle with n i P , and n G being the two ends of its diagonal, the particle's directional movement towards n i p , makes the particle search around this hyper-rectangle and improves its fitness value locally. Hence, this directional movement essentially reflects the local search of the particle. In equation (1), (5) or (6), there are three parts on the right side. The last two ones are known as the 'cognition' part and the 'social' part, the superimposition of which results in the directional motion of the particle toward n i p , . The first part on the right side of each equation is the 'inertia part', which may lead the particle to fly away from n i p , or n G and provide necessary momentum for the particle to search globally in the search space. The 'inertia part' is deterministic and reflects the global search of the particle.
The motivation of the proposed RDPSO algorithm comes from the above trajectory analysis of the canonical PSO and the free electron model in metal conductors placed in an external electric field (Omar, 1993). According to this model, the movement of an electron is the superimposition of the thermal motion, which appears to be a random movement, and the drift motion (i.e., the directional motion) caused by the electric field. That is, the velocity of the electron can be expressed by , where VR and VD are called the random velocity and the drift velocity, respectively. The random motion (i.e., the thermal motion) exists even in the absence of the external electric field, while the drift motion is a directional movement in the opposite direction of the external electric field. The overall physical effect of the electron's movement is that the electron careens towards the location of the minimum potential energy. In a non-convex-shaped metal conductor in an external electric field, there may be many locations of local minimum potential energies, which the drift motion generated by the electric force may drive the electron to.
If the electron only had the drift motion, it might stick into a point of local minimum potential energy, just as a local optimization method converges to a local minimum of an optimization problem. The thermal motion can make the electron more volatile and, consequently, helps the electron to escape the trap of local minimum potential energy, just as a certain random search strategy is introduced into the local search technique to lead the algorithm to search globally. Therefore, the movement of the electron is a process of minimizing its potential energy. The goal of this process is essentially to find out the minimum solution of the minimization problem, with the position of the electron represented as a candidate solution and the potential energy function as the objective function of the problem. Inspired by the above facts, we assume that the particle in the RDPSO behaves like an electron moving in a metal conductor in an external electric field. The movement of the particle is thus the superposition of the thermal and the drift motions, which implement the global search and the local search of the particle, respectively. The trajectory analysis, as described in the first paragraph of this subsection, indicates that, in the canonical PSO, the particle's directional movement toward its local attractor n i p , reflects the local search of the particle. In the proposed RDPSO, the drift motion of the particle is also defined as the directional movement toward n i p , , which is the main inheritance of the RDPSO from the canonical PSO.
However, in the RDPSO, the 'inertia part' in the velocity equation of the canonical PSO is replaced by the random velocity component. This is the main difference between the RDPSO and the canonical PSO. The thermal motion in the RDPSO is far different from the 'inertia' movement in the canonical PSO, although both of them have an identical functionality, namely, to implement the global search ability of the particle.
From a physical perspective, the particle in the canonical PSO is in a mechanical movement and its velocity and acceleration can be depicted by a set of deterministic dynamics equations. Consequently, it is natural that there should be an 'inertia part' in the velocity equation to reflect the change in the particle's velocity with time. On the contrary, the thermal motion of the particle in the RDPSO is random in nature and can not be described by the dynamics equations used for mechanical movements. The only way of describing the thermal motion in statistical physics is by providing the probability distribution function of the particle's velocity or momentum. It is unnecessary and impossible to depict the exact change of the particle's velocity with time. Therefore, there is no 'inertia part' in the velocity equation of the RDPSO algorithm anymore.
From an algorithm design point of view, the role of the 'inertia part' in the global search is assumed by the random velocity component in the RDPSO, so that there is no need of an 'inertia part' in the RDPSO.
Therefore, the velocity of the particle in the RDPSO algorithm has two components, i.e., the thermal component and the drift component. Mathematically, the velocity of particle i in the jth dimension can be expressed by A further assumption is that the value of the random velocity component essentially follows a normal distribution (i.e., Gaussian distribution) whose probability density function is given by where ) , , , ( 2 1 N n n n n C C C C L = is known as the mean best (mbest) position defined by the mean of the pbest positions of all the particles, namely, (12) Thus, equation (10) can be restated as where 0 > α is an algorithmic parameter called the thermal coefficient.
As for the drift velocity component, , + , its role is to achieve the local search of the particle. As has been mentioned above, the directional movement toward in (Sun et al., 2010) is just the combination of the 'cognitive part' and the 'social part' of equation (1), namely, is a random number, its effect is to make the movement of the particle randomized, which is not consistent with the free electron model. Therefore, in this paper we modify it to be the following simple linear expression: where 0 > β is a deterministic constant and is another algorithmic parameter called the drift coefficient.
Equation (14) has a clear physical meaning that it reflects the particle's directional movement towards n i p , .
In Theorem A1 in the Appendix, it is proven that, if there is only drift motion and, i.e., With the above specification, a novel set of update equations can be obtained for the particle of the RDPSO algorithm: (16) The procedure of the algorithm is outlined below. Like in the canonical PSO, the value of j

Begin
Initialize the current positions and velocities of all the particles randomly; Set the personal best position of each particle to be its current position; Set n=0; While (termination condition = false)

n=n+1;
Compute mean best position n C ; Evaluate the objective function value ) ( ,n i X f ; Update n i P , according to equation (4) and then update n G ;

Dynamical Behavior of the RDPSO Particle
An analysis of the behavior of an individual particle in the RDPSO is very essential to understanding how the RDPSO algorithm works and how to select the algorithmic parameters. Since the particle's velocity is the superimposition of the thermal velocity and the drift velocity, the conditions for the particle's position to converge or to be bounded are far more complex than those given in subsection 3.1 when only the drift motion exists. In this subsection, we undertake theoretical and empirical studies on the stochastic dynamical behavior of the particle in the RDPSO. Since each dimension of the particle's position is updated independently, we only need to consider a single particle in the one-dimensional space without loss of generality. As such, equations (15) and (16) can be simplified as where n X and n V denote the current position and the velocity of the particle, respectively, and the local focus of the particle and the mean best position are denoted by p and C , which are treated as probabilistically bounded random variables, i.e., In equation (17), Since the distribution of n ϕ is symmetrical with respect to the ordinate, equation (17) has the following equivalence: that is, the probability distributions of 1 + n V in equations (17) and (19) are the same. Based on equations (19) and (18), several theorems on the dynamical behavior of a single particle in RDPSO are proved in the Appendix. As shown by Theorem A2, the particle's behavior is related to the convergence of , namely, the values of α and β satisfy the following relationship: n ρ is probabilistically bounded and, thus, the position of the particle is probabilistically bounded too. In inequality (20), the value of Δ is an improper integral which is undefined at . By Dirichlet test, this improper integral is convergent if both α and β are two finite numbers (Courant, 1989).
Inequality (20) does not provide any explicit constraint relation between α and β due to the difficulty in calculating the improper integral in the inequality. A sufficient condition for ) is derived in Theorems A4. It says that if the values of α and β are subject to the constraint: . In practice, the values of α and β can generally be selected within the intervals given by (21), for a satisfactory algorithmic performance when the algorithm is applied to real-world problems. In Section 4, a detailed investigation into how to select these algorithmic parameters is undertaken by using a set of benchmark functions from the CEC2005 benchmark suite.  (21),

The RDPSO's Search Behavior
In the above analysis, it is assumed that each particle in the RDPSO updates its velocity and position independently, with the mean best position C and the local focus p being treated as independent probabilistically bounded random variables, and thus it is revealed that the behavior of the particle is related to the convergence or the boundedness of n ρ . However, the actual situation is more complex when the RDPSO algorithm is running in a real-world landscape. During the search process of the RDPSO algorithm, each particle is influenced not only by n ρ but also by the points n C and n i p , , which can not be treated as independent random variables anymore, but are relevant to the other particles. As for n C , it is the mean of the . It can also be found from Theorems A2 and A3 that, when 0 = Δ , the particle's position is probabilistically bounded and oscillates around but does not converge to n C or n i p , , even , it is shown by Theorems A2 and A3 that the particle's current position diverges and the explosion of the whole particle swarm happens.
In practical applications, it is always expected that the particle swarm in the RDPSO algorithm can converge to a single point, like that in the canonical PSO. Essentially, there are two movement trends, i.e. the random motion and the drift motion, for each particle in the RDPSO, as has been described in the motivation of the algorithm. These two motions reflect the global search and the local search, respectively. The drift motion, represented by the j n i VD 1 , + in the velocity update equation (15), draws the particle towards the local focus and makes the particle search in the vicinity of the gbest position and its pbest position so that the particle's current and pbest positions can constantly come close to the gbest position. On the other hand, the random component results in a random motion, leading the particle to be so volatile that its current position may reach a point far from the gbest position and its pbest position. This component can certainly provide the particle a global search ability, which, in the canonical PSO algorithm, is given by the velocity at the last iteration, i.e. j n i V 1 , + . Nevertheless, an important characteristic distinguishing the RDPSO from other randomized PSO methods is that the random component of the particle's velocity uses an adaptive standard deviation for its distribution, i.e.
. Such a random component makes the random motion of the particle have a certain orientation. The effect of is to pull or push the particle away from the gbest position by j n C as shown by Figure 2, not only to displace the particle randomly as the mutation operation does in some variants of PSO and evolutionary algorithms.
, which makes the particle move to the right further and, thus, pushes , whose effect is that the particle's position is pulled away from j n G . Figure 2 will be away from the gbest position. If the particle's position is close to the gbest position, the random component can help the particle escape the gbest position easily, when the gbest position is stuck into a local optimal solution. As far as the whole particle swarm is concerned, the overall effect is that the RDPSO has a better balance between the global search and the local search, as illustrated below.
Figure3. The figure shows that n C is shifted toward the lagged particles and thus far from the particles clustering around n G . The particles are pulled or pushed away from the neighbourhood of n G and would search the landscape globally.
In the RDPSO method, the swarm could not gather around the gbest position without waiting for the lagged particles. Figure  is, converging to n G , n C is approaching n G slowly. The current positions of the particles within the neighbourhood would be pulled or pushed outside the neighbourhood by n C , and the particles would explore the landscape globally around n G so that the current n G could skip out onto a better solution. As n C is careening toward the neighbourhood, the exploration scope of the particle is becoming narrower.
After the lagged particles move into the neighbourhood of the gbest position, n C also enter the neighbourhood and the particles would perform the same search process based on a smaller neighbourhood of the gbest position. In the canonical PSO, each particle converges to the gbest position independently and has less opportunity to escape from the neighbourhood of the gbest position. When the speed of the particle is small, it is impossible for the particles within the neighbourhood to jump out of the neighbourhood. As a result, these particles would perform local search around the gbest position and only the lagged particles could search globally. Evident from the above analysis, the RDPSO algorithm generally has a better balance between exploration and exploitation than the canonical PSO. Moreover, different from mutation operations that play minor roles in some variants of PSO and evolutionary algorithms, the random motion has an equally important role as the drift motion in the RDPSO.
Owing to the random motion oriented by n C , the RDPSO achieves a good balance between the local and global searches during the search process. By the influences of both n C and their local focuses, the particles in the RDPSO have two movement trends, convergence and divergence, but the overall effect is their convergence to a common point of all the particles if 0 < Δ . The convergence rate of the algorithm depends on the values of α and β , which can be tuned to balance the local and global search, when the algorithm is used for a practical problem.

Variants of RDPSO
In order to investigate the RDPSO in depth, some variants of the algorithm are proposed in this paper.
Two methods are used for determining the random component of the velocity. One employs equation (13) for this component and the other replaces the mbest position in (13) by the pbest position of a randomly selected particle in the population at each iteration. For convenience, we denote the randomly selected pbest position by n C′ . For each particle, the probability for its pbest position to be selected as n C′ is 1/M.
Consequently, the expected value of n C′ equals to n C , that is, However, since the n C′ appears to be more changeful than n C , the current position of each particle at each iteration shows to be more volatile than that of the particle with equation (13), which diversifies the particle swarm and in turn enhances the global search ability of the algorithm.
In addition to the global best model, the local best model is also examined for the RDPSO. The ring topology is a widely used neighborhood topology for the local best model (Li, 2010), in which each particle connects exactly to two neighbors. The standard PSO (SPSO) in (Bratton and Kennedy, 2007) is defined by the integration of the PSO-Co with the ring topology. Although there are various neighborhood topologies, we chose the ring topology for the RDPSO with the local best model. Thus, the combination of the two topologies with the two strategies for the random velocity component produces the four resulting RDPSO variations:

RDPSO-Gbest:
The RDPSO algorithm with the global best model and the random velocity component described by equation (13).

RDPSO-Gbest-RP:
The RDPSO algorithm using the global best model and employing a randomly selected pbest position to determine the random velocity component.

RDPSO-Lbest:
The RDPSO algorithm with the ring neighborhood topology and the random velocity component in (13), where, however, the mbest position is the mean of the pbest positions of the neighbors of each particle and the particle itself, instead of the mean of the pbest positions of all the particles in the population.

RDPSO-Lbest-RP:
The RDPSO algorithm using the ring neighborhood topology and employing the pbest position of a particle randomly selected from the neighbors of each particle and the particle itself.

Benchmark Problems
The previous analysis of the RDPSO provides us with a deep insight into the mechanism of the algorithm. However, it is not sufficient to evaluate the effectiveness of the algorithm without comparing it with other methods on a set of benchmark problems. To evaluate the RDPSO in an empirical manner, the twenty five functions from the CEC2005 benchmark suite  were employed for this purpose. Functions F 1 to F 5 are unimodal, functions F 6 to F 12 are multi-modal, F 13 and F 14 are two expanded functions, and F 15 to F 25 are hybrid functions. The dimension N was chosen as 30 for each of these functions. The mathematical expressions and properties of the functions are described in detail in . The codes in Matlab, C and Java for the functions could be found at http://www.ntu.edu.sg/home/EPNSugan/.

Empirical Studies on the Parameter Selection of the RDPSO Variants
Parameter selection is the major concern when a stochastic optimization algorithm is being employed to solve a given problem. For the RDPSO, the algorithmic parameters include the population size, the maximum number of iterations, the thermal coefficient α and the drift coefficient β . Like in the canonical PSO, the population size in the RDPSO is recommended to be set from 20 to 100. The selection of the maximum number of iterations depends on the problem to be solved. In the canonical PSO, the acceleration coefficients and the inertia weight (or the constriction factor) have been studied extensively and in depth since these parameters are very important for the convergence of the algorithm. For the RDPSO algorithm, α and β play the same roles as the inertia weight and the acceleration coefficients for the canonical PSO.
In Section 3, it was shown that it is sufficient to set α and β according to (21), such that 0 < Δ , to prevent the individual particle from divergence and guarantee the convergence of the particle swarm.
However, this does not mean that such values of α and β can lead to a satisfactory performance of the RDPSO algorithm in practical applications. This section intends to find out, through empirical studies, suitable settings of α and β so that the RDPSO may yield good performance in general. It also aims to compare the performance of the RDPSO variants with other forms of PSO.
There are various control methods for the parameters α and β when the RDPSO is applied to practical problems. A simple approach is to set them as fixed values when the algorithm is executed. Another method is to decrease the value of the parameter linearly during the course of the search process. In this work, we fixed the value of β in all the experiments and employed the two control methods for α , respectively.
To specify the value of α and β for real applications of the RDPSO, two groups of experiments were performed on the benchmark functions. The first group of experiments tested the RDPSO algorithm with different parameter settings on several benchmark functions in order to find out the parameter settings that can yield satisfactory performance on these functions. Then, the identified parameter settings were tested by more benchmark functions, to verify their generalizability, in the second group of experiments.
In the first set of experiments, we tested the RDPSO-Gbest, RDPSO-Gbest-RP, RDPSO-Lbest, and RDPSO-Lbest-RP on three frequently used functions in the CEC2005 benchmark suite: Shifted Rosenbrock Function (F 6 ), Shifted Rotated Griewank's Function (F 7 ), and Shifted Rastrigin's Function (F 9 ), using the two methods for controlling α with β fixed at 1.5 or 1.45. The initial position of each particle was determined randomly within the initialization range. For each parameter configuration, each algorithm, using 40 particles, was tested for 100 runs on each problem. To determine the effectiveness of each algorithm for the α setting under each control method with a fixed value of β on each problem, the best objective function value (i.e., the best fitness value) found after 5000 iterations was averaged over 100 runs of tests for that parameter setting and the same benchmark function. The results (i.e., the mean best fitness values) obtained by the parameter settings with the same control method for α were compared across the three benchmarks. The best parameter setting with each control method for α was selected by ranking the averaged best objective function values for each problem, summing the ranks, and taking the value that had the lowest summed (or average) rank, provided that the performance is acceptable (in the top half of the rankings) in all the tests for a particular parameter configuration.
The rankings of the results for the RDPSO-Gbest are plotted in Figure 4. When the fixed value method was used for α , it was set to a range of values subject to constraint (21), with β setting at 1.5 or 1.45 in each case. Results obtained for other parameter settings were very poor and are not considered for ranking. When linearly varying α was used, its initial value 1 α and final value 2 α ( 2 1 α α > ) were selected from a series of different values subject to constraint (21), with β setting at 1.5 or 1.45. Only acceptable results are ranked and plotted in Figure 4. It was found that with , decreasing α linearly from 0.9 to 0.3 leads to the best performance among all the tested parameter settings.  Figure 4. The rankings of the mean best fitness values for each of the three benchmarks and the average rank for the RDPSO-Gbest.
The rankings of the results for the RDPSO-Gbest-RP are visualized in Figure 5. It is clear from these results that the value of α , whether it used the fixed value or time-varying method, should be set relatively small, so that the algorithm is comparable in performance with the RDPSO-Gbest, when β was given.
Results obtained with α outside the range [0.38, 0.58] were of poor quality and were not used for ranking.
As shown in Figure 5, when the fixed value method for α was used, the best average ranks among all tested parameter settings were obtained by setting   In the second group of experiments, each variant of the RDPSO with the parameter settings for α and β that were identified to yield better performance on average in the first group of experiments were tested by the first twelve benchmark functions in the CEC2005 benchmark suite. The purpose here is to find out whether the identified parameter settings are able to obtained satisfactory performance for other problems and to make a further performance comparison between the two methods of controlling α for each RDPSO variant. The results listed in Table 1 include the means and standard deviations of the best fitness values obtained over 100 runs of each RDPSO variant on each of the twelve benchmarks. For the RDPSO-Gbest, the linearly varying α method outperformed the fixed α method on all the twelve functions except F 4 and F 11 . For the RDPSO-Gbest-RP, the linearly varying α generated better results than the fixed α on eight functions (i.e. F 3 , F 5 , F 6 , F 7 , F 9 , F 10 , F 11 and F 12 ). It can be seen that the linearly varying α method outperformed the fixed α method on all of the twelve functions for the RDPSO-Lbest.
For the RDPSO-Lbest-RP, the linearly varying α had better performance than the fixed α on five benchmarks. On the other benchmark functions, the linearly varying α method did not show significant poorer performance compared to the fixed α method. However, among the eight versions of the RDPSO, the total rank of the RDPSO-RP with the linearly varying α are smaller than that with the fixed α . Besides, in the first set of experiments, we found that the performance of each RDPSO variant with the fixed α is more sensitive to the value of α than that with the linearly varying α . Considering the above facts, we recommended that the linearly varying α method should be used for real applications.

Performance Comparisons among the RDPSO Variants and Other PSO Variants
To investigate the generalizability of the parameter settings for the linearly varying α method used in the RDPSO, and to the determine whether RDPSO can be as effective as other variants of PSO, a further performance comparison using all the twenty five benchmark functions of the CEC2005 benchmark suite was made between the RDPSO algorithms (i.e., the RDPSO-Gbest, RDPSO-Gbest-RP, RDPSO-Lbest and RDPSO-Lbest-RP) and other variants of PSO, including the PSO with inertia weight (PSO-In) (Shi and Eberhart, 1998a;1998b;, the PSO with constriction factor (PSO-Co) (Clerc and Kennedy, 2002;Clerc 1999), the PSO-In with local best model (PSO-In-Lbest) (Liang et al., 2006), the standard PSO (SPSO) (i.e. PSO-Co-Lbest) (Bratton and Kennedy, 2007), the Gaussian bare bones PSO (GBBPSO) (Kennedy, 2003;, the comprehensive learning PSO (CLPSO) (Liang et al., 2006), the dynamic multiple swarm PSO (DMS-PSO) , and the fully-informed particle swarm (FIPS) (Mendes, 2004).
Each algorithm was run 100 times on each problem using 40 particles to search the global optimal fitness value. At each run, the particles in the algorithms started in new and randomly-generated positions, which are uniformly distributed within the search bounds. Each run of each algorithm lasted 5000 iterations, and the best fitness value (objective function value) for each run was recorded.
For the four RDPSO variants, the linearly decreasing α with fixed β was used, and the parameters for each case were set as those indentified and recommended by the previous experiments. Thus, the results for the first twelve functions by the RPSO variants are those listed in Table 1, which were yielded by the algorithms with linearly varyingα . The parameter configurations for other PSO variants were the same as those recommended by the existing publications. For the PSO-In, the inertia weight linearly decreased from 0.9 to 0.4 in the course of the run and we fixed the acceleration coefficients (c 1 and c 2 ) at 2.0, as in the empirical study performed by Shi and Eberhart (1999). For the PSO-Co, the constriction factor was set to be , and the acceleration coefficients c 1 =c 2 =2.05, as recommended by Clerc and Kennedy (2002).
Eberhart and Shi also used these values of the parameters when comparing the performance of the PSO-Co with that of the PSO-In (Eberhart and Shi, 2000). For the SPSO, the ring topology was used and other parameters were set as those in the PSO-Co (Bratton and Kennedy, 2007). Parameter configurations for the GBBPSO, FIPS, DMS-PSO and CLPSO were the same as those in (Kennedy, 2003;Mendes et al., 2004;Liang and Suganthan, 2005;Liang et al., 2006), respectively.
Tables 2 and 5 record the mean and the standard deviation of the best fitness values out of 100 runs of each algorithm on each problem. To investigate if the differences in the mean best fitness values between the algorithms were significant, two statistical tests were employed for this purpose. The first one is the unpaired t test between two adjacent mean best fitness values in ascending order for each problem with 0.05 as the level of significance. The t values and p values of the t tests are provided in Tables 6 to 10. The second one is a multiple comparison procedure which was used to determine the algorithmic performance ranking for each problem in a statistical manner. The procedure employed in this work is known as the "stepdown" procedure (Day and Quinn, 1989). The algorithms that were not statistically different to each other were given the same rank; those that were not statistically different to more than one other groups of algorithms were ranked with the best-performing of these groups. For each algorithm, the resulting rank for each problem and the average rank across all the twenty five benchmark problems are shown in Table 11.
For the Shifted Sphere Function (F 1 ), the RDPSO-Lbest-RP generated better results than the other methods. The results for the Shifted Schwefel's Problem 1.2 (F 2 ) show that the PSO-Co and the GBBPSO performed better than the others, but the performance of the CLPSO seems to be inferior to those of other For F 24 (another rotated hybrid composition function) and F 25 (the version of F 24 without bounds), the RDPSO-Gbest-RP and RDPSO-Gbest showed the better performance than the others.
The average ranks listed in Table 11 reveal that the RDPSO-Lbest had the best overall performance among all the tested algorithms. For ten of the benchmark functions, the algorithm had the first performance ranks, but unsatisfactory performance for F 2 due to its slow convergence speed resulted from the local best model. The second best-performing was the RPDSO-Gbest-RP. Across the whole suite of benchmark functions, it had fairly stable performance, with the worst rank being 6 for F 9 , F 16, F 17 and F 18 , respectively.
The RDPSO-Gbest had the third best overall performance. Compared to the RDPSO-Gbest-RP, the RDPSO-Gbest performed somewhat unstable, with the resulting ranks for F 1 and F 16 being only 8 and 10, respectively. However, like the RDPSO-Gbest-RP, the RDPSO-Gbest had the first ranks for nine benchmark functions. The fourth best performing was the RDPSO-Lbest-RP, which did not show satisfactory performance on F 2 and F 4 . Nevertheless, it had a significant advantage over the DMS-PSO, the next best performing one. Between random velocity components determined by the mbest position and the random selected pbest position, the two versions of the RDPSO with the mbest position obtained the total average rank of 2.92, while the two with the randomly selected pbest position had the total average rank 3.10. Also, what can be found from the total average ranks is that the RDPSOs were able to work slightly better by using the local best model (with the total average rank 3.06) than the global best model (with the total average ranks 3.16) for the CEC2005 benchmark suite. Besides, the total average rank over all the versions of the RDPSO is 3.11, which implies that the RDPSOs with the linearly varying α and fixed β had a satisfactory overall performance. Therefore, it is recommended that the linearly varying α method with fixed β should be employed when the RDPSO is used for real applications. More specifically, for the Except the RDPSO algorithms, the best-performing algorithm was the DMS-PSO, which yielded the best results for F 22 . It showed good performance for most of the multimodal functions, but did not work well on unimodal ones. The next best algorithm was the SPSO, i.e. PSO-Co-Lbest. For F 7 and F 8 , it yielded the best results among all the competitors. The FIPS, which also employs the ring topology, was the next best performing algorithm and generated the best results for F 21 . It is conclusive, from the total average ranks in Table 11, that incorporating the ring topology into the PSO-In and the PSO-Co could enhance the overall performance of the two PSO variants on the tested benchmark functions. What should be noticed is that the CLPSO is very effective in solving separable functions such as F 9 , but not in the rotated functions and unimodal ones due to its slower convergence speed, as has been indicated in the related publication (Liang, et al., 2006). The GBBPSO, an important probabilistic PSO variant, had good performance for unimodal functions. It is impressive that it generated the best result for F 2 , implying that it has a relative faster convergence speed than its competitors on this type of functions.

Conclusion
In this paper, inspired by the free electron model in metal conductors in an external electric field, the RDPSO algorithm was proposed as a novel variant of PSO. The velocity updated equation of the particle in the RDPSO algorithm is a superposition of two parts, i.e., a random component and a drift component, which reflect the global and the local search of the particle, respectively. These two components were designed to simulate the thermal motion as well as the drift motion of the electron, which lead the electron to a location with minimum potential energy in a metal conductor under an external electric field. Thus, the search process of the RDPSO algorithm is analogous to the process of minimizing the electron's potential energy.
A comprehensive analysis of the RDPSO algorithm and its variants was made in order to better understand the mechanism behind the algorithm. Firstly, the stochastic dynamical behavior of a single particle in the RDPSO was analyzed theoretically. We derived the sufficient and necessary condition as well as a sufficient condition for the particle's current position to be probabilistically bounded. Secondly, the search behavior of the RDPSO algorithm itself was investigated by analyzing the interaction between the particles, and it was found that the RDPSO may have a good balance between the global and the local search, due to the designed random component of the particle's velocity. Subsequently, some variants of the RDPSO algorithm were proposed by combining different random velocity components with different neighborhood topologies.
Empirical studies on the RDPSO algorithm were conducted on all the twenty five benchmark functions of the well-known CEC2005 benchmark suite. Two methods for controlling the algorithmic parameters were employed, and each RDPSO variant, with each control method, was first tested on three of the benchmark functions in order to identify the parameter values that can generate the best performance.
Then, the RDPSO variants with the identified parameter values were compared on the first twelve benchmark functions. Finally, the RDPSO variants with the linearly varying thermal coefficient and the fixed drift coefficient were further compared with other forms of PSO on all the twenty five functions. The experimental results show that the RDPSO algorithm is comparable with, or even better, than its competitors in finding the optimal solutions of the tested benchmark functions.
From which we can recursively derive the following formula The necessary and sufficient condition for n ρ to be probabilistically bounded, i.e. . This completes the proof of the sufficiency.
(2) From (A11), we have the following equivalent propositions: Thus, considering the case for