Dynamics of bioinspired computation

Since its birth, Computer Science has been inspired by natural phenomena. Two main approaches where developed through the years. The first one is concerned with the study of the properties nature-inspired models that can also be used to model nature. Examples in this fields are Cellular Automata and Reaction Systems. The second one uses nature-inspired model to perform optimization tasks where exact algorithms are not applicable. Evolutionary algorithms, like Genetic Algorithms and Genetic Programming are some of the most prominent examples. The main aim of this thesis is the study of the dynamics of four different nature-inspired models with the goal of providing both an improvement in the single areas and a cross-pollination of methods and techniques. The four chosen models are: Genetic Algorithms. A traditional optimization techniques that is inspired by the Darwinian theory of evolution. Genetic Programming. A more recent technique, similar to classical Genetic Algorithms, that uses programs instead of fixed length binary strings as a representation method. Reaction Systems. A recently developed formalism inspired by chemical reactions. Cellular Automata. A extensively studied model made of a lattice of identical automata that can exchange information only locally. As for Genetic Algorithm, one of their main operators, the crossover, was studied. In particular, the minimum number of iteration of the crossover operator needed to produce certain individuals was investigated. As for Genetic Programming, two new measures to quantify the quality of the solution learned were developed. To better understand the dynamics of Genetic Programming a new benchmark, inspired by a similar benchmark in Genetic Algorithms, was introduced. Finally, a method to reduce the worst case space requirements of Semantic Genetic Programming from exponential to polynomial was devised. Some combinatorial properties of Reaction Systems were studied. Furthermore, an evolutionary version of Reaction Systems to be used for optimization was introduced. This new algorithm proved to have performances comparable to current state-of-the-art machine learning algorithms. The dynamical and computational properties of a variation of classical Cellular Automata, fully-Asynchronous Cellular Automata, have been studied. Furthermore, a first step in providing a more general framework to study asynchronicity in Cellular Automata has been made with the introduction of m-Asynchronous Cellular Automata. This thesis provides both improvements in these four different areas and a first step toward an exchange of methods and techniques between those areas.