Dynamics Behavior Analysis And Inverse Problem Research Of Cellular Automata

In this paper, we study the mathematical characteristics, evolving dynamics behavior and inverse problem of one-dimension two-value cellular automata. The main content of this paper is as follows:One kind of one-dimension two-value cellular automata in the Galois Field named additive cellular automata is studied. The running mechanism of the additive cellular automata is introduced and the examples of group cellular automata and non-group cellular automata are given. An necessary condition, GF(2) cellular automata has the circle which length is K, is educed. Besides, gives the necessary and sufficient condition that the K circle includes the 0 element. Those are K circle theoryⅠandⅡ.The complexity of cellular automata dynamic behavior is studied. According analyzing the signification of the "Edge of Chaos" and emergence of complexity system, gives the reason why the "Edge of Chaos" should become the center of complexity study. By the cellular automata evolving information entropy and word entropy, describes the cellular automata dynamics behavior in the sense of time. In certain extend, realizes the transition from the qualitative description to quantitive computation by the connection of cellular automata evolving information entropy-word entropy plain field and its dynamics behavior. Analyzes the laws of between Langton parameter and cellular automata dynamics behavior. A new method using the combination rule entropy to characterize the cellular automata rule is given. In addition, the characteristics of the combination entropy are educed and the relation with Langton parameter is described too. At last, the distribution of cellular automata dynamics behavior in different combination entropy interval based on Langton parameter is also listed. The inverse problem of cellular automata is studied. The new explain of bionic algorithm life based on the "Edge of Chaos", which gives the guidance about design and modification of evolving algorithm, is showed. Using the characteristics of one-dimension two-value cellular automata, the general algorithm solving the inverse problem of cellular automata based on the binary particle swarm algorithm is given. The experiments using the algorithm to solve the density classification problem and the searching cellular automata quasiperiod-3 behavior rule problem are designed. The compare between the cellular automata rule searching algorithm based on the genetic algorithm and the searching algorithm based on the binary particle swarm optimization algorithm is done too. In the end, gives an algorithm to improve the efficiency of searching cellular automata rule by reducing cellular automata rule space depending on the combination rule entropy and make some compare with Langton parameter's searching capability for cellular automata with some special dynamics behaviors.