## 2 Swarm Algorithms
### Ant-Based Algorithms  
Ant-based algorithms are inspired by the behaviour of natural ants, which communicate among themselves by the pheromone that they deposit on the ground when they walk. If there is only one ant, it moves randomly; but if there are several ants, the movement of each ant is conditioned by the movement of the others. Ants prefer moving by paths with more pheromone and this movement increases the amount of pheromone of these paths, making them more desirable for other ants. The pheromone evaporates over time, and this makes the paths selected by a small number of ants less desirable. The first algorithm proposed to mimic the behaviour of natural ants was called Ant System algorithm and it was applied to solve the Travelling Salesman Problem (TSP) [23; 24]. Given a set of nodes interconnected by weighted connections, the objective of the TSP is to find a closed tour of minimum cost which includes each node once and only once [25; 26]. The problem is represented by a graph with two values associated with each connection \((i,j)\): the cost, which represents the distance between the nodes \(i\) and \(j\), and the pheromone \(\tau_{ij}(t)\in(0,1]\). The Ant System method considers a set of \(n\) ants and applies the operations shown in Algorithm 1. The first operation defines the initial pheromone (random values are usually considered) and then an iterative process is applied. At each iteration, each ant defines a solution to the problem (a tour) and the cost of this solution is computed. After this, the pheromone is updated, to make the connections of the tours defined at the present iteration more desirable for the next iteration. The pheromone matrix is the means used by each ant to share information with the other ants. \begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Description** \\ \hline \(f(x)\) & Objective function of a problem, which is computed for a feasible solution to the problem \(x\) \\ \hline \(r\) & Dimension of the solution space \\ \hline \(x_{i}=(x_{i1},...x_{ir})\) & A solution to the problem (a vector with \(r\) components) \\ \hline \(n\) & Number of individuals or elements used by the algorithm to find a solution \\  & (ants, particles, fish, food sources or fireflies) \\ \hline \(t\) & The current iteration of the algorithm \\ \hline \(x_{i}(t)\) & The solution represented by the individual \(i\) at iteration \(t\), with \(i=\{1,...,n\}\) \\ \hline \(x^{\prime}\) & A tentative solution evaluated by the algorithm \\ \hline \(rnd_{(min,max)}\) & A real value randomly selected from the interval \((min,max)\) (that is, excluding extreme values), \\ \(rnd_{(min,max)}\) & or \([min,max]\) (that is, including both extreme values). \\ \(rnd\) & When the limits are not specified, this means that they must be set for each specific problem \\ \hline \(||A-B||\) & Euclidean distance between vectors \(A\) and \(B\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notation used to describe the algorithms. To define its tour, the ant \(k\) starts at a randomly selected node and progressively selects the other nodes. When it is at node \(i\), Equation (1) determines the probability of choosing \(j\) as the next node of its path. \(\eta_{ij}(t)\) is the visibility of the connection \((i,j)\); for a TSP, it is the inverse of the cost of \((i,j)\). \(N_{i}^{k}\) is the set of nodes connected to \(i\) not visited by the ant (Figure 1). The parameters \(\alpha\) and \(\beta\) determine the relative influence of the pheromone and the visibility, respectively. Equation (1) indicates that ants prefer connections with small length and high amount of pheromone. \[p_{ij}^{k}(t)=\frac{\tau_{ij}(t)^{\alpha}\eta_{ij}(t)^{\beta}}{\sum_{l\in N_{ i}^{k}}\tau_{il}(t)^{\alpha}\eta_{il}(t)^{\beta}} \tag{1}\]  
The pheromone is updated by applying Equation (2) to each connection \((i,j)\) of the graph, where \(\rho\in(0,1)\) is the evaporation rate of the pheromone and \(\Delta\tau_{ij}^{k}\) is the amount of pheromone deposited by ant \(k\) on the connection \((i,j)\).