Basic GA search problem

[doyler]

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();
  }
}

[quuba]

I like posts like this.
It is like checking to Newton's law of the apple falling to head from a tree.
Graph is also needed to compare the results with a certain amount of starts.
First look, very cursory: mutChance is absence in calculations. Why?

(my English reflects the degree of perfection google translator)

[mKorbel]

and what's your question

[doyler]

Ah, i figured I had missed something small. My chromosomes were acting up strangely because they all were mutating.

Thanks