solutions of the Travelling Salesman Problem
using a neural net (Hopfield net)
an applet made by António Miguel de Campos (Portugal)
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).
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
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.
Fractal figures generated using L-systems