Roulette selection function for a genetic algorithm

Question

So I've written a roulette selection function for my genetic algorithm which follows:

public String tournament(float fitness, Chromosome pop[], int selection)
{
    // roulette
    if (selection == 1)
    {
        Random random = new Random();
        float slice = random.nextFloat() * fitness;

        float curFitness = 0.0f;

        for (int i = 0; i < initialPopulation; i++)
        {
            curFitness += pop[i].fitness;

            if (curFitness >= slice)
                return pop[i].bits;
        }
    }
    return "";
}

The problem is that it is sometimes returning the blank string, which has only been placed their to satisfy the return condition. This is generally not a problem, but during some runs it causes the GA to terminate since the next step involves the crossover stage. Any ideas?

under what condition will you fail to return from the statement in the loop? Why is that happening? Put in some debug lines and find out. Or run it with the debugger. — Tony Ennis, Oct 28 '10 at 22:46
I realize that I am a bit late to this party, but user the 'fitness' value that you are passing into this function, is it the sum of all the individual fitnesses? Just curious as to how this works. — flavour404, Apr 29 '11 at 20:32

score 2 · Answer 1 · answered Oct 28 '10 at 23:22

So it turns out the mutation function was occasionally nulling some of my bit strings, which was causing the population to contain empty strings.

Before, it looked like this:

public String mutate(String bits)
{   
    Random random = new Random();
    StringBuffer buf = new StringBuffer(bits);
    for (int i = 0; i < bits.length(); i++)
    {
        if (random.nextFloat() < mutationRate)
        {
            if (bits.charAt(i) == '1')
            {
                buf.setCharAt(i, '0');
                                    return buf.toString();

            }
            else
            {
                buf.setCharAt(i, '1');
                                    return buf.toString();
            }
        }
    }
    return "";
}

And I changed it to this:

public String mutate(String bits)
{   
    Random random = new Random();
    StringBuffer buf = new StringBuffer(bits);
    for (int i = 0; i < bits.length(); i++)
    {
        if (random.nextFloat() < mutationRate)
        {
            if (bits.charAt(i) == '1')
            {
                buf.setCharAt(i, '0');
            }
            else
            {
                buf.setCharAt(i, '1');
            }
        }
    }
    return buf.toString();
}

Careless mistake.

score 0 · Answer 2 · answered Oct 28 '10 at 22:51

My guess would be that the problem is that your fitness is occasionally less than the sum of your pop[i].fitnesses. Try putting a return "ERROR: " + fitness + " / " + curFitness; line after the for loop but within the if, or something of that nature, and see what gets returned.

Roulette selection function for a genetic algorithm

2 Answers2