Music Generation through Cellular Automata: How to Give Life to Strange Creatures

 

Eleonora Bilotta, Pietro Pantano and Valerio Talarico.

Centro Interdipartimentale della Comunicazione, Università della Calabria, Arcavacata di Rende, Cosenza, Italy.

 

 eleb@abramo.it

 

piepa@abramo.it

 

tvalerio@abramo.it

 

 

 

Abstract

Cellular Automata (CA), like every other dynamical system, can be used to generate music. Starting from any initial state and applying to CA simple transition rules, such models are able to produce numerical sequences that can be successively associated to physical parameters. This approach is interesting because, maintaining fixed the set of rules and varying the initial data, many different, though correlated, numerical sequences can be originated, which in turn can be translated into music. In fact, a rendering process  can tie one or more physical parameters to these numerical sequences, creating musical compositions. Furthermore, a genetic algorithm (GA) can be utilized to promote their evolution, giving birth to a process of progressive refinement of the musical compositions.

The aim of this paper is to present a series of musical pieces generated by CA.

The first section of the paper has been devoted to the effects coming from the application of various rendering processes to one dimensional binary state CA. Typical behaviours of automata, belonging to each of the four classes discovered by Wolfram, have been studied: CA evolving to uniform state, CA evolving to a steady cycle, chaotic and complex CA. Musical Dreams, the system for the simulation and musical rendering of one dimensional CA, has been used in analyzing the resulting patterns and in discovering strange creatures in the artificial worlds.

In the second section of the study, various CA, obtained both by random generation and by the preceding analysis, have been organised into families and, successively, evolved through a genetic algorithm. Harmony Seeker, a system for the generation of evolutionary music, based on GA, let us improve our musical compositions. The obtained results vary depending on the rendering system used. In general, automata belonging to the first of the Wolfram’s classes, seem well fit for the production of rhythmical patterns, while elements belonging to the second and the fourth class  seem to produce better harmonic patterns. Chaotic systems have produced good results only starting with simple initial conditions (IC). Experiments made in the second section of the study have produced acceptable harmonic results with CA belonging to the second Wolfram’s class.

1. Introduction

Cellular automata are dynamical systems useful to investigate complexity and self organization in artificial systems. Though regulated by simple mechanisms of evolution, they produce extremely diversified patterns with regular and crystalline structures in some cases and chaotic structures in many others. Between these two extremes, CA with complex behaviour find their place; they are particularly interesting because they show periodic, and in some case dynamical structure, known as “gliders”. Many authors attempted to classify the behaviour of CA. Wolfram identified four main classes of CA rules [1], using qualitative observations on patterns, resulting from the CA’s state transitions in subsequent time steps. Wolfram asserted that such diagrams are generated by rules belonging to four classes:

1.      rules pushing the state of the automaton on a uniform, homogeneous value, in a finite and short number of time steps;

2.      rules producing cyclic state transitions, with variable-length periods;

3.      rules determining chaotic behaviour;

4.      rules generating complex and localized structures.

In some former works ([2-4]), we have proposed various systems for musical rendering, aimed at music generation from CA. Such musical translating systems (which we have called Minuet, Bog and Alien) are based on transforming numerical information, contained in the state transition matrices, in sequences of single notes,  scales and chords. In particular, in this paper, we will use Alien and Bog. This choice has been made because both Alien and Bog behave in a way to preserve a strong correspondence (immediately recognizable) between the generated state transition diagrams and the musical pieces that have been produced by them. In particular, using the above mentioned rendering systems, we have experimented that well identified patterns are musically reproduced by creating, from an auditive point of view, identical mental images correlated to the sound. In other words, sound follows exactly the structure of patterns, giving to the subjects hearing and looking at the patterns the impression of a translation from visual sensorial data to auditory data, by a correlated mental image.
 In the following, we will examine in a systematic way the musical compositions generated using binary state automata (also known as elementary CA) belonging to the different classes mentioned before. In the final section of this paper we will present some results, obtained using multiple states CA selected by a GA.

2. Music produced by elementary one dimensional CA

We can think of an elementary one dimensional cellular automaton as a set of n adjacent sites (a lattice), whose values are either 0 or 1. Such values will vary during the course of time. Given a site i at time t, its value at time t+1 will be a function of the same site’s value and the value of its neighbours. A two dimensional space-time pattern results from state change of sites during time. If, given a site, only the site’s value and the value of the two closer neighbours influence the state transition of the that site, we can said that the radius r of the neighbourhood is 1. If r=2 then the next value of the site will be influenced by its own value, the two neighbours on the left and the two neighbours on the right. A CA’s rule is given by the set of local transition rules for a site. For elementary CA having r=1, the number of local rules is 8 (or 23). Consequently, there are 256 (or 28) evolution rules. We will use periodic boundary conditions (PBC): a site at the extreme boundary of the lattice has the other extreme as a neighbour. In tab. 1 some patterns resulting from simple initial conditions (only one site has state 1) are shown.

01001000 (72)

01001100 (76)

01011010 (90)

01011110 (94)

 

 

 

Table 1: State transition diagrams for r=1 CA with simple IC.

 

The first two rules (72, 76) represent ordered states, whose results from a musical point of view are not interesting. The other two patterns show crystalline-like structures. The third pattern, generated by rule 90,  is analogous to that generated by rule 18, 146 and 218. In this case, the emerging figures are those of modulo 2 Pascal’s triangle. These patterns are called self similar or scale-invariant because they appear at different scales, a fractals’ characteristic. Another pattern, slightly different from the former, is that produced by rule 150 shown in tab. 2 along with a pattern produced by rule 146.

10010010 (146)

10010110 (150)

 

 

 

Table 2: State transition diagrams from rules 146 and 150 with simple IC.

 

Music produced using rule 150 is different from that created by rule 146. In fact, as it happens  at the visual level,  a greater information content can be perceived in the rule 150’s state transition diagram. In the same way,  at the musical level, compositions  drawn on it present a greater harmonic content.

With two initial non zero sites, the patterns resulting from rule 146 will be a superposition of those obtained with one non zero site. The interaction between those two patterns, still separated for a certain time interval, generates more articulated and structured self similar patterns. The resulting music will become chaotic and difficult to follow from a musical point of view. The same result is obtained with rule 150.

If  various random initial states, in which the probability of a site to be 0 or 1 is equal to ½, most of the patterns will be chaotic or ordered. Four examples are shown in tab. 3.

 

01101000 (104)

01101100 (108)

01111010 (122)

01111110 (126)

 

 

 

Table 3: Ordered and chaotic patterns obtained from random IC.

 

By rendering these ordered or periodic diagrams, music results monotonous especially if the pattern has a short period. Chaotic diagrams produce exclusively music that is hard to appreciate and not harmonic.

Among the 256 rules considered for r=1, only rules 54 and 110 are appreciable in the musical translation. Patterns generated by these two rules, starting from a random IC, are shown in tab. 4.

 

00110110 (54)

01101110 (110)

 

 

 

Table 4: State transition diagrams from rules 54 and 110, with random IC.

 

Elements from these diagrams may be subdivided into two categories: from a qualitative point of view, the first contains everything can be considered as a background; the second contains the structures that are in evidence in comparison with the background. Music produced by both patterns is chaotic and dissonant, according to the opinions  some subjects gave in hearing it the first time. But analyzing better the diagrams, we found that a way to improve our musical compositions was to use only the structures belonging to the second category, by using suited filtering techniques. These techniques are well described by Crutchfield and Hanson [5-6], who have developed a theory called Computational Mechanics by which they formally define the background elements (recognizable pattern localized in a bounded region) as regular domains and complex structures (separating a regular domain from another) as particles [7].

The behaviour of rule 54 has been deeply studied by Crutchfield and his collegues who has provided a systematic classification of the particles it produces. In this work, every particle is identified by the pattern that characterizes it, by the period of pattern repetition and the speed of propagation. When two particles hit each other, an interaction begins. This interaction leads to the creation of other particles or to the mutual destruction of the interacting ones. Crutchfield essentially found six kinds of particles (a, b, g, d, m and n) and catalogued their interactions. Particles and their interactions could produce musical pieces, which vaguely resemble to scales crossings.

 

3. Gliders and Beetles

Complex rules are less than ordered and chaotic ones and give birth to state transition diagrams whose structure are easily singled out without filters. These complex emergent structures can be stable or unstable depending on if they live or not in time if they are not subject to perturbations or interactions.

If we consider CA having r=2, there are 232 rules in the rules’ space. Such huge spaces can’t be explored by exhaustive search. Hence it is necessary to use different means of study, such as genetic algorithms [3][8].

Let us consider the totalistic rule 20, whose binary representation is

      01101001100101101001011001101000,

which is able to create, with suited IC, complex stable structures identified as gliders [9]. According to some qualitative observations we made, a glider has specific characteristics given by a sequence of state transitions of a certain number of sites, localized in a certain area of the lattice. Such characteristics can be preserved in time and can move in space. In tab. 5 we show four gliders generated by using the rule 20, along with their magnifications.

 

 

 

IC=11011101

 

IC=10111011

 

 

 

 

IC=11101001

 

IC=10111101

 

 

 

Table 5: Gliders for totalistic rule 20.

 

The gliders move slowly toward the left or the right of the screen, depending on their IC. The period of such a structure is 10. Music generated by these gliders has a well determined tempo scheme. Furthermore, the moving of the configuration toward the left or the right causes the recurrent musical phrase to be transposed to a lower or a higher semitone, along the tonal scale. Rule 20 also generates a second kind of gliders that are steady. Two of these gliders are shown in tab. 5. One has period 2 and the other has period 1. Music produced by the first structure is monotonous, using both Alien and Bog. The same thing happens for the second glider. This behaviour is similar to those observed for CA of class 2 CA, identified by Wolfram. The lower harmonic content, generated by the steady glider, produces less unpleasant, though dissonant, music.

 

IC=11111

 

 

 

Figure 2: The “Beetle” produced by the totalistic rule 20 (r=2).

 

Furthermore, changing the IC, we verified that rule 20 produces also unstable structures as shown in fig. 2, to which we gave the conventional name of “Beetle”.

According to our experiments, this structure seems to come out at a second level of self organization in comparison with the structures generally classified as gliders. The Beetle is drawn in 20 time steps, starting from IC 11111. The observation of the pattern shows some sequences of sites with state 1, interleaved by many cells with state 0, at regular intervals. For example, the 17th  time step is characterized by the local state 1000100100010010001, which is rendered by Bog as a kind of scale-like composition, whose first three notes and the notes from the third to the fifth are major harmonies, the notes from the second to the fourth and from the fourth to the sixth are minor harmonies. In fact, if we suppose that the first note is a C, we obtain respectively a C major and a G major chord, an E minor and a B minor chord. Hence, the Beetle shows, in some points, relevant harmonic contents. This has suggested us that more sophisticated rendering techniques could be able to extract more significant musical contents. The analysis of the rule 20 can be concluded by outlining the possibility to observe and render every combination of interactions between the above mentioned structures.

 

5. Solitons, Spiders, Beehives and much more

Among the rules derived for r=2, an important role is played by those producing “Solitons” [10]. They have been subdivided into seven different classes:

A.     rules in which more solitons appear, after a collision between two solitons;

B.     rules in which the number of solitons remains constant after a collision, but augments after multiple collisions;

C.     rules in which a stable core pattern emits a constant number of solitons periodically;

D.     rules that construct a steady, non-propagating and oscillating pattern. This kind of pattern is called breather;

E.      rules in which a giant soliton exists and this soliton emits a type of breather or soliton; the giant soliton is also called mobile core;

F.      rules generating a kink pattern such as those of the class 3 of Wolfram categorization;

G.     rules in which no detectable excitation exists.

The first rule we studied, belonging to class A, is known as A1 and its binary representation is

      10111111100010100001100011001000.

Starting from structured seeds 1101 and 1011, it produces two gliders with period 1, moving respectively toward the left and toward the right of the diagram. An example of the left case is shown in fig. 3.

 

 

 

 

 

Figure 3: a soliton generated by rule A1 whit seed 1101.

 

In this simple case this rule produces scale-like music, both with Bog and Alien. Bog, given a reference semitone, plays in sequence for each period the reference semitone, the semitone immediately following the reference semitone and the semitone at distance one from the last played semitone. At the end of this sequence, the reference semitone is shifted back of one semitone and the playback process restarts. Alien plays the three semitones of each Bog sequence together, thus giving life to a dissonant descending scale. The behaviour of rule A1 becomes different if we consider many interacting solitons. More precisely, if we put in the lattice a left soliton and a right soliton, we can notice that the product of their interaction varies, according to the initial distances between the solitons. In fact, even distances trigger the generation of symmetric higher order structures, while odd distances imply structural stability. Examples of these structures are given in tab. 6. The state of the automaton with two solitons at an even distance (tab. 6b) goes into a steady cycle of period 2, after a rather long transient. In the case of odd distance (tab. 6a), the system is already in its steady cycle, with period 95.

In the first case, the music we have realized becomes more complex and dissonant, while presenting recurrent structures. In the second case, the superposition of the effect, already exposed for a single soliton, takes place.

Solitons produced by rule A2, whose binary representation is

            10111111100010100101100011001000,

and differing only for one bit from A1, have behaviour and music very similar to those of rule A1.

Solitons of type B, generated by a rule such as:

            00111100110001100110101110000100,

are extremely stable when two of them interact. In fact, in such systems, structures of higher order never appear, even varying the distance between solitons. Things change radically if more than two particles are introduced. An example is shown in tab. 6c. In this case, music goes quickly toward an ordered and harmonic chaos with Alien, while some consonant scales are produced by Bog. If simple IC are used, the behaviour of rule B changes. Examples are shown in tab. 6d and 6e. The first figure shows a pattern resembling to a spider within its web. Using Bog with this configuration, we have obtained good results especially in correspondence of the areas where gliders interact, i.e. where the tight meshes of the rhomboidal structures are generated. Alien gives better musical pieces in the first part of the figure in tab. 6e (the glider eater), where the central structures produce a rhythmical pattern, while the side scales produce the melody.

 

(a)

(b)

(c)

(d)

(e)

(f)

(g)

 

 

 

Table 6: Solitons’ interactions. From left to right: left and right A1 solitons at odd distance and even distance; three B solitons interacting; the B solitons’ spider; the B soliton’s glider eater; the C2’s complex interactions; the E moving glider gun.

 

Solitons of type C are given by rules such as

            00011101001001100101111011001000 (C2).

In this case, using a core IC such as 11, we obtain the result shown in tab. 6f. In this configuration, every 13 time steps, the core emits two solitons. After a certain number of time steps these solitons collide and very complex and structured behaviours result by these multiple interactions. Such transients exhaust when solitons, previously created, collide with freshly baked solitons as a matter of fact destroying each other. At this point, the automaton enters a steady cycle. Both Alien and Bog produce relevant music in the areas where behaviour is more regular and there are few interactions.

An example of class E rule is:

            10111101101000100101100011001000.

This kind of rule is called moving glider gun. Starting from a structured IC such as 11, this rule produces the result shown in tab. 6g. In this figure, a bigger central structure contracts and expands itself until it emits two solitons which collide and destroy each other. The behaviour is periodic. Alien produces music which shows a certain crescendo in pathos. In fact, if we consider a left soliton, the distance between its rightmost part and the leftmost part of the successive left soliton, is exactly one octave (12 sites). This implies that exists a certain harmonic reinforcement between notes with a quasi maximum consonance (the octave interval). The same does not happen for notes with a great dissonance. The consequence is that the notes belonging to a particular octave interval tend to stand out clearly. On the contrary, the effect of harmonization among respectively the outer and the inner parts of the same solitons is negligible, because of the dominant dissonant effect that these notes, played together, produce. The same result is obtained when considering the right part of the diagram. The octaves leap is immediately perceivable using Bog.

 

6. Music from multiple state systems

Searching for rules and analyzing their patterns in order to detect relevant musical configurations is a difficult task, especially if we let the r parameter grow. In this last case, the complexity of the search problem grows exponentially. Furthermore, if we want to get more expressive music from the rendering process, it is possible to think of introducing in our analysis multiple states based CA (this choice has been discussed in [2-3]). Again, the search space increases its dimension exponentially. Hence, it is necessary to develop automatic and efficient search techniques aimed at spotting better rules. One of such techniques has been developed by the authors [3] and is based on a GA that operates a selection on populations of one-dimensional multiple state CA. Such selection promotes the spreading out of rules generating high-fitness patterns into the population. The fitness function [3-4] is based on the analysis of patterns with harmonic consonance.

The discussed experiment has been conducted using Harmony Seeker, a software system developed by the authors. A trial version of this software can be requested by e-mail to the authors.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(a)

(b)

(c)

 

 

 

Table 7: Sample CA patterns evolved by a GA.

 

A typical experiment, made with population of 250 CA with 4 states per site, a lattice with dimension 12 and r=1, organized into 50 genetic families, evolved for 300 generations (75000 CA in total), with random IC and random genotypes (rules) for the first generation, leads to the result shown in tab. 7. Tab. 7a shows individuals belonging to the bootstrap generation, in which chaotic components of the behaviours overkill structured components. Figure in tab. 7b shows CA belonging to generation 145. In this case, the effect of the selection process starts to be evident: rules triggering structured behaviours begin to be visible. The CA shown in tab. 7c belong to the last generation. Though some non-ordered behaviour still persists, the vast majority of the population shows ordered structures, recalling both gliders and solitons. Moreover, it is evident that these rules are extremely stable to perturbations. because they tend to exhaust transients very quickly.

In general, music produced by multiple state CA is more structured and rich of complex rhythmical patterns, and this is also due to the codification processes Bog and Alien utilize. Furthermore, the method used for the selection process reveals to be well suited to obtain harmonic results.

References

[1] Wolfram, S. Universality and complexity in cellular automata. Physica D, 10:1-35, January 1984.

[2] Bilotta, E., Pantano, P. and Talarico, V. Synthetic harmonies: an approach to musical semiosis by means of cellular automata. In M.A. Bedau, J.S. McCaskill, N.H. Packard and S. Rasmussen, editors, Artificial Life VII, August 2000. Cambridge, Massachusetts. The MIT Press.

[3] Bilotta, E., Pantano, P. and Talarico, V. Music, mathematics and artificial life. In 11th ECMI Symposium, September 2000. Palermo. Italy.

[4] Bilotta, E. and Pantano, P. In search for musical consonance. Electronic Musicological Review, 5.3 (in press), 2000.

[5] Crutchfield, J.P. and Hanson, J.E. The attractor basin portrait of a cellular automaton. Journal of Statistical Physics, 66(5/6):1415-1462, 1992.

[6] Crutchfield, J.P. and Hanson, J.E. Turbulent pattern bases for cellular automata. Physica D, 69:279-301, 1993.

[7] Mitchell, M., Crutchfield J.P. and Hordijk, W. Embedded-particle computation in evolved cellular automata. In Pre-Proceedings of Physics and Computation ’96, 1996.

[8] Mitchell, M. and Crutchfield J.P. Evolving cellular automata to perform computations. Complexity, 7:89-130, 1993.

[9] Berlekamp, E.R., Conway, J.H. and Guy, R. Winning Ways for Your Mathematical Plays. Academic Press, New York, 1982.

[10] Aizawa, Y., Nishikawa, I. and Kaneko K. Soliton turbulence in one-dimensional cellular automata. Physica D, 45:307-327, 1990.