Ant Colony Optimization And Its Application In Communication Network

A general-purpose metaheuristic named Ant Colony Optimization algorithm, which take inspiration from real ant's behavior in finding shortest paths using as information only the trail of a chemical substance (called pheromone) deposited by other ants, boasts a number of attractive features, including adaptation, robustness and distributed, decentralized nature, and have recently been successfully applied to several discrete optimization problems. In all these algorithms a set of artificial ants collectively solve the problem under consideration through a cooperative effort. This effort is mediated by indirect communication of information on the problem structure the ants concurrently collect while building solutions by using a stochastic policy. The details were studied as follows:In the first chapter of this paper, the definition, taxonomy and characteristics of the routing problem are reported. The routing problem is a stochastic distributed multi-objective problem. Information propagation delays, and the difficulty to completely characterize the network dynamics under arbitrary traffic patterns, make the general routing problem intrinsically distributed. Routing decision can only be made on the basis of local and approximate information about the current and the future network states. These features make the problem well suited for Ant Colony Optimization algorithm.The second chapter presents a formal definition of graphs and the theory of ant algorithms, self-organization and the Ant Colony Optimization metaheuristic. The pheromone-based parameterized probabilistic model for the ACO algorithm is presented as the solution construction graph that the combinatorial optimization problem can be mapped on. Based on the solution construction graph, the unified framework of the ACO algorithm is presented. And this paper proposed several extensions of the Ant System that was the prototype of the ant algorithms. All these extensions were in some sense "greedier" than Ant System, but differ significantly in main aspects of the search control.In the third chapter, the solution of a metaheuristic following the ant colony optimization paradigm, the graph-based ant system, converge with a probability that can be made arbitrarily close to unity to one element of the set of optimal solutions.The 4^th chapter introduces an Enhance Ant-Q, a family of algorithms that presentmany similarities with Q-learning. In initialization phase, a same value is given to pheromone trail, so in the early stages of the computation the use of the heuristic improves the performance and pheromone trail have no special meaning. As computation goes on, pheromone trail become more and more useful to direct agents in finding good solutions. Thus we apply a non-linearity parameter to weigh more importance of the heuristic values than pheromone trail in the first iterations. The results obtained by Enhance Ant-Q are competitive with those obtained by other heuristic approaches.The 5^th chapter presents a distributed algorithm based on the self-organized capacity of ants for routing and load balancing in dynamic communication networks. Agents concurrently explore the network and exchange collected information. The communication among the agents is indirect and asynchronous, mediated by the network itself. This form of communication is typical of social insects and is called stigmergy. The algorithms' performance is shown to significantly improve the network's relaxation and its response to perturbations.The 6^th chapter describes an adaptive swarm-based routing algorithm inspired by the social behavior of ants which boasts a number of attractive features, including adaptation, robustness and distributed, decentralized nature, which are well suited for routing in modern communication networks. The algorithm increases convergence speed, reduces routing instabilities and oscillations by using a novel variation of reinforcement learning and a technique called momentum. We run many experiments over real IP datagram networks and under several traffic distributions. Results are very encouraging.In the 7^th chapter all of the work in this dissertation was summed up, and the future researches in this area were prospected.