مقایسه چندین الگوریتم هوشمند برای حل مسئله TSP در مهندسی صنایع

The paper presents three intelligent algorithms, namely, basic genetic algorithm, Hopfield neural network and basic ant colony algorithm to solve the TSP problem. Then different algorithms are compared in the perspectives of time complexity, space complexity, the advantages and disadvantages of the calculation results, and difficulty level of realization. We use the application of paired comparison matrix to make comprehensive evaluation, and then give the value of comprehensive evaluation in engineering.

The travelling salesman problem (TSP) is a problem in combinatorial optimization studied in operations research and theoretical computer science and in engineering . Given a list of cities and their pair wise distances, the task is to find a sho rtest possible tour that visits each city exactly once.This is an NP hard problem, when a large number of nodes of G, if the use exhaustive search, the time complexity is )!(nO ,if use the search of dynamic programming, the time complexityis )2(22nO, combinatorial explosion will occur in the both search methods. Therefore, the majority of domestic and foreign scholars began to study intelligence algorithms for TSP, since the basic genetic algorithm appears, they began to exa mine the use of genetic algorithm on solve TSP problems until present and proposed many improvements. Reference [1] presents a genetic algorithm based on common path, reference [2] proposed a new genetic algorithm through using multiple - search method. All these improved genetic algorithms are promising approach for TSP problem. Hopfield network was proposed in 1970s, and in 1985, Hopfield proposed to use CHNN for solving TSP problems, but Hopfield network prone to ineffective solutions and local solutions, so many scholars have been studying how to improve the algorithm, reference [3] analyzed the effectiveness of solving TSP with Hopfield, reference [4] through optimizing the Hopfield network and path of the initial steps to improve the Hopfield network to solve TSP and received good results. Ant colony algorithm which is effectiveness proposed a new computational intelligence algorithm for solving TSP problems recently. Because of its use of pheromone heuristic function, can greatly reduce the search