Genetic Algorithm Evolution of Cellular Automata Rules for Complex Binary Sequence Prediction

摘要

Complex binary sequences were generated by applying a simple threshold, linear transformation to the logistic iterative function, x_(n+1) = rx_n(1 —x_n). Depending primarily on the value of the non-linearity parameter r, the logistic function exhibits a great variety of behavior, including stable states, cycling and periodical activity and the period doubling phenomenon that leads to high-order chaos. Binary sequences of length 2L were used in our computer experiments. The first L bits (first half) were given as input to Cellular Automata (CA) with the task to regenerate the remaining L bits (second half) of the binary sequence in less than L evolution steps of the CA. To perform this task a suitably designed Genetic Algorithm (GA) was developed for the evolution of CA rules. Various complex binary sequences were examined, for a variety of initial values of xo and a wide range of the non-linearity parameter, r. The proposed hybrid prediction algorithm, based on a combination of GAs and CA proved quite efficient.