A modified particle swarm optimizer based on cloud model

A Modified Particle Swarm Optimizer Based on CloudModelJianping Wen and Binggang CaoResearch Institute of Electric Vehicle and System Control,Xi’an Jiaotong University, Xi’an, Chinawenegle@Abstract – In this paper, we introduce cloud model theory to the particle swarm optimization algorithm to improve the global search ability and make a faster convergence speed of the algorithm. Some modifications are presented. First, we adopt cloud model to initialize the positions and velocities for entire population in the initialization range. Second, inertia weight isdy namically , nonlinearly decreased as the search progresses byusing the data set, which can be obtained by cloud model. Third, two random variants in the velocity rule are assigned with cloud model. Four, inertia weight and the two random variants are correlated b ycloud model. The modified particle swarm optimization is tested on some benchmark functions and the results are compared with the result of the standard particle swarm optimization. Experimental results indicate that the modified particle swarm optimization outperforms the standard particle swarm optimization in the global search ability with aquicker convergent speedIndex Terms – Particle swarm optimization, cloud model, initialization, global optimization. I. I NTRODUCTION The particle swarm optimization (PSO), first proposed by Dr. Kennedy and Dr. Eberhart [1], [2] in 1995, is a stochastic population-base d evolutionary computation optimization technique.. It is inspired originally by the social and cognitivebehavior existed in the bird flocking. The algorithm is initialized with a population of particles random distributed inthe search space. Each particle is assigned a randomized velocity. During a search process, each particle has a tendencyto fly towards better search areas with a velocity, which isdynamically adjusted according to its own experiences and those of its companion, i.e., other members of the population set. The velocity of each particle is updated using the best position it visited so far and the overall best position visited by its companions. Then, the position of each particle is updated using its updated velocity per iteration.Since its introduction, PSO has attracted much attention from researchers around the world. There have been manyresearch works to improve the performance of the original PSO algorithm. Among these improvements, Shi and Eberhart[3] introduced new parameter called inertia weight to the original PSO algorithm to overcome the shortcoming of no actual control mechanism for the velocity. Clerc [4] introduced another parameter called constriction factor to the original PSO algorithm, which may help to ensureconvergence. Eberhart and Shi [5] compared the performance of PSO algorithm using inertia weight to one using the constriction factor. The results indicated the inclusion ofconstriction factor increasing the rate of convergence. The most widely used improvement is the introduction of inertia weight [6], which is employed to control the impact of the previous history of velocities on the current one. On the basis of the PSO algorithm using inertia weight, Shi and Eberhart [7] used the method of a linearly varying inertia weight over the generations to balance global exploration and local exploitation, which improved the performance of the PSO significantly. For better performance, Shi and Eberhart [8] designed a fuzzy system to adjust the inertia weight of PSO algorithm. Inertia weight was nonlinearly, dynamically changed to have better dynamics of balance between global and local search abilities over the generations.In this paper, we present and analyze the modified PSO (mPSO) algorithm. For reflecting the nature of the flocking behavior of bird or the sociological behavior of a group ofpeople and providing balance between the global exploration and local exploitation abilities, the cloud model is adopted toinitialize the positions and velocities for entire population inthe initialization range. Inertia weight is nonlinearly,dynamically decreased as the search progresses by using cloud model. In addition, we replace the uniform distribution function in the velocity rule with the cloud model in order tomaintain diversity of the population. Finally, a numerical simulation result is given, in which the mPSO algorithmsuperiority significantly over the standard PSO (sPSO) algorithm is verified. II. T HE S TANDARD PSO A LGORITHMSuppose that the search space is D-dimensional. A swarm consists of N particles moving around in the D-dimensional search space. The i th particle has an associated current position )x ,,x ,x (X iD i i i "21=, a current velocity )v ,,v ,v (V iD i i i "21=, a personal best position achieved so far by itselfi pbest , which is represented by )p ,,p ,p (P iN i i i "21=. The best position achieved so far by the whole swarm gbest , which is represented by )g ,,g ,g (G N "21=. At each step, the velocity of the i th particle and its new position will be updated according to the following two equations:))()()(( ))()()(()()1(2211t x t g t r c t x t p t r c t wv t v id d i id id i id id −+−+=+ (1))t (v )t (x )t (x id id id +=+1 (2) Proceedings of the 2008 IEEE/ASMEInternational Conference on Advanced Intelligent MechatronicsJuly 2 - 5, 2008, Xi'an, Chinawhere w is called inertia weight; 1c and 2c are constants, called cognitive learning coefficient and social learning coefficient, respectively. )t (r i 1 and )t (r i 2 are two separately generated uniformly distributed random number in the range [0.1] and the values of )t (r i 1 and )t (r i 2 are not same for every iteration. The position of each particle is updated every iteration by adding the velocity vector to the position vector, as given in (2).III. P ROPOSED N EW D EVELOPMENTA. Cloud ModelThe cloud model [9] is defined as follows. Supposed that U is the quantitative universe of discourse, and C is the qualitative concept in U. If the quantitative value x is one of the random values of C belongs to U, and the certainty degree )t (C F of x to C is a random number with stable tendency. Then the distribution of x in the universe of discourse U is called a cloud model, and x a cloud drop. A piece of cloud is made up of a great number of cloud drops that represent a realization of a qualitative concept. Any one of the cloud drops is a mapping in the discourse universe from qualitative concept.The normal cloud is most useful in linguistic terms of vague concepts because the normal distribution have been supported by the results in every branch of both social sciences and natural sciences [10]. A normal cloud is defined with three digital characteristics: Expected value (x E ), Entropy (n E ) and Hyper entropy (e H ). Expectation (x E ) is the point that represents the qualitative concept properly in the universe of discourse. It is the most typical sample of the concept. Entropy (n E ) represents the measure of the concept coverage. If is larger, the concept is more macro. Hyper entropy (e H ) is the uncertain degree of entropy, and can also be considered as the entropy of n E . It reflects the randomness of samples of a qualitative concept [11].To realize the transform between quantitative value and qualitative concept, two kinds of cloud generators are introduced as positive cloud generator and backward cloud generator.G iven three digital characteristics x E , n E and e H , the positive cloud generator can produce a set of cloud drops as requirement [12].B. The Modified PSO AlgorithmThe modified PSO algorithm is presented based on the sPSO algorithm. The detailed modifications will be given in following.In most research on the sPSO algorithm, a population of particles is uniformly generated with random positions, and then random velocities are assigned to each particle in the process of initialization [13]. The general location of potential solutions in a search space may not be known at advance. In this paper, the cloud model is adopted to initialize particles throughout the initialization range for its position and velocityvectors, which can rather reflect the flocking behavior of bird or school of fish. The inertia weight is used to control the momentum of the particle by weighing the contribution of the previous velocity-basically controlling how much memory of the previous flight direction will influence the new velocity and balance the global and local search ability. A large inertia weight facilitates global exploration, while a small one tends to facilitate local exploration. It is crucial in finding the optimum solution efficiently that the inertia weight is nonlinearly, dynamically changed to have better dynamics of balance between global and local search abilities during the search process. In this paper, to efficiently provide balance between global and local exploration abilities, we present the new method for using the normal cloud to nonlinearly, dynamically adjust the inertia weight through the course of the run. The parameters )t (r i 1 and )t (r i 2 are used to maintain the diversity of the population. Considerably high diversity is necessary during the early part of the search to allow use of the full range of the search space. On the other hand, during the latter part of the search, when the algorithm is converging to the optimal solution, find-tuning of the solutions is important to find the global optima efficiently. We replace the old uniform distribution function in the velocity rule with the normal cloud to maintain the diversity of the population over the generations. The velocity equation is expressed as follows: ))()()(( ))()()(()()1(2211t x t g t C c t x t p t C c t v w t v id d i id id i id i id −+−+′=+ (3)where the value of i w ′ over the generations is set as the value of the cloud drops arranged in descending order; )t (C i 1 and )t (C i 2 are set as the value of the cloud drops not arranged in descending order. In the mPSO algorithm, each particle of the swarm shares mutual information globally and benefits from discoveries and pervious experiences of all other colleagues during the search process. The modified PSO method can be described as follows: Step1. G enerate a data set amounted to the number ofalgorithm iterations by using the cloud model.Step2. Initialize each particle’s position and velocity vector byusing a portion of those data and initialization range. Step3. Evaluate the fitness value of each particle.Step4. Set i pbest of each particle as its initial position anddetermine gbest .Step5. Update each particle’s velocity and position using (3)and (2), respectively.Step6. Evaluate the fitness value of each particle. If the currentfitness value for a particle excels its best previous fitness, revise the location of i pbest . After all the particles have been updated, determine and revise gbest if necessary.Step7. Judge the stop criterion, whether the iteration reachedthe given number or the best fitness reaches the givenvalue. If the criterion is satisfied then stop the program, else go to Step5.IV. S IMULATION R ESULTSIn order to test the capability of the mPSO algorithm, a set of 10 benchmark functions [14] are selected. The comparison is taken between the mPSO algorithm and the sPSO algorithm. The benchmark functions as follows: Spherical: ¦==ni i Sph x x f 12)(Ackley:()()e x nx n x f ni i n i i Ack ++⋅−¸¹·¨©§⋅−−=¦¦== 202cos 1exp 12.0exp 20)(112πGriewank:∏¦==¸¸¹·¨¨©§−+=n i i n i i Gri ix cos x )x (f 112400011 Rosenbrock:()()()¦=+−+−=ni ii i Ros x x x )x (f 122211100Rastrigin:()()¦=+−=ni i i Ras x cos x )x (f 1210210πBohachevsky 1:70440 *******221.)x cos(.)x cos(.x x )x (f Boh +−−+=ππEasom:()()0.1cos cos )(222121+−=−−−−ππx x Eas e x x x fColville:)1)(1(8.19 ))1()1((1.10 )1()(90 )1()(100)(422422232234212212−−+−+−+−+−+−+−=x x x x x x x x x x x f Col Hyperellipsoid:¦==n i i Hyp x i )x (f 122Schwefel: ()n .x sin x )x (f ni i i Sch 98294181+=¦=Some parameters of the algorithm in this paper are set as follow: the number of particles in the population space is ser as 30; The maximum iteration number is set as 2000 in each running. Each optimization experiment is run 50 times. A fullyconnected topology is used in all cases. During the optimization process, the particles are limited to move in the region defined by []max max x ,x − and the velocity is restricted to[]max max x ,x −. The number of dimensions, the search space and the optimum are listed in Table I. The range of swarm initialization and goal of function are indicated in Table II.The parameters 1c ,2c , x E , n E and e H for the mPSO algorithm are listed in Table III.TABLE IB ENCHMARKC ONFIGURATION FOR S IMULATIONSFunction Dimension Optimal f [-x max , x max ] f Sph 30 0 [-100,100] f Ack 30 0 [-100,100] f Gri 30 0 [-600,600] f Ros 30 0 [-100,100] f Ras 30 0 [-100,100] f Boh 2 0 [-100,100] f Eas 2 0 [-100,100] f Col 4 0 [-100,100] f Hyp 30 0 [-100,100] f Sch 30 0 [-500,500] TABLE III NITIALIZATION R ANGE AND G OAL OF F UNCTIONS Function Initialization range Goal of f f Sph [50,100] 10-3 f Ack [50,100] 10-3f Gri [300,600] 10-2f Ros [50,100] 10-3 f Ras [50,100] 10-3 f Boh [50,100] 10-3f Eas [50,100] 10-2f Col [50,100] 10-3f Hyp [50,100] 10-3f Sch [250,500] 10-3TABLE IIIT YPE S IZE FOR P APERS c 1c 2E x E n H e 1.6 1.6 1.0 0.02 0.003 For the sPSO algorithm, the parameter 1c and 2c is set as 1c =2c =1.8. The inertia weight is scaled linearly from 1.0 to0.4 over a maximum of 2000 iterations of the algorithm. A population of particles is uniformly distributed in theinitialization range, and velocities uniformly distributed in theinitialization range are assigned to each particle. The PSOstructure implemented is also a fully connected structure. The experimental results are reported in Table IV and V. To evaluate the performance of the proposed mPSOalgorithm, the average gbest and the standard deviations of thefunction values found in 50 times of running for the mPSO algorithm and the sPSO algorithm on each test function are listed in Table IV.As shown in table IV, it is clear that the mPSO algorithm outperforms the sPSO algorithm on all the benchmarkproblems on which we have conducted experiments so far. The mPSO algorithm achieves the smaller fitness value and standard deviation than the sPSO algorithm. The standarddeviation indicates the robustness of the mPSO algorithm. Table V gives the average, minimum and the maximumiteration number of the mPSO algorithm and the sPSO algorithm needed to achieve the goal in 50 times of running. From simulation, we can see that faster convergence isachieved and an improvement in the best solution is found bythe mPSO algorithm. It can be conducted that the introduction of the normal cloud model not only accelerates convergence but also improves the solution quality.TABLE IVT HE C OMPARISON R ESULTS OF A LGORITHM A FTER 2000I TERATIONSFunction Algorithm Average Std.f Sph mPSO 4.6382E-018 3.2467E-018 sPSO 1.5952E-007 6.2310E-007f Ack mPSO 5.5796(-0 5 2.9805(-0 5sPSO 19.5760 3.6978f Gri mPSO 3.7748E-016 2.6423E-016sPSO 0.0155 0.0185f Ros mPSO 0 0 sPSO 597.7322 1.3618e+003f Ras mPSO 3.2373E-011 3.0176E-011 sPSO 88.2172 28.7097f Boh mPSO 0 0 sPSO 0 0f Eas mPSO 0.0200 0.1400 sPSO 0.5600 0.4964f Col mPSO 0 0 sPSO 7.3418E-004 7.7795E-004f Hyp mPSO 5.9360E -020 6.2510E -020sPSO 4.3589E-007 2.7298E-006f Sch mPSO 3.8183E -004 2.0143E -004sPSO -6.0905E+007 4.2633E+008 TABLE VT HE C OMPARISON R ESULTS OF N UMBER OF A LGORITHM I TERATIONS TOA CHIEVE THE G OALFunction Algorithm Average Minimum Maximumf Sph mPSO 354.5400 139 439 sPSO 1.0782E+003 1031 1148f Ack mPSO 644.2000 525 759 sPSO - - -f Gri mPSO 600.7200 176 730 sPSO 1.2970e+003 1252 1415f Ros mPSO 638.1200 152 889 sPSO - - -f Ras mPSO 644.1800 398 775 sPSO - - -f Boh mPSO 453.1200 368 515 sPSO 556.8800 447 623f Eas mPSO 50.0600 19 847 sPSO - - -f Col mPSO 363.6600 91 612 sPSO 1.3690E+003 857 1784f Hyp mPSO 510.3000 116 706 sPSO 1.4511e+003 1396 1533f Sch mPSO 385.7010 213 635 sPSO - - - V.C ONCLUSIONIn this paper, on the basis of the standard particle swarm optimization algorithm together with the cloud mod el, we present a new methodology with promising new features. The initialization of the population and velocity upd ate rule of particle swarm optimization algorithm are mod ified. The mPSO possesses fast searching speed, efficiency and well behavior of global searching in tackling complex optimization problems. It is very simple that the mPSO is carried out. Experimental results ind icate that the mPSO improves the search performance on the benchmark functions significantly.R EFERENCES[1]J. Kennedy, R.C. Eberhart, “Particle swarm optimization,” Proc. IEEEInt’l. Conf. on Neural Networks, Perth, Australia: IEEE Service Center, Piscataway, NJ, pp. 1942Ω1948, Nov. 1995.[2]R.C. Eberhart, J. Kennedy, “A new optimizer using particle swarmtheory,” proc. Sixth Int’l Symposium on Micro Machine and Human Science, Nagoya, Japan, IEEE Service Center, Piscataway, NJ, pp. 39-43, 1995.[3]Y. Shi, R.C. Eberhart, “A modified particle swarm optimizer,” Proc. IEEEInt’l Conf. on Evolutionary Computation, Anchorage, Alaska, pp. 69–73, May 1998.[4]M. Clerc, “The swarm and the queen: towards the deterministic andadaptive particle swarm optimization,” proc. Congr. on Evolutionary Computation, Washington DC, USA, IEEE Service Center, Piscataway, NJ, pp. 1951–1957, 1999.[5]R.C. Eberhart, Y.C. Shi, “Comparing inertia weights and constrictionfactors in particle swarm optimization,” proc. Congress on Evolutionary Computation, San Diego, USA, IEEE Service Center, Piscataway, NJ, pp.84–89, 2000.[6]M. Senthil Arumugam, M.V.C. Rao, “On the improved performances ofthe particle swarm optimization algorithms with adaptive parameters, cross-over operators and root mean square (RMS) variants for computing optimal control of a class of hybrid systems,” Applied Soft Computing, vol. 8, no. 1, pp. 324-336, Jan. 2008.[7]Y. Shi, R.C. Eberhart, “Empirical study of particle swarm optimization,”proc. IEEE Int. Congr. Evolutionary Computation, vol. 3, pp. 101–106, 1999.[8]Y.H. Shi, R.C. Eberhart, “Fuzzy adaptive particle swarm optimization,”proc. Congr. on Evolutionary Computation, Seoul, Korea, pp. 101-106, 2001.[9]D.Y. Li, “Uncertainty reasoning based on cloud models in controllers,”Computer science and Mathematics with Application, pp. 399-421, 1996. [10]D.Y. Li, H.J. Meng, X.M. Shi, “Membership clouds and membershipcloud generators,” Computer R&D, vol. 32, no. 6, pp. 15-20, 1995.[11]L.B. Zhang, F.C. Sun, Z.Q. Sun, “Cloud model-based controller designfor flexible-link manipulators,” proc. IEEE Conf. on Robotics, Automation and mechatronics, pp. 1-5, Dec. 2006.[12]C.H. Xie, Y. Li, J. Shen, J.J. Cai, J.L. L, “A constructing algorithm ofconcept lattice with attribute generalation based on cloud models,” proc.IEEE 5th Int’l Conf. on Computer and Information Technology, IEEE Service Center, Piscataway, NJ, pp. 110–114, Sept. 2005.[13]R. Brits, A. P. Engelbrecht, F. van den Bergh, “Locating multiple optimausing particle swarm optimization,” AppliedMathematics andComputation, no. 189, pp. 1859-1883, 2007.[14]F. van den Bergh, A.P. Engelbrecht, “A study of particle swarmoptimization particle trajectories,” Information Sciences, no. 176, pp. 937-971, 2006.。