Roulette Selection in Genetic Algorithms

Question

I have the following code:

g = lambda a, b, c: sum(a, b, c)
print g([4,6,7])

How do I get the lambda function to expand the list into 3 values?

Solution 1

It's been a few years since i've done this myself, however the following pseudo code was found easily enough on google.

for all members of population
    sum += fitness of this individual
end for

for all members of population
    probability = sum of probabilities + (fitness / sum)
    sum of probabilities += probability
end for

loop until new population is full
    do this twice
        number = Random between 0 and 1
        for all members of population
            if number > probability but less than next probability 
                then you have been selected
        end for
    end
    create offspring
end loop

The site where this came from can be found here if you need further details.

Solution 2

The pseudocode posted contained some unclear elements, and it adds the complexity of generating offspring in stead of performing pure selection. Here is a simple python implementation of that pseudocode:

def roulette_select(population, fitnesses, num):
    """ Roulette selection, implemented according to:
        <http://stackoverflow.com/questions/177271/roulette
        -selection-in-genetic-algorithms/177278#177278>
    """
    total_fitness = float(sum(fitnesses))
    rel_fitness = [f/total_fitness for f in fitnesses]
    # Generate probability intervals for each individual
    probs = [sum(rel_fitness[:i+1]) for i in range(len(rel_fitness))]
    # Draw new population
    new_population = []
    for n in xrange(num):
        r = rand()
        for (i, individual) in enumerate(population):
            if r <= probs[i]:
                new_population.append(individual)
                break
    return new_population

Solution 3

This is called roulette-wheel selection via stochastic acceptance:

/// \param[in] f_max maximum fitness of the population
///
/// \return index of the selected individual
///
/// \note Assuming positive fitness. Greater is better.

unsigned rw_selection(double f_max)
{
  for (;;)
  {
    // Select randomly one of the individuals
    unsigned i(random_individual());

    // The selection is accepted with probability fitness(i) / f_max
    if (uniform_random_01() < fitness(i) / f_max)
      return i;
  }   
}

The average number of attempts needed for a single selection is:

τ = f_max / avg(f)

• f_max is the maximum fitness of the population
• avg(f) is the average fitness

τ doesn't depend explicitly on the number of individual in the population (N), but the ratio can change with N.

However in many application (where the fitness remains bounded and the average fitness doesn't diminish to 0 for increasing N) τ doesn't increase unboundedly with N and thus a typical complexity of this algorithm is O(1) (roulette wheel selection using search algorithms has O(N) or O(log N) complexity).

The probability distribution of this procedure is indeed the same as in the classical roulette-wheel selection.

For further details see:

• Roulette-wheel selection via stochastic acceptance (Adam Liposki, Dorota Lipowska - 2011)

Solution 4

Here is some code in C :

// Find the sum of fitnesses. The function fitness(i) should 
//return the fitness value   for member i**

float sumFitness = 0.0f;
for (int i=0; i < nmembers; i++)
    sumFitness += fitness(i);

// Get a floating point number in the interval 0.0 ... sumFitness**
float randomNumber = (float(rand() % 10000) / 9999.0f) * sumFitness;

// Translate this number to the corresponding member**
int memberID=0;
float partialSum=0.0f;

while (randomNumber > partialSum)
{
   partialSum += fitness(memberID);
   memberID++;
} 

**// We have just found the member of the population using the roulette algorithm**
**// It is stored in the "memberID" variable**
**// Repeat this procedure as many times to find random members of the population**

Solution 5

From the above answer, I got the following, which was clearer to me than the answer itself.

To give an example:

Random(sum) :: Random(12) Iterating through the population, we check the following: random < sum

Let us chose 7 as the random number.

Index   |   Fitness |   Sum |   7 < Sum
0       |   2   |   2       |   false
1       |   3   |   5       |   false
2       |   1   |   6       |   false
3       |   4   |   10      |   true
4       |   2   |   12      |   ...

Through this example, the most fit (Index 3) has the highest percentage of being chosen (33%); as the random number only has to land within 6->10, and it will be chosen.

    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
    }       
    double rand = (((double)rand() / (double)RAND_MAX) * sum);
    sum = 0;
    for (unsigned int i=0;i<sets.size();i++) {
        sum += sets[i].eval();
        if (rand < sum) {
            //breed i
            break;
        }
    }

View more solutions

Comments

[rampion]

You may be able to make this more efficient by doing a binary search on the probability array (rather than an iterative search).

[gpampara]

Please note that this algorithm will not function as expected for minimization problems. It is a common problem with the Roulette Selection (fitness proportionate selection).

[WSBT]

Fitness score should be assigned in a way such that higher score is always more favourable. For minimization problems, the invert is usually taken. For example, to minimize the sum of x and y, a fitness function could be written as fitness = 1 / (x + y).

[user1520427]

@JarodElliott I might be missing something, but that psuedocode doesn't look correct. The later values in probability could well be greater than 1 and will therefore never be selected.. number should be number = (Random between 0 and 1) * sum of probabilities shouldn't it?

[zhangyangyu]

You answer is wrong, the sum can not accept there arguments.

[smac89]

This is an example, I am trying to do something else but the lambda parameters are what I wanted to know about.

[Mateusz Kacprzak]

@user1520427 probability serves as a prefix sum such that the last member of population has a probability of 1.

[CatsLoveJazz]

@Jarod Elliott do the population fitnesses need to be sorted in this example?

[Zimano]

Would also like to know if they should be sorted.

[Zimano]

Should the members be sorted?

[Jacob Garby]

Would still like to know if they should be sorted.

[Jacob Garby]

Actually, you know, I'm assuming they don't need to be sorted, since a ctrl+f "sort" on the wikipedia page returns nothing.

[OscarVanL]

When you use the roulette selection, the members of the population must be sorted by ascending probability calculations. However, this will already be the case as the probabilities are calculated as an increasing sum, with the last individual in the list having a probability of 1. As long as you don't re-order your population between the second for-loop and the final loop, this doesn't require sorting.