Abstract: To maintain the diversity and improve the convergence rate of Particle Swarm Optimization (PSO), three kinds of modified PSO algorithms are proposed and they are PSO based on molecular force (MFPSO), PSO combined with Brownian motion (BMPSO) and PSO hybrid with diffusion phenomenon (DPPSO), respectively. The three above strategies are all inspired by the mechanism of statistical physics and thermodynamics. Comparison experiments involve four test functions. They are sphere function, griewank function, rastrigin function and ackley function which are frequently used in the evolutionary optimization literature to test and compare the performance differences of algorithms. The results show that BMPSO generally outperforms MFPSO and DPPSO. And then qualitative analysis about the features of the three PSO algorithms is proposed.
INTRODUCTION
In the 90's of last century, the Particle Swarm Optimization (PSO) was initialized as a novel heuristic algorithm. PSO designed and developed by Eberhart and Shi (1998) in the beginning, was intended for simulating social behavior of bird flocking or fish schooling. In PSO, each particle adjusts its movement according to its own activity experience and its companions' activity experience rather than the traditional genetic operators. There are plenty of real-world applications (Chen et al., 2012) in which the PSO algorithm has shown its outstanding performance.
Many literatures have been devoted to compare the heuristic algorithms to each other. To raise added perceptions to how each paradigm works and to suggest methods in which performance might be promoted by incorporating characteristics and advantages from one paradigm into the other, Eberhart and Shi (1998) hence, compared PSO with Genetic Algorithm (GA). Angeline (1998) made a thorough investigation into the philosophical and performance differences of particle swarm and evolutionary algorithm. Vesterstrom and Thomsen (2004), whose study focused on a large and diverse number of numerical function optimization problems, made a comparative research of Differential Evolution (DE), PSO and GA. Basu and Mahanti (2010) then, applied the improved PSO, DE and Artificial Bees Colony algorithms in synthesis of circular array and demonstrated a comparative assessment of the three algorithms. As for the three types of particle swarm, optimization Jamian et al. (2012) have carried out a comparative study.
The mechanism of statistical physics and thermodynamics which consists of the molecular force, Brownian motion and diffusion phenomenon, is utilized to design and modify the PSO algorithm. And then, this study compares the three PSO algorithms which are mixed with different thermodynamics mechanisms on a set of benchmark problems for the first time and furthermore, these algorithms are analyzed at the level of quality.
PARTICLE SWARM OPTIMIZATION
In PSO, the particles are manipulated in accordance with the following equations:
| (1) |
| (2) |
More details about PSO were given in related refercences (Xu, 2011).
HYBRID PARTICLE SWARM ALGORITHMS
Particle swarm optimization algorithm based on diffusion phenomenon: The diffusion phenomenon of thermodynamics was applied to improve particle swarm optimization and a modified PSO algorithm (DPPSO) based on diffusion mechanism was proposed as well. In the DPPSO algorithm, the diffusion energy of the particle, together with the temperature of the swarm and the diffusion probability of the particle, were defined, respectively. Then, on the basis of former three definitions, the core idea of DPPSO algorithm and the algorithm process are described in details.
Particle diffusion energy:
where, Dim is the particle dimension in the search space, i is the particle index and Vij is the jth dimensional component of the ith particle velocity vector.
Population temperature:
where, M is the number of the particles, that is to say, M stands for the population size.
Particle diffusion probability:
where, Qi is the ith particle diffusion energy, T is the population temperature, the gas constant R = 1.
In DPPSO algorithm, double populations (P1 and P2) are used to simulate the diffusion mechanism. Based on diffusion mechanism, the procedure of the hybrid particle swarm optimization is as follows:
| Step 1: | Initialize the velocity and position of the particles in P1 and P2, respectively |
| Step 2: | Evaluate the fitness value of each particle in P1 and P2, then update the global best among all particles and the best previous position of each particle |
| Step 3: | Compute the diffusion energy of all particles in P1 and P2, the population temperature in addition and the diffusion probability of all particles in P1 and P2 |
| Step 4: | for (i = 0; i<M; i ++)/*for P1*/ if (rand()<Pro1), the ith particle is chosen into the diffusion pool DP1> |
| Step 5: | for (i = 0; i<M; i++) /*for P2*/ |
| Step 6: | if (rand()<Pro2) The ith particle is selected into the diffusion pool DP2 |
| Step 7: | Two particles, randomly selected in the diffusion pool DP1 (DP2), are used to generate a difference vector which is the disturbance of the global minimum of population P1 (P2). If the global minimum with the disturbance vector is better than the global minimum of other population P2 (P1) then it will be replaced |
| Step 8: | Adjust the velocity and position in accordance with the Eq. 1 and 2 |
| Step 9: | If the convergence criterion is not fulfilled, go to Step 2), otherwise, output the global optimal solution and end the algorithm |
PARTICLE SWARM OPTIMIZATION COMBINED WITH MOLECULAR FORCE
To maintain the diversity of particles is crucial to improve the performance of PSO algorithm. Inspired by molecular kinetic theory, the particle swarm optimization algorithm based on the molecular force (MFPSO) is put forward. To make an analogy to thermodynamic molecular system, the molecular force between particles, swarm centroid and particle acceleration are introduced in the MFPSO and thus the particle’s velocity updating formula is modified. The molecular force between swarm centroid and itself is presented as an attractive or repulsive force determined by the distance of them and this force decides whether the particle moves towards the swarm centroid or keeps away from it for the sake of the maintenance of diversity, hence the MFPSO could effectively balance the global as well as the local search.
Swarm centroid:
where, mi is the quality of particle i. In order to simplify, the quality of all particles is assumed to be equal to 1. Particle acceleration ai = Fi/Mi, where, Fi is the molecular force between two particles. Just consider its direction instead of the numerical size of ai, when the molecular force Fi is attractive, ai = +1, or when the molecular force Fi is repulsive, ai = -1. According to the definition of swarm centroid and particle acceleration, the posiion formula is re-fined as follows:
| (3) |
The process of MFPSO Algorithm is presented as follows:
PARTICLE SWARM OPTIMIZATION BASED ON BROWNIAN MOTION
In order to improve the convergence rate of particle swarm optimization, a kind of hybrid algorithm, i.e. BMPSO which mixes Brownian motion and PSO algorithm, is proposed with the inspiration of the Brownian motion and ITO process. The drift operator and fluctuation operator are designed by abstracting Brownian motion from the ITO process.
Drift operator: The drift operator retains the position property of particle while there is no speed attribute for particle of BMPSO. The attractor concept is also introduced and the position formula is re-defined as follows:
| (4) |
The differential mutation operator: The differential mutation operator is used to design the fluctuation operator. The above-mentioned formula changes into the following formula:
| (5) |
where, δ is the fluctuation coefficient, m and n are the indices of randomly selected particles, besides, m≠n≠i.
The process of BMPSO algorithm undergoes as follows:
ALGORITHMS PERFORMANCE COMPARISON
Experimental contrastive analysis:
Comparative experiments involving four test functions which are well studied in the evolutionary optimization literature, are used to highlight some performance differences between DPPSO and the particle swarm optimization algorithms mixed with different thermodynamics mechanisms, i.e., MFPSO, BMPSO. The dimensions of all four benchmarks are set to 30. For more details about the parameter settings of these PSO algorithms, refer to the related literature. Table 1 and 2, whose mean column represents the mean of the best fitness values of 50 runs and standard deviations respectively, summarize the results of these algorithms.
| Table 1: | Average fitness of the fifty runs obtained by MFPSO, BMPSO and DPPSO method for the different test function |
MFPSO represents PSO based on the molecular force; BMPSO represents PSO based on the Brownian motion; DPPSO represents PSO based on the diffusion phenomenon |
|
Figure 1 is the average fitness curves of the three PSO algorithms for the function F01, F02, F03 and F04, respectively. From the Fig. 1, it can be seen that the BMPSO algorithm converges toward the optimum and the fitness curve obtained by BMPSO tends to zero very quickly at early stage; MFPSO and DPPSO could converge except function F03. Among the three PSO algorithms, the performance of the BMPSO is best.
Qualitative analysis: All the three particle swarm optimization algorithms, that is, MFPSO, BMPSO and DPPSO, are inspired by thermodynamics and statistical physics theories and their characteristics are as follows:
| • | The three algorithms can improve the performance of standard PSO algorithm to some degree. Relatively speaking, the convergence speed of BMPSO is the fastest. The accuracy and stability of the BMPSO algorithm are the best as well |
| • | BMPSO algorithm abandons the concept of particle velocity while MFPSO and DPPSO algorithm still retain the characteristics of the particle velocity |
| • | MFPSO and BMPSO algorithms are based on single population, though the double-populations are adopted in DPPSO algorithm |
| • | DPPSO algorithm introduces the concept of temperature and the temperature calculation does derive from the formula in real time |
| • | The drift operator and the fluctuation operator of BMPSO algorithm can be respectively viewed as the crossover operator and the mutation operator of the evolutionary algorithms, respectively which shows that the integration of the PSO and other evolutionary computation can improve the performance of PSO algorithm |
| Table 2: | Standard deviations of the best fitness of the fifty runs for the different test function |
MFPSO represents PSO based on the molecular force; BMPSO represents PSO based on the Brownian motion; DPPSO represents PSO based on the diffusion phenomenon | |
| Fig. 1(a-d): | Fitness curves of MFPSO, BMPSO and DPPSO changing with the iteration for the different test functions; subfigures (a)-(d) are the curves of the function F01, F02, F03 and F04, respectively |
CONCLUSION
Particle Swarm Optimization (PSO) is designed and also improved by the different aspects of molecular thermal motion. The MFPSO, BMPSO and DPPSO algorithm has its own characteristics each. So, PSO can be recognized from the perspective of thermodynamics, rather than the angle of artificial intelligence or evolutionary computation.
ACKNOWLEDGMENTS
This study was supported by the National Science and Technology Support Plan (2012BAH25F02, 2013BAF02B01), State Key Lab. of Software Engineering (SKLSE2012-09-35), the National Natural Science Foundation of Jiangxi Province (20122BAB211036, 20122BAB201044), the National Nature Science Foundation of China (61202313, 11226225).