Research On Hybrid Evolutionary Algorithm Of Solving Traveling Salesman Problem

TSP (Traveling Salesman Problem) is a combination optimization problem with simple definition but difficult to be solved, which attracts many researchers in various fields including mathematics, physics, biology and artificial intelligence (AI). It has become and will continue to become a standard problem to test a new algorithm of combination optimization. Theoretically speaking, the enumeration not only can solve TSP, but also can get the best answer. But to all computers nowadays, it's hardly to obtain its best answer in such huge search space by using common enumeration. Therefore, all kinds of algorithms to solve TSP emerged because of demand. Among of them, evolutionary algorithm is one of advanced technologies.Evolutionary algorithm (EA) is an intelligent algorithm that learns from the evolutionary process in the nature. EA employs a coding technology and some genetic operations. Under the pressure of selection, which means "fits survive", the algorithm can produce an optimal solution. Because EA is simple and it seldom needs any additional information about the problem, EA becomes a general solver of challenge problems.The new 2-adjacency representation of the hybrid evolutionary algorithm (HEA) is presented in this paper. The reason for this is that the traditional routing representations are not considerably appropriate for evolutionary processing. The new representation which is exclusive for each routing improves the heritability of evolutionary operators. The properties and operations of this new representation turn into the parameters and evolutionary operators of the HEA. In order to speed up HEA, the local optimizations are hybridized in.Local optimizations are the methods which are always used to solve the TSP. They are also as parts of some other methods. They are very efficient. The performances of different local optimizations are analyzed in this paper. This paper presents a hybrid local optimization which is a part of the HEA.The experiments of TSP benchmarks indicate that the proposed scheme reach the existing optimal solutions, even get better solutions. As efficiency concerned, hybrid local optimization has better efficiency, but the HEA is able to get better solutions,and efficiency is acceptable. In order speed up the scheme, a multi-threading HEA is implemented. The results reveal the parallel essence of evolution algorithms.