Application Research of Ant Colony Algorithm in Traveling Agent Problem
|School||Xi'an University of Architecture and Technology|
|Course||Computer Software and Theory|
|Keywords||traveling agent problem ant colony algorithm follow ants obstructionfactor information entropy|
Mobile agent technology is a new network computing technology, which has the characteristics of autonomy, collaboration and mobility. It can not only accomplish the specific tasks on behalf of the users, but also move independently according to the needs of users and the situation of the network. The remarkable characteristic of mobile agents is mobility. Reasonable routing policies and routing plannings will obviously improve the system performance of mobile agents. Traveling agent problem (TAP) is a classic and complex combinatorial optimization problem, which is from the path selection of mobile agent migration. The TAP aims at searching the optimal migration path for agents migrating, but the time complexity of conventional algorithms is extremely high, which requires the solving methods should be adaptive, self-learning, distributed and parallel.Ant colony algorithm, which imitates the ant swarm intelligence behavior in the insect kingdom, has the characteristic s of positive feedback, distributed computing and constructive greedy heuristic search. As an evolutionary algorithm, it is suitable for solving the TAP. But the basic ant colony algorithm not only is easy to fall into local optimum but also costs a long time. Aiming at these defects, firstly, inspired by the idea of follow bees in the bee colony algorithm, this thesis introduces the follow ants to speed up the process of searching for the optimal solution. Secondly, the thesis adds the obstruction factor to avoid the algorithm trapping into the local optimal solution. Finally, the thesis constructs the global pheromone updating rule to make the algorithm more suitable for the characteristics of TAP. The simulation results show that the proposed algorithm is a better way to solve the contradiction between the population diversity and long search time.And it makes mobile agents find the optimal solution with a better efficiency.This thesis compares the impacts, which are determined by the values of the parameters (information heuristic factor a, expectations heuristic factor P and pheromone evaporation rate p) in the ant colony algorithm, on the efficiency of the algorithm by experiments. On the basis of the aforementioned algorithm, this thesis introduces the information entropy to make the improved algorithm adjust adaptively the pheromone evaporation rate. The simulation results show that the improved algorithm has better applicability in solving the actual TAP.