import
java.util.Random;
import
java.util.Arrays;
public class KSON
{
static final int maxInputNodes = 3;
static final int N = 30; //Max cities
static final int maxCycles = 5000;
static double [][]w; //Connection strength matrix between
input and output nodes
static double ai[]; //Activation values of the
input nodes
static double ao[]; //Activation values of the
output nodes
static double C[][]; //All cities have x and y coordinates
and 1 normalization component
static double [][]d; //distance between cities matrix
static double alpha;
static int interactionDistance;
static int cityImages[][];
static int cycleIndex;
static double alphaSlopeCycle1;
static double alphaSlopeCycle2;
public static void main(String[]
args)
{
//-------------------------------------------------------------------------
//PART1 - training the network (mapping)
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//Initializations
//-------------------------------------------------------------------------
Random rand = new Random();
ai = new double[maxInputNodes];
ao = new double[N];
w = new double[maxInputNodes][N];
C = new double[N][maxInputNodes];
cityImages = new int[N][N];
d = new double[N][N];
//Set the initial gain parameter
alpha = 2.0;
interactionDistance = N / 10;
cycleIndex = 0;
alphaSlopeCycle1 = (alpha*0.1 - alpha) / (maxCycles / 10);
alphaSlopeCycle2 = (-alpha*0.1) / (maxCycles - (maxCycles / 10));
//Set weights to random values
uniformly distributed between 0 and 1
for (int i=0 ; i<maxInputNodes ; i++)
for (int j=0 ; j < N ; j++)
w[i][j] = rand.nextDouble();
//Create all cities randomly
for (int i=0 ; i<N ; i++)
{
C[i][0] =
rand.nextDouble(); //x coordinate
within a unit square
C[i][1] =
rand.nextDouble(); //y coordinate
within a unit square
//Compute the
normalization component
C[i][2] =
1/(Math.sqrt(Math.pow(C[i][0], 2) + Math.pow(C[i][1], 2)));
}
//Calculate
distances between cities
for (int x=0 ; x<N ; x++)
for (int y=0 ; y<N ; y++)
d[x][y] = Math.sqrt(Math.pow(C[y][0] - C[x][0], 2) +
Math.pow(C[y][1] - C[x][1], 2));
//Print out the position of each city
System.out.println("1. City
Positions");
for (int x=0 ; x<N ; x++) // for each
city
{
System.out.format("city%d
at %2.4f, %2.4f\n", x, C[x][0], C[x][1]);
}
System.out.print("\n\n");
//Set the city bitmask
int citybitmask = 0;
for(int i = 0 ; i < N ; i++)
citybitmask |= (1 << i);
while(cycleIndex < maxCycles)
{
//1
//Select a city randomly
int cityIndex =
rand.nextInt(N);
//Don't do anything if the city
has already been selected in the current cycle
if((citybitmask
& (1 << cityIndex)) == 0)
continue;
//Remove the city from the
problem set in the current cycle
citybitmask &= ~(1
<< cityIndex);
//Set the activation of the
input neurons with the city's parameters
ai[0] = C[cityIndex][0];
ai[1] = C[cityIndex][1];
ai[2] = C[cityIndex][2];
//2
//Compute the activation of all
the neurons in the output layer
for(int i = 0 ; i < N ; i++)
{
ao[i] = C[cityIndex][0]*w[0][i] + C[cityIndex][1]*w[1][i] + C[cityIndex][2]*w[2][i];
}
//Set the city image by finding
the highest activation
double cityImage =
0.0;
int cityImageIndex
= 0;
for(int i = 0 ; i < N ; i++)
{
if(ao[i] >
cityImage)
{
cityImage = ao[i];
cityImageIndex =
i;
}
}
for(int i = 0 ; i < N ; i++)
{
if(cityImages[cityImageIndex][i]
== -1)
{
cityImages[cityImageIndex][i]
= cityIndex;
break;
}
}
//3
//Adjust connection vector of
the image neuron and the i adjacent neurons
//W(t+1) = [ W(t) + C alpha(t)]
/ || W(t) + C alpha(t) ||
//where ||x|| is the Euclidean
norm of x.
//To avoid edge effects, the
nth neuron is treated as being adjacent to the first neuron
//(i.e.: wrap around).
//Start with the image index
updateWeights(cityIndex,
cityImageIndex, 1);
//Do the adjacent neurons to
the right
updateWeights(cityIndex,
cityImageIndex+1, interactionDistance);
//Do the adjacent neurons to
the left
updateWeights(cityIndex,
cityImageIndex-interactionDistance, interactionDistance);
//Gain and interaction are
updated at the end of a cycle,
//that is when each city of the
problem set has been presented once
//at the input neurons.
if(citybitmask ==
0)
{
//Completed
the current cycle
cycleIndex++;
//4
//The
interaction distance i is updated according to a predefined schedule.
if((cycleIndex % (maxCycles / 20) == 0)
&& (interactionDistance > 1))
interactionDistance--;
//5
//The gain
parameter, alpha, is reduced by a small amount, according to a predefined
schedule.
if(cycleIndex <= (maxCycles / 10)
&& (alpha > 0.0))
{
alpha += alphaSlopeCycle1;
}
else
{
alpha += alphaSlopeCycle2;
}
//Reset the
city bitmask
for(int i = 0 ; i < N ; i++)
citybitmask |= (1
<< i);
//Reset the
city images
if(cycleIndex < maxCycles)
for(int i = 0 ; i < N ; i++)
for(int j = 0 ; j < N ; j++)
cityImages[i][j] = -1;
}
}
//-------------------------------------------------------------------------
//PART2 - printing results
//-------------------------------------------------------------------------
//Print out the tour that resulted
System.out.println("The
shortest tour occurs when visiting: ");
for (int i = 0 ; i < N ; i++)
{
for (int j = 0 ; j < N ; j++) // for each
sorted city
if(cityImages[i][j] != -1)
System.out.format( "City
%d\t(%2.4f, %2.4f)\n", cityImages[i][j], C[cityImages[i][j]][0], C[cityImages[i][j]][1]);
}
System.out.print("\n\n");
//Compute the length of the tour
double tourLength =
0.0;
int city1_index = -1, city2_index =
-1;
for (int i = 0 ; i < N ; i++)
for (int j = 0 ; j < N ; j++)
{
if(cityImages[i][j] != -1
&& city1_index == -1)
{
city1_index = cityImages[i][j];
continue;
}
if(cityImages[i][j] != -1
&& city2_index == -1)
city2_index
= cityImages[i][j];
if(city1_index !=
-1 && city2_index != -1)
{
tourLength += d[city1_index][city2_index];
city1_index = city2_index;
city2_index = -1;
}
}
System.out.format("The
shortest length is: %2.4f\n\n", tourLength);
System.out.print("\n\n");
}
public static void updateWeights(int cityIndex, int neuronIndex, int distance)
{
double wt_c_alpha_term
[] = new double [3];
int i = neuronIndex;
//Ensures wrap around
if(i < 0)
{
i = N - distance;
}
for(int j = 0; j <
distance ; j++)
{
//Ensures wrap around
if(i >= N)
{
i = 0;
}
//W(t) + C alpha(t)
wt_c_alpha_term[0]= w[0][i] + alpha * C[cityIndex][0];
wt_c_alpha_term[1]= w[1][i] + alpha * C[cityIndex][1];
wt_c_alpha_term[2]= w[2][i] + alpha * C[cityIndex][2];
//Normalize W(t) + C
alpha(t)
double
norm_wt_c_alpha_term = (Math.sqrt(Math.pow(wt_c_alpha_term[0], 2)
+
Math.pow(wt_c_alpha_term[1], 2) +
Math.pow(wt_c_alpha_term[2], 2)));
//W(t+1) = [ W(t) + C alpha(t)]
/ || W(t) + C alpha(t) ||
w[0][i] =
wt_c_alpha_term[0] / norm_wt_c_alpha_term;
w[1][i] =
wt_c_alpha_term[1] / norm_wt_c_alpha_term;
w[2][i] =
wt_c_alpha_term[2] / norm_wt_c_alpha_term;
}
}
}