37.

[Cover] [Contents] [Index]

Page 130

Figure 3.13 The energy surface and local and global minima. See text for further discussion.

high temperature then gradually cool down. This technique is described more fully in Chapter 6.

3.4.5 Energy and weight coding: an example

Consider the travelling salesman problem. At the start of his journey, the salesman has to plan a route such that the distance travelled is the smallest possible. A solution based on the Hopfield network was proposed by Hopfield and Tank (1985). A two-dimensional array of units is employed. Figure 3.14 shows an example for a 4×4 Hopfield network in which the columns denote the visit sequence and the rows represents the city to be visited. Units with an output value of 1 are shaded, whilst units with an output value 0 are unshaded. The solution shown by Figure 3.14 indicates that the city visit sequence is Z2–Z4–Z1–Z3.

In order to obtain a meaningful result from a Hopfield network, the energy function has to be properly modelled (Section 3.4.4). The energy function consists of two parts: constraint and objective. In the travelling salesman problem, one can establish the following three constraints:

1 each city can only be visited once; that requires that the sum of each row must be exactly 1.

2 only one city can be visited at a given time, which indicates that each column also must sum to 1.

[Cover] [Contents] [Index]