Ant Colony Optimization

ACO is a relatively novel meta-heuristic technique and has been successfully used in many applications especially problems in combinatorial optimization. ACO algorithm models the behavior of real ant colonies in establishing the shortest path between food sources and nests. Ants can communicate with one another through chemicals called pheromones in their immediate environment. The ants release pheromone on the ground while walking from their nest to food and then go back to the nest. The ants move according to the amount of pheromones, the richer the pheromone trail on a path is, the more likely it would be followed by other ants. So a shorter path has a higher amount of pheromone in probability, ants will tend to choose a shorter path. Through this mechanism, ants will eventually find the shortest path.

Artificial ants imitate the behavior of real ants, but can solve much more complicated problem than real ants can. ACO has been widely applied to solving various combinatorial optimization problems such as Traveling Salesman Problem (TSP), Job-shop Scheduling Problem (JSP), Vehicle Routing Problem (VRP), Quadratic Assignment Problem (QAP), etc. Although ACO has a powerful capacity to find out solutions to combinational optimization problems, it has the problems of stagnation and premature convergence and the convergence speed of ACO is very slow. Those problems will be more obvious when the problem size increases. Therefore, several extensions and improvements versions of the original ACO algorithm were introduced over the years.

Various adaptations: dynamic control of solution construction, mergence of local search, a strategy is to partition artificial ants into two groups: scout ants and common ants and new pheromone updating strategies, using candidate lists strategies are studied to improve the quality of the final solution and lead to speedup of the algorithm. All these studies have contributed to the improvement of the ACO to some extents, but they have little obvious effect on increasing the convergence speed and obtaining the global optimal solution.

In the proposed system, the main modifications introduced by ACO are the following. First, to avoid search stagnation and ACO is more effective if ants are initially placed on different cities. Second, information entropy is introduced which is adjust the algorithm’s parameters. Additionally, the best performing ACO algorithms for the TSP improve the solutions generated by the ants using local search algorithms.