"Anyone who attempts to generate random numbers by
deterministic means is, of course, living in a state of sin."
John Von Neumann
The GIF below shows the evolving outputs of Pseudo Random Number Generators (PRNGs) produced by the Genetic Program I implemented in C.
See the Wiki pages on Genetic Algorithms & Programming, Entropy and Koza's paper [1] for supporting information to this post.
Each PRNG in the population outputs 16384 "random" bits / 2048 bytes. Fitness (or "randomness") of a PRNG is measured using the Shannon Entropy equation for binary sub sequences of size $h$ from $1 \to N_{max} = 8$, across the 2Kb output. For each sub sequence of size $h$;
$E_{h} = - \sum_{j} P_{(hj)}\ \log_2\ P_{(hj)}$
therefore the total entropy of a PRNG output for binary sub sequences of size $h$ from $1 \to N_{max} = 8$;
$E_{total} = \sum_{h = 1}^{N_{max}} \left[ - \sum_{j} P_{(hj)}\ \log_2\ P_{(hj)} \right]$
Therefore in order to achieve maximum entropy for $E_h$, all probabilities for all $2^h$ binary sub sequences of length $h$ must be equal to $\frac{1}{2^h}$.The maximum achievable entropy for sub seqences of sizes $1 \to 8$ can be calculated as;
$E_{max} = \sum_{i = 1}^{8} i = \frac{8 \cdot (8 + 1)}{2} = 36$
For this run the population is evolved over 39 Generations. The entropy is evolved rapidly to begin with and then fluctuates around 97~99%* until on the 39th generation it reaches the terminating entropy of 99.93% (or 35.97386 bits of entropy out of a maximum 36 bits). Each frame in the GIF shows the output of the fittest PRNG in the population at that generation.
May the lord have mercy on my soul!
[1] John R. Koza, Evolving a Computer Program to Generate Random Numbers Using the Genetic Programming Paradigm. Stanford University, 1991.
.png)
