Cracking and Co-Evolving Randomizers
Jan Jannink · The MIT Press eBooks · 2003
This paper discusses two experiments designed to test the applicability of genetic programming to the analysis and the unconstrained construction of randomizers. The first experiment attempts to unravel the structure of a number of generators recommended in the literature by guessing their output, given previous output data. The second examines the possibility that co-evolving populations of programs in a competitive environment can produce randomizers which conform to the criteria without explicitly testing for them. In other words, the requisite properties must emerge from the experiments' nature. The experiments have a convenient representation as a guessing game, closely resembling the two player penny matching problem, in which each player choses heads or tails, and one player hopes to outwit the other in order to prevent a match between the pennies, while the other tries to guess what the first will to do and force a match. Such competition betweenprograms in the genetic programming framework should breed functions whose output sequence is difficult to reproduce. Through this simple mechanism we strive for a further result, a functional approach to randomness, rather than its statistical description. This would have the advantage of being similar to the definition as put forth in information theory. Finally, in addition to introducing novel fitness measurement techniques, these simulations aim to show that the genetic programming paradigm is suitable for building structured models of randomness from limited information, without using the exhaustive traditional tests of randomness. 20.1 Background The themes which pervade the discussion that follows are randomness, game theory, coevolution, information theory and competition, with genetic programming as a binding f...