2
$\begingroup$

Currently I am coding the ALNS algorithm for the vehicle routing problem .

I am stuck in the operator selection phase, I did not understand how I can apply this formula: $$p_i=\frac{f_i}{\sum_{j=1}^Nf_j}$$

Please can someone post some little ALNS java code with the roulette-wheel-selection?

$\endgroup$
2
$\begingroup$

The idea behind roulette wheel selection is to use a random number generator to pick an index, so that the probability of index $i$ being selected is your $p_i$. One way to do this is to compute partial sums $s_i = \sum_{j=1}^i p_j$, then generate a random value $u~U(0,1)$ and pick the largest index $i$ for which $u\le s_i$.

Below is a Java function that does it slightly differently. Rather than computing the partial sums, it subtracts each $p_i$ from $u$ until $u$ goes negative, at which point you have the "winning" index. The input vector to the function is your $f$. Since Java uses 0-based indexing, it return an index in $\lbrace 0,\dots,N-1\rbrace$ rather than $\lbrace 1,\dots,N\rbrace$.

  /**
   * Selects an input entry using roulette wheel selection,
   * where the probability of an entry being chosen is proportional to its
   * input value.
   * @param input the vector of input values
   * @param rng the random number generator to use for selection
   * @return the 0-based index of the selected entry
   */
  private int roulette(final double[] input, final Random rng) {
    // Sum the input vector.
    double sum = Arrays.stream(input).sum();
    // Calculate probabilities by dividing inputs by the sum.
    double[] prob = Arrays.stream(input).map((x) -> x / sum).toArray();
    // Generate an observation from the U[0,1] distribution.
    double u = rng.nextDouble();
    // Find the first index for which the cumulative sum of the probabilities
    // is greater than the observation. Rather than summing the probabilities,
    // we subtract each probability from the observation until the difference
    // becomes negative.
    for (int i = 0; i < input.length; i++) {
      u -= prob[i];
      if (u < 0) {
        return i;
      }
    }
    // We should never reach this point, but to appease the compiler we need
    // a return value here. It would have to be the highest index.
    return input.length - 1;
  }
$\endgroup$

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.