8.4: Ant Colony Optimization

Ants as insects are social by nature and live in colonies. Their objective is to survive collectively as a colony, instead of survival as an individual ant. Ants communicate with each other using sound, touch, and pheromones.  Ant colony optimization (ACO) focuses on pheromones. Ants carry a portion of the food. While returning, they leave traces of pheromone. Other ants try to find an optimal path by following the pheromone trail left by other ants on the ground. ACO tries to mimic the behavior of ants to find the shortest path for food as an optimization algorithm. Figure 8.4.1 below illustrates the ACO metaheuristic algorithm.

.

Figure 8.4.1: ACO metaheuristic.

In the first step, the pheromone trail and parameters are initialized. Each ant then constructs a complete solution for the problem using a pheromone trail and heuristic information.

Starting nodes, and a path between the nest and food, which passes through nodes are selected at random. Paths with a higher number of pheromone trails are given a higher probability. Ants travel between food and nest by passing through multiple nodes. This process is called a 'tour'. Each completed tour is a solution.

After pheromone trails are generated, their update is initiated. Pheromone can evaporate. As a result of evaporation, the level of pheromone in the pheromone trail can increase or decrease. Pheromone update considers this for improving the solution search. Pheromone update happens in two steps. In the first step, a fraction of the pheromone evaporates. In the second step, each ant updates the pheromone trail by depositing the amount of pheromone, proportional to how good or bad the trail is. Better solutions receive more pheromone trails, whereas worse solutions receive fewer pheromone trails.

In the next step, a new cycle is performed and this process is repeated until most of the ants follow the same tour on most of the cycles. At each iteration, the pheromone tends to concentrate within the reduced search space. The global optima are searched within the reduced search space in subsequent iterations, using the best values obtained from the new ant colony from the previous iteration.

Figure 8.4.2 below illustrates the pseudocode of ACO, and figure 8.4.3 explains all the variables used in ACO.

Figure 8.4.2: ACO pseudocode

 

Figure 8.4.3: Variables used in ACO pseudocode

After understanding all the details of the ACO algorithm, we should remember that it is useful for a smaller number of features. For a large number of features, it may or may not give the best solution.

We can use the function AntColonyOptimization in the feature selection object fsObj for performing ant colony optimization. Below is how the syntax will look like.

best_columns = fsObj.AntColonyOptimization(iterations = 25,
                                           N_ants = 75,
                                           run_time=1200,
                                           evaporation_rate=0.8,
                                           Q=0.2)

In this syntax example, we have executed ant colony optimization for 25 iterations. Within each iteration, we have 75 ants. Execution time limit is set for 1200 minutes. We have set evaporation rate for pheromones as 0.8 and Q as 0.2.