CODEWITHSUNDEEP
javagenetic-algorithmgenetic-programming
Jacob N.
Jacob N.

Reputation: 3

Genetic Algorithm Fitness Score Issue

I am trying to write a java program that generates a population of random characters and eventually lands at an inputted string to simulate something like the infinite monkey theorem (https://en.wikipedia.org/wiki/Infinite_monkey_theorem). The issue I am having is as I am testing it, all of the starting population have a fitness level of 0 so nothing gets added to the mating pool during the natural selection process. Here is what the project entails.

Target: the string "Hello"

Mutation Rate: 0.01

Population Max: 100 DNA objects each containing a char[] array for the genes.

Here is my function for calculating the fitness:

public void calcFitness(String target){
        double score = 0.0;
        for(int i = 0; i < this.genes.length; i++){
            if(this.genes[i] == target.charAt(i)){
                score++;
            }
        }
        this.fitness = score/this.genes.length;
    }

I am new to genetic programming and not sure what I am doing wrong, any help would be appreciated and any tips or insight about genetic programming would also be appreciated.

EDIT

Here is the code for the selection process:

 public void naturalSelection(){
        ArrayList<DNA> selection = new ArrayList<>();
        Random rand = new Random();
        String child = "";
        DNA[] newPop = new DNA[popMax];
        for(int i = 0; i < population.length; i++){
            for(int j = 0; j < population[i].getFitness(); j++){
                selection.add(population[i]);
            }
        }
        for(int i = 0; i < selection.size(); i++){
            int parentSelect = rand.nextInt(selection.size());
            DNA parent1 = selection.get(parentSelect);
            child = parent1.split(true);
            parentSelect = rand.nextInt(selection.size());
            DNA parent2 = selection.get(parentSelect);
            child += parent2.split(false);
            newPop[i] = new DNA(child);
        }
        double mutation = rand.nextDouble();
        if(mutation < this.mutationRate){
            this.population = swapMutation(newPop);
            calcFittest();
        }
        else{
            this.population = newPop;
            calcFittest();
        }
    }

Where swap mutation swaps two random chars if mutation occurs.

Upvotes: 0

Views: 736

Answers (2)

WillEnsaba
WillEnsaba

Reputation: 777

I just finished a GA for infinite monkey theorem. You may find at https://github.com/Willtl/infinite_monkey_theorem

It is in C++ but it would not be difficult to do the same in Java. You can open the project it using Eclipse CPP.

void Individual::calculateFitness(vector<char> chromosomePlate) {
fitness = 0;

for (int i = 0; i < chromosome.size(); i++) {
    int gene = (int) chromosome[i];
    int genePlate = (int) chromosomePlate[i];
    if (gene == genePlate && gene != 32) {
            fitness++;
    }
}

First of all, when I read the input I put it to lower case. Then to make it easy to randomize and compare, I am using ASCII. So as I am just considering lower case my characters range goes from 97 to 122. I also keep the spaces at the chromosome, however in the fitness function I ignore it (32).

Anything that you need just post here I will be more than happy to help.

Upvotes: 0

Piers Williams
Piers Williams

Reputation: 182

I would suggest using a fitness function that measures distance from a candidate to the target string. You would then minimise overall fitness instead of maximising.

To do this:

public void calcFitness(String target){
    double score = 0.0;
    for(int i = 0; i < this.genes.length; i++){
        score += Math.abs((int)this.genes[i] - (int)target.charAt(i));
    }
    this.fitness = score / this.genes.length;
}

This should work better because it will differentiate each candidate much better. Without seeing the random string generator you are using it is hard to say but it is likely that the number of possible candidates is astronomical with a very low chance that any of them score a single point with your fitness function.

Might also be worth pointing out that your code is likely part of a Genetic Algorithm rather than Genetic Programming.

If you want to improve the selection I would recommend as an easy to program technique Tournament Selection - choose n random individuals from the population and then select the best fitness individual from the n individuals. This gives better candidates a higher chance of being selected than other individuals and has the added bonus that you don't need to calculate fitness for every individual in a population.

Upvotes: 1

Related Questions