Speaker
Description
Evolutionary design has become a successful concept in the areas where a solution to a problem needs an exploration of extensive search spaces (i.e. the analytical approach is intractable or not known). It has been shown during recent years that innovative or still unknown solutions can be obtained automatically using proper evolutionary setups. Cellular automata represent a massively parallel computational concept allowing us to simulate various complex systems or event to perform computations (cellular automaton represents a universal computing model). The cellular automaton consists of a regular structure of many simple computing elements - cells, each of which may, at a given moment, acquire a state from a given finite set of states. The cell states are updated synchronously in discrete time steps according to transition rules specified for a given task to be solved. This process is called a development or computation of the cellular automaton. However, the design of suitable transition rules represents a difficult problem especially due to the fact that common programming paradigms are hardly applicable for the cellular automata. Moreover, the number of transition rules (and the number of transition functions determining the global behaviour of the cellular automaton) grows exponentially depending on the number of states and the simulation of the target behaviour typically requires a significant amount of time (it is needed to calculate the states of all cells for a sequence of several time steps). Therefore, the design of a cellular automaton is often treated as a search problem in the space of potential transition functions by means of suitable (meta)heuristic algorithms, e.g. by means of evolutionary techniques. This paper summarises some recent results regarding the research of representation techniques for the evolutionary design of complex two-dimensional cellular automata. Two representations will be mentioned: a conventional table-based method and an advanced approach utilising conditionally matching rules. In both cases the evolution strategy will be applied to design cellular automata for solving selected benchmark and real-world problems. In particular, the pattern development problem and the problem of filtering gray-scale images corrupted by a given type of noise are considered as case studies. It will be shown that using a proper settings of the evolutionary algorithm, interesting results can be obtained representing solutions of the given problems that have not been known before. Some observations from the analysis of resulting cellular automata will be presented which indicate, for example, that in some cases the behavior of the resulting automata is totally different depending on the representation applied. Specifically, the table representation exhibits a rather chaotic development of the cellular automaton during which a target pattern emerges at a single specific moment. On the other hand, the conditionally matching rules showed an ability to achieve behaviors that progressively construct the target pattern from a given initial state which, in addition, may represent a final state of the cellular automaton. Moreover, the latter method also exhibits significantly higher success rate which represents one of its advantages and proves an importance of systematic research in this area.
