PJWSTK - Kohonen Self-Organizing Map for TSP Problem - Assignment

This assignment presents a comprehensive solution to the Traveling Salesperson Problem (TSP) using the Kohonen Self-Organizing Map (SOM). The solution begins with a 1D Kohonen SOM implementation, detailing the creation of cities, neuron placement, and the iterative process of training the map. The MATLAB code includes explanations of variables such as the learning rate, neighbor size, and iteration limits. The solution visualizes the city positions, the self-organized map, and the TSP tour. The assignment then investigates the impact of varying parameters such as learning rate and neighborhood size. Finally, the code is adapted to a 2D grid to solve the TSP, with corresponding MATLAB output and plots. The solution showcases the application of Kohonen SOM in solving the TSP and highlights the effects of different variables on the performance and accuracy of the algorithm.

Task 1:
Kohonen Self-Organizing Map for the TSP Problem:
In this assignment the one-dimensional Kohonen Self-Organizing Map is created for solving
TSP problem. The TSP problem has 11 cities with co-ordinates from 0 to 10 respectively.
The self-organizing map starts from initial tree iteration of 1 and continues until 601 tree
iterations are reached. The updated tree is displayed in each iteration with the location of
neurons in the map in red circles. The initial neighbour size used is 5 and the distance
function of neurons is Euclidean distance.
MATLAB code:
% creating 11 cities with co-ordinates inside [0,10]
% for 1D problem
% x1 = [0 1 2 3 4 5 6 7 8 9 10];
% x2 = [0 1 2 3 4 5 6 7 8 9 10];
% for 2D problem
x1 = [0 1 2 3 4 5 6 7 8 9 10];
x2 = [2 3 6 5 8 5 9 1 3 5 1];
% inserting 2D neurons in the map. For each city 10 neurons are inserted of

% 2-dimension
for m1=1:10
for m2=1:10
rng('default') % using default random number seed for repeatability
we1(m1,m2)=rand;
rng('default') % using default random number seed for repeatability
we2(m1,m2)=rand;
end
end
mul=1; % multiplying factor
nsize=5; % initial size of neighbour neurons
T=10000; % final iteration number or final simulation tree
t=1; % initial iteration
while (t< T)
n=mul*(1-t/T); % factor reduced with increase in iterations
nreduced=round(nsize*(1-t/T)); % neighbor size reduction with increase in iterations
%looping for all 11 cities
for i=1:11
euclidean_dist=(x1(i)-we1).^2+(x2(i)-we2).^2; % calculating the euclidean distance
from node to 2D

minj1=1;minj2=1;
min_dist=euclidean_dist(minj1,minj2);
% extracting the minimum distance co-ordinates
for m1=1:10
for m2=1:10
if euclidean_dist(m1,m2)<min_dist
min_dist=euclidean_dist(m1,m2);
minj1=m1;
minj2=m2;
end
end
end
k1dot= minj1;
k2dot= minj2;
%updating the neurons having least distance to the city points or
%the neurons that wins
we1(k1dot,k2dot)=we1(k1dot,k2dot)+n*(x1(i)- we1(k1dot,k2dot));
we2(k1dot,k2dot)=we2(k1dot,k2dot)+n*(x2(i)- we2(k1dot,k2dot));
%updating the neighbour neurons of the winning neurons
for rr=1:1:nreduced

j1st=k1dot-rr;
j2nd=k2dot;
if (j1st>=1)
we1(j1st,j2nd)=we1(j1st,j2nd)+n*(x1(i)-we1(j1st,j2nd));
we2(j1st,j2nd)=we2(j1st,j2nd)+n*(x2(i)-we2(j1st,j2nd));
end
j1st=k1dot+rr;
j2nd=k2dot;
if (j1st<=10)
we1(j1st,j2nd)=we1(j1st,j2nd)+n*(x1(i)-we1(j1st,j2nd));
we2(j1st,j2nd)=we2(j1st,j2nd)+n*(x2(i)-we2(j1st,j2nd));
end
j1st=k1dot;
j2nd=k2dot-rr;
if (j2nd>=1)
we1(j1st,j2nd)=we1(j1st,j2nd)+n*(x1(i)-we1(j1st,j2nd));
we2(j1st,j2nd)=we2(j1st,j2nd)+n*(x2(i)-we2(j1st,j2nd));
end
j1st=k1dot;
j2nd=k2dot+rr;

if (j2nd<=10)
we1(j1st,j2nd)=we1(j1st,j2nd)+n*(x1(i)-we1(j1st,j2nd));
we2(j1st,j2nd)=we2(j1st,j2nd)+n*(x2(i)-we2(j1st,j2nd));
end
end
end
t=t+1;
end
figure(1)
plot(x1,x2,'bo')
ylim([0 10])
title('City position co-ordinates')
figure(2)
plot(we1,we2,'ro')
hold on
plot(we1,we2,'k','linewidth',1)
ylim([0 10])
title(['Self-organized map with neurons after iteration t= ' num2str(t)]);

% for 1D problem TSP tour distance
% Tour_distance = sqrt((10-0)^2 + (10-0)^2)
figure(3)
tspx =[0 1 2 3 4 6 5 9 10 8 7 0];
tspy =[2 3 6 5 8 9 5 5 1 3 1 2];
comet(tspx,tspy)
title('TSP tour')
% Calculating TSP tour distance
Tour_distance = 0;
for i=1:10
Tour_distance = Tour_distance + sqrt((tspx(i+1)-tspx(i))^2 + (tspy(i+1)-tspy(i))^2);
end
sprintf('The TSP tour length or distance is %f',Tour_distance)
MATLAB output:
Self_organizing_map
ans =
'The TSP tour length or distance is 14.1421'

Plot:
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10 City position co-ordinates

0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10 Self-organized map with neurons after iteration t= 10000
From the above plot the TSP tour is the straight line distance between the cities. The straight
line distance or the TSP tour distance is 14.1421.
Task 2:
The variables in the Self-organizing map which has the ability to learn in an unsupervised
way has the following variables which determines the performance or accuracy of organizing
to target nodes.
The variables are given below.
1. The current iteration t
2. The iteration limit T
3. I which is the index of the input data vector X
4. x(I) or [x1,x2] is the target input data vector or cities with co-ordinates
5. Index m = [m1,m2] for neurons

6. Wm = [we1,we2] current weight of neuron having index m
7. k = [k1dot,k2dot] the index of best matching neuron or the neuron which has smallest
distance from city x(I)
8. The neighbourhood function θ(k,m,t)
9. n(t,T) is learning rate or the reduction factor through iterations
The weight vectors in each iterations for the neighbourhood neurons of the best matching
neuron is updated by the following formula
Wm(t+1) = Wm(t) + θ(k,m,t)* n(t,T)*( x(I) - Wm(t))
Now, the learning rate or the distance reduction factor is doubled and initial neighbour
size is also doubled. The total iteration number is reduced to 100. The self-organized map
for the above changes is shown below.
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10 City position co-ordinates

0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10 Self-organized map with neurons after iteration t= 100
It can be seen from the plot that although the neurons are assigned in the TSP tour but the
deviations of the neurons from the city co-ordinates are large due to small number of
iterations and increased learning rate. This effect is minimum of one dimensional problem
however this effect is large as the TSP paths will be different for more than one dimensional
problems.
Task 3:
Now, the code is changed in such a way that the cities are assigned to a 2D grid instead of 1D
grid and the same algorithm is applied to find the TSP tour.
MATLAB output:
Self_organizing_map
ans =

'The TSP tour length or distance is 28.699757'
Plot:
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10 City position co-ordinates

0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10 Self-organized map with neurons after iteration t= 10000
0 1 2 3 4 5 6 7 8 9 10
1
2
3
4
5
6
7
8
9 TSP tour