Research On The TSP Promble Based On Distributed Ant Colony Algorithms

Many actual engineering problems can be regarded as combination optimization problems, and TSP (Traveling Salesman Problem) is a typical combination optimization problem, it has become and will continue to become a standard problem to test a new algorithm of combination optimization. Theoretically speaking ,the enumeration can get the best answer of TSP; but to all computers nowadays, it is hardly to obtain the best answer in such huge researching space by using common enumeration. So all kinds of algorithms emerged because of demand, the ant colony algorithm described is one of them.But face bigger scale TSP problem all heuristic algorithms include ant colony algorithm are poor efficiency.Therefore this thesis has put forward a idea to solve the TSP problem through the combination of distributed technology and ant colony algorithm.First, the thesis discussed the distributed computing frame.Based on making use of RMI to be a fundamental frame,the thesis designed and realized the task management mechanism and the task pool.Through the mechanism,we've improved the utilization of computing resource.Then, thesis compared two kinds different information renew method: part system renew and overall situation renew.According to the characteristic of distributed computing,thesis has given forward asynchronization renewal method afterwards, whose effective lessening communication amount having carried out the corresponding emulation certificate improves calculation efficiency fact.Then, in order to determine the optimal parameter optimization of the algorithm,we study the parameter selectionn of the ant colony optimization algorithm.There are a series of parameters for the algorithm including number of ants,expected heuristie factor,local pheromone evaporation factor ete.We compared different selections of these parameters using distribution ant colony algorithms in a series of simulated experiments and attain optimal parameter combination of TSP promble.Finally, the work of this thesis is summarized and the prospective of distribution ant colony algorithms is discussed.