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.