Application Of Ant Colony Algorithm On Network Routing

Ant colony algorithm (ACA) is a new kind of meta-heuristic algorithms for solving combinatorial optimization problems or continuous function optimization problems, and it borrows the mechanism of ant colony's forage, and every ant is looked for as an agent.The characteristic of ACA are parallel, positive feedback and robust is strongly showed during ant colony's forage, ACA also has these characteristics, so the research of theory and utility of ACA has great merit.Related research and applications of ACO (Ant Colony Optimization) have been promoted in the past ten years. The validity and advantages are proved by a great deal of trials. It should be pointed out, anyway, that ACO has its own defectives. For example, it requires a long period of time to search a good route when the ant colony is relatively large, because individual locomotion of the colony is stochastic. With the ever-increasing city scale of TSP, the disadvantages of basic ACA are obviously seen, such as long time searching. Besides, the basic algorithmen has little guidance meaning for outcoming data when pheromone cumulated to a certain extent, which will degrade the quality of outcoming data. On that account, we improved the basic ACA, and the renewed one is featured with excellent computing capability and high operating efficiency. We can apply ACO when computing QoS issue on the ground of similar situations of QoS and TSP. Meanwhile, the optimized outcoming could be found out by this rapid and efficient algorithm, which is guaranteed by a variety of alternative routes. Many have argued that only one or two limits are taken into consideration by QoS algorithm. Moreover, the entire network status is asked to maintain in every node. While this brand-new ACO introduced by us has five limits taken into consideration. Its efficiency is proved by simulation test.This paper analyzes the basic theory and model of ACA; introduces the features of ACA and its research state; selects some key parameters' value of ACA by simulations.The slow convergence and stagnation behavior are the main drawback of basic ACA, so we propose some methods to overcome these shortcomings. First, adopts the determinative and stochastic searching method to make selection; second, proposes the idea of subarea's searching to produce different quantity of pheromone in every route, accelerates the convergence of algorithm quickly in initial phase; third, combines with local and global pheromone's adjustment to update route's pheromone dynamically; fourth, alter some correlative parameters of pheromone adaptively; last, the idea of mutation is used to extend searching space. Puts forward a new ACA based on grid division to overcome the weakness of ACA in solving continuous function optimization Problem, and expands the discrete space to the continuous space.On the applying study, as to the problem of the Internet router optimization, we reasonable apply ACA to the QoS multi-point router problem. The goal of the QoS multi-point router is to find the optimum route among the scattering nets. It is required that we should start from the resource point and pass by all the aim point and fit for all the limited condition to reach the certain service level or the minimal cost. QoS multi-point router problem is complete NP problem. The essence of the multi-point communication problem is to find the smallest connection tree which connects a group of points based on some cost. The essence of resolving the problem is to find out the minimal connection point. The smallest connection tree is belonging to the complete NP problem of pic.argument. Generally speaking, the optimum calculation can't accomplish within polynomial time. Then the effective inspiriting calculation, though the hardness declines, the less optimum results can be acquired. Because constructing the minimal generating tree relatively simple, a lot of inspiriting calculation progress based on MST. Among those, the KMB calculation is famous for its concise and effectiveness.Here we focus on IP muilt-node route network that based on ACA and upgrades are made in accordance with optimization principle. Positive results have come out in terms of increasing alternative routes, as well as optimizing the computing efficiency. The new algorithm with individual differences outgoes the basic one in many aspects like constringency speed improvement. But the new algorithm has an accidental preference that lack of principle guidance. Research on these above-mentioned points is strongly required to perfect ACA in the future. Besides, other applications of ACA are also discussed here.Simulations are made on some examples for the improved ACA proposed. Results of simulations demonstrate that the improved ACA is effective and feasible; simulations are also made for continuous function optimization and network routing optimization based on ACA etc. This paper could promote the research of theory and application of ACA.