Can someone with GA experience examine my fitness function?

Question

Here is my problem, I'm modifying code I found for Genetic Algorithms to do numerical optimization of a function. Essentially, given a function F and our Desired Value, the program uses GA to searches for values of x and y which provide the appropriate Desired Value. I keep tinkering with my fitness function, which I feel is the root of the issue.

The basic code break down is:

Generate a random chromosome population

Use a bubble sort based on each chromosomes fitness

Check if any of them happen to solve the function

If one solves it, then stop and print it

Else, Generate children based on the parents Sort, check the best answer, loop

I hope someone can point me in the right direction I'm going to dissect it again some more tonight but I seem to have hit a snag on this. For more complex functions than that I have hard coded, it seems to converge around a random percentage (usually less than 20)... but it should be much closer to 0. The simple coded function keeps returning around 99% difference... so I'm not 100% on whats up.

import java.util.*;
import java.util.Comparator;
import java.util.TreeMap; 
/**
 * Modified from a file created Jul 9, 2003
 * Original @author Fabian Jones
 * Modified @author Cutright
 * @version 2
 */
public class ScratchGA
{
private static int NUM_CHROMOSOMES = 100;   //num of chromosomes in population
private static double MUTATE =  .01;  //chance of a mutation i.e. 88.8%
private static int desiredValue = 60466176; //desired value of function 
private static int cutoff = 1000; // number of iterations before cut off
private static int longPrint = 0;  //1 means print out each iteration of the population
private boolean done = false;
private Chromosome[] population;
int iteration = 0;

/**
 * Constructor for objects of class ScratchGA
 */
public ScratchGA()
{
    generateRandomPopulation(NUM_CHROMOSOMES);
    printPopulation();
}

/**
 * Generate a random population of chromosomes  - WORKS
 * 
 */
private void generateRandomPopulation(int pop)
{
    System.out.println("Generating random population of " + pop + ", now." +"\n");

    population = new Chromosome[pop];

    for(int i=0; i<pop; i++)
    {
        int rand = (int)(Math.random()*4095);  // Range 0 to 4095
        population[i] = (new Chromosome(rand, 12));
    }
}

/**
 * Codesaver for generating a new line in the output
 */
private void newLine()
{
    System.out.println("\n");
}

/**
 * Prints the population (the chromosomes)
 */
private void printPopulation()
{
    int x=1; // variable to print 10 chromosomes on a line
    if (iteration==0)
    {
    System.out.println("Initial population: " + "\n" );
    }
    else
    {
        if (longPrint ==1)
        {
    System.out.println("Population " + iteration + " :" + "\n");
    for(int i=0; i<=(NUM_CHROMOSOMES-1); i++)
    {
        System.out.print(population[i] + " ");
        if(x == 10)
        {
            newLine();
            x=1;
        }
        else
        {
            x++;
        }
    }

    newLine();
      }
      else
      {
      System.out.println("Best answer for iteration " + iteration + " is: " + population[0] + " with a % difference of " +population[0].getFitness());
      newLine();
    }
}
}
 /** 
 * Start
 * Bubblesort initial population by their fitness, see if the first chromosome
 * in the sorted array satisfies our constraint.
 * IF done ==true or max num of iterations
 *        Print best solution and its fitness
 * ELSE
 *    generate new population based on old one, and continue on
 */
public void start()
{
   // System.out.println("Starting bubblesort... Please Wait.");
    bubbleSort();
    //System.out.println("After Bubblesort: " );
    //printPopulation();
    topFitness();

    if(done || iteration==cutoff){
        System.out.println("DONE!!");   
        System.out.println("Best solution: " + population[0] + " % Difference: " + population[0].getFitness());
    }
    else{
        iteration++;
        generateNewPopulation();
        printPopulation();
        start();
    }
}
 /**
 * If the top chromosomes fitness (after being sorted by bubblesort) is 100%
 * done == true
 */
private void topFitness()
{
    if (population[0].getFitness() == 0)
    {
        done = true;
    }
}

/**
 * Called from chromosome,
 * Tests the x and y values in the function and returns their output
 */
public static double functionTest(int x, int y)
{
    return (3*x)^(2*y); // From our desired value we're looking for x=2, y=5 
}

/**
 * Returns the desired outcome of the function, with ideal x and y
 * Stored above in a private static
 */
public static int getDesired()
{
    return desiredValue;
}

/**
 * Sort Chromosome array, based on fitness
 * utilizes a bubblesort
 */
 private void bubbleSort()
 {
     Chromosome temp;

     for(int i=0; i<NUM_CHROMOSOMES; i++){
         for(int j=1; j<(NUM_CHROMOSOMES-i); j++){
             if(population[j-1].getFitness() > population[j].getFitness())
             {
                 //swap elements
                 temp = population[j-1];
                 population[j-1] = population[j];
                 population[j] = temp;
                }
            }
        }
    }
/**
* Top 30: Elitism
* Next 60: Offspring of Elitists
* Next 10: Random
*/
  private void generateNewPopulation(){

    System.out.println("***Generating New Population");
    Chromosome[] temp = new Chromosome[100];
    for (int i = 0; i < 30; i++)
    {
     Chromosome x = population[i];
     if (shouldMutate())
     mutate(x);
     temp[i]=x;
    } 
   for (int i = 0; i < 30; i++)
   {
    temp[i+30] =cross1(population[i], population[i+1]);
    temp[i+60] = cross2(population[i], population[i+1]);
   } 
   for (int i = 90; i<100; i++)
   {
        int rand = (int)(Math.random()*4095);  // Range 0 to 4095
        Chromosome x = new Chromosome(rand, 12);
        temp[i] = x;
    }
    population = temp;
}
/**
 * First cross type, with two parents
 */
private Chromosome cross1(Chromosome parent1, Chromosome parent2){
    String bitS1 = parent1.getBitString();
    String bitS2 = parent2.getBitString();
    int length = bitS1.length();
    int num = (int)(Math.random()*length); // number from 0 to length-1
    String newBitString = bitS2.substring(0, num) + bitS1.substring(num, length);
    Chromosome offspring = new Chromosome();
    offspring.setBitString(newBitString);

    if(shouldMutate()){
        mutate(offspring);
    }

    return offspring;
}

/**
 * Second cross type, parents given in same order as first, but reverses internal workings
 */
private Chromosome cross2(Chromosome parent1, Chromosome parent2){
    String bitS1 = parent1.getBitString();
    String bitS2 = parent2.getBitString();
    int length = bitS1.length();
    int num = (int)(Math.random()*length); // number from 0 to length-1
    String newBitString = bitS2.substring(0, num) + bitS1.substring(num, length);
    Chromosome offspring = new Chromosome();
    offspring.setBitString(newBitString);

    if(shouldMutate()){
        mutate(offspring);
    }

    return offspring;
}

/**
 * Returns a boolean of whether a character should mutate based on the mutation value at top
 */
private boolean shouldMutate(){
    double num = Math.random()*100;
    return (num <= MUTATE);
}

/**
 * Returns a boolean of whether a character should mutate based on the mutation value at top
 */
private void mutate(Chromosome offspring){
    String s = offspring.getBitString();
    int num = s.length();
    int index = (int) (Math.random()*num);
    String newBit = flip(s.substring(index, index+1));
    String newBitString = s.substring(0, index) + newBit + s.substring(index+1, s.length());
    offspring.setBitString(newBitString);
}
/**
 * Flips bits in a string 1 to 0, 0 to 1
 */
private String flip(String s){
    return s.equals("0")? "1":"0";
}

}

import java.lang.Comparable;
import java.math.*;
/**
* Modified from a file created on Jul 9, 2003
* Unsure of original author
* 
*/
public class Chromosome implements Comparable
{
protected String bitString;

/**
 * Constructor for objects of class Chromosome
 */
public Chromosome()
{
}

public Chromosome(int value, int length)
{
    bitString = convertIntToBitString(value, length);
}

public void setBitString(String s)
{
    bitString = s;
}

public String getBitString()
{
    return bitString;
}

public int compareTo(Object o)
{
    Chromosome c = (Chromosome) o;
    int num = countOnes(this.bitString) - countOnes(c.getBitString());
    return num;
}

public double getFitness()
{
    String working = bitString;
    int x1 = Integer.parseInt(working.substring(0,6),2);
    int x2 = Integer.parseInt(working.substring(6),2);
    double result = ScratchGA.functionTest(x1,x2);
    double percentDiff =  ((ScratchGA.getDesired() - result)/ScratchGA.getDesired())*100;
    if (percentDiff >= 0)
    {
    return percentDiff;
}
    else
    {
    return -percentDiff;
}
}

public boolean equals(Object o)
{
    if(o instanceof Chromosome)
    {
        Chromosome c = (Chromosome) o;
        return c.getBitString().equals(bitString);
    }
    return false;
}

public int hashCode()
{
    return bitString.hashCode();
}


public String toString()
{
    return bitString;
}

public static int countOnes(String bits)
{
    int sum = 0;
    for(int i = 0; i < bits.length(); ++ i){
        String test = bits.substring(i, i+1);
        if(test.equals("1")){
            sum = sum + 1;
        }
    }
    return sum;
}

public static String convertIntToBitString(int val, int length)
{
    int reval = val;

    StringBuffer bitString = new StringBuffer(length);
    for(int i = length-1; i >=0; --i ){
        if( reval - (Math.pow(2, i)) >= 0 ){
            bitString.append("1");
            reval = (int) (reval - Math.pow(2, i));
        }
        else{
            bitString.append("0");
        }
    }
    return bitString.toString();
}

public static void main(String[] args
){
    //System.out.println(convertIntToBitString(2046, 10));
    Chromosome c = new Chromosome(1234, 10);
    //System.out.println(c.fitness());
}
}

Answer 1

Actually, it was a simple error that eluded me, that I should have caught. The major issue was in using return (3*x)^(2*y); ^ is a bitwise XOR in java, but an exponent. (Whoops) The problem was rectified using Math.pow(3*x,2*y); ...and a little double check of the fitness function had it up and running with some other minor changes :)