0

I am trying to implement a roulette wheel selection. I have understood this algorithm:

  1. Calculate the sum S of all chromosome fitnesses in population
  2. Generate a random number, r, from interval (0,S)
  3. Loop through the population and sum fitnesses from 0 till S, this is the partial sum, call it P.
  4. When the P > S: stop and return the corresponding chromosome.

What I don't understand is how this corresponds to doing this instead: Roulette wheel selection algorithm (the answer with 44 votes). This makes sense to me, but not the one above.

Green
  • 3
  • 4

2 Answers2

0

In the answer with 44 votes, the range has been normalised between 0 to 1 which is easier to understand but requires extra steps for calculations.

You can implement the approach you mentioned. In that while calculating the sum, each individual chromosome adds its own value, so when a random number is generated between 0 and S we assume that if r is between 2 numbers whose range is equal to the above mentioned value, it is chosen with the probability proportional to its fitness value. The bigger the value the more is the probability of r to come in its range.

For example, lets say that a chromosome having a fitness of 23 (assumption) is the 5th chromosome when you iterate and the total sum S is 130. The sum of the first 4 chromosomes is, lets say, 54. So if random r is between 55 and 77 (both inclusive), this chromosome is chosen.

After normalisation, 55/130 ~= 0.423 and 77/130 ~= 0.5923 is the range a random number r2 (between 0 and 1) should fall for this chromosome to be selected.

guroosh
  • 642
  • 6
  • 18
  • But, what does adding each chromosomes fitness value mean? I mean why do we to that? In the other answer its clear that we divide the range 0 to 1 up into a number of non-overlapping segments, corresponding to the number of chromosones. Each segment is proportional to the fitness of one of the ten item. Then you just generate a random number and see in which range it lies in. Doing this, we don't keep adding the fitness of each chromosone. – Green Feb 13 '19 at 16:01
  • How will you make **number of non-overlapping segments, corresponding to the number of chromosones**. For example, how will you know that a chromosome of fitness value 23 in a population of 130 will correspond to 0.1769 length segment and how will you choose it? – guroosh Feb 13 '19 at 19:22
  • Its just as the answer with 44 votes explained. You just divide the circle diagram according to each chromosome fitness proportionality. – Green Feb 14 '19 at 13:14
  • Yes, but to know the proportion of a chromosome you will have to divide its fitness value by the total fitness value of the population, hence you will have to find the sum. That's why we do the sum. Once we have the sum, its the implementer's choice of whether to normalise every thing between 0 and 1 by dividing everything by 130 (the sum), where 130 (fitness value of the total population) becomes 1; and 23 (value of a single chromosome) becomes 23/100 ~= 0.1769. So to answer the original question **How does this algorithm corres...tte wheel selection?**, the 44 votes has been normalised. – guroosh Feb 14 '19 at 14:11
0

The following is done using the sum

def choose_parent_using_RWS(genes, S, points):
    P = randint(0, int(S))
    for x in genes:
        P += evaluate(x, points)
        if P > S:
            return x
    return genes[-1]

the following is done by normalizing between 0 and 1

def choose_parent_using_RWS(genes, S, points):
    P = randint(0, int(S))/S
    for x in genes:
        P += evaluate(x, points)/S
        if P > S/S:
            return x
    return genes[-1]
guroosh
  • 642
  • 6
  • 18
  • I have a follow up question. The random number shouldnt be added to the first chromosome. Shouldn't it be if r (i.e. the random number) < P choose x? – Green Feb 14 '19 at 19:43
  • Quote: `Shouldn't it be if r (i.e. the random number) < P`, P is the random number since `P = randint(0, int(S))`, otherwise I didnt understand. – guroosh Feb 15 '19 at 10:05
  • Okey, I thought that P is the partial sum, since we keep on adding the fitnesses. Then in my mind we should have a random number call it r. So when r < P then we choose x. – Green Feb 15 '19 at 22:48
  • we need the position of the chromosome we need to choose. When it is P > S choose x, here `P = initial random number r + the sum of all fitness up to and including x`. – guroosh Feb 16 '19 at 20:09