Answers.Body: <p>As originally conceived in James Baker's 1989 paper <a href="https://books.google.com/books?hl=en&amp;lr=&amp;id=MYJ_AAAAQBAJ&amp;oi=fnd&amp;pg=PA14&amp;dq=Reducing%20Bias%20and%20Inefficiency%20in%20the%20Selection%20Algorithm&amp;ots=XwtGqi3xGF&amp;sig=ldv4xuElciFpR_XbEITj-9pbzQs#v=snippet&amp;q=stochastic%20universal&amp;f=false" rel="nofollow noreferrer">Reducing bias and inefficiency in the selection algorithm</a>, Stochastic Universal Sampling accepts a population containing <span class="math-container">$N$</span> individuals, and a <em>number of parents to sample</em>, denoted <span class="math-container">$n$</span>. Assuming fitness values are normalized so that they sum up to <span class="math-container">$N$</span>, at each step, a new pointer is placed a step equal in size to the fraction <span class="math-container">$\frac{N}{n}$</span> 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, <span class="math-container">$\frac{N}{n}$</span>) ). So, for example, if you want to sample 6 individuals from a population of size 10, you would make steps of size <span class="math-container">$\frac{10}{6}$</span>, spacing your pointers at even intervals of <span class="math-container">$\frac{10}{6}$</span>.</p>
  
  <p>Modern implementations, like the one on <a href="https://en.wikipedia.org/wiki/Stochastic_universal_sampling" rel="nofollow noreferrer">Wikipedia</a> 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 <span class="math-container">$\frac{F}{n}$</span>, where <span class="math-container">$F$</span> 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.</p>
  
  <p>So in summary, the step size <span class="math-container">$\frac{F}{n}$</span> used if fitness values of a population sum to <span class="math-container">$F$</span>, and you want to select <span class="math-container">$n$</span> individuals. If you want to select more individuals, use a higher value for <span class="math-container">$n$</span>. If you want to select fewer, use a lower value for <span class="math-container">$n$</span>, which updates your step size accordingly.</p>
  
  <p>Values of this parameter of <span class="math-container">$\frac{1}{4}$</span> or <span class="math-container">$\frac{1}{6}$</span> 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 <span class="math-container">$\frac{1}{4}$</span> of the population" and "Select <span class="math-container">$\frac{1}{6}$</span> of the population". </p>
  
  <p>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 <a href="https://en.wikipedia.org/wiki/Reinforcement_learning#Exploration" rel="nofollow noreferrer">exploration/exploitation tradeoff</a>. </p>
  
  <p>Some ways you might pick <span class="math-container">$n$</span>:</p>
  
  <ol>
  <li>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 <a href="https://machinelearningmastery.com/k-fold-cross-validation/" rel="nofollow noreferrer">cross validation</a>, and pick whichever one seems to work best.</li>
  <li>You can use a value that changes over time. A common strategy for this would be to use one of the <a href="https://www.fys.ku.dk/~andresen/BAhome/ownpapers/permanents/annealSched.pdf" rel="nofollow noreferrer">temperature schedules developed in the simulated annealing literature</a>, and keep a portion of the population that was inversely proportionate to the temperature. That is, early on, you'd use a large <span class="math-container">$n$</span>, and keep most of the population around (probably with mutations). Later, you'd use a small <span class="math-container">$n$</span> and keep only the best individuals around.</li>
  <li>You could use a value of <span class="math-container">$n$</span> that changes in response to the fitness of the population. This is much like the <a href="https://towardsdatascience.com/gradient-descent-algorithms-and-adaptive-learning-rate-adjustment-methods-79c701b086be?gi=12bf1035e653" rel="nofollow noreferrer">adaptive learning rates</a> 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 <span class="math-container">$n$</span> to encourage more exploitation. When fitness levels are all within a narrow band, use high values of <span class="math-container">$n$</span> to encourage more exploration. </li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-15T16:16:06.040Z
Answers.Text: 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)?
Answers.UserDisplayName: helen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-01-15T16:24:58.213Z
Answers.Text: @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.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-25T15:51:39.550Z
Answers.LastActivityDate: 2020-01-15T15:42:40.400Z
Answers.LastEditDate: 2020-01-15T15:42:40.400Z
Answers.UserDisplayName: John Doucette
Body: <p>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.</p>
  <p>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?</p>
  
Tags: <genetic-algorithms><selection-operators><stochastic-universal-sampling>
Title: How is the distance between pointers in Stochastic Universal Sampling determined?
UserDisplayName: helen
ThreadText: # How is the distance between pointers in Stochastic Universal Sampling determined?
  
  (Asked by: username_0 on 2019-10-08)
  
  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?
  
  **Tags:** genetic-algorithms, selection-operators, stochastic-universal-sampling
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-10-25. Score: 2 | Accepted answer
  
  As originally conceived in James Baker's 1989 paper [Reducing bias and inefficiency in the selection algorithm](https://books.google.com/books?hl=en&lr=&id=MYJ_AAAAQBAJ&oi=fnd&pg=PA14&dq=Reducing%20Bias%20and%20Inefficiency%20in%20the%20Selection%20Algorithm&ots=XwtGqi3xGF&sig=ldv4xuElciFpR_XbEITj-9pbzQs#v=snippet&q=stochastic%20universal&f=false), 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](https://en.wikipedia.org/wiki/Stochastic_universal_sampling) 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](https://en.wikipedia.org/wiki/Reinforcement_learning#Exploration).
  
  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](https://machinelearningmastery.com/k-fold-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](https://www.fys.ku.dk/~andresen/BAhome/ownpapers/permanents/annealSched.pdf), 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](https://towardsdatascience.com/gradient-descent-algorithms-and-adaptive-learning-rate-adjustment-methods-79c701b086be?gi=12bf1035e653) 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.
  
  > **Comments:**
  > **username_0**: 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)?  
  > **username_1**: @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.  
  
  ---
  
  