Co-evolutionary Optimization Method Based On Cellular Automata

Cellular Automata is one of the current hot topics in the area of computer science. The massive parallelism, simplicity of basic components, locality of cellular interactions it contains have attracted much attentions from lots of researchers in different fields.Nowadays in the most optimized sector, more and more super large scale problems have been found. They are very complex, nonlinear with many constraints, thus makes it difficult to solve. Direct at those characteristics, algorithms have showed high performances on solving these problems, such as simulated annealing algorithm, artificial neutral network, genetic algorithm and so on. But these algorithms are designed for Von Neumann computer. The super computer in the future may have the capability of a million billion or even ten million billion floating decimal per second. One possible structure of this kind of computer is based on the framework of Cellular Automata. The paper focuses on how to combinate the evolutionary algorithm and cellular automata to solve the optimization problem and exert the capacity of machine and algorithmns.The paper extent the concept of cellular automata and proposed the comcept of evolutionary cellular automata. According to the ideals that simple rules lead to complex behaviors and local interaction leads to global computation in cellular automata the paper proposed a co-evolutionary algorithm based on cellular automata to solve the difficult function optimization problem and combination optimization problem by the definition of co-evolutionary rules. The paper gives a proof on the convergence of the algorithms. The results of experiments on non-restraint function optimization, restraint function optimization and combination optimization show that the algorithm is good at the function optimization problem, the algorithm can converge with the exponential speed in the early execution, and pays exponential time in the later execution. In general, it is faster than some algorithms such as GT algorithms. The paper discussed the relation between the dimension of cellular automata and the convergent speed and has a conclusion that the bigger the dimension is, the faster the algorithm is, and the easier the algorithm converges. The algorithms can run on the machines based on cellular automata.