Particle Swarms Reformulated towards a Unified and Flexible Framework

The Particle Swarm Optimisation (PSO) algorithm has undergone countless modifications and adaptations since its original formulation in 1995. Some of these have become mainstream whereas many others have not been adopted and faded away. Thus, a myriad of alternative formulations have been proposed to the extent that the question arises as to what the basic features of an algorithm must be to belong in the PSO family. The aim of this paper is to establish what defines a PSO algorithm and to attempt to formulate it in such a way that it encompasses many existing variants. Therefore, different versions of the method may be posed as settings within the proposed unified framework. In addition, the proposed formulation generalises, decouples and incorporates features to the method providing more flexibility to the behaviour of each particle. The closed forms of the trajectory difference equation are obtained, different types of behaviour are identified, stochasticity is decoupled, and traditionally global features such as sociometries and constraint-handling are re-defined as particle's attributes.


Introduction
Inspired by earlier bird flock simulations, the Particle Swarm Optimisation (PSO) method was proposed in 1995 [34]. It is a global optimiser in the sense that it is able to escape poor suboptimal attractors by means of a swarm of particles performing a parallel collaborative search. In fact, it is a search rather than optimisation method, as no optimality criteria is checked or guaranteed.
The overall system behaviour emerges from a combination of each particle's individual and social behaviours [50]. The former is manifested by the trajectory of a particle pulled by its attractors, governed by a second order difference equation with three control coefficients. In the classical (and in most) versions of the algorithm, there is one individual attractor given by the particle's best experience, and one social attractor given by the best experience in its neighbourhood. The social behaviour is governed by the way the individually acquired information is shared among particles and therefore propagated throughout the swarm, which is controlled by the neighbourhood topology. The individual and social behaviours interact through the update of the social attractor. Thus, the two main features of the algorithm are the trajectory difference equation (and the setting of its coefficients) and the neighbourhood topology (a.k.a. sociometry).
In the early days, numerous empirical studies were carried out to investigate the influence of the coefficients in the trajectory difference equation on the overall performance of the method, and to provide guidelines for their settings [48,47,17,36]. Early theoretical work [41,42,2,13,52] provided insight into the inner workings of the method and some interesting findings of practical use such as Clerc et al.'s constriction factor(s) [13] to ensure convergence. These pioneering studies were a source of inspiration and set the foundations for an explosion of theoretical work. [54,35,10,31,29,46,37,44,3,11,45,18,51,12,24,26,7,19,8,21,9,6]). For recent reviews of the PSO method, refer to [5,20].

Trajectory Difference Equation
In classical PSO (CPSO), three forces govern a particle's trajectory: the inertia from its previous displacement, the attraction to its own best experience, and the attraction to the best experience in its neighbourhood. The importance awarded to each of them is controlled by three coefficients: the inertia (ω), the individuality (iw), and the sociality (sw) weights. Stochasticity is introduced to enhance exploration via random weights applied to iw and sw. The behaviour of a particle, and by extension of the PSO algorithm as a whole, is very sensitive to the settings of these control coefficients. The system of two 1 st -order difference equations for position and velocity updates in the CPSO algorithm proposed in [49] is rearranged in (1) as a single 2 nd -order Trajectory Difference Equation: ij is the coordinate j of the position of particle i at time-step t; xb (t) ij is the coordinate j of the best experience of particle i by time-step t; k is the index identifying the particle with the best experience in the neighbourhood of particle i at time-step t; ω, iw and sw are the inertia, individuality, and sociality weights, respectively (which may depend on i, j, t); and U (0,1) is a random number from a uniform distribution within [0,1] resampled anew every time it is referenced.
In the original formulation [34], ω = 1 and iw = sw = 2. This leads to an unstable system, as particles tend to diverge. The first strategy to prevent this was to bound the size of each component of a particle's displacement, which helps prevent the so-called explosion but does not ensure convergence or a fine-grain search. Instead, the coefficients in (1) can be set to ensure that.
Alternatively, Clerc et al. [13] analysed the trajectory of a deterministic particle in the original PSO (ω = 1) and developed so-called constriction factors (χ) that ensure convergence. Some authors include both ω and χ in their formulations [27,53].

Neighbourhood Topology
The original PSO algorithm [34] presented a global topology in which every particle has access to the memory of every other particle in the swarm. Local topologies were proposed soon thereafter [16]. Since then, a plethora of sociometries have been proposed [40,38,39,4]. Three classical ones are shown in Fig. 1.  The global topology tends to lead to a rapid loss of diversity, which may lead to premature convergence to a poor suboptimal solution. Whilst this can be controlled to some extent by the settings of the coefficients in the trajectory equation, numerous neighbourhood topologies have been proposed reducing connectivity to delay the propagation of information throughout the swarm.

Other Features
Other important features of the PSO algorithm are the initialisation of the particles [11,22,33,32], the synchrony of the memory updates [1], the size of the swarm [15,43], and the handling of constraints [24,30].
The PSO algorithm is an unconstrained search method, therefore requiring an external constraint-handling technique (CHT) to be integrated to handle these types of problems. A straightforward CHT is the Preserving Feasibility Method [23], in which infeasible experiences are banned from memory. Another one is the Penalty Method, in which infeasible solutions are penalised by augmenting the objective function and treating the problem as unconstrained. Some authors propose adaptive penalties by using adaptive coefficients in the penalty function [14] or by adapting the tolerance relaxation [28]. Innocente et al. [25] propose using a Preserving Feasibility with Priority Rules Method, in which the objective function values and the constraint violations are treated separately.
Since its original formulation in 1995, countless variants have been proposed. Some of them have become mainstream whereas many others have faded away. Thus, a myriad of alternative formulations have been proposed raising the question of what the basic features of an algorithm must be to belong in the PSO family. The aim of this paper is to establish what defines a PSO algorithm, and to attempt to formulate it in such a way that it encompasses many existing variants so that different versions may be posed as settings within the proposed unified framework. In addition, the proposed formulation generalises, decouples and incorporates new features providing more flexibility to the behaviour of each particle. The remainder of this paper is organised as follows: the overall proposed Reformulated PSO is introduced in Section 2, with the Global Features, the Individual Behaviour Features and the Social Behaviour Features discussed in more details in Sections 3, 4 and 5, respectively. Conclusions are provided in Section 6.

Reformulated Particle Swarm Optimisation
The proposed Reformulated Particle Swarm Optimisation (RePSO) method is structured in three sets of features: 1) Global Features (GFs), 2) Individual Behaviour Features (IBFs), and 3) Social Behaviour Features (SBFs). Fig. 2 shows a high-level description of RePSO, where IBFs and SBFs are both viewed as individual attributes of a particle (Particle Attributes).

Global Features
Despite being a swarm-intelligent method, some characteristics must still be defined at the swarm level. We define here three main subsets of global features: 1) Global Settings, 2) Initialisation, and 3) Termination Conditions. The first one consists of scalar settings like maximum search length (t max ) and swarm size (m), whereas the other two involve methods. Whilst the Neighbourhood Topology and the Constraint-Handling Technique are traditionally viewed as global features, it is porposed here that they be defined at the individual level.

Initialisation
It is important to differentiate two aspects of the initialisation in PSO: 1. The sampling method to be used to place m points over the search-space. 2. What variables associated with each particle are to be initialised.
Note that the particle's position update in RePSO -and in (1)-is a 2 nd order difference equation rather than the classical system of two 1 st order difference equations (position and velocity). Therefore, the variables which may be involved in the initialisation are the initial, the previous, and the memorised positions (x (1) , x (0) , xm (1) ) instead of two positions and one velocity (x (1) , xm (1) , v (1) ).
Sampling Method. Originally, initialisation was purely random from uniform distributions: x  Initial Conditions. This aspect of the PSO method seldom receives any attention from researchers or practitioners. Four types are proposed here: (1) This requires the sampling of each particle's position at the initial time-step (x (1) ). Stagnation implies that the previous position x (0) = x (1) , and that the particle has converged to its attractor: xm (1) = x (1) . Thus, movement starts purely due to cooperation (no inertia, no individual attractor).
3. One Position and One Memory: x (1) = x (0) = xm (1) Two positions per particle are sampled and compared, with the better one becoming xm (1) and the other x (1) = x (0) . Movement starts due to both cooperation and acceleration towards its individual attractor (no inertia).

Two Positions and
One Memory x (1) = x (0) = xm (1) = x (1) Three positions per particle are sampled and compared, with the best one becoming xm (1) . Thus, movement starts both due to all three sources: cooperation, inertia, and acceleration towards its individual attractor.
Initialised Variables Relation. For all initial conditions other than stagnation, more than one position is to be sampled per particle. The question is then whether these should be somehow related. Three alternatives are proposed here: 1. Perturbation: x (0) is generated from controlled perturbations on x (1) . If applicable, xm (1) is also generated from perturbations on x (1) .
2. Independent: Each population of positions is sampled independently.
3. Simultaneous: All populations of positions are sampled at once. For instance, if using the Latin Hypercube Sampling, there would be one single sampling with as many points as twice or three times the swarm size, as applicable.

Termination Conditions
The population-based nature of the method enables termination conditions different from the classical ones in numerical optimisation: 1) maximum number of iterations, and 2) convergence. Three types of conditions are identified here: 1) based on search length (or maximum number of iterations), 2) based on clustering measures (diversity loss), and 3) based on measures of convergence.

Individual Behaviour Features
These are the features of the algorithm which control the individual behaviour of a particle. Each particle has its own set of IBFs, which are viewed as particle attributes. The individual behaviour of a particle is materialised by its trajectory as it is pulled by its attractor. This is governed by a second order difference equation and the setting of its coefficients. The IBFs are grouped here in two main families, namely Deterministic Features and Stochastic Features.

Deterministic Features
Instead of viewing PSO as a guided random search method, it is viewed as a randomly-weighted deterministic search method. Thus, its desired deterministic behaviour is defined, adding only as much stochasticity as deemed beneficial. By formulating the position update as in (5), it is clear that any given particle at any given time is pulled by a single attractor which results from a randomly weighted average of the components of the individual and social attractors. Thus, the Trajectory Difference Equation in (1) may be expressed as in (5).
Since we are dealing with a single particle, sub-index i is dropped. For simplicity, let us assume (ω, φ) constant in every dimension and ∀t, dropping sub-index j and super-index (t). If stochasticity is removed, the deterministic coefficients (ω,φ) are referred to as Reference Trajectory Coefficients.
CPSO Recurrence Formulation. The CPSO Recurrence Formulation is as in (6), which is the deterministic version of (5). The generation of the overall attractor p (t) i is now decoupled, comprising a Social Behaviour Feature (SBF).
CPSO Closed-Form Formulation. This is obtained by solving the difference equation in (6). The roots of the characteristic polynomial are as in (7) and (8). The solution is per dimension and per particle (therefore dropping indices i and j), and the attractor p is stationary.
Case 1 (γ 2 > 0). The two roots of the characteristic polynomial are real-valued and different (r 1 = r 2 ). Therefore the closed-form for Case 1 is as in (9).
Case 2 (γ 2 = 0). The two roots of the characteristic polynomial are the same (r 1 = r 2 ), as shown in (10). Therefore the closed-form for Case 2 is as in (11).
Thus, the chosen trajectory equation in RePSO may be given by the Recurrence Formulation in (6) or by the Closed-Form Formulations in (9), (11) and (16). Other recurrence formulations as well as some considerantions to be taken into account for the closed-form formulation are beyond the scope of this paper.
Reference Trajectory Coefficients Settings. An analysis of the trajectory closed-forms shows that the magnitude of the dominant root r = max ( r 1 , r 2 ) controls convergence. Fastest convergence occurs for (φ,ω) = (1, 0), where r = 0 (see Fig. 3 (a)). The resulting convergence conditions are shown in (17), which define the area inside the convergence triangle (r < 1) shown in Fig. 3.
Whilst the magnitude of the dominant root controls the speed of convergence, the sign of the dominant root (if any) controls the Type of Behaviour : 1. Oscillatory: Roots are complex conjugates (no dominant root). 2. Monotonic: Dominant root is real-valued and positive. 3. Zigzagging: Dominant root is real-valued and negative.
These Types of Behaviour are bounded within specific Sectors in the (ω,φ) plane, each associated with one edge of triangular isolines (same r). These three Sectors are shown in Fig. 3 (b), where the white triangle separates the Convergence (inside) and Divergence regions. The settings of (ω,φ) can be chosen so as to achieve the desired behaviour and convergence speed.

Stochastic Features
The random weights in (1) affect the trajectory of a particle towards the overall attractor (p) whilst also affecting the generation of this attractor as a stochastic convex combination of the individual (xb i ) and the social (xb k ) attractors. Different from classical PSO formulations, these two features are decoupled here. The Stochastic Features within the IBFs are concerned only with the former.
Stochastic Scaling. This refers to whether the stochastic variables in (5) are sampled once per particle position update (vector scaling) or resampled anew per dimension as well (component scaling). The latter is sometimes used by mistake.
Stochastic Sampling. This refers to the probability distributions chosen for the control coefficients (ω, φ). In classical formulations, ω =ω (deterministic) whereas the probability distribution of φ is not directly chosen but resulting from the sum of two stochastic terms sampled from uniform distributions: φ = ι + σ as in (3). If they are sampled from the same interval (i.e. iw = sw), the resulting probability distribution of φ is triangular. Otherwise, it is trapezoidal. In the proposed RePSO, the user is allowed to choose any distribution for (ω, φ).
Trajectory Coefficients Sampling Settings. Once the distributions have been chosen, the parameters defining them must be set. For example, (φ min , φ max ) for a uniform distribution, or the standard deviation for a normal distribution.

Social Behaviour Features
These are the features of the algorithm which control the social behaviour of a particle. Despite being SBFs, they are defined as Particle Attributes in RePSO. A particle's social behaviour is governed by its access to other particles' memories (Local Sociometry) and by how it handles this information (social influence).

Local Sociometry
In classical formulations, the sociometry is a global feature. It can be defined as a regular graph, or irregulary by defining one connection at a time. In the latter case, the structure cannot be automatically generated nor is it scalable. In RePSO, automation and scalability are paramount. Therefore, a Local Sociometry is defined for each particle, with the Global Sociometry resulting from their assembly. This has the advantange that sociometry is a particle attribute, facilitating object-oriented implementation. Also that different social behaviours can be exhibited by different particles, and that irregular global sociometries are possible without renouncing automation or scalability. The Local Sociometry in RePSO is generated by defining the Neighbourhood Topology and potentially the Neighbourhood Extent. Examples of the former are the Global, Ring, Forward and Wheel topologies. The Neighbourhood Topology defines a methodology to generate unidirectional connections from the particle informed to its informers. The Neighbourhood Extent defines the neighbourhood size, if applicable (number of neighbours, distance of influence). An example of an unstructured global neighbourhood is shown in Fig. 4, where the Local Sociometry of particle 1 is the Global topology whilst that of particle 2 is the Ring topology. Other aspects may be considered, such as whether a particle's memory is part of its neighbourhood (X in the connectivity matrix in Fig. 4).

Current Information Update
Any particle holds two types of information: 1) current, and 2) memorised. The update of the former takes place by gathering information (e.g. memorised attractors), generating an overall attractor using the information gathered, and then applying the trajectory equation to update the current information. A particle may access the information currently held, the one memorised, or both from its neighbours (Information Gathering). This is an extension to classical formulations, where a particle can only access their memorised information.

Memorised Information Update
This controls the update of a particle's memory when it accesses new information. This is performed directly rather than through a trajectory equation. The question is what Type of Information is accessible to a particle's memory. Another feature affecting this update is the Synchrony, which defines whether a particle's memory is updated immediately after its currently held information is updated (asynchronous) or only after the currently held information of every particle is updated (synchronous). Typically, the update is synchronous.
RePSO also proposes to include the CHTs here. Thus, different particles may have different CHTs, and therefore may value a given location differently.

Conclusions
A general framework has been proposed aiming to encompass many variants of the PSO algorithm under one umbrella so that different versions may be posed as settings within the proposed unified framework. In addition, some extensions to the classical PSO method have been made such as the decoupling of the stochasticity that affects both the acceleration coefficient (φ) and the generation of the overall attractor, an extended treatment of the swarm initialisation, the particle trajectory closed forms, the identification of three types of deterministic behaviour to inform the setting of the control coefficients, and the global sociometry resulting from assembling local sociometries defined as particle attributes. Due to space constraints, most of these features are discussed only superficially.