COMP572

Neural Networks

Ludovic Hilde

Summer 2008

07/30/08

Assignment 6

NETWORK ARCHITECTURE

The Kohonen neural network is used to solve the Traveling Salesman Problem (TSP), which consists of creating the shortest tour possible by traversing each city exactly once, starting at any city, and ending at the same city.

The network contains 3 input neurons and N output neurons, where N stands for the number of cities in the network. In my implementation, two of the input neurons represent the xy Cartesian coordinates of a city in the unit square, and the third input neuron represent the normalization component of that city, which is calculated as 1 / √(x^2 + y^2).

All input neurons are connected to all output neurons.

The network’s architecture is shown in the picture below:

SIMULATION

The simulation first trains the network by mapping each city presented at the input layer to one of the image neuron at the output layer. It then prints the results.

The source was written in Java.

Click on the link below to access the source code of the simulation:

Kohonen Self-Organizing Networks

MAPPING PROCESS

Initialization

The alpha gain is initialized to 2.

The interaction distance is initialized to 0.1N, which equals 3 for 30 cities.

The weights are initialized to values between 0 and 1. these values are uniformly distributed when using the nextDouble function of the Java Random Class

All cities are located within the unit square.

The number of cycles is set to 1000

Algorithm

One city is chosen from the training set and is presented at the input neurons, that is ai0 = x, ai1 = y, ai2 = c.

The activation values of the Ith output neuron are computed as follows, aoi = C(x, y, c) * W(w1i, w2i, w3i) = x* w1i + y* w2i + c* w3i = ai0 * w1i + ai1 * w2i + ai2 * w3i.

The city image is set to the output neuron with the highest activation value. The city image is stored in a double array to account for duplicate.

The weights between output and input neurons are updated as follows:

1- Select the city image output neuron

2- Compute W(t) + C alpha(t) -> ( w1i + alpha * C1x, w2i + alpha * C2x, w3i + alpha * C3x)

3- Normalize W(t) + C alpha(t) -> √( (w1i + alpha * C1x)^2 + (w2i + alpha * C2x)^2 + (w3i + alpha * C3x)^2)

4- Update weights W(t+1) = W(t) + C alpha(t) / || W(t) + C alpha(t) || ->

( w1i + alpha * C1x / √( (w1i + alpha * C1x)^2 + (w2i + alpha * C2x)^2 + (w3i + alpha * C3x)^2),

w2i + alpha * C2x / √( (w1i + alpha * C1x)^2 + (w2i + alpha * C2x)^2 + (w3i + alpha * C3x)^2,

w3i + alpha * C3x / √( (w1i + alpha * C1x)^2 + (w2i + alpha * C2x)^2 + (w3i + alpha * C3x)^2

)

5- Repeat steps 2 to 4 for neurons within interaction distance located left of the city image (accounting wrap around)

6- Repeat steps 2 to 4 for neurons within interaction distance located right of the city image (accounting wrap around)

Decrease the interaction distance linearly if it is greater than one and the number of cycles is within the first 10%.

Decrease alpha linearly to 10% of its initial value if the number of cycles is within the first 10%. (In this simulation, alpha decreases by 0.2 - 2/100 = -0.018 at each cycle.)

Decrease alpha linearly to 0 if the number of cycles is past the first 10%. (In this simulation, alpha decreases by - 0.2/900 = -0.000222 at each cycle.)

RESULTS

The following depicts several runs of a Kohonen network with 30 cities, 1000 cycles, and the initialization parameters described in the MAPPING PROCESS section.

The shortest length is: 4.6750

The shortest length is: 4.9169

The shortest length is: 4.7193

The shortest length is: 4.5051

Path lengths for a 30-city problem are shown in the table below.

Cycles	Average Path	Best Path
1000	4.61711	4.0069
2000	4.8811	4.0935
5000	4.83974	4.2102

The path lengths generated by my simulation are consistent with the results described by Favata and Walker for a 30-city problem. The increase in the number of cycles does not have an impact for such small problem set because near optimum solutions are found with 1000 cycles.