|
Emergence of an efficient way to observe and evolve cellular automata
|
|
Hugues Bersini
|
|
IRIDIA |
|
|
| On 2004-01-15 at 15:00:00 (Brussels Time) |
Abstract
For many years now, cellular automata (CA) have been the favorite computational platform to experiment and illustrate emergent phenomena. It is far from surprising that many authors have relied on their experimentation to quest for formal definitions of the nature of “emergence” and to validate them. My recent work is following a similar trend by fully adopting the practice of CA. On the whole, all authors interested in the rationalization of emergence converge to the fact that at least two levels of observation are required: A first one in which the micro-states and micro behavioral rules are specified and implemented, and a second one, which by only depending upon the underlying micro-characteristics, exhibits interesting macro-phenomena. They are obtained by unfolding in space and time the micro-rules though the micro-states, most of the time in a non-decomposable way. An observer, so far always human, is necessary to instantiate this second and more abstract level of observation and to detect and follow these interesting and original phenomena. This characterization of emergence has turned out to be quite common. Nevertheless, I'll show that such a classical characterization, though including necessary ingredients (i.e. the two levels of observation and the abstraction in space and time of the second with respect to the first), is far from sufficient and severely limited and incomplete on one essential aspect: the identity and the role of this second level observer. For CA, Neural Networks, other computer simulations of networks and whatever computational source of emergence, the observer is generally accepted to be human. However, this “anthropomorphisation” of the phenomenon of emergence is antagonistic to any scientific practice that, in principle, aims at not leaving subjectivism a leg to stand on. Basically, if the formalization of emergence demands the intervention of a human observer, even worse to be “psychologically surprised”, its intrusion in the vocabulary of physics is compromised right off the bat. Such a limitation has been faced and removed mainly by two authors who, in their writing, have answered this preoccupation by supplying the characterization of emergence with a key ingredient: a “functional device” must substitute the human observer that, for whatever utility or performance reasons, will fine-tune its observation of any macro-phenomena produced by the system. Cariani claims that, for a phenomenon to be said emergent, devices need to be built, able to find new observable, autonomously relative to us, whose selection and tuning must rely on performance measures. However the most convincing reply to this limitation and which provides the main guidelines for the work to be described in my talk is part of Crutchfield’s definition of “intrinsic emergence”: “… Pattern formation is insufficient to capture the essential aspect of the emergence of coordinated behaviour and global information processing… At some basic level though, pattern formation must play a role… What is distinctive about intrinsic emergence is that the patterns formed confer additional functionality which supports global information processing… During intrinsic emergence there is an increase in intrinsic computational capability, which can be capitalized on and so lends addi-tional functionality.” Indeed like initiated by Crutchfield and Mitchell, the work I will describe consists in using an evolutionary algorithm to discover a CA able to perform an engineering task, in our case, the binary addition of numbers coded on 5 bits. It is shown that the discovery of such an efficient CA is very painful by adopting the natural micro-coding of the states and the rules. An important improvement and acceleration of this discovery is allowed by adopting a simplified macro or abstract characterization of the states and the rules of the CA. This new “macro-observation”, intrinsically emerges, since autonomously tuned by the system itself on the basis of performance measures. Allowing part of the evolutionary process to take place by adopting such an emergent observable accelerates in an consequent way the discov-ery of a quasi-optimal CA. Apart from casting some fresh light on the characterization of emergence, any engineering of distributed computation should often be able to reproduce such a practice: find a w ay of observing the system which helps the optimizing of its structure and behaviour.
Keywords
CA, GA, intrisic emergence, binary additions
