basic genetic algorithm implemented in java


The following java classes provide tha basis for a very simple genetic algorithm. The source code has been copied from Appendix B of the book Applied Evolutionary Algorithms in Java by Robert Ghanea-Hercock. I want to use it as a blueprint to achieve a more complex implementation by myself, incorporating all improvements suggested in Appendix B and Chapter 3 in that excellent book.

The first class called individual.java, acts as a generic object representation of each chromosome in a GA population. An individual contains all the data required to define a specific chromosome and stores the current fitness values associated with the individual. The actual chromosome is stored within a Java Vector object, so we have the choice of using any basic Java object as a gene representation (floats, integers, doubles, …)

Here is the source code (I’ve used a nice online utility by Greg Houston, which alloes me to format the source code for blogging. If anyone knows a better form, with syntax colouring for example, let me know please)

/** A Genetic Algorithm Example in Java

From Applied Ecolutionary Algorithms in Java by Robert Ghanea-Hercock.
Appendix B.

individual.java

individual class, defines a single individual chromosome. Acts as a generic
object representation of each chromosome in a GA population. An individual
contains all the data required to define a specific chromosome and stores
current fitness values associated with hte individual.

The actual chromosome is stored within a Java vector object. By selecting
this design we have the choice of using any basic Java object as a gene
representation: floats, integers, doubles, etc.

**/

import java.util.Observable;
import java.util.Hashtable;
import java.util.Vector;

public class individual implements Cloneable {

/** constructor */

public individual () {

chromosome = new Vector(); // Dynamic resizable array for genes
fitness = 0.0; // raw fitness value
scaledFitness = 0.0; //relative fitness value
}

/** variable class members */

public double fitness;
public double scaledFitness;
public Vector chromosome;

/** Method for return full copy of this individual */

public individual copy () {

individual newInd = new individual ();
newInd.chromosome = (Vector)this.chromosome.clone();
newInd.fitness >= this.fitness;
newInd.scaledFitness = this.scaledFitness;

return newInd;

}

}

/** end class **/

The second class, genetic.java, tries to match the contents of a one-dimensional set of double values generated from a simple mathematical function (sin x) and prints the output to screen. This is the source code:

/**

Main genetic algorithm class. This version tries to match the contents of a
1-D array of double numeric values. A one-dimensional set of double values
generated from a simple mathematical function (sin x) Then it prints the
output to screen.

**/

import java.util.*;

public class genetic {

/** variables */

// fitness calculation

double sumFitness;
double bestFitness;
double averageFitness;

// individuals to evolve

individual population []; // array of current individuals
individual newpopulation []; // array of next generation of individuals
individual bestIndividual; // best individual

// GA parameters

int popSize; // number of individuals
double alleleSize; // range of the target numeric values
int maxLength; // (maximum) length of chromosome
int minLength; // (minimum) same as above for fixed length chromosomes
int generation = 0; // generation count

// Random

Random random;
static final int seed = 93404;


// array to match

public double testarray [];

/** constructor */

public genetic ()
{

// Fist, we choose a suitable GA parameters (could be fetched from file?)

popSize = 120;
maxLength = 16;
minlength = 16;
alleleSize = 99.0;

// Fitness and Random

sumFitness = 0.0;
random = new Random (seed);

// Creation of population

testarray = new double(maxlength);
bestIndividual = new individual ();
population = new individual[popSize];

for (int i=0; i<popSize; i++)
{
population[i] = new individual();
}

// Initialise population

population = initialisePopulaton (population);
}

/** method to initialise the population of individuals */

public individual[] initialisePopulation (individual pop[])
{
int g = 0;
double gene = 0.0;

for (int i=0; i<pop.length; i++)
{
// choose the number of genes we are going to fill for
// this individual
g = (int)(random.nextFloat() * maxLength);
if (g <= minLength) g = minLength;


// fill chromosome for this individual
for (int j=0; j<g; j++)
{
gene = Math.abs((random.NextFloat() * alleleSize));
pop[i].chromosome.addElement(new Double(gene));
}
}

return pop;
}

/** Main methid will loop until program is halted, or alternatively could set
to end after a fixed number of runs or a minimum fitness value is reached
*/

public void evolve ()
{

while (true)
{
for (int i=0; i<population.length; i++)
{
double testcase [] = convertchromosome (population[i].chromosome);
population[i].fitness = evaluate (testcase);
}

sort (0, population.length - 1);
normalizeFitnessOfPopulation ();
select ();
generation++;
}
}

/** Re-scale fitness of all individulas and print results of current best
individual */

public void normalizeFitnessOfPopulation ()
{
double minFitness = 10000.0;
sumFitness = 0.0;

for (int i=0; i<population.length; i++)
{
if (population[i].fitness < minFitness)
minFitness = population[i].fitness;

if (population[i].fitness > bestFitness)
{
bestFitness = population[i].fitness;
bestIndivu¡idual = population[i];
printStats (bestIndividual);
}
}

for (int i=0; i<population.length; i++)
{
population[i].scaledFitness = population[i].fitness - minFitness;
}

for (int i=0; i<population.length; i++)
{
sumFitness += population[i].scaledFitness;
}
}

/** Print statistics of an individual */

private void printStats (individual ind)
{

double test[];

test = convertChromosome (ind.chromosome);

for (int i=0; i<test.length; i++)
{
double a = test[i];
System.out.print (a + " ");
}

System.out.println ("Current best genome");

for (int j=0; j<test.length; j++)
{
double t = testarray[j];
System.out.print (" ");
}

System.out.println("Target genome");
System.out.println (ind.fitness);
}

/** Applies the GA processes of fitness proportionate selection, crossover
and mutatition to the population */

private void select()
{
int index = 0;
int step = 0;
int mutate = 0;

newPopulation = new individual[popsize];

individual ind1;
individual ind2;
individual children[];

for (int i=0; i<population.length; i++)
{
newpopulation[i] = population[i].copy();
}

int index = 2;

while (index < ((popSize/2)-1))
{
step = index + (popSize/2); // replace bottom half
ind1 = selectIndividual();
ind2 = selectIndividual();
children = crossOver (ind1, ind2);
newpopulation[step] = children[0].copy();
index++;
newpopulation[step] = children[1].copy();
index++;
mutate++;

if (mutate % 3 == 0)
{
int k = (int)(random.nextFloat() * popSize - 1);
newpopulation[k] = mutate(population[k].copy());
}
}

// copy newpopulation into the current population

for (int i=0; i<population.length; i++)
{
population[i] = newpopulation[i].copy();
}
}

/** Returns an individual based on a Roulette Wheel selection method,
see chapter 3. */

private individual selectIndividual ()
{
double sumOfFitness = 0.0;
int inedx = 0;
individual temp = new individual ();
float ran = random.NextFloat();
double limit = ran * sumOfFitness;

while ((index < population.length) && (sumOfFitness < limit))
{
sumOfFitness += population[index].scaledFitness;
index++;
}

temp = population[index-1].copy();
return temp;
}

/** Swap segments of two selected parent individual chromosomes */

private individual[] crossOver (individual parent0, individual parent1)
{
individual children = new individual[2];
individual longest;
individual shortest;
int nin = 0;
int max = 0;

min = (int)Math.min(parent0.chromosome.size(), parent1.chromosome.size());
max = (int)Math.max(parent0.chromosome.size(), parent1.chromosome.size());

int cut = (int)(random.nextFloat()*min);

//assumes chromosome may be variable length
if (parent0.chromosome.size() > parent1.chromosome.size())
{
longest = parent0.copy();
shortest = parent1.copy();
}
else
{
longest = parent1.copy();
shortest = parent0.copy();
}

for (int i=cut; i<max; i++)
{
if (i <= (min-1))
{
Double a = (Double)parent0.chromosome.elementAt(i);
Double b = (Double)parent1.chromosome.elementAt(i);
longest.chromosome.setElementAt(b,i);
shortest.chromosome.setElementAt(a,i);
}
else
{
Double a = (Double)longest.chromosome.elementAt(i);
shortest.chromosome.addElement(a);
}
}

for (int i=min; i<max; i++)
{
int len = longest.chromosome.size();
longest.chromosome.removeElementAt(len-1);
}

children[0] = shortest.copy();
children[1] = longest.copy();

return children;
}

/** Returns a new individual from a mutation applied to an existng
individual */

private individual mutate(individual mutant)
{
int m,r = 0;
double g = 0.0;
Double gene;
float f = random.nextFloat();

r = (int)(f * mutant.chromosome.size());
g = ((random.nextFloat())) * alleleSize;
gene = new Double(g);
mutant.chromosome.setElemenyAt(gene, r);

return mutant;
}

/** An optional method, to allow alternative primitive representation
within the chromosome */

public double[] convertChromosome (Vector chrom)
{
Double val;
double out[] = new double[chrom.size()];

for (int i=0; i<chrom.size(); i++)
{
val = (Double)chrom.elementAt(i);
out[i] = (double)val.doubleValue; // select ints or double
}

return out;
}

/** Do the comparison between the targer array of doubles and the current
individual being tested for fitness */

private double evaluate(double[] genome)
{
double answer = 0.0;
boolean flag = false;
short[] shortGenome = new short[maxLegnth];

//fill the test array, see sinc function in chapter 3
for (int i=0; i<genome.length; i++)
{
testarray[i] = Math.abs(10 * Math.sin(i));
}

for (int i=0; i<genome.length; i++)
{
answer += Math.abs(testarray[i] - genome[i]);

// measure the difference between each target element and the individual
// array
}

return 1.0 - (answer/genome.length);
// scale as 1.0 = fittest individual
}

/** Simple quick sort algorithm, to arrange the population by fitness */

private void sort (int low, int high)
{
int index1, index2;
double pivot;
individual temp;

index1 = low;
index2 = high;

pivot = population[(low + high)/2].fitness;

do
{

while (population[index1].fitness > pivot) {index1++;}
while (population[index2].fitness < pivot) {index2--;}

if (index1 <= index2)
{
temp = population[index2];
population[index2] = population[index1];
population[index1] = temp;
index1++;
index2--;
}

} while (index1 <= index2);

if (low < index2)
{
sort(low, index2);
}

if (index1 < high)
{
sort(index1, high);
}
}

/** Main program method, creates an instance of the class genetic */

public static void main (String args[])
{
genetic test = new genetic();
test.evolve();
}

} //end class genetic

The genetic class uses some of the techniques outlined in chapter 3 of the book. The sequence of actions implemented (in the evolve() method) are more or less the following steps:

(1) Create a randomly population of N chromosomes, each of some length m genes (being those bits, integers, doubles, … what have you) (i.e constructor plus initialisePopulation method of genetic.java class)

(2) Test each chromosome (i.e a possible task solution) within the problem space and assign a measure of fitness f(x) (i.e evaluate method of gentic.java class)

(3) Selection phase: select a pair of chromosomes from the population with probability based on their fitness (i.e selectIndividual() method of genetic.java class)

(4) Apply a set of genetic operators to the two parent chromosomes: with some crossover probability pc, apply crossover at some (uniform/non-uniform) random selected point (or points) along each chromosome, resulting in two offspring (i.e crossOver() methods of genetic.java class)

(5) Apply mutation to each new chromosome (offspring) with probability pm (i.e mutate() method of genetic.java class)

(6) Place the new chromosomes in the new population (i.e select() method of genetic.java class)

(7) Replace the old population with the new population (but maybe for a best old individual …), or we may use a steady-state method, in which an overlapping population model is mantained (i.e select() method of genetic.java class)

(8) Test if target termination criteria is met (such as a specified best fitness value or a number of generations passed); else repeat step 2 (i.e evolve() method of genetic.java class)

Experiments

By modifying the GA parameters (which are hard coded in genetic class; maybe some java properties file might be useful here to make them independent of code … first imporvement?) such as mutation rate, population size or representtaion scheme I can gain useful insight into the relative importance each plays in the performance of GA (I think I shoold do it and make a report)

Improvements

The additions suggested by the author to the source code above are the following:

(1) Modify the genetic class to match two-dimensional array of integer or double values

(2) Enable a binary genome representation.

(3) Provide a choice of selection operators, e.g. tournament selection (see Chapter 3)

(4) Enable variable-length genomes (the Java Vector class to store the chromosome makes this simple) Also use the ArrayList object as a storage mechanism and compare the performance with the Vector object.

(5) Provide a choice of multipoint crossover schemes.

The array performance problem

In relation to point (4), there are several points to consider in choosing which Java array to use in the GA algorithm:

* Synchronisation: Vectors are synchronised, that is thread-safe, but this comes with a performance hit; ArrayList is not; Do I need a thread-safe collection for my GA?)

* Data Growth: ArrayList and Vector internally use an Array container and as you insert a new element, the object will expand this internal array if it runs out of room; a Vector defaults to doubling the size of the array; the ArrayList increases the array size by 50%; so we have again a performance hit!

I can use a simple Java array in place of either Vector or ArrayList, avoiding synchronisation, extra method calls and suboptimal resizing BUT I’ll have to be careful with the indexing of the array elements.

(more on genetioc algorithms)

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s