## 2 Swarm Algorithms
### Particle Swarm Optimisation  
The Particle Swarm Optimisation (PSO) algorithm was proposed by [PERSON] and [PERSON] [41]. It is inspired by the movement of a flock of birds or insects and it can be applied to solve optimisation problems [42; 43]. With this purpose, the algorithm considers a set of \(n\) particles. Each particle \(i\) has a position \(x_{i}(t)\) and a velocity \(v_{i}(t)\) that are updated as \(t\) increases. Moreover, the particle'remembers' the best solution it found until the current iteration, which is denoted \(b_{i}(t)\). Each particle moves on the search space guided by its previous experience and the experience of other particles, which is  
Figure 1: The ant \(k\) is at node \(i\) and must select the next node of its path from \(N_{i}^{k}\)=\([r,s,t,u]\).  
represented by the velocity vector of the particle. The movement of all the particles tries to find a good solution to the problem. The best solution found by the swarm until iteration \(t\) is denoted \(g(t)\) and its value at the end of the algorithm defines the solution to the problem.  
The new position of particle \(i\), \(x_{i}(t+1)\), is computed by Equation (3) as a function of the previous position, \(x_{i}(t)\), and the velocity of the particle (Figure 2).  
\[x_{i}(t+1)=x_{i}(t)+v_{i}(t+1) \tag{3}\]  
To compute the new velocity of this particle (by Equation (4)), three elements are considered: The previous velocity, \(v_{i}(t)\), the best position of this particle, \(b_{i}(t)\), and the best solution found by the swarm, \(g(t)\). Equation (4) includes three parameters that weight these three elements: \(\omega\) (the inertia coefficient), \(\phi_{1}\) and \(\phi_{2}\). The velocity of each particle is limited to an interval \([v_{min},v_{max}]\).  
\[v_{i}(t+1)=\omega v_{i}(t)+\phi_{1}rnd_{(0,1)}(b_{i}(t)-x_{i}(t))+\phi_{2}rnd_ {(0,1)}(g(t)-x_{i}(t)) \tag{4}\]  
The basic steps of PSO algorithm are shown in Algorithm 2. To start the operations, the particles are placed at random positions on the search space, and each particle is assigned a random velocity in \([v_{min},v_{max}]\). Moreover, the best position of each particle equals its initial position. The global best particle is the one whose position gives the best value for the objective function of the problem. Next, an iterative process is applied to find a good solution to the problem. Each iteration updates the position and the velocity of the particles, by Equations (3) and (4). Then, the fitness of each particle is computed. This value is used to determine if the new position of the particle is better than the one considered the best so far, in which case this new position replaces the previous one. If some particle has better fitness than that considered as the global best, it becomes the new global best.  
```
Initialise the swarm of particles ; repeat  Update the velocity of each particle;  Update the position of each particle;  Calculate the fitness of each particle;  Update the memory of each particle;  Update the global best solution; untilRequirements are met;
```  
**Algorithm 2**Particle Swarm Optimisation algorithm  
Figure 2: Movement of particle \(i\) in a two-dimensional search space. The particle, which is currently at position \(x_{i}(t)\), will move to a new position, \(x_{i}(t+1)\), taking into account its new velocity, \(v_{i}(t+1)\). That velocity is computed based on the current velocity of the particle, \(v_{i}(t)\), the best position found so far by the particle, \(b_{i}(t)\), and the global best position found so far by the swarm, \(g(t)\).  
This algorithm has been applied to problems such as the task assignment problem [44], the flowshop scheduling problem [45], the capacitated vehicle routing problem [46], and several real-time optimisation problems [47].