6
$\begingroup$

I'm studying about different selection methods in genetic algorithm. My question is about 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 on determining 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.
| improve this answer | |
$\endgroup$
  • $\begingroup$ You don't mention "pointers" anywhere in your answer. How is the concept of a pointer, mentioned by Helen, related to what you wrote? $\endgroup$ – nbro Oct 25 '19 at 16:08
  • $\begingroup$ @nbro The "steps" I mention are the spacing between the pointers. I'll update the answer to make that explicit. $\endgroup$ – John Doucette Oct 25 '19 at 17:18
  • $\begingroup$ Thanks for your explanation, but in fact I didn't understand how I can choose the number of pointers or steps dynamically in each iteration. In fact, I want to determine the value of $n$ in each iteration, I want to know how many samples I need in each iteration. I want to know if it is possible to change the distance between pointers in each iteration according to different situations or conditions. $\endgroup$ – helen Oct 28 '19 at 11:39
  • $\begingroup$ @JohnDoucette I had another question about this line:"When fitness levels are all within a narrow band, use low values of n to encourage more exploration.": Here shouldn't we use higher values of n to encourage more exploitation? Because as far as I know, when fitness values are close, it means that we should start searching locally for finding the best value. $\endgroup$ – helen Jan 15 at 8:36
  • $\begingroup$ @helen Yep, good catch. I'll update the answer. $\endgroup$ – John Doucette Jan 15 at 15:42

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.