Improved Ant Colony Algorithm And Its Application In The QoS

Ant colony optimization algorithm, as a new kind of novel simulated evolutionaryalgorithm after genetic algorithm, simulated annealing algorithm, tabu search algorithm andso on, provides a new way to efficiently solve complicated combinatorial optimizationproblems. Ant colony optimization was first proposed in 1992 by Italian researchers M.Dorigo in his doctoral dissertation, the inspiration first came from the fact that ants can foundthe shortest path in their process of searching for food. The latest research showed that antcolony optimization algorithm is a population-based and self-organized algorithm which ispositive feedback, distributed computing, better robust and combined with heuristic pathinformation, etc, so it can find better solution paths in a very short time. However, as theinitial pheromone information cant't reflect the quality of the path, it will spend a long time inthe early search and it is easy to fall into local optimal solution, all of which have a badinfluence on the performance of searching the shortest path.This dissertation introduces the most representative NP problem, so-called TravelingSalesman Problem as a start, which is usually used to analyze the performance of ant colonyalgorithm. Then the model, mechanism, advantages, disadvantages and the implementationsteps of the ant colony optimization algorithm are discussed in detail. After that we bring forthto the main improvement strategies on the basic ant colony optimization algorithm andpresent an analysis on its model parameters to guide the parameter setting later. Adding fourimprovement strategies to max-min ant algorithm, we call it E-MMAS that get a betterperformance, the later TSP's and Minimum Ratio TSP's simulation experiments proves thatE-MMAS has the advantage of a better convergence speed and a better solution path. In thefollowing we discuss the QoS routing technology, network model, the mathematical modeland the new features about the path constraints on QoS routing problem. Based on the fasterconvergence speed of E-MMAS, adding neighbors detection method and modifying itsprobability formula, we implement a superior algorithm called QoS-MMAS which is suited tosolve QoS routing problem. This paper uses two evaluation functions for the quality of thesolution paths. In the last part, a performance comparison between QoS-MMAS and otheralgorithms is made on solving QoS routing problem represented in both directed graph model and undirected graph model. The results indicate that the QoS-MMAS algorithm caneffectively solve the QoS routing problem.