Roulette wheel selection with positive and negative fitness values for minimization

Question

I'm doing a genetic algorithm where each inidividual generates 3 new offsprings. The new individuals are evaluated using the fitness function, which may return negative and positive values. What is the correct approach to choose between the offsprings using the roulette wheel selection if I want to minimize?

Some possible values of the fitness function are: fitness_offspring_1 = -98.74; fitness_offspring_2 = -10.1; fitness_offspring_3 = 100.31

I'm working on Python but I only need the idea so I can implement it by myself.

Answer 1

Roulette wheel selection is simply assigning probability values proportional to an individuals fitness. And then randomly selecting from that distribution. Fit individuals get a better chance at being selected, while less-fit individuals get lower chances.

You can easily adapt this to your code by using the offspring list instead of the individuals.

Lets start with as simple pseudo-codeish implementation in python, you can modify it to your needs:

fitness_sum = sum([ind.fitness for ind in individuals])
probability_offset = 0

for ind in individuals:
    ind.probability = probability_offset + (ind.fitness / fitness_sum)
    probability_offset += ind.probability

r = get_random_float()

selected_ind = individuals[0] # initialize
for ind in individuals:
    if ind.probability > r:
        break; 
    selected_ind = ind

Now, the code above (by the nature of roulette wheel) assumes all fitness values are positive. So in your case we need to normalize it. You can simply sum all values by the absolute value of smallest offspring. But that would make its probability 0 so you could simply add a bias to all to give it a slight chance as well.

Lets see how it works with simple values, say [1, 5, 14]

fitness_sum = 20
previous_probability = 0

# iterating first for loop:
individual[0].fitness => 0 + 1 / 20 = 0.05
individual[1].fitness => 0.05 + 5 / 20 = 0.3 
individual[2].fitness => 0.3 + 14 / 20 = 1

# We created the wheel of probability distributions, 
# 0 - 0.05 means we select individual 0
# 0.05 - 0.3 means we select individual 1 etc...

# say our random number r = 0.4

r = 0.4
selected_ind = individual_0

# iterating second for loop:
# 0.05 > 0.4 = false
selected_ind = individual_0
# 0.3 > 0.4 = false
selected_ind = individual_1
# 1.0 > 0.4 = true
break

I'm sure there are much better pseudo-codes or implementations in python you can search for. Just wanted to give you an idea.

Answer 2

This is how I implemented it in JavaScript, to give you a general idea:

    var totalFitness = 0;
    var minimalFitness = 0;

    for(var genome in this.population){
      var score = this.population[genome].score;
      minimalFitness = score < minimalFitness ? score : minimalFitness;
      totalFitness += score
    }

    minimalFitness = Math.abs(minimalFitness);
    totalFitness += minimalFitness * this.popsize;

    var random = Math.random() * totalFitness
    var value = 0;

    for(var genome in this.population){
      genome = this.population[genome];
      value += genome.score + minimalFitness;
      if(random < value) return genome;
    }

    // if all scores equal, return random genome
    return this.population[Math.floor(Math.random() * this.population.length)];

However, just as @umutto has mentioned, this gives the genome with the lowest score no chance of being selected. So you could artificially add a little bit of fitness to each genome, so that even the lowest invidivudla has a chance. Note: I didn't implement that small bias in the above code @umutto mentioned.

Answer 3

For using Roulette wheel selection for minimization, you have to do two pre-processing steps:

1. You have to get rid of the negative fitness values, because the fitness value will represent the selection probability, which can't be negative. The easiest way for doing this, is to subtract the lowest (negative) value from all fitness values. The lowest fitness value is now zero.
2. For minimizing, you have to revert the fitness values. This is done by setting the fitness values to max fitness - fitness. The individual with the best fitness has now the highest fitness value.

The transformed fitness values are now feed into the normal Roulette wheel selector, which selects the individual with the highest fitness. But essentially you are doing a minimization.

The Java GA, Jenetics, is doing minimization in this way.

Answer 4

Here's what I use. The 'simple' solution as I see it is to scale all fitness to a common range, e.g., [1.0 .. 10.0]. It manages multiple unique selections (see Cohort_Size) and generalizes across ranges of fitness values . . .

auto Selector::select_roulette(const Pool& pool, Set& indices) const -> void
{
    const auto& fitness = pool.fitness().scale(1, 10);
    const auto sum = fitness.sum();
    const auto num = fitness.enumerate();
    while (indices.size() <= Cohort_Size)
        for (auto p = uniform_real(sum); const auto && [i, pi] : num)
            if (p -= pi; p <= 0.0)
            {
                indices.insert(i);
                break;
            }
}