How random number generator quality affects simple genetic algorithm performance.

摘要

Genetic Algorithms (GAs) are computer programs that simulate evolutionary processes in order to solve difficult problems in diverse areas such as function optimization, scheduling, engineering, and many others. GAs simulate evolution through operations that mimic sexual reproduction, biological mutation, and natural selection. GAs are stochastic algorithms, that is, they rely on randomness for their function.; Since truly random sequences of numbers cannot be generated by computer programs, GAs rely on pseudo-random number generators (PRNGs) as their source of randomness. PRNGs are computer algorithms that produce sequences of numbers that appear to be random. PRNGs of varying quality have been developed over the last sixty years. PRNGs that are of higher quality produce sequences of numbers that satisfy more stringent statistical and theoretical tests than do PRNGs of lower quality.; GAs are by no means the only type of stochastic algorithms. In the past, other types of stochastic algorithms have been shown to be sensitive to the quality of PRNG employed. However, before we began the research described in this report, the relationship between PRNG quality and the performance of simple GAs had not been studied. Our research has been undertaken to begin to understand the relationship between PRNG quality and GA performance.; This report details a sequence of studies we performed to examine this relationship. We found that PRNG quality does, in fact, impact GA performance, albeit not in the expected manner. We found that PRNGs of poor quality sometimes caused degraded GA performance, while for other problems the same PRNGs caused improved performance. We have shown that this curious behavior can be explained by the GA theory developed by Vose [Vos99]. In addition, we have constructed an empirical test of PRNG quality tailored to the GA that is able to predict when a specific PRNG is likely to cause unexpected GA performance.