Proceedings of the ACM Genetic and Evolutionary Computation
Conference (GECCO-2009), Montreal, Canada, July 2009.

Evolving Quorum Sensing in Digital Organisms
Benjamin E. Beckmann and Phillip K. McKinley
Department of Computer Science and Engineering
3115 Engineering Building
Michigan State University
East Lansing, Michigan 48824{beckma24,mckinley}@cse.msu.edu
ABSTRACT1.

For centuries it was thought that bacteria live asocial lives.
However, recent discoveries show many species of bacteria
communicate in order to perform tasks previously thought
to be limited to multicellular organisms. Central to this capability is quorum sensing, whereby organisms detect celldensity and use this information to trigger group behaviors. Quorum sensing is used by bacteria in the formationof biofilms, secretion of digestive enzymes and, in the caseof pathogenic bacteria, release of toxins or other virulence
factors. Indeed, methods to disrupt quorum sensing are currently being investigated as possible treatments for numerous diseases, including cystic fibrosis, epidemic cholera, andmethicillin-resistant Staphylococcus aureus. In this paper wedemonstrate the evolution of a quorum sensing behavior in
populations of digital organisms. Specifically, we show that
digital organisms are capable of evolving a strategy to collectively suppress self-replication, when the population density
reaches a specific, evolved threshold. We present the evolved
genome of an organism exhibiting this behavior and analyze
the collective operation of this “algorithm.” Finally, througha set of experiments we demonstrate that the behavior scales
to populations up to 400 times larger than those in which
the behavior evolved.

The human body is made up of 1013 human cells. Yet,this number is an order of magnitude smaller than the number a bacterial cells living within the gastrointestinal tractof a single adult [4]. Although it was previously assumed
that bacteria and other microorganisms rarely interact [24],in 1979 Nealson and Hastings found evidence that bacterial
communities of Vibrio fischeri and Vibrio harveyi were able
to perform a coordinated behavioral change, namely emitting light, when the cell density rose above a certain threshold [20]. This type of density-based behavioral change iscalled quorum sensing [27]. In quorum sensing (QS), continual secretion and detection of chemicals provide a way
for bacteria to assess local cell density. Reaching a sufficient density can trigger expression of genes that produce
behaviors more likely to succeed under such conditions.
The initial discovery of Nealson and Hastings spawned a
new branch of research to discover the nature of such interactions, whether they occur in other microorganisms, andthe consequences of these behaviors. QS has since been observed in many species of bacteria, which use it for a varietyof purposes, including secretion of digestive enzymes in thegastrointestinal tract [6], bioluminescence and phototrophy
in marine bacteria [3, 20], and, in the case of pathogenic
bacteria such as Salmonella and Staphylococcus, release of
toxins or other virulence factors [7, 9, 18]. QS is also known
to be closely related to more complex behaviors, such as
aggregation into biofilms [12] and even fruiting bodies [10].
For example, when confronted with starvation due to nutrient depletion, Myxococcus xanthus bacteria cooperate toform a stalk, enabling some cells to be carried as spores to
new locations where conditions might be better.
Improved understanding of QS has numerous scientificbenefits [7]. Foremost, diseases caused by quorum-sensing
bacteria might be treated with medications that inhibit thisbehavior (i.e., quorum quenching) [18], an approach that
may have milder side effects than some antibiotics. For example, Davies et al. [8] showed that QS is essential to thedevelopment of biofilms in Pseudomonas aeruginosa, the primary pathogen observed in the lungs of people with cystic
fibrosis. In addition, quorum quenching has been proposed
as a possible treatment for methicillin-resistant Staphylococcus aureus [23], some strains of which are resistant to mosttraditional antibiotics [16]. Moreover, a deeper understanding of these interactions and their evolution may provide
insight into the evolution of multicellularity itself.

Categories and Subject Descriptors
I.2.8 [Computing Methodologies]: Artificial Intelligence—
Problem Solving, Control Methods, and Search

General Terms
Experimentation

Keywords
Artificial life, digital evolution, quorum sensing, multi-agent
system, cooperative behavior, self-organization.

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
GECCO’09, July 8–12, 2009, Montréal Québec, Canada.
Copyright 2009 ACM 978-1-60558-325-9/09/07 ...$5.00.

INTRODUCTION

In addition to furthering biological studies, knowledge of
how relatively simple organisms cooperate to perform complex tasks may also be beneficial to the development of distributed computational systems that need to tolerate dynamic conditions and survive component failures as wellas cyber-attacks. For example, collective behaviors among
agents in an artificial immune system are essential to detecting and responding to potential threats, while nodes insensor networks need to implement complex distributed operations such as multicasting, gathering sensed data, andmaintaining a network topology. Many traditional algorithms for solving these problems are brittle when deployedin dynamic environments, and several promising algorithms
proposed recently are inspired by biology [2]. Leveraging
the evolutionary process to produce well adapted systems isa logical next step.
In this paper we demonstrate the evolution of QS behavior in populations of self-replicating digital organisms.
Specifically, we show that digital organisms in the Avida
system [22] are capable of evolving a strategy to collectively suppress self-replication when the population density
reaches an evolved threshold. We describe the operation ofan evolved genome exhibiting this behavior and analyze thecollective operation of a population of such organisms. We
also show that the behavior scales to populations up to 400
times larger than those in which the behavior evolved. This
study represents a first step in using artificial life, specifically
digital organisms, to investigate the evolution and operationof QS.

2.

2.2. Avida Overview
Avida is a well established artificial life platform used inevolutionary biology [1, 14, 15, 22] and more recently in distributed systems research [17]. In Avida, individuals, ordigital organisms, compete for space within a fixed-size twodimensional collection of cells. Each cell can contain at mostone organism, which comprises a circular list of instructions(its genome) and a virtual CPU that executes those instructions, as shown at the top of Figure 1. Instructions perform
simple arithmetic operations (addition, bit-shift, increment,etc.), control execution flow, aid in self-replication, and provide a means for the organism to interact with other organisms and the environment. The execution of an instruction
costs both virtual CPU cycles and energy. Different instructions can be assigned different CPU cycle and energy costs.
An organism executes instructions on its virtual CPU, whichcontains three general purpose registers (AX, BX, CX), twogeneral purpose stacks, and special purpose heads that point
to locations within an organism’s genome. Similar to a traditional program counter and stack pointer, heads are used
to control the flow of execution.

BACKGROUND

2.1. Quorum Sensing in Bacteria
Bacteria that participate in QS continuously release signaling molecules, called autoinducers (AIs) [21], which they canalso detect with AI receptors. Under low-density conditions,
AI molecules diffuse throughout the environment and go undetected by the bacteria. However, the level of AI increases
directly with cell density and, if it exceeds a threshold, thedetection mechanism in the bacteria causes the up regulation of the genes that produce AI molecules. This creates a
positive feedback loop which greatly increases the level of AI
in the environment. Once a receptor has been fully activatedby a high concentration of AI, the activated receptor causes
the up or down regulation of other genes in the bacteria. If
the level of AI is relatively uniform throughout the environment, all of the bacteria that respond to the high level of AI
will begin transcription of the same genes at approximately
the same time, thereby changing the population’s behavior
once a quorum has been reached.
In addition to numerous wet lab studies of QS and biofilm
formation [6–8,18,20,27], several researchers have constructed
mathematical models that describe gene expression in QS
bacteria [5,25,26]. These works differ from ours in that theyuse P systems to model known gene expression mechanisms.
In addition, Nadell et al. [19] recently simulated pairwise
evolutionary competitions to investigate the production of
extracellular polymeric substances (EPS) used in biofilm formation. To our knowledge, however, the study described in
the remainder of this paper is the first to demonstrate theevolution of QS behavior in self-replicating digital organisms.

Figure 1: Population (bottom), sub-population(middle) and composition of a digital organism:
genome (top right), virtual CPU (top left) withheads pointing to locations within the genome.
Avida organisms are self replicating, that is, their genomesmust contain instructions to create offspring. An offspringis placed in a randomly selected cell, terminating any previous inhabitant. Typically, an Avida population starts witha single ancestral seed organism capable only of replication.
As organisms replicate, instruction-level mutations produce
variation within the population. In this study, the ancestralorganism contains 49 no-operation (nop) instructions anda single repro instruction, which performs self-replication.
The nop instructions have no effect on the ancestral organism’s observed behavior, or phenotype, excluding its gesta-

tion time. However, they do provide the evolutionary process more room to work, as mutations during replication
bring different instructions into the genome with selective
pressures, discussed below, favoring resulting behaviors that
benefit the organism and its offspring.
Each organism has an energy store that is used to calculate its metabolic rate using Equation 1. An organism’s
metabolic rate is inversely proportional to a user defined
limit on the total number of instructions an organism can
execute before its energy is depleted, assuming no new energy influx and all instructions cost 1 energy unit. Probabilistically, an organism with a higher metabolic rate will begiven more virtual CPU cycles to execute instructions at ahigher energy cost per instruction, calculated by Equation
2, than an organism with a lower metabolic rate. Generally,an organism can increase its energy, either individually or as
part of a group, by exhibiting behaviors prescribed by theuser.
metabolic rate =actual energy cost

stored energy
max. executed inst.

= metabolic rate ×
inst. energy cost

(1)

(2)

In Avida, time is measured using an abstract unit called
an update. During an update, an average organism is willprobabilistically execute 50 instructions. When exploringa particular problem, we execute several batches of Avida
runs, each with a different configuration, and analyze theevolutionary process and resulting behaviors. A batch typically contains of 20 runs, each of which starts with the sameancestral organism but a different random number seed,causing the populations take different evolutionary paths.

2.3. Demes and Group-level Selection
In some Avida studies all organisms are treated as part of asingle population, in which case individual organisms compete against each other. However, in other studies, especially those involving the evolution of cooperative behavior,
it is useful to subdivide a population and have groups oforganisms compete. As shown at the bottom of Figure 1,
a population of organisms can be subdivided into multiple
sub-populations, called demes. While all demes have identical environments and initial configurations, an organism caninteract only with other organisms in its deme. Subdividing
the population this way is akin to the island model [28] commonly used in evolutionary computation, enabling the detection and eventual selection of demes that perform grouplevel behaviors.
Multilevel selection [29] can be described as the application of natural selection at different granularities. Avida
supports multilevel selection, specifically at the individualand deme levels. However, in the work presented here fitness proportional selection is performed only at the demelevel. A deme’s fitness is evaluated using Equation 3. After
selection and prior to creating an offspring deme, mutations
are applied to the genome that was used to seed the parent deme. During this mutation process each instruction in
the genome is subject to a 0.75% chance of being mutatedto a random instruction. In addition, there is a 5% changethat a random instruction is inserted and deleted from arandom location in the genome. The newly created genome
is then used to seed the offspring deme. The sequence of an-

cestral genomes make up the germline from which all seedorganisms are produced. In contrast, other non-germline, or
somatic, organisms play no role in deme replication.
(1
if i is sterile,(3)
f itnessi = RemaingingEnergyi+ 1 otherwise.
InitialEnergyi
In this work individual organisms within a deme are able
to replicate, however those self-replications do not involve
mutations to the genome. Hence, all organisms within ademe are genetically identical. Floreano et al. [11] have previously shown that this approach is effective in evolving cooperative behavior.

2.4. Avida Messaging and Interrupt Handling
Avida organisms can communicate by sending messages to
one another. An Avida message consists of a single packet
containing the values of two of the sending organism’s registers. The send-msg instruction delivers a message to theorganism residing in the currently faced cell. If the cell isunoccupied, then the message fails to be received. An organism can change its facing by executing one of several rotate
instructions, discussed later.
In most prior studies using Avida messages, a receivingorganism must explicitly retrieve the message from its input buffer in order to process it. However, we recently extended Avida with an interrupt model similar to the execution model of TinyOS [13], an operating system for sensor
networks. In this model, depicted in Figure 2, an organism’s main execution thread can be interrupted by a particular event, such as receiving a message. To enable context
switching of this type, we introduced two instructions that
denote the beginning (msg-handler) and end (end-handler) of
an interrupt handler. We emphasize that these instructions
have simply been added to the set of instructions available
for mutation into an organism’s genome. Whether they areused or not is solely a result of natural selection.

Figure 2: Context switch from sequential execution
to an interrupt handler and back.
Figure 3 depicts the semantics of these instructions if they
do enter the genome. When an organism receives a message,
it genome is searched in the forward direction for the nearest instance of a msg-handler instruction. If none is found,the message is ignored. If a msg-handler instruction does
exist, then the organism’s context is saved, the contents ofthe message are placed in two of the organism’s registers,
and the instruction pointer is moved one instruction past
the msg-handler instruction. The interrupt handler returns
when an end-handler instruction is executed, which causes
the interrupt context to be flushed from the organism’s virtual CPU and the original context to be restored. If no
end-handler instruction exists, then execution continues se-quentially through the genome. Lastly, if a msg-handler instruction is encountered during normal sequential execution,
the handler code is skipped and execution jumps past thenext end-handler instruction.
In this work an interrupt handler cannot be preempted;
therefore, all interrupts are handled atomically. Specifically,
if a message is received while an organism is interrupted, themessage is queued until the handler has finished, at whichtime the handler is re-entered and the next message in thequeue is processed. The original context is restored only
when all received messages have been processed. Furthermore, the incoming message buffer is limited to 20 messages.
Messages received when the buffer is full are dropped. As weshall see in Section 3, the evolutionary process exploited thisproperty in order to produce quorum sensing behavior. If
no end-handler instruction exists then the jump is not taken.

Figure 3: Sample genome containing a single interrupt handler. During sequential execution thefirst four instruction of this genome are executed. If
a message is received the organism’s IP is jumped
into the interrupt handler. This example also contains “junk” code that will not be executed unlessthe genome is mutated.

3.

EVOLVING QUORUM SENSING

In this section we demonstrate that the digital evolution
system as described above is capable of producing deme-level
populations that exhibit QS. Specifically, we observed Avida
populations that evolved a group communication behavior
to inhibit self-replication once a deme has reached a density
threshold. Moreover, the threshold itself was not specified apriori, but rather was an evolved characteristic of the population. In addition, we will show that this behavior arises
under different initial conditions and is scalable to demes up
to 400 times larger than the demes in which the behavior
evolved.

3.1. Experimental Setup
In the experiments described below, multiple populations
are divided into 400 demes. Each deme’s topology is a 5 × 5
torus that is seeded with a single organism at the beginningof each competition period. A competition period lasts for
20 updates, where the average organism in the entire population will probabilistically execute 50 instructions per update. After each competition period, each deme’s fitness isevaluated using Equation 3, and individual deme germlines
are selected, mutated, and used to seed demes in the nextcompetition period. Each seed organism is placed and rotated randomly, so that its initial position and facing cannot

be “learned” through the evolutionary process. In addition,deme-level populations are well-mixed, meaning that during
replication, the offspring is placed in a random cell within ademe, with a preference for empty cells.
This study focuses on the evolution of a digital organism’s“gene” (instruction) regulation mechanism, specifically thechange in an organism’s instruction expression under low
and high density conditions. To facilitate genome analysis,given in Section 3.4, we use an instruction set that is includes the send-msg, msg-handler, end-handler, and various
rotate instructions described below. Additionally, four different no-operation instructions and the repro instruction areprovided. This instruction set contains fewer instructions
than previous Avida studies [15]. Other instructions could
be included in the set of instructions available for mutation.
However, since we are not applying any additional selective
pressures, organism behaviors will evolve in accordance tothe deme-level fitness function.
Treatments. Our initial experiments are divided into
three treatments based on available rotation methods. There
are three types: Single step, Labeled, and Neighbor-based.
Single step rotations enable an organism to rotate one cellto its left or right by executing the rotate-right or rotateleft instruction, respectively. The rotate-label instruction
enables an organism to rotate to a direction specified by asequence of subsequent nop instructions, or label. (An explanation of labels and nop-modifiable instructions can be foundin [22].) Lastly, the instructions rotate-occupied-neighborand rotate-unoccupied-neighbor perform neighbor-based rotations. These instructions will rotate an organism to aneighbor cell that is occupied or unoccupied, respectively.
Each treatment consists of 20 runs with each run lastingfor 2500 deme competition periods (generations). Within agiven run, the evolutionary process has access to only oneof the three rotations methods, simplifying intra-treatmentcomparisons. In addition, we compare results from all treatment, however, all comparisons are limited to those runsthat exhibit the desired overall behavior, namely population
control. Out of the 20 runs in each treatment, we observed
15 runs in the Single step treatment and 14 runs in both theLabel and Neighbor treatments that exhibited this behavior,
only those runs are used in the following discussion.

3.2. Energy Conservation
We begin by considering the amount of energy conserved per
deme for the three different treatments. This value alone
determines the fitness of the deme. We note that there are
only two ways for a deme to lose energy: the deme’s constituents use energy when executing instructions, and theenergy remaining in an organism is purged when the organism is replaced. Since every instruction has the same energy
cost, different instruction execution sequences of the samelength all have the same explicit energy cost. Therefore, theonly way organisms in a deme can reduce their total energy
usage is to limit self-replication.
Figure 4 displays the average fraction of energy remaining
within a deme at the end of a competition period. Since Figure 4 shows an increase in energy conserved per deme in alltreatments, it can be assumed that the number of births perdeme is declining over evolutionary time. This assumption
is confirmed by Figure 5, which shows the average numberof births per deme. For all three treatments, the number
declines to approximately 30-35 births per deme.

or right. Performing this basic behavior in the Label treatment requires a much longer sequence of instructions and istherefore less likely to evolve. In addition, this basic send
and rotate strategy is not possible in the Neighbor treatment
without additional information about the organism’s current
neighborhood. In the remainder of this paper we focus only
on results produced in the Single rotation treatment.

Figure 4: Mean fraction of energy remaining perdeme over deme generations for each treatment.

Figure 6: Average organism density per deme.

Figure 5: Average number of births per deme for all
three treatments.

3.3. Group Behavior
QS behaviors found in natural organisms exhibit two key
features. First, a density based change in behavior can beobserved, and secondly, after a threshold has been reached
a positive feedback loop is created that causes more AI to
be released. In this paper messages are analogous to AIs,
and alternate gene (instruction) activation can be realized
through the evolution of an interrupt handler. We define organism density as the number of organisms per cell; therefore, a density of 1.0 can be achieved only if every cell inthe environment contains an organism. Figure 6 plots theaverage organism density per deme over evolutionary time.
Both the Label and Neighbor rotation treatments exhibit aslight, yet steady decline in organism density. However, theSingle rotation treatment displays a larger decline in organism density, reaching a value of approximately 0.9. The Single rotation instructions provided organisms with the ability
to easily send a message and then rotate one cell to the left

We focus on the most abundant, or dominant, genomes
produced by runs. These dominant genomes are extracted
from each run at its conclusion, and a replicate of each isused to seed 400 demes which are then run for one competition period. While these demes are executing, we record foreach deme the organism density, total births, and number oforganisms running in an interrupted state. Figure 7 showsgraphically the correlation between organism density and total births per deme averaged over all dominant genomes. As
seen in Figure 7, after update 4, both the organism density
and total births per deme plateau. Therefore, deme-wide
self-replication behavior, which is present before update 4,
is suppressed when the organism density reaches approximately 0.8, demonstrating a quorum has been reached.
To this point we have not discussed methods by which
the organisms implement quorum sensing. Figure 8 plots theaverage number of organisms per deme that are executing in
an interrupt handler. This curve closely mirrors the curves
in Figure 7, providing an indication that interrupts are being
used to suppress organism self-replication. In addition, if
we disable messaging, therefore organisms cannot become
interrupted, the average organism density within a deme
quickly increase to 1.0 and all demes die out due to energy
depletion. This provides further evidence that interruptcausing messages are an important feature of the evolved
genomes. Now let us focus on the genome of an organismthat realizes this behavior.

3.4. Genome Analysis
Here, we focus on the dominant genome that produced thelowest average organism density of 0.67. An organism containing this dominant genome, shown in Figure 9, will execute the first 16 instructions in the genome before it replicates, as denoted by the black line to the left of the genome.
During this sequence the organism sends a single message

into the interrupt handler caused by receiving a message,
the organism will produce three messages. Hence executionof the interrupt handler produces a positive feedback loop
where the level of messaging (AI) in the system is increased,thus tripling the chances than an organism will become interrupted. Therefore, the expression of this individual behavior in a dense group of digital organisms will cause anorganism to remain in a state of perpetual interruption andnever self-replicate.

Figure 7: Organism density and total births perdeme for dominate organisms.

Figure 8: Average number of organisms interrupted
per deme.
Figure 9: Evolved dominate genome that produces
the lowest average organism density.
to its initially faced cell and the two neighboring cells to
its left, finally replicating while facing the cell one rotation
to the left of its initial facing. In short, the organism will
send 3 messages for every 16 executed instructions during
normal execution and then replicate. Upon replication theorganism’s state is reset, causing the genome to be processedfrom the beginning. Since genomes are executed in a cyclicmanner, this sequence will be repeated until the organism
either runs out of energy, is replaced by an offspring of another organism, or is interrupted. If interrupted, the current
context of this organism is saved and the interrupt-causing
message is processed in the interrupt handler, denoted by
the red boxes at the bottom (beginning of handler) and top(end of handler) of the genome in Figure 9. While interrupted, the organism will send one message to the cell it
currently faces and two messages to the cell left of its initialfacing. Moreover, the organism will remain in the interrupt
handler, and hence will not replicate, until all received messages have been processed. Furthermore, for every entrance

3.5. Experiments with Larger Demes
To determine whether this QS behavior is truly density based
we seeded demes several times larger than the original 5 × 5demes in which the behavior evolved. Table 1 provides a listof deme sizes tested, their scale relative to a 5×5 deme, total
number of demes per run, and total number of demes used
to generate averages plotted in Figure 10. Note that only 15of the 20 runs evolved population control behavior, so only
those dominants were used, producing the values in column
4 of Table 1. Each deme is again allowed to execute for a single competition period and the average organism density for
all three scalings over time is shown in Figure 10. The final
average densities produced for all three scalings are insignificantly different. Therefore, the evolved dominant genomes
exhibit a quorum sensing behavior that suppresses organism self-replication under multiple scalings. In addition, aquorum is reached at similar organism densities.

Table 1: Deme size comparision
deme size N × larger # demes total demes
5×5
1
400
6000
25 × 2525
20
300
50 × 50100
10150

Continuing with this line of research, we intend to extend
the interrupt model to incorporate active messages, enabling
the sending of a message to a specific handler. This extension will move us one step closer to the TinyOS execution
model, enabling us to evolve digital organisms with capabilities similar to those of wireless sensor network nodes. We
also intend to add individual tasks in order to study tradeoffs between individual and group-level behaviors. Lastly,
we plan to remove the intra-deme mutation restriction that
we used in this paper, so that our model will more closely
resemble the natural world.
Acknowledgments. This work was supported by NSF
Grants CCF-0750787, CNS-0751155, CCF-0820220, by U.S.
Army Grant W911NF-08-1-0495, and by a Quality Fund
Grant from Michigan State University.

5.

Figure 10: Average organism density under multiple
deme sizes.
Finally, we seeded a single 100 × 100 deme with an organism containing the genome in Figure 9. We then allowed thedeme to execute for one competition period, and we tracked
the constituent organisms’ execution behavior. Figure 11
shows snapshots of the resulting behavior, where each (x, y)
coordinate corresponds to a single cell in the 100×100 deme.
A cell is colored according to the current activity withinthat cell. If a cell does not contain an organism, it is colored white. A cell that contains an uninterrupted organism
is colored black, and a red cell denotes the presence of anorganism in an interrupted state. As depicted in Figure 11,
the population quickly switches behaviors when it becomes
dense. In fact, the time difference between Figures 11(c) and11(e) is less than two updates. The rapid change is behavior
is a hallmark of QS and has been observed in natural andnow digital organisms.

4.

CONCLUSIONSIn this paper we have demonstrated the evolution of quorum sensing behavior in digital organisms. Specifically, we
examined the evolution of behavior that suppresses individual self-replication under high density conditions. First, we
showed that this type of behavior evolves in a majority ofruns in all three of our rotation treatments. Second, we extracted the dominant genomes from the single rotation treatments and showed the tight correlation between organism
density, total births, and number of interrupted organisms.
Third, we discussed the individual behavior of the dominant
genome that produced the lowest organism density. Fourth,
we increased the size of the demes by two orders of magnitude and showed the average organism density remained thesame. Lastly, we visualized the rapid change in behavior ofa dominant organism in a deme 400 times larger than theenvironment it evolved in.

REFERENCES[1] C. Adami, C. A. Ofria, and T. C. Collier. Evolution of
biological complexity. Proceedings of the National
Academy of Sciences, 97(9):4463–4468, April 2000.
[2] O. Babaoglu, G. Canright, A. Deutsch, G. A. D. Caro,
F. Ducatelle, L. M. Gambardella, N. Ganguly,
M. Jelasity, R. Montemanni, A. Montresor, and
T. Urnes. Design patterns from biology for distributed
computing. ACM Transactions on Autonomous andAdaptive Systems, 1(1):26–66, 2006.
[3] O. Béjà, E. N. Spudich, J. L. Spudich, M. Leclerc, andE. F. DeLong. Proteorhodopsin phototrophy in theocean. Nature, 411:786–789, 2001.
[4] R. D. Berg. The indigenous gastrointestinal microflora.
Trends in Microbiology, 4(11):430 – 435, 1996.
[5] F. Bernardini, M. Gheorghe, and N. Krasnogor.
Quorum sensing P systems. Theor. Comput. Sci.,
371(1-2):20–33, 2007.
[6] S. P. Brown and R. A. Johnstone. Cooperation in the
dark: Signalling and collective action inquorum-sensing bacteria. Proc. of the Royal Society of
London B: Biological Sciences, 268(1470):961–965,
2001.
[7] B. Crespi. The evolution of social behavior in
microorganisms. Trends in Ecology and Evolution,
16(4), 2001.
[8] D. Davies, M. Parsek, J. Pearson, B. Iglewski,
J. Costerton, and E. Greenberg. The involvement ofcell-to-cell signals in the development of a bacterial
biofilm. Science, 280(5361):295–8, Apr. 1998.
[9] T. R. de Kievit and I. B. H. Bacterial quorum sensingin pathogenic relationships. Infect. Immun.,
68(9):4839–4849, September 2000.
[10] M. Dworkin and D. Kaiser. Cell interactions inmyxobacterial growth and development. Science,
230(4721):18–24, Oct. 1985.
[11] D. Floreano, S. Mitri, S. Magnenat, and L. Keller.
Evolutionary conditions for the emergence ofcommunication in robots. Current Biology,
17:514–519, March 2007.
[12] S. K. Hansen, P. B. Rainey, J. A. J. Haagensen, and
S. Molin. Evolution of species interactions in a biofilm
community. Nature, 445:533–536, February 2007.
[13] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and
K. Pister. System architecture directions for networked
sensors. SIGPLAN Not., 35(11):93–104, 2000.

(a) t = 0.0 updates(b) t = 3.2 updates(c) t = 4.0 updates(d) t = 4.8 updates(e) t = 5.6 updates(f) t = 8.0 updates

Figure 11: Images of a 100 × 100 deme initially seeded with the genome shown in Figure 9. Figure 11(a)shows the initial state of the deme with a single uninterrupted organism in the lowest, left-most cell. Figures
11(b) and 11(c) show a steady exponential increate in population size where the majority of organisms are
executing sequentially. Figures 11(d) and 11(e) depict the rapid behavioral change from self-replication to
suppression of self-replication. Lastly, Figure 11(f ) shows the state of the deme population 40% of the way
through a competition period.
[14] R. E. Lenki, C. A. Ofria, T. C. Collier, and C. Adami.
Genome complexity, robustness and genetic
interactions in digital organisms. Nature, 400:661–664,
1999.
[15] R. E. Lenski, C. Ofria, R. T. Pennock, and C. Adami.
The evolutionary origin of complex features. Nature,
423:139–144, 2003.
[16] R. C. Massey, M. J. Horsburgh, G. Lina, M. Höök, ,and M. Recker. The evolution and maintenance ofvirulence in staphylococcus aureus: a role forhost-to-host transmission? Nature Reviews
Microbiology, 4:953–958, December 2006.
[17] P. McKinley, B. Cheng, C. Ofria, D. Knoester,B. Beckmann, and H. Goldsby. Harnessing digital
evolution. IEEE Computer, 41(1):54–63, January 2008.
[18] M. B. Miller and B. L. Bassler. Quorum sensing inbacteria. Annu. Rev. Microbiol, 55:165–199, 2001.
[19] C. D. Nadell, J. B. Xavier, S. A. Levin, and K. R.
Foster. The evolution of quorum sensing in bacterial
biofilms. PLoS Biology, 6(1):0171–0179, January 2008.
[20] K. Nealson and J. Hastings. Bacterial
bioluminescence: its control and ecologicalsignificance. Microbiol. Rev., 43(4):496–518, 1979.
[21] K. H. Nealson, T. Platt, and J. W. Hastings. Cellular
control of the synthesis and activity of the bacterial
luminescent system. J Bacteriol., 104(1):313–322,
1970.
[22] C. Ofria and C. O. Wilke. Avida: A software platform
for research in computational evolutionary biology.
Artificial Life, 10:191–229, March 2004.

[23] J. Park, R. Jagasia, G. F. Kaufmann, J. C. Mathison,
D. I. Ruiz, J. A. Moss, M. M. Meijler, R. J. Ulevitch,
and K. D. Janda. Infection control by antibody
disruption of bacterial quorum sensing signaling.
Chemistry & Biology, 14(10):1119–1127, Oct. 2007.
[24] J. R. Porter. Antony van leeuwenhoek: tercentenary of
his discovery of bacteria. Microbiol. Mol. Biol. Rev.,40(2):260–269, 1976.
[25] F. J. Romero-Campero and M. J. Pérez-Jiménez. A
model of the quorum sensing system in Vibrio fischeriusing P systems. Artificial Life, 14(1):95–109, 2008.
[26] G. Terrazas, N. Krasnogor, M. Gheorghe,
F. Bernardini, S. Diggle, and M. Cámara. An
environment aware P-System model of quorum
sensing. In S. B. Cooper, B. Löwe, and L. Torenvliet,
editors, New Computational Paradigms, volume 3526
of Lecture Notes in Computer Science, pages 479–485.
Springer, 2005.
[27] C. M. Waters and B. L. Bassler. Quorum sensing:
Cell-to-cell communication in bacteria. Annual Review
of Cell and Developmental Biology, 21:319–346, 2005.
[28] D. Whitley, S. Rana, and R. B. Heckendorn. Islandmodel genetic algorithms and linearly separable
problems. In Proceedings of AISB Workshop on
Evolutionary Computation, volume 1305 of LNCS,
pages 109–125. Springer-Verlag, 1997.
[29] D. S. Wilson. Introduction: Multilevel selection theory
comes of age. The American Naturalist, 150(S1-S4),
July 1997.