SKEDSOFT

Neural networks have proved to be efficient at solving some optimization problems. Optimization problems are about finding a minimum of a goal function. A neural network, for example, the Hopfield network, can be represented by an energy function which tends to its minimum during convergence. Now, the problem of using a neural network for solving an optimization task is how to represent the optimization goal function as an energy function of a network.

 As an example, a solution to the Traveling Salesman Problem (TSP) is given here. One connectionist solution of the TSP was suggested by Hopfield and Tank (1985). They represented the problem as an N2-dimensional Hopfield network. The rows represent N towns and the columns the position of the town in the route.

The Boolean matrix shows a possible tour, where 1 denotes an activation of the corresponding neuron. The path in the example is Q S P T R. There are some constraints to be satisfied by the system when using such a representation: only one 1 in every row; only one 1 in every column; only N 1's in the whole matrix; the shortest path. The constraints are fulfilled respectively by the following optimization functions.

Where M_xi denotes the value of the xth row and ith column (town x being at the ith position in the matrix M of the towns and positions; x and y denote towns; i and j denote positions; d_xyis the distance between x and y; and x_i is town x placed on the ith position in the tour. The four constraint terms can be aggregated in a global optimization goal function:

                                                                               F = - aC1 - bC2 - cC3 - dC4

Where a, b, c and d are constants. F takes a minimum value when all the terms are at minimum values. Each of the four terms in the above optimization function has its minimum value when a corresponding constraint is satisfied. If we make the energy function E of a Hopfield network equal to the optimization function F above, the following formulas can be derived for calculating the weights of the network:

The symbol Dij is the Cronecker function, Dij = 1, if i = j, otherwise Dij = 0. There are some other connectionist methods for solving the TSP, for example, with the use of SOM.

Other optimization problems, like the shortest path problem, dynamic programming problems, the transitive closure problem, the assignment problem, and so on, have also been solved using connectionist models.