import java.lang.Math;
import java.util.*;
import java.io.*;
public class TspGA
{
static final int maxIterations = 10000; //Maximum
number of iteration
static final int orderMethod = 1; //
static final int distanceMethod = 2; //
static final int N = 20; //Number of
neurons (max cities)
static int Np = N; //Population
Size
static BufferedWriter out;
static double [][]c = //City
coordinates
//The cities are set to the following
positions by default, in order to compare the results
//for the
different mutation rate and recombination methods.
{
{0.1441, 0.2672},
{0.8364, 0.6216},
{0.7941, 0.2506},
{0.1681, 0.1589},
{0.7665, 0.5870},
{0.8617, 0.3194},
{0.9602, 0.3857},
{0.4802, 0.9095},
{0.2667, 0.0610},
{0.5013, 0.1440},
{0.1495, 0.9376},
{0.1490, 0.5305},
{0.1654, 0.2104},
{0.7425, 0.0457},
{0.9024, 0.8253},
{0.8148, 0.0904},
{0.6858, 0.3236},
{0.8954, 0.5802},
{0.0601, 0.2041},
{0.7750, 0.9286},
};
static double [][]d; //distance
between each city
static double mutation_rate;
static int recombination_method;
static Person bestTour, worstTour;
public static void main(String[] args)
{
//Inits
Random rand = new Random();
Vector<Person> population = new
Vector<Person>();
Np = N;
//c = new double[N][2];;
d = new double[N][N];
//Place city randomly in unit square
//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();
//}
//Print out the position of each city
System.out.println("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));
//Create the members of the initial
population (ancestors)
for(int i = 0 ; i < N ; i++)
{
population.addElement(new Person(d));
}
//Select the mutation rate by removing
one of the commented out values
//4 different mutation rates
//a. mutation rate = 0.00
//b. mutation rate = 0.02
//c. mutation rate = 0.04
//d. mutation_rate
= 0.06;
//mutation_rate
= 0.00;
//mutation_rate
= 0.02;
//mutation_rate
= 0.04;
mutation_rate = 0.06;
//Select the recombination method by
removing one of the commented out values
//recombination_method
= orderMethod;
recombination_method = distanceMethod;
try
{
out = new BufferedWriter(new FileWriter("best_worst.csv"));
}
catch (IOException e)
{
}
for(int k = 0 ; k < maxIterations ; k++)
{
//1. Perform the
Selection/Recombination to create a child.
//---------------------------------------------------------------------------
//Selection
//---------------------------------------------------------------------------
//Sort the population by
fitness
Collections.sort(population);
//plot of the length of the
best and worst tour at each generation (gives the range of fitness values for
each generation).
try
{
out.write(String.format( "%2.4f, %2.4f , %d\n", population.firstElement().fitness, population.lastElement().fitness, k));
}
catch (IOException e)
{
}
//Choose 2 parents using:
//pick one randomly from the top half
of the list (call it mom)
//pick one randomly from the whole
list (call it dad)
Person mom = population.elementAt(rand.nextInt(population.size()/2));
Person dad = population.elementAt(rand.nextInt(population.size()));
//---------------------------------------------------------------------------
//End of Selection
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//Recombination
//---------------------------------------------------------------------------
Person child = new Person();
if(recombination_method == orderMethod)
{
//Order method recombination
selected
//First select 2 crossover points:
randomly chosen positions in the sequence.
int crossover1 = rand.nextInt(N);
int crossover2 = rand.nextInt(N);
//Create a child from mom and
dad
int bitmask = 0x0FFFFF;
for(int i = Math.min(crossover1,
crossover2) ; i <= Math.max(crossover1,
crossover2) ; i++)
{
//Copy the
integers between the crossover points in mom to the
corresponding positions in the child.
child.tour[i] = mom.tour[i];
bitmask &= ~(1 << (mom.tour[i] - 1));
}
//copy the
missing integers (ones not in the child yet) from dad, position by position, in
the order they appear in dad.
for(int i = 0; i < N ; i++)
{
if((bitmask & (1 << dad.tour[i] - 1)) != 0)
{
for(int j = 0; j < N ; j++)
{
if(child.tour[j] == 0)
{
child.tour[j] = dad.tour[i];
break;
}
}
bitmask &= ~(1 << (dad.tour[i] - 1));
}
}
}
else
{
//distance method recombination
selected
//The child is created by picking a
starting city and following the shortest edge
//of the
available edges (from either of the two parents) until a tour is formed.
int city_index = dad.tour[0]; //Start with a
city
child.tour[0] = city_index;
int bitmask =
0x0FFFFF;
bitmask &= ~(1 << city_index
- 1);
int child_tour_index = 1;
for(int i = 0 ; i < N ; i++)
{
double momNextDistance = mom.getDistanceOfEdgeAt(d, city_index);
double dadNextDistance = dad.getDistanceOfEdgeAt(d, city_index);
if(momNextDistance <= dadNextDistance)
{
city_index
= mom.getNextCity(city_index);
}
else
city_index
= dad.getNextCity(city_index);
//Prevent duplicate cities
if((bitmask & (1 << city_index
- 1)) != 0)
{
child.tour[child_tour_index++] = city_index;
bitmask &= ~(1 << city_index - 1);
}
}
//Complete the tour randomly when
running out of edges from either parent
while(bitmask != 0)
{
int tempNum = rand.nextInt(TspGA.N);
if((bitmask & (1 << tempNum)) != 0)
{
child.tour[child_tour_index++] = tempNum + 1;
bitmask &= ~(1 << tempNum);
}
}
}
//---------------------------------------------------------------------------
//End of Recombination
//---------------------------------------------------------------------------
//2. Insert the child into the
bottom of the population list (throwing the lowest member out).
child.setFitness(d);
population.addElement(child);
if(population.size() > 10000)
population.removeElementAt(10000);
//3. Apply the mutation
operator.
//---------------------------------------------------------------------------
//Mutation
//---------------------------------------------------------------------------
//Go through
the population members, one by one.
//Randomly apply
the mutation operator:
//Let mutation rate be the
probability that the mutation operator will be applied.
//If the mutation rate is 0.1
then there is a 1 in 10 chance that
//the mutation operator will be
applied to the member.
//So, for a population of size
100, and a mutation rate of 0.1,
//we would expect to have
approximately 10 mutations in a given generation.
int invertedMutationRate
= (int)(1/mutation_rate);
int selectedValue
= rand.nextInt(invertedMutationRate);
//Prevent the top 200 hundredth
of the population from being mutated
for(int i = 0 ; i < population.size() ; i++)
{
if(population.size() < 100)
break;
if( i < 100)
continue;
if(selectedValue == rand.nextInt(invertedMutationRate))
{
//Mutation
Operator #1:
//Randomly swap two of the integers in the permutation.
Person person = population.elementAt(i);
int
selectedInteger1 = rand.nextInt(N);
int
selectedInteger2 = rand.nextInt(N);
int tempVal = person.tour[selectedInteger1];
person.tour[selectedInteger1] = person.tour[selectedInteger2];
person.tour[selectedInteger2] = tempVal;
population.setElementAt(person, i);
}
}
//---------------------------------------------------------------------------
//End of Mutation
//---------------------------------------------------------------------------
//4. Back to step 1 (stop if
maximum iterations is reached).
}
try
{
out.close();
}
catch (IOException e)
{
}
System.out.println("Simulation Ended");
bestTour = population.firstElement();
System.out.println("The shortest tour occurs when visiting: ");
for (int i = 0 ; i < N ; i++) // for each
sorted city
{
System.out.format( "City %d\t(%2.4f, %2.4f)\n", bestTour.tour[i], c[bestTour.tour[i]-1][0], c[bestTour.tour[i]-1][1]);
}
System.out.print("\n\n");
System.out.format("The shortest tour length is %f\n\n", bestTour.fitness);
}
}
import java.util.Random;
public class Person implements
Comparable<Person>
{
public int tour[];
public double fitness; //better fitness corresponds to lower
tour length
public Person(double d[][])
{
Random generator = new Random();
tour = new int[TspGA.N];
//Create the DNA (tour) for a person
//Trash duplicate cities since all
tours go through all cities exactly one time
int bitmask =
0x0FFFFF;
int i = 0;
while(bitmask != 0)
{
int tempNum = generator.nextInt(TspGA.N);
if((bitmask & (1 << tempNum)) != 0)
{
tour[i++] = tempNum + 1;
bitmask &= ~(1 << tempNum);
}
}
//Compute the fitness of this person
(i.e. tour length)
fitness = 0.0;
for (int y=0 ; y < TspGA.N - 1 ; y++)
fitness += d[tour[y] - 1][tour[y+1] - 1];
}
public Person()
{
tour = new int[TspGA.N];
for (int y=0 ; y < TspGA.N - 1 ; y++)
tour[y] = 0;
fitness = 0.0;
}
public void setFitness(double d[][])
{
fitness = 0.0;
for (int y=0 ; y < TspGA.N - 1 ; y++)
fitness += d[tour[y] - 1][tour[y+1] - 1];
}
public double getDistanceOfEdgeAt(double d[][], int city_index)
{
int i;
for( i = 0 ; i < TspGA.N - 1; i++)
if(city_index == tour[i])
break;
if(i == TspGA.N
- 1)
return d[tour[i] - 1][tour[0] - 1];
else
return d[tour[i] - 1][tour[i+1] - 1];
}
public int getNextCity(int city_index)
{
int i;
for( i = 0 ; i < TspGA.N; i++)
if(city_index == tour[i])
break;
if(i == TspGA.N
- 1)
return tour[0];
else
return tour[i+1];
}
public int compareTo(Person p)
{
if(fitness > p.fitness)
return 1;
else if(fitness < p.fitness)
return -1;
else
return 0;
}
}