pythongenetic-algorithmroulette-wheel-selection

Roulette wheel selection with positive and negative fitness values for minimization


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.


Solution

  • roulette wheel selection

    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.