# ALNS java code with the roulette-wheel-selection?

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?

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;
}