This is an implementation of the Ant Colony Optimization to solve the
Traveling Salesman Problem. In this project, the
berlin52 dataset that maps
52 different points in Berlin, Germany was used.
Figure 1: Graph of the Berlin52 Dataset
Ant Colony Optimization
The Ant Colony Optimization algorithm is inspired by the foraging behaviour of ants (Dorigo, 1992) . The behavior of the ants are controlled by two main parameters: , or the pheromone’s attractiveness to the ant, and , or the exploration capability of the ant. If is very large, the pheromones left by previous ants in a certain path will be deemed very attractive, making most of the ants divert its way towards only one route (exploitation), if is large, ants are more independent in finding the best path (exploration). This ACO implementation used the Ant-System (AS) variant where the movement from node to node is defined by:
As mentioned, the and parameters control the exploitation and exploration behaviour of the ants by setting the attractiveness of pheromone deposits or the “shortness” of the path (Engelbrecht, 2007). The graphs below (in clockwise order, starting from the upper left) describe the (i) city locations, the (ii) solution found by the algorithm, the (iii) (mean) behaviour of the ants, and the (iv) minimum tour distance for each iteration.
Parameters: = 15, = 20, = 0.15
Figure 2: ACO Simulation when the exploration parameter is higher
Parameters: = 20, = 15, = 0.15
Figure 3: ACO Simulation when the exploitation parameter is higher
rho parameter controls the evaporation of pheromone for each time step
. In this case, setting a small
rho leads to a slow evaporation of the
pheromones, which affects the ants’ exploitation ability as shown below. On
the other hand, setting a very high evaporation coefficient makes the
pheromones for each time step evaporate quickly. This means that ants are
constantly doing random searches for each iteration.
Increased pheromone evaporation rate
Parameters: = = 15, = 0.8
Figure 4: ACO Simulation when pheromone evaporation is high
Decreased pheromone evaporation rate
Parameters: = = 15, = 0.01
Figure 4: ACO Simulation when pheromone evaporation is low
The best solution for ACO was 7548.9927 (the optimal solution achieved by current research so far is 7542.00) . It was obtained with the following parameters:
Table 1: ACO Parameters that was used in the implementation
Figure 5: ACO Best Solution
In this ACO implementation, arriving at the best solution requires balancing the exploitation-exploration tradeoff. Setting the evaporation coefficient low makes the pheromones stay longer. However, this was balanced by setting the path bias of the colony very high, so that they get to explore more options near the route with the highest pheromone concentration (instead of causally settling in it). In contrast with the GA implementation, ACO is much easier to control. There are few parameters needed and the exploration capability doesn’t necessarily go out of control. It also helps that the ants are randomly placed in different areas of the map and allowed to make a “guided” initial tour. This makes the initial values much lower as compared in the case of GA where initial costs are very high if a greedy search is not first implemented to construct the initial tour.
- Engelbrecht, Andres (2007). Computational Intelligence: An Introduction, John Wiley & Sons.
- Dorigo, Marco (1992). Optimization, Learning, and Natural Algorithms, PhD Thesis, Politecnico di Milano.
You can access the gist here.