量子行为粒子群优化算法-英文版.ppt

1、Quantum-behaved Particle Swarm Optimization,Outline,Background Quantum Particle Swarm Optimization Convergence of the Particle Experiment Results on Benchmark Functions Conclusion Future Work,Background,swarm intelligence a type of biological (social) system the collective behaviors of simple indivi

2、duals interacting with their environment and each other There are two popular swarm inspired methods in swarm intelligence areas: Ant Colony Optimization (ACO) Particle Swarm Optimization (PSO),Background,Particle Swarm Optimization It mimics the collective intelligent behavior of “ intelligent ” cr

3、eatures It was developed in 1995 by James Kennedy and Russell Eberhart Kennedy, J. and Eberhart, R. (1995). “Particle Swarm Optimization”, Proceedings of the 1995 IEEE International Conference on Neural Networks, pp. 1942-1948, IEEE Press. (/members/payman/swarm/kennedy95-ijcnn

4、.pdf ) It has been applied successfully to a wide variety of search and optimization problems In PSO, a swarm of n individuals communicate either directly or indirectly with one another in each search directions.,A particle (individual) is composed of: Three vectors: The x-vector records the current

5、 position (location) of the particle in the search space The p-vector records the location of the best solution found so far by the particle The v-vector contains a gradient (direction) for which particle will travel in if undisturbed. Two fitness values: The x-fitness records the fitness of the x-v

6、ector The p-fitness records the fitness of the p-vector.,Particle Swarm OptimizationThe Anatomy of a Particle,The Anatomy of a Particle,Ii X = P = V = x_fitness = ? p_fitness = ?,Particle Swarm Optimization,Particle Swarm Optimization,The particle will move according to the following equation: Veloc

7、ity calculation vid(t)=w*vid(t-1)+c1*rand()*(pid-xid(t-1)+c2*rand()*(pgd-xid(t-1) Position calculation xid(t)=xid(t-1)+vid(t) xid current value of the dimension “d” of particle “i” vid current velocity of the dimension “d” of particle “i”. Pid optimal value of the dimension “d” of particle “i” so fa

8、r. Pgd current optimal value of the dimension “d” of the swarm. c1, c2 acceleration coefficients. w - inertia weight factor,Particle Swarm Optimization,Pid,Pgd,Vid(t),Vid(t-1),Particle Swarm OptimizationSwarm Search,In PSO, particles never die! Particles can be seen as simple agents that fly through

9、 the search space and record the best solution that they have discovered. Initially the values of the velocity vectors are randomly generated with the range -Vmax, Vmax where Vmax is the maximum value that can be assigned to any vid. Once the particle computes the new Xi it then evaluates its new lo

10、cation. If x-fitness is better than p-fitness, then Pi = Xi and p-fitness = x-fitness.,Particle Swarm Optimization,The algorithm 1. Initialise particles in the search space at random. 2. Assign random initial velocities for each particle. 3. Evaluate the fitness of each particle according to a user

11、defined objective function. 4. Calculate the new velocities for each particle. 5. Move the particles. 6. Repeat steps 3 to 5 until a predefined stopping criterion is satisfied.,Quantum-behaved Particle Swarm Optimization,There are still some limitations in particle swarm including but not limited to

12、: The PSO is not a global convergence-guaranteed algorithm. The reliance of the search global search ability on the upper limit of the velocity reduces the robust of PSO algorithm. Parameter selection is another problem,Quantum-behaved Particle Swarm Optimization,The Motivation of QPSO According to

13、the characteristic of collectiveness of swarm intelligence, the potential well of was built on the point between pid and pgd The probability density function and distribution function are Where L is a parameter.,Quantum-behaved Particle Swarm Optimization,The evolution equations of the QPSO Using Mo

14、nte Carlo method, we obtain the following equation The mean of the pbest position is introduced L is evaluated by The evolution equation of the QPSO,The QPSO Algorithm,(1) Initialize population: random xi (2) do (3) Calculate mbest using equation (10) (4) for i=1 to population size M (5) If f(xi)0.5

15、 (13) xid=P-L*ln(1/u) else (14) xid=P+L*ln(1/u) (15) Until termination criterion is met,QPSO is provided with the following characteristics： Enhance the global search ability of PSO algorithm Has just only one parameter, easy to realize and to select the parameter. It is more stable than original PS

16、O.,Convergence Behavior of the individual particle in QPSO,In the stochastic simulations, point P is fixed at x=0, and the initial position of the particle is set to be 1000, that is x(0)=1000. The value of Contraction-Expansion Coefficient a is set to be 0.7, 1.0, 1.5, 1.7, 1.8 and 2.0 respectively

17、, and the number of iterations are 1000, 1500, 5000, 1500, 50,000, and 7000 respectively. The logarithmic value of the distance between current position x(t) and point p is recorded.,Convergence Behaviour of the Individual Particle in QPSO,Convergence Behavior of the Individual Particle in QPSO,Conv

18、ergence Behavior of the Individual Particle in QPSO,Convergence Behavior of the Individual Particle in QPSO,It can be concluded that when a1.8, it will diverge. There must be such a threshold value a0 in interval (1.7, 1.8) that if a a0). We have theoretical demonstrated using probabilistic analysis

19、 that a0=exp(g)1.778, where g is Euler constant.,Parameter Control of QPSO,The only parameter needed to be controlled in QPSO is a. The previous experiment results show that QPSO has a general good performance when a is decreasing linearly from 1.0 to 0.5,Experiment Configuration,Experiment Configur

20、ation,We had 50 trial runs for every instance and recorded mean best fitness and standard deviation. The population sizes are 20, 40 and 80. The maximum generation is set as 1000, 1500 and 2000 corresponding to the dimensions 10, 20 and 30 for first four functions, respectively, and the dimension of the last function is 2. The coefficient a decreases from 1.0 to 0.5 linearly when the algorithm is running.,Experiment Results,1. Results on Sphere Function,2. The Results on Rosenbrock Function,Experiment R