import java.util.*;
import java.lang.Math;
public class TspNN
{
//Constant definition
static final int N = 20; //Number of
neurons (max cities)
static final double M = 1.0; //Maximum
activation
static final double m = -1.0/(N-1.0); //Minimum activation
static final int CASE1 = 1; //City
positioning, first case
static final int CASE2 = 2; //City
positioning, second case
static final int MAX_ITERATION = 200; //
//Variables
static double [][]a; //nxn grid of neurons, a(i,x) is the activation of neuron(i,x)
static double [][][][]W; //w(i,x,j,y)
is the connection strength between neuron(i,x) and
neuron(j,y)
static double [][]d; //distance between cities matrix
static double [][]c; //City coordinates
static double [][]net; //Net input of each neuron
static double step; //Step size
static int case_type;
static double shortestTour;
public static void main(String[] args)
{
//case_type
= CASE1;
case_type = CASE2;
initNetwork();
runNetwork();
}
public static void initNetwork()
{
Random rand = new Random();
//----------------------------------------------------------------------
//Initialization Phase
//----------------------------------------------------------------------
//Initialize the arrays
a = new double[N][N];
W = new double[N][N][N][N];
c = new double[N][2];
d = new double[N][N];
net = new double[N][N];
//Set the step size
step = 1.0;
shortestTour = 0.0;
//Set the
neural activations to a small random values between 0 and 10-10
for (int x=0 ; x<N ; x++)
for (int i=0; i<N; i++)
a[x][i] = rand.nextDouble() / Math.pow(10.0, 10.0);
//Set the
coordinates of each city in a unit square based on case
switch(case_type)
{
case CASE1:
//Case 1: uniformly placed on a circle
of radius = 0.25, centered at (0.5, 0.5)
double r = 0.25;
double Theta = 0.0;
//The angle is incremented by
360 / N (e.g. N = 20 then Theta increment is 18 degrees)
double ThetaIncrement = 2*Math.PI / N;
for (int x=0 ; x<N ; x++)
{
//Set the
x-coordinate on the circle
c[x][0] = 0.5 + r * Math.cos(Theta);
//Set the y-coordinate on the circle
c[x][1] = 0.5 + r
* Math.sin(Theta);
Theta += ThetaIncrement;
}
break;
case CASE2:
//Case 2: random (x, y) coordinates, 0
<= x <= 1 and 0 <= y <= 1
for (int x=0 ; x<N ; x++)
{
//Set the
x-coordinate within unit square
c[x][0] = rand.nextDouble();
//Set the y-coordinate within unit
square
c[x][1] = rand.nextDouble();
}
break;
}
//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.println("city"
+ x + " at\t" + c[x][0] + "\t\t" + c[x][1]);
System.out.format("city%d at %2.4f, %2.4f\n", x, c[x][0], c[x][1]);
}
System.out.print("\n\n");
//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));
//Set the
connection strength matrix
for (int x=0 ; x<N ; x++)
for (int i=0 ; i<N ; i++)
for (int y=0; y<N ; y++)
for (int j=0; j<N; j++)
{
//Row
connections:
//if y = x and
j <> i :
// w(i,x,j,y) = 1/n2 - 1/n
if((x == y)
&& (i != j))
W[x][i][y][j] = 1.0/Math.pow(N, 2) - 1.0/N;
//Column
connections:
//if y
<> x and j = i :
// w(i,x,j,y) = 1/n2 - 1/n
else if((x != y)
&& (i == j))
W[x][i][y][j] = 1.0/Math.pow(N, 2) - 1.0/N;
//Self
connections:
//if y = x and
j = i :
// w(i,x,j,y) = 1/n2 - 2/n
else if((x == y)
&& (i == j))
W[x][i][y][j] = 1.0/Math.pow(N, 2) - 2.0/N;
//Distance
connections (neighboring columns):
//if y
<> x and j = i+1 or j = i-1 :
// w(i,x,j,y) = 1/n2 - d(x,y)/n
else if((x != y)
&& ((j == i+1) || (j == i-1)))
W[x][i][y][j] = 1.0/Math.pow(N, 2) - d[x][y]/N;
//All other
connections:
//if j
<> i-1, i, i+1, and y <> x :
// w(i,x,j,y) = 1/n2
else
W[x][i][y][j] = 1.0/Math.pow(N, 2);
}
//Calculate
the net input of each neuron
//net(i,x) = Sy
Sj (w(i,x,j,y) * a(j,y))
//Note:
external input = 0.
for (int x = 0 ; x < N ; x++)
for (int i = 0 ; i < N ; i++)
{
net[x][i] = 0.0;
for (int y = 0; y < N ; y++)
for (int j = 0; j < N; j++)
{
net[x][i] += (W[x][i][y][j] * a[y][j]);
}
}
}
public static void runNetwork()
{
//----------------------------------------------------------------------
//Network Dynamics Phase
//----------------------------------------------------------------------
//Iterate at
most max_iteration
for(int iteration = 0 ;
iteration < MAX_ITERATION ; iteration++)
{
// Fuzzy read output
//1.
Assuming the grid indices:
// columns
(time stops): i
// rows
(cities): x (changed from j in
the project in order to be compliant with the rest of my implementation)
Vector<CMS> cms = new Vector<CMS>(N);
//2. Set: base = 2 // this is the width of the center of mass
calculation.
int base = 2;
//3. Center of Mass calculation:
for (int x=0 ; x<N ; x++) // for each
city
{
// calculate
the max activation and corresponding index:
double max_act =
-999999999.0;
int i_max = -1;
for (int i=0; i<N; i++)
{
if (a[x][i]
> max_act)
{
max_act = a[x][i];
i_max = i;
}
}
// calculate
the center of mass:
double sum1 = 0.0;
double sum2 = 0.0;
for(int k = i_max - base ; k < i_max +
base; k++)
{
if(a[x][(N+k)%N] > 0)
{
sum1
= sum1 + k * a[x][(N+k)%N];
sum2
= sum2 + a[x][(N+k)%N];
}
}
// now store the center of mass
("value") and the corresponding city index:
if(sum2 > 0.0)
cms.addElement(new CMS (x+1,
sum1/sum2));
}
// Now SORT
the center of mass by value (use a sort routine).
// After the
sort, center(0).value, center(1).value, ....,
center(N-1).value
// should be an increasing sequence
/of center of mass values,
// And, we
should have a corresponding sequence of cities: center(0).city,
//center(1).city, etc.
// That's it. The sequence of cities in tour(j)
specifies the tour.
Collections.sort(cms);
//Convergence Scheme 1: Check
if a permutation matrix exists (does not work)
//Convergence Scheme 2:
Calculate the fuzzy tour as long as there are valid cms
for each row
if(cms.size() == N)//isPermutationMatrix())
{
double totalTourLength
= 0.0;
for (int y=0 ; y < cms.size()- 1 ; y++)
totalTourLength += d[cms.elementAt(y).city - 1][cms.elementAt(y+1).city - 1];
//Display
results
if(totalTourLength < shortestTour
|| shortestTour == 0.0)
{
//Print out
the tour that resulted
System.out.println("2. Tour that resulted at iteration " + iteration);
System.out.print("cities: ");
for (int y = 0 ; y < cms.size()
; y++) // for each sorted city
{
System.out.print( cms.elementAt(y).city + " ");
}
System.out.print("\n\n");
//Print out distances between each
city of the tour
System.out.println("3. Distances between each city of the tour");
for (int y=0 ; y < cms.size()-
1 ; y++)
{
System.out.print( "distance between cities "+ cms.elementAt(y).city + " and " + cms.elementAt(y+1).city + ":\t");
System.out.print( d[cms.elementAt(y).city - 1][cms.elementAt(y+1).city - 1] + "\n");
}
System.out.print("\n\n");
//Print out the total length of the
tour
System.out.println("4. Total length of the tour: " + totalTourLength);
System.out.print("\n\n");
shortestTour = totalTourLength;
//Print out the final activations
System.out.println("5. Final activations of the network: ");
for (int x=0 ; x<N ; x++)
{
System.out.print("\nv" + x + "<\n");
for (int i=0; i<N; i++)
{
System.out.format("%2.4e", a[x][i]);
if( i < N-1)
System.out.print(", ");
if( (i+1)%5 == 0)
System.out.print("\n");
}
System.out.print(">");
}
System.out.print("\n\n");
}
}
//Print out the energy function
System.out.print("6. Energy function at iteration: " + iteration + "\t");
double energy = 0.0;
for (int x=0 ; x<N ; x++)
for (int i=0 ; i<N ; i++)
for (int y=0; y<N ; y++)
for (int j=0; j<N; j++)
{
energy += a[x][i]*a[y][j]* W[x][i][y][j];
}
energy =
energy * -0.5;
System.out.format("%2.4e", energy);
System.out.print("\n");
//Update the activation values
//a(i,x)t+1
= a(i,x)t
+ step * (a(i,x)t
- m) * (M - a(i,x))t) * net(i,x)t)
for (int x=0 ; x<N ; x++)
{
for (int i=0; i<N; i++)
{
a[x][i] += (step * ((a[x][i] - m) * (M - a[x][i]) * net[x][i]));
}
}
}
System.out.println("End Program");
}
static boolean isPermutationMatrix()
{
double convergenceCriteria = 0.7;
//Check each row
for (int x=0; x<N; x++)
{
boolean gotOne = false;
for (int i=0; i<N; i++)
if(a[x][i] > convergenceCriteria)
if(gotOne)
return false;
else
gotOne = true;
if(gotOne == false)
return false;
}
//Check each column
for (int i=0; i<N; i++)
{
boolean gotOne = false;
for (int x=0; x<N; x++)
if(a[x][i] > convergenceCriteria)
if(gotOne)
return false;
else
gotOne = true;
if(gotOne == false)
return false;
}
return true;
}
}
public class CMS implements Comparable<CMS>
{
public int city;
public double value;
public CMS(int city , double value)
{
this.city = city;
this.value = value;
}
public int compareTo(CMS o1)
{
if(value > o1.value)
return 1;
else if(value < o1.value)
return -1;
else
return 0;
}
}