يك شبكه عصبي جديد با ساختار سازنده - تركيبي براي حل مساله هاي فروشنده دوره گرد و كوتاهترين مسير با تعداد شهر مشخص

A Novel Combinatorial Constructive Neural Network for the Traveling Salesman Problem and Shortest Path Problem with Specified City Number

In this paper a novel constructive neural network is introduced for solving the classic traveling salesman problem (CNN-TSP). The proposed neural network is inspired by the idea of the Kohonen SOFM and the Hopfield NN. The Kohonen SOFM introduces suitable TSP solutions for its competitive training algorithm though it slowly converges. Contrarily, the Hopfield NN quickly converges for its recursive structure while its solutions are poor. The proposed CNN combines the recursive structure (inspired from the Hopfield NN) with the competitive training algorithm (inspired from the Kohonen SOFM) to give both suitable performance and quickly convergence. The experimental results show that the CNN convergence speed is faster than the Kohonen SOFM by 20 times while its performance (with respect to the best-to-date solutions) is better than Kohonen by 3.81% for 29 benchmark TSP problems from TSPLIB. Also, the proposed NN appears better performance than other conventional approaches such as simulated annealing and Budinichʹs SOM. CNN can be used to solve other optimization NP-complete problems for its flexibility; i.e. in this paper, it is used to solve shortest path problem with specified city number (SPSN) as well as TSP.