Evolution of Pseudo Randomness

                "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!

* The implementation isn't driven by hill climbing.

[1] John R. Koza, Evolving a Computer Program to Generate Random Numbers Using the Genetic Programming Paradigm. Stanford University, 1991.