Pheromone deposition/updating strategy in a network: using ant colony optimization (ACO) approach

Abstract

The study and understanding of the social behavior of insects has contributed to the definition of some algorithms that are capable of solving several types of optimization problems. The most important and challenging problems that the ants encounters when routing through a network arc, is their ability to searching for the path with a shorter length as well as to minimize the total cost incurred in the process of routing  through the network. In this paper, we introduced some features to the existing Ant Colony Optimization (ACO) algorithm to help tackle this problem. First, we defined two kinds of pheromone and then we also defined three kinds of heuristic information to guide the searching direction of ants for this bi-criteria problem. Each of the ants uses the heuristic types and the pheromone types in each iteration based on the probability, controlled by two parameters. These two parameters are adaptively adjusted in the process of the algorithm. Second, we used the information of the partial solutions to modify the bias of ants so that inferior choices will be ignored. Finally, we tested the performance of the experimental results of the algorithm in an application under different Deadline constraints and the performance of the algorithm prove to be more promising, for it outperformed the performance of most of the algorithm we downloaded on line.

Keywords: Ant Colony Optimization algorithm, Pheromone Deposition, Pheromone Updating strategy, Cost Minimization, Network Routing, Optimization problem.