I've been messing around with basic GAs in Java but I seem to have run into an algorithmic problem but can't seem to find where exactly.
My code seems to narrow down the average fitness very quickly, but then seems to hover around the right answer without getting there pretty often.
import java.util.Random;
public class GAHelloWorld
{
String targetString = "";
private int[] target;
private int[][] population;
private int[][] generation;
private int crossoverChance;
private int mutationChance;
private int generations;
private int currLoc;
public GAHelloWorld(String targetS, int populationSize, int crossChance, int mutChance, int gens)
{
targetString = targetS;
target = new int[targetString.length()];
population = new int[populationSize][target.length];
generation = new int[populationSize][target.length];
crossoverChance = crossChance;
mutationChance = mutChance;
generations = gens;
for (int i = 0; i < targetString.length(); i++)
{
char c = targetString.charAt(i);
target[i] = (int)c;
}
}
private void generatePopulation()
{
Random gen = new Random();
for (int i = 0; i < population.length; i++)
{
for (int j = 0; j < target.length; j++)
{
int next = gen.nextInt(256);
population[i][j] = next;
}
}
}
private void populationToString()
{
for (int i = 0; i < population.length; i++)
{
System.out.println(chromosomeToString(population[i]));
}
}
private void run()
{
generatePopulation();
for (int i = 1; i < generations + 1; i++)
{
for (int j = 0; j <= (population.length / 2) - 1; j++)
{
currLoc = j;
selectParents();
}
population = generation;
if (i == 1 || i % 5 == 0)
System.out.println("Best in round " + i + ": " + chromosomeToString(findBest()));
if (chromosomeToString(findBest()).compareTo(targetString) == 0)
{
System.out.println("Best in round " + i + ": " + chromosomeToString(findBest()));
break;
}
}
}
private int fitness(int[] chromosome)
{
int toReturn = 0;
for (int i = 0; i < target.length; i++)
{
toReturn -= Math.abs(targetString.charAt(i) - chromosome[i]);
}
return toReturn;
}
private void selectParents()
{
Random gen = new Random();
int[] parentA = new int[target.length];
int[] parentB = new int[target.length];
int parent1Loc = gen.nextInt(population.length);
int parent2Loc = gen.nextInt(population.length);
while (parent2Loc == parent1Loc)
{
parent2Loc = gen.nextInt(population.length);
}
int[] parent1 = population[parent1Loc];
int[] parent2 = population[parent2Loc];
if (fitness(parent1) > fitness(parent2))
parentA = parent1;
else
parentA = parent2;
parent1Loc = gen.nextInt(population.length);
parent2Loc = gen.nextInt(population.length);
while (parent2Loc == parent1Loc)
{
parent2Loc = gen.nextInt(population.length);
}
parent1 = population[parent1Loc];
parent2 = population[parent2Loc];
if (fitness(parent1) > fitness(parent2))
parentB = parent1;
else
parentB = parent2;
mate(parentA, parentB);
}
private void mate(int[] parentA, int[] parentB)
{
Random gen = new Random();
int breedingType = gen.nextInt(100);
if (breedingType < crossoverChance)
crossover(parentA, parentB);
else
clone(parentA, parentB);
}
private void crossover(int[] parentA, int[] parentB)
{
Random gen = new Random();
int crossOverPoint = gen.nextInt(target.length);
int[] childA = new int[target.length];
int[] childB = new int[target.length];
for (int i = 0; i < crossOverPoint; i++)
{
childA[i] = parentA[i];
childB[i] = parentB[i];
}
for (int j = crossOverPoint; j < target.length; j++)
{
childA[j] = parentB[j];
childB[j] = parentA[j];
}
mutate(childA, currLoc * 2);
mutate(childB, (currLoc * 2) + 1);
}
private void clone(int[] parentA, int[] parentB)
{
int[] childA = parentA;
int[] childB = parentB;
mutate(childA, currLoc * 2);
mutate(childB, (currLoc * 2) + 1);
}
private void mutate(int[] chromosome, int loc)
{
Random gen = new Random();
int toMutate = gen.nextInt(target.length);
int mutAmount = gen.nextInt(11) - 5;
chromosome[toMutate] += mutAmount;
add(chromosome, loc);
}
private void add(int[] chromosome, int loc)
{
generation[loc] = chromosome;
}
private int[] findBest()
{
int[] bestChromosome = population[0];
for (int i = 1; i < population.length; i++)
{
if (fitness(population[i]) > fitness(bestChromosome))
{
bestChromosome = population[i];
}
}
return bestChromosome;
}
private String chromosomeToString(int[] chromosome)
{
String toReturn = "";
for (int i = 0; i < chromosome.length; i++)
{
toReturn += (char)chromosome[i];
}
return toReturn;
}
public static void main(String[] args)
{
String theString = "Hello World!";
int populationSize = 400;
int crossChance = 90; //90%
int mutChance = 20; //20%
int gens = 100;
GAHelloWorld myGA = new GAHelloWorld(theString, populationSize, crossChance, mutChance, gens);
myGA.run();
}
}