1
$\begingroup$

I found in the literature that Adaptive Large Neighborhood Search (ALNS), which uses a roulette mechanism to select the best-performing operators, is the most efficient method. However, other approaches use other selection mechanisms such as choice function.

What are the most known disadvantages of the roulette selection mechanism compared to the choice function mechanism?

$\endgroup$
1
4
$\begingroup$

The roulette selection mechanism is a kind of choice function. Thus, the question is not well stated. What is the other choice function you consider against roulette selection?

The roulette selection is a randomized, possibly biased, choice function. Randomization is an important ingredient of the efficiency of neighborhood search approaches in combinatorial optimization. At each new iteration of the search, the idea is to select the best-performing operators with a higher probability and the worst-performing ones with a lower probability. The choice is randomized to ensure diversification and avoid bias for a given instance to solve. It also favors the robustness of the search when solving instances that possibly have a different combinatorial structure.

There is no particular drawback to use the roulette selection. It can be implemented quite easily in its simplest form while almost nothing in terms of running time. Indeed, you have to add some counters in your algorithm that count successes or failures for each operator and then implement your roulette choice function.

We prefer to use a quick and dirty pseudo-random number generator, like linear congruential generators, in roulette selection. By experience, the random sequence's quality is not critical in such a context, even if you perform millions of moves over the search.

Some examples of roulette selection approach for variable neighborhood search can be found in the papers below:

B. Estellon, F. Gardi, K. Nouioua (2008). Two local search approaches for solving real-life car sequencing problems. In Special Issue: The Car Sequencing Problem (C. Solnon, V.D. Cung, A. Nguyen, C. Artigues, eds.), European Journal of Operational Research 191(3), pp. 928-944. pdf

T. Benoist, B. Estellon, F. Gardi, A. Jeanjean (2011). Randomized local search for real-life inventory routing. Transportation Science 45(3), pp. 381-398. pdf (extended version pdf)

$\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.