Search heuristics and the influence of non-perfect randomness: examining Genetic Algorithms and Simulated Annealing

Simulated Annealing and Genetic Algorithms are important methods to solve discrete optimization problems and are often used to find approximate solutions for diverse NP-complete problems. They depend on randomness to change their current configuration and transition to a new state. In Simulated Annealing, the random choice influences the construction of the new state as well as the acceptance of that new state. In Genetic Algorithms, selection, mutation and crossover depend on random choices. We experimentally investigate the robustness of the two generic search heuristics when using pseudorandom numbers of limited quality. To this end, we conducted experiments with linear congruential generators of various period lengths, a Mersenne Twister with artificially reduced period lengths as well as quasi-random numbers as the source of randomness. Both heuristics were used to solve several instances of the Traveling Salesman Problem in order to compare optimization results. Our experiments show that both Simulated Annealing and the Genetic Algorithm produce inferior solutions when using random numbers with small period lengths or quasi-random numbers of inappropriate dimension. The influence on Simulated Annealing, however, is more severe than on Genetic Algorithms. Interestingly, we found that when using diverse quasi-random sequences, the Genetic Algorithm outperforms its own results using quantum random numbers.