Comparison of Non-Deterministic Iterative Methods
Éric D. Taillard · ArODES (HES-SO (https://www.hes-so.ch/)) · 2001
Comparing two (or more) heuristic methods based on metaheuristic principles is a difficult task that is not solved yet in a satisfactory way. Indeed these methods are iterative, meaning that the longer they run, the better the solution they produce are. They are also almost all non-deterministic, since they use a pseudo-random number generator. This means that when running twice the same heuristic method, it is possible to obtain two different solutions. There are few deterministic taboo searches (all the other metaheuristic are based on probabilistic choices), but it would be easy to make them non deterministic since they made arbitrary choices, such as the order in which neighbour solutions are examined, the neighbour solution chosen in case of equivalent evaluation, etc.