6
$\begingroup$

I'm studying about different selection methods in genetic algorithms. My question is about the Stochastic Universal Sampling (SUS) selection method. I know that each individual will occupy a segment of the line according to its fitness value and then equally spaced pointers will be placed over this line.

I want to know how the distance between pointers is determined. I have seen 1/6 and 1/4 as the distance between pointers. I want to choose the number of pointers dynamically according to the situation. I want to know what conditions or factors affect the determination of this distance. For example, when do we decide to choose 1/4 as distance? I want to know if it is possible to change the number of samples in each iteration according to different conditions or situations. If so, what are these conditions?

$\endgroup$
2
$\begingroup$

As originally conceived in James Baker's 1989 paper Reducing bias and inefficiency in the selection algorithm, Stochastic Universal Sampling accepts a population containing $N$ individuals, and a number of parents to sample, denoted $n$. Assuming fitness values are normalized so that they sum up to $N$, at each step, a new pointer is placed a step equal in size to the fraction $\frac{N}{n}$ ahead of the location of the previous pointer (and the location of the first pointer is set to a random value in the range [0, $\frac{N}{n}$) ). So, for example, if you want to sample 6 individuals from a population of size 10, you would make steps of size $\frac{10}{6}$, spacing your pointers at even intervals of $\frac{10}{6}$.

Modern implementations, like the one on Wikipedia sometimes do not document this fact clearly, although it is apparent what is intended if you already understand the method. They often write the step size as $\frac{F}{n}$, where $F$ is the total fitness of the population, without discussing its relation to the size of the population. The extra normalization step is actually not essential, so modern implementations generally seem to skip it.

So in summary, the step size $\frac{F}{n}$ used if fitness values of a population sum to $F$, and you want to select $n$ individuals. If you want to select more individuals, use a higher value for $n$. If you want to select fewer, use a lower value for $n$, which updates your step size accordingly.

Values of this parameter of $\frac{1}{4}$ or $\frac{1}{6}$ suggest that the implementation may be normalizing the sum of fitness values is being normalized to N, and then using the parameter as a multiplicative factor automatically. This is a fairly reasonable design. You could interpret these values as "Select $\frac{1}{4}$ of the population" and "Select $\frac{1}{6}$ of the population".

Note that this sort of bumps your question up a level: how do you pick the fraction of the population to keep? That question doesn't have a clean answer, and picking it is generally an art developed by experts through practice. It is very closely related to the exploration/exploitation tradeoff.

Some ways you might pick $n$:

  1. Use a fixed value, for instance, keep half the population at each step. The exact proportion you will want to pick is not something you can know in advance. Expert practitioners can make effective guesses. Others will need to just try out different values using a technique like cross validation, and pick whichever one seems to work best.
  2. You can use a value that changes over time. A common strategy for this would be to use one of the temperature schedules developed in the simulated annealing literature, and keep a portion of the population that was inversely proportionate to the temperature. That is, early on, you'd use a large $n$, and keep most of the population around (probably with mutations). Later, you'd use a small $n$ and keep only the best individuals around.
  3. You could use a value of $n$ that changes in response to the fitness of the population. This is much like the adaptive learning rates used in some algorithms to train neural networks (most notably: the ADAM optimizer). When fitness levels have a lot of variety, use low values of $n$ to encourage more exploitation. When fitness levels are all within a narrow band, use high values of $n$ to encourage more exploration.
$\endgroup$
2
  • $\begingroup$ I'm a little confused @JohnDoucette. When fitness values are very different, doesn't it mean that we are in the exploration phase and we should choose more chromosomes from population (so higher number of n)? When our fitness values are near to each other, doesn't it mean that we are in the exploitation phase, so we can choose fewer chromosomes (so lower number of n)? $\endgroup$
    – helen
    Jan 15 '20 at 16:16
  • $\begingroup$ @helen The right adaptive learning rate will depend on your problem. In my answer, I've suggested that if you're seeing a very large variety, you can afford to exploit more. If you're seeing very little variety, you can afford to explore more. $\endgroup$ Jan 15 '20 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.