Finding solutions of the Travelling Salesman Problem
using a neural net (Hopfield net)
an applet made by António Miguel de Campos (Portugal)

The Travelling Salesman Problem

The Travelling Salesman Problem (TSP) consists in the problem of determining the shortest circuit which can be made visiting a list of cities, in such a way that each city is visited (once and only once).

This is an "NP-complete" optimization problem, which means that, for a problem with a reasonable dimension, there are so many hypothesis to consider that it is generally unpractical to look for an optimum solution, because the computation cost is too high. That is why, finding a "good" solution in a short computation time is considered to be a good result.

A neural net allows the fast determination of solutions that, when valid, are all among the best 30 or 40 of the hundreds of thousands of possible hypothesis. If we choose among them the one that corresponds to the shortest traveled distance, we will obtain in a fast way a solution which, if it is not the best, it "close to" the best.

The representation scheme used to display the circuits of the TSP is based in a permutation matrix: there is a line for each city and each column represents the position of the city in the circuit. For instance, if the first neuron of the third column has an output close to 1 (shown by a red square which occupies the corresponding cell of the matrix), that means that the possibility that the city of Lisbon (X) will be the third city to be visited is being considered.

The program is based in the simulation of the non-linear differential equations which describe the net. The output value of each of the 100 neurons is represented in the matrix by the color and size of the square inside the corresponding cell. The number of iterations used can be modified by the user, by changing it directly in the respective text field. When a satisfactory solution is not found with the selected number of iterations, each time you press the Cont button the computation will proceed till a number of iterations equal to the present value incremented by the initially selected number of iterations (though, in certain cases, the net can definitely stabilize in a state which corresponds to a non-satisfactory solution), If you alter the number of iterations (increasing it) and press, in the keyboard, the Enter key (or line feed) the computation will proceed till the newly selected value of iterations.

The red squares represent output values which are greater than 0.5 ( if they totally occupy the corresponding cell, the output value will be 1).The blue squares represent output values which are smaller than 0.5 ( and, when they totally disappear, they correspond to output values smaller than 0.05). The color for each trajectory between two cities is the same as the one of the square representing the city in which it ends.

 

Lorenz atractor - the butterfly effect in a strange atractor  

Fractal figures generated using L-systems