## 5 Ant Colony Optimization  
Ant colony optimization (ACO) is a simple mathematical method that draws inspiration from the foraging behavior of ants. The ACO algorithm allows the ants to explore various routes to discover the optimal or near-optimal path. Within an ant colony, individual ants venture through different paths in search of food to sustain the colony. As they travel through these paths, they leave an odorous trail of pheromones, which allows them to return to the colony. When an ant finds a shorter and more efficient route, it goes back and forth through this route more times, leaving a stronger pheromone path. Eventually, more ants are attracted to this reinforced pheromone path, and the other pheromone paths eventually evaporate since the ants are now traveling along the shorter and more efficient path. The goal of the ACO is to converge the optimal path through the accumulation and update of pheromones and achieve the optimal path through the appropriate amount of iterations. Figure 2 represents a simple demonstration of the ACO. As the ant follows the shorter path, it traverses the route more frequently, resulting in a stronger pheromone attraction, depicted by the thicker path. Consequently, more ants are inclined to follow this path, enticed by the stronger pheromone scent. This cooperative behavior by the ants guides the algorithm into finding a near-optimal solution through a suitable number of iterations. Figure 1: Example of a solution to the TSP problem, showing the shortest possible route that can connect every dot and return to the origin dot. The ACO can be simplified into four steps:  
1. First, a population of virtual ants is created, where each ant and its path represent a possible solution to the problem. Each ant starts at a random point on the field and iteratively constructs a path based on certain probabilistic rules. These probabilistic rules include the intensity of the pheromone scents and heuristic information, like proximity, which is the inverse of the distance between the nodes. An example of how an ant uses the probability rules is shown in Figure 3 from [5]. As shown in the figure, the ant chooses the next node to move based on the functions of the pheromone count \(\tau_{i,j}\) and the heuristic values \(\eta_{i,j}\). 2. At each step, an ant selects the next node based on the combination of the pheromone trail intensity and the heuristic information, like the distance or cost associated with moving to that node. This equation can be represented by the following: \[P_{i,j}(t)=\frac{\tau_{i,j}^{\alpha}*\eta_{i,j}^{\beta}}{\sum_{m \in all\in\in\mathcal{M}}\tau_{i,m}^{\alpha}*\eta_{i,m}^{\beta}}\] (2) where \(P_{i,j}\) represents the probability of moving from node \(i\) to node \(j\), \(\tau_{i,j}*\eta_{i,j}\) represents the desire to move from node \(i\) to node \(j\), \(\tau_{i,j}\) represents the number of pheromones between nodes \(i\) and \(j\), \(\eta_{i,j}\) represents the proximity between nodes \(i\) and \(j\), and \(\sum_{m\in all\in\mathcal{M}}\tau_{i,m}*\eta_{i,m}\) represents the sum of the desires of an ant to move from node \(i\) to all vertices available for the ant. Altering \(\alpha\) and \(\beta\) affects the probability of choice. It represents the power to which either proximity or pheromone is raised. For instance, a higher value of \(\beta\) means that the algorithm places more importance on the heuristic information, and a higher value for \(\alpha\) means that there is more importance on the pheromone information. 3. In each iteration, a number of ants are going to use the probability rules to construct their initial paths. Then, the pheromones are going to be updated after each iteration. The pheromone update aims to reinforce the paths taken by the ants that lead to better solutions while evaporating the weaker pheromone trails to encourage exploration. 4. This process is repeated until a termination criterion is met.