Genetic Algorithm - 5 Generations  

Posted by Sue

import java.util.*;

public class Chromosome
{
private String [] chromosome;
private int [] value;
private int [] fitness;
private int no;
private int size;
private int parent1;
private int parent2;
private int xoverPoint = 0;
private String offspring1;
private String offspring2;
private int fitnessOS1;
private int fitnessOS2;
private int valueOS1;
private int valueOS2;
private int probC;
private int probM;
private boolean crossover;
private boolean mutation;
private int choose1;
private int choose2;
private Random r = new Random();

public Chromosome(int noNew, int sizeNew)
{
no = noNew;
chromosome = new String[no];
value = new int[no];
fitness = new int[no];
crossover = false;
mutation = false;
size = sizeNew;
}

//method for executing generations - somewhat like a semi-main method :p
public String doGeneration()
{
int generation = 1;
String output = "[ - G E N E R A T I O N "+generation+" - ]\n\n";
String xoverStatus = "";
String mutateStatus = "";
int size;
int sum;
double average;

randomPopulation();

size = chromosome[0].length();

calculateFitness();

sum = calculateSum();
average = sum/no;

for (int i=0; i<no; i++)
{
output += "NO - "+(i+1)+"\nCHROMOSOME - "+chromosome[i]+"\nVALUE - "+value[i]+"\nFITNESS - "+fitness[i]+"\n";
}

while (generation&#605)
{
selectParents();
performCrossover();
calcOffspringFitness();

if (!crossover)
xoverStatus = "NO CROSSOVER OCCURED.\n\n";
else
xoverStatus = "CROSSOVER OCCURED AT POINT = "+xoverPoint+"\n\n";

output +="\n\n\n- s e l e c t e d p a r e n t s -\n\nPARENT 1 - "+chromosome[parent1]+"\nFITNESS - "+fitness[parent1]+"\nPARENT 2 - "+chromosome[parent2]+"\nFITNESS - "+fitness[parent2]+"\n\n\n";
output +="- c r o s s o v e r -\n\nPROBABILITY OF CROSSOVER = "+probC+"/100\n\n"+xoverStatus+"OFFSPRING 1 - "+offspring1+"\nFITNESS - "+fitnessOS1+"\n\nOFFSPRING 2 - "+offspring2+"\nFITNESS - "+fitnessOS2+"\n\n\n";

performMutation();

if (!mutation)
mutateStatus = "NO MUTATION OCCURED.\n\n";
else
mutateStatus = "MUTATION OCCURED\n\n";

output +="- m u t a t i o n -\n\nPROBABILITY OF MUTATION = "+probM+"/100\n\n"+mutateStatus+"OFFSPRING 1 - "+offspring1+"\nFITNESS - "+fitnessOS1+"\n\nOFFSPRING 2 - "+offspring2+"\nFITNESS - "+fitnessOS2+"\n\n\n";

generation++;

output +="[ - G E N E R A T I O N "+generation+" - ]\n\n";

replace();
sum = calculateSum();
average = sum/no;

output += "REPLACED "+(choose1+1)+" WITH OFFSPRING 1: "+offspring1+"\n";
output += "REPLACED "+(choose2+1)+" WITH OFFSPRING 2: "+offspring2+"\n\n";

calculateFitness();

sum = calculateSum();
average = sum/no;

for (int i=0; i<no; i++)
{
output += "NO - "+(i+1)+"\nCHROMOSOME - "+chromosome[i]+"\nVALUE - "+value[i]+"\nFITNESS - "+fitness[i]+"\n";
}

output+="\nSUM = "+sum;
output+="\nAVERAGE = "+average;

}

return output;
}

//method for generating a random population. will be run once in goGeneration method
private void randomPopulation()
{
int part;
for (int i=0; i<no; i++)
{
chromosome[i] = "";
for (int j=0; j<size; j++)
{
part = r.nextInt(2);
chromosome[i] += "" + part;
}
}
}

//method for calculating each of the chromosome's fitness
private void calculateFitness()
{
int part;
for (int i=0; i<no; i++)
{
size = chromosome[i].length();
value[i] = 0;
for (int j=0; j<size; j++)
{
part = Integer.parseInt(chromosome[i].charAt(j)+"");
if (part==1)
{
value[i] += Math.pow(2,((size-1)-j));
}
}
fitness[i] = (value[i]*value[i]) - value[i];
}
}

//method for calculating total fitness of all chromosomes
private int calculateSum()
{
int sum = 0;
for (int i=0; i<no; i++)
{
sum += fitness[i];
}
return sum;
}

//method for selecting parents with the highest fitness
private void selectParents()
{
int maxfitness1 = 0;

for (int i=0; i<no; i++)
{
if (fitness[i] > maxfitness1)
{
parent1 = i;
maxfitness1 = fitness[i];
}
}

int maxfitness2 = 0;

for (int i=0; i<no; i++)
{
if (fitness[i] > maxfitness2 && fitness[i] != maxfitness1)
{
parent2 = i;
maxfitness2 = fitness[i];
}
}
}

//method for performing crossover
private void performCrossover() {
probC = r.nextInt(100);
if (probC>70)
{
xoverPoint = r.nextInt(size);
offspring1 = (chromosome[parent1]).substring(0,xoverPoint);
offspring1 = offspring1 + (chromosome[parent2]).substring(xoverPoint,size);
offspring2 = (chromosome[parent2]).substring(0,xoverPoint);
offspring2 = offspring2 + (chromosome[parent1]).substring(xoverPoint,size);
crossover = true;
}
else
{
offspring1 = chromosome[parent1];
offspring2 = chromosome[parent2];
crossover = false;
}
}

//method for calculating offsprings' fitness
private void calcOffspringFitness()
{
int part1, part2;

valueOS1 =0;
valueOS2 = 0;

for (int j=0; j<size; j++)
{
part1 = Integer.parseInt(offspring1.charAt(j)+"");
part2 = Integer.parseInt(offspring2.charAt(j)+"");
if (part1==1)
valueOS1 += Math.pow(2,((size-1)-j));
if (part2==1)
valueOS2 += Math.pow(2,((size-1)-j));
}
fitnessOS1 = (valueOS1*valueOS1) - valueOS1;
fitnessOS2 = (valueOS2*valueOS2) - valueOS2;
}

//method for performing mutation
private void performMutation()
{
int size = offspring1.length();
Random r = new Random();
String temp;
int part1,part2;
int hold1, hold2;

probM = r.nextInt(100);

if (probM<20)
{
part1 = r.nextInt(size);
part2 = r.nextInt(size);
hold1 = Integer.parseInt(offspring1.charAt(part1)+"");
hold2 = Integer.parseInt(offspring2.charAt(part2)+"");
if (hold1 == 1)
{
temp = offspring1.substring(0,part1) + "0" + offspring1.substring(part1+1,size);
offspring1 = temp;
}
else
{
temp = offspring1.substring(0,part1) + "1" + offspring1.substring(part1+1,size);
offspring1 = temp;
}

if (hold2 == 1)
{
temp = offspring2.substring(0,part2) + "0" + offspring2.substring(part2+1,size);
offspring2 = temp;
}
else
{
temp = offspring2.substring(0,part2) + "1" + offspring2.substring(part2+1,size);
offspring2 = temp;
}
mutation = true;
}
else
mutation = false;


valueOS1 =0;
valueOS2 = 0;

for (int j=0; j<size; j++)
{
part1 = Integer.parseInt(offspring1.charAt(j)+"");
part2 = Integer.parseInt(offspring2.charAt(j)+"");
if (part1==1)
valueOS1 += Math.pow(2,((size-1)-j));
if (part2==1)
valueOS2 += Math.pow(2,((size-1)-j));
}
fitnessOS1 = (valueOS1*valueOS1) - valueOS1;
fitnessOS2 = (valueOS2*valueOS2) - valueOS2;
}

//method for replacing 2 of the original chromosomes with the two offsprings
private void replace()
{
choose2 = r.nextInt(no);
choose1 = r.nextInt(no);
int size = chromosome[0].length();
int part;

while(choose1==choose2)
{
choose2 = r.nextInt(no);
}

chromosome[choose1] = offspring1;
chromosome[choose2] = offspring2;

for (int i=0; i<no; i++)
{
size = chromosome[i].length();
value[i] = 0;
for (int j=0; j<size; j++)
{
part = Integer.parseInt(chromosome[i].charAt(j)+"");
if (part==1)
{
value[i] += Math.pow(2,((size-1)-j));
}
}
fitness[i] = (value[i]*value[i]) - value[i];
}

}

}

This entry was posted on Friday, August 14, 2009 and is filed under . You can leave a response and follow any responses to this entry through the Subscribe to: Post Comments (Atom) .

4 comments

saja nk share dengan kawan2 coding ni. ;)

since u already use random for generating the first generation, apa kata klu bg choice klu xnak random utk mutation n crossover point letak value.its gud for testing, algo pun da cantik..:)

menarik, open source

so offspring ganti parents la ya. maknanya each generation ada same number of population ke?

Meet Minty the Hamster