Enhanced Particle Swarm Optimization (EPSO)

Introduction

xlOptimizer implements an enhanced version of Particle Swarm Optimization (PSO), a a well-known swarm intelligence algorithm suitable for global optimization. The method, introduced by Kennedy and Eberhart [1], mimics the social behavior of flocks of birds and swarms of insects. 

How does it work?

PSO has many similarities with other algorithms such as Genetic Algorithms (GA). At first, the population (or "swarm") is initialized with random solutions. However, unlike GA, PSO has no selection or evolution operators such as crossover and mutation; in PSO the members of the swarm (or "particles") "fly" through the problem space following simple mechanics. Thus, PSO searches for optima by updating each particle according to notions such as position, velocity, inertia etc. This movement of particles is not entirely random; each particle is attracted towards both its own personal best position and the swarm's best position.

Mathematical formulation

We assume that the population consists of p individuals. Within the Design Space (DS) each individual is characterized by its position and velocity, determined at time instant k by the corresponding vectors xk and vk. Initially, the particles are distributed randomly in the box-constrained search space, as follows:

pso equation #1

where, xLB and xUB are vectors defining the lower and upper values of the variables, respectively. The position vector of individual d at the next time instant k+1 is given as:

pso equation #2 

where the time step Δt between the distinct time instants is assumed to be equal to unity. The velocity vector vdk+1 is given as:

pso equation #3

where, wk is the inertia factor at time instant k; c1, c2 are the cognitive and social parameters of the algorithm, respectively; pdis the best ever position vector of individual d at time instant kpgk is the best ever position vector amongst all individuals at time instant k; r1, r2 are vectors of random variables with uniform distribution in the interval [0,1] and the (o) operator indicates element-by-element multiplication. The simple PSO algorithm imposes no limitations with regard to the maximum velocity of the particles.

The enhanced PSO variant is based on [3], as follows:

  • The initial maximum velocity of the individuals is evaluated so that in one time step an individual may travel up to a certain fraction of the search space:

pso equation #4

  • If the best solution found in the whole swarm is not improved over a period of h consecutive steps, then it is assumed that the velocities are large and the algorithm cannot locate better solutions due to overshooting. For this reason, both the inertia factor and the maximum velocity are decreased as follows: 

pso equation #5

where, α, β < 1.

  • The craziness operator assigns a random velocity vector to an individual resulting in its moving away from the swarm and thus exploring other regions of the search space. The operator is activated with a probability Pcr as follows:

pso equation #6

 where r is a random variable with uniform distribution in the interval [0,1].

  •  The algorithm employs both an elite particle and an elite velocity. The individual with the worst performance is moved to the best ever position of the swarm:

pso equation #7

In addition, if the velocity vector vdresulted in an improvement of the global best position, then:

pso equation #8

where, c3 is a parameter of the algorithm and r3 is a vector of random variables with uniform distribution in the interval [0,1]. 

Usual parameter values for small to medium-sized problems are the following: (a) population size p=20-30, (b) cognitive parameter c1=0.5, (c) social parameter c2=1.6, (d) constant inertia factor w=0.8, (d) maximum velocity coefficient γ=0.4, (e) initial inertia factor w0=1.40, (f) maximum steps without improvement h=3, (g) fraction for the decrease of the inertia factor α=0.99, (h) fraction for the decrease of maximum velocity β=0,95, (i) craziness factor Pcr=0.22, (j) elite velocity factor c3=1.30. [2], [3]. 

Options in xlOptimizer

The following options are available in xlOptimizer:

Step 1

enhanced particle swarm optimization xloptimizer options step 1

Enter a short title for the scenario. The log files will be saved to a subfolder with this name.

Step 2

enhanced particle swarm optimization xloptimizer options step 2

Select the number of particles. The optimum value depends on the complexity of the problem. For PSO, values are usually selected in the range 10-30.

The variables that may be used in the expression are:

  • VARIABLES: the number of variables.

Step 3

enhanced particle swarm optimization xloptimizer options step 3

Select the parameters of the PSO algorithm:

  • Cognitive parameter C1: controls the weight of the pull of each particle to the best ever position of the same particle. Usual value for EPSO is 0.5.
  • Social parameter C2: controls the weight of the pull of each particle to the best ever position of the whole swarm. Usual value for simple EPSO is 1.6.
  • Inertia parameter W0: controls the inertia of the particle. Usual values for EPSO are in the range 0.8-1.4.
  • Parameter gamma: controls the initial maximum velocities of the particles, as the fraction of the design space (per variable) that can be travelled in one time step. Usual value is 0.4.
  • Parameter h (consecutive steps without improvement of the global optimum): If more than h steps are observed without improvement, then it is assumed that the velocities are large and w=alpha*w, vmax=beta*vmax. Use zero to disable. Usual value is 3.
  • Parameter alpha : If the h-parameter is activated, the inertia parameter is decreased according to w=alpha*w. Use 1 to disable. Usual value is 0.99.
  • Parameter beta: If the h-parameter is activated, the maximum velocities are decreased according to vmax=beta*vmax. Use 1 to disable. Usual value is 0.95.
  • Parameter Pcr: 'Craziness' probability. When activated, the velocity of a particle is initialized randomly. It is a safeguard against premature convergence. Use 0 to disable. Usual value is 0.22.
  • Elite velocity: if the velocity of a particle improved the best ever position of the swarm, then it is used again, multiplied by a random number in [0.1] and also multiplied by parameter C3.
  • Elite velocity coefficient C3: used when a particle improved the best ever position of the swarm. Usual value is 1.3.
  • Elite particle: the worst particle in each step is transferred to the best ever position of the swarm.
  • Clamp variables: the variables are clamped within their boundaries prior to evaluation.

Step 4

enhanced particle swarm optimization xloptimizer options step 4

Choose whether to use the Registrar operator with the algorithm. This is recommended only for expensive objective functions.

Step 5

enhanced particle swarm optimization xloptimizer options step 5

Select the termination criteria. At least one termination criterion must be active. Usually one selects a maximum number of function evaluations and/or a time limit.

Step 6

enhanced particle swarm optimization xloptimizer options step 6

Select the action when the analysis is finished:

  • Nothing: The last individual analysed remains.
  • Restore previous solution: The solution that was visible before the analysis is restored.
  • Use best: The best solution that was discovered during the analysis is applied.
  • Use best if better than the previous version (recommended): The best solution that was discovered during the analysis is applied only if it is better than the previous solution. In the opposite case the previous solution is restored.

Step 7

enhanced particle swarm optimization xloptimizer options step 7

Select whether you want to use random or specific seeds for the random number generator. The seeds must be large negative numbers e.g. -100000. Usually a number of analyses with random seeds is performed. The filename of the log is the seed used in the specific analysis.

Step 8

enhanced particle swarm optimization xloptimizer options step 8

Select the output path. A subfolder with the name of the scenario will be used. Usually a relative path is used i.e. the absolute path check box is not checked. This results in the output logs being saved in the same path as the project file.

References

[1] Kennedy J, Eberhart RC. Particle swarm optimization. In: Proceedings, of IEEE International Conference on Neural Networks IV, Perth Australia, IEEE press Piscataway, NJ,1995; p. 1942–1948.
[2] Charalampakis, A. E., Dimou, C. K., “Identification of Bouc–Wen Hysteretic Systems using Particle Swarm Optimization”, Computers and Structures, 88 (2010): 1197–1205, doi:10.1016/j.compstruc.2010.06.009.
[3] Fourie PC, Groenwold AA. The particle swarm optimization algorithm in size and shape optimization. Struct Multidisc Optim 2002;23(4):259–267.