Evolving the selfish herd: emergence of distinct aggregating strategies in an individual-based model

Andrew J Wood, Graeme J Ackland

Abstract

From zebra to starlings, herring and even tadpoles, many creatures move in an organized group. The emergent behaviour arises from simple underlying movement rules, but the evolutionary pressure which favours these rules has not been conclusively identified. Various explanations exist for the advantage to the individual of group formation: reduction of predation risk; increased foraging efficiency or reproductive success. Here, we adopt an individual-based model for group formation and subject it to simulated predation and foraging; the haploid individuals evolve via a genetic algorithm based on their relative success under such pressure. Our work suggests that flock or herd formation is likely to be driven by predator avoidance. Individual fitness in the model is strongly dependent on the presence of other phenotypes, such that two distinct types of evolved group can be produced by the same predation or foraging conditions, each stable against individual mutation. We draw analogies with multiple Nash equilibria theory of iterated games to explain and categorize these behaviours. Our model is sufficient to capture the complex behaviour of dynamic collective groups, yet is flexible enough to manifest evolutionary behaviour.

Keywords:

1. Introduction

Collective aggregation behaviour is a ubiquitous biological phenomenon (Sumpter 2006). The most established candidates for stimuli driving its evolution are foraging efficiency (Cody 1971; Murton 1971; Krebbs et al. 1972; Benkmann 1988) and reducing predation risk. Predation avoidance has many suggested mechanisms such as the ‘many eyes’ effect (Lima 1995), the confusion effect (Neill & Cullen 1974; Hall et al. 1986) or dilution and encounter effects (Cresswell 1994), as described in the selfish herd hypothesis (Hamilton 1971; Morton et al. 1994). Recent experimental work has tended to favour predation as the dominant effect (Hart & Freed 2005).

Modelling aggregations is a different but related problem; the required level of detail remains unclear, but the ubiquity of the phenomena suggests simple underlying principles (Parrish & Edelstein-Keshet 1999). Here, we adopt an individual- or agent-based modelling approach considering each group member separately and specifying the interaction rules between them. This approach is well developed (Aoki 1982; Reynolds 1987; Huth & Wissel 1992; Couzin et al. 2002) but the necessary requirements for ‘realistic’ models are not firmly established; greatly simplified models (Vicsek et al. 1995) have demonstrated many of the coarse features. Understanding is also hampered by the lack of real-time data to compare systematically with simulation results, though this situation is improving (Tien et al. 2004; Becco et al. 2006). Among the many plausible individual-based models, those based on nested radii following Aoki (1982) and Couzin et al. (2002) now have experimental evidence (Tien et al. 2004), and we adopt this style here.

There have been many models of the attack of predators on a prey group (Inada & Kawachi 2002; Lee et al. 2006) but only limited attempts to include evolutionary dynamics (Zheng et al. 2005). A more complete model has allowed trait evolution (Spector et al. 2005) but does not use nested radii. There is also work that interprets Hamilton's hypothesis literally by assuming that the individuals' decisions are based on calculation of the so-called ‘domains of danger’, the area to which a given individual is closer than any other individual (Reluga & Viscido 2005).

In this work, we consider a model for aggregation in two dimensions (Couzin et al. 2002) based on local rules that retain a considerable degree of biological plausibility. This model predicts several distinct aggregation behaviours, referred to as phases, dependent on the values of the model parameters. Individuals sense within three distinct regions (Aoki 1982): a repulsive zone; an orientation zone; and an attractive zone each of which is a circle excluding an area defined by a blind angle to the rear. Individuals move away from others in the repulsive zone, parallel to others in the orientation zone and towards those in the attractive zone. The relative sizes of these zones determine the phase of the consequent group; different phases may correspond to differing species or alternate behaviours for the same species. For convenience, we shall use the terminology flock or flocking to refer to the aggregation and the term boid (Reynolds 1987) as an identifier for the component individuals.

2. Model description

The group we study has N boids, indexed by i, with position ri(t) and velocity vi(t). The speed vi≡|vi(t)| has constant magnitude for each boid during each instance. We use the term instance to refer to a single application of selection stimuli followed by an evolutionary step (see below); run refers to a large number of instances during which boid behaviour evolves.

The movement rules are implemented in discrete time-steps Δt as follows. At each time-step, a new position ri(tt)=ri(t)+vi(ttt and velocity vi(tt) are calculated by examining the area immediately adjacent to each individual. We use the angle θ to refer to the total viewing arc and the overhat notation to notate a unit vector. Firstly, the regions are scanned outwards starting in the centre in order to determine orientation in response to flock fellows in order to produce a normalized vector Embedded Image using the algorithm described by Couzin et al. (2002). We defineEmbedded Image(2.1)If a boid or boids are detected in the region defined by rij<Rr,i and not excluded by the blind angle Embedded Image then the vector vb isEmbedded Image(2.2)If individuals are found then this determines Embedded Image regardless of more distant boids. In the next two regions, defined by Rr,i<rij<Ro,i and Ro,i<rij<Ra,i and not excluded by the blind angle, orientation or attraction are attempted.Embedded Image(2.3)If boids are found in only one region then we define Embedded Image or Embedded Image. If found in both regions then Embedded Image. Using this method, we have determined a unit vector associated with the boid–boid interaction Embedded Image.

If another object (predator or food, at Embedded Image) is detected within the visual range Embedded Image then another normalized vector Embedded Image is constructed (towards food, away from predator), which has an associated evolvable weighting Embedded Image. This step is not done if repulsion was determined (or alternately Embedded Image). Vectorial Gaussian random noise with unit standard deviation (Embedded Image) multiplied by the evolvable parameter σi is also calculated. A new vectorial headingEmbedded Image(2.4)is finally calculated. If, in order to turn onto this heading, the boid exceeds its maximum allowed turn then it turns through this angle, ϕi, instead. The resulting heading is normalized to unit length and multiplied by vi to determine the velocity vi(tt) of the ith boid. Once this is complete for all N individuals, the simulation is iterated forward in time by the time-step Δt.

The parameters of the model evolve via natural selection in response to simulated stimuli. Genetic algorithms have been used before in these situations (Oboshi et al. 2002; Hancock et al. 2006) but not on a biologically inspired individual-based model in continuous space. Our model also evolves on an individual basis—with each boid possessing characteristics different from its fellows but similar to those of its haploid parent. We constrain two parameters in the model by preserving each individual's possible sighting area Embedded Image and possible movement area Embedded Image. We adopt this computational choice in order to prevent the evolution of boids from simply maximizing all possible parameters. Instead, a balancing solution between contrasting properties must be found; our choice means that long-range vision compromises peripheral vision and high speed compromises turning ability.

The third parameter is Ro,i, which can evolve freely in the range Rr,i<Ro,i<Ra,i. There are two other evolvable parameters; the noise σi and the weighting associated with the detection of stimuli Embedded Image. Therefore, the individuals evolve in a five-dimensional continuous trait space.

Our procedure for a run is:

  1. Begin the simulation with N boids each with some set of either predetermined or random initial parameters and random initial positions.

  2. Run the simulation for specified amount of time (warm-up time) to allow aggregation to occur or otherwise. The warm-up time must be sufficiently long so that the boids have attained a phase. This is complete within 10 000 time-steps (15 min with our choice of time-step).

  3. Introduce the artificial stimuli, predators or food, and iterate until completion—see below.

  4. Breed the next generation of boids. This may involve completely regenerating the flock or retaining some and replenishing according to the information obtained in step (iii).

  5. Return to (ii), this ‘instance’ represents a single generation. Repeat for a number of generations, creating a ‘run’.

We evolve the parameters at each breeding step of the algorithm by adding a random number chosen from a uniform distribution in the range [−m, m], where m is a constant proportion of the existing value or a fixed value. As we are evolving multiple parameters, the dynamics of the evolutionary process may be affected by the relative values of the mutation ranges m. In this study, we endeavour to suppress any effects associated with this by choosing fixed fractional values for the mutation range. In each simulation, we ran the code for 1000–2000 generations which in most cases was sufficient to observe a state that could be described as steady.

(a) Model parameters

The model has a number of parameters, representing both biological features and choices in methodology (table 1). These can have an important effect on the outcome of the simulations, so we have sought to explore the effect of varying as many parameters as feasible within this study. Some choices are clear: the simulations are extremely sensitive to insufficient warm-up time, but once the flock is formed from the randomized starting configuration consistent results are obtained. We have chosen the constraints to ensure that our parameters lie within biologically plausible ranges explored by Couzin et al. (2002). The radius of repulsion, Rr sets the length-scale in this model; all other length parameters are quoted in units of Rr to keep this study general. For guidance, Rr has been estimated as approximately a body length, e.g. approximately 0.1 m for a whiting (Merlangius merlangus; Hall et al. 1986). We use a time-step Δt of 0.1 s conforming to that used by Couzin et al. (2002) and Zheng et al. (2005).

View this table:
Table 1

The basic simulation parameters used unless otherwise stated in the text.

The adoption of a system with regularized values and no units leads to a generic phase diagram purely in terms of ratios to the body lengths (figure 1). By preference, we chose our sighting area to be Embedded Image, as this minimized the necessary warm-up space, and movement area to be Embedded Image. We have chosen to study a flock of eighty (80) individuals as a compromise between reasonable statistics and sufficient flock number to observe interesting effects (Parrish et al. 2002).

Figure 1

Phase diagram for flocks of identical boids with Embedded Image. Contours represent the average polarization, a measure of the group alignment (Couzin et al. 2002; black is angularly disordered, white is highly ordered). The coupling of the attraction radius to the viewing angle increases the instability of the flock and leads to a sharp drop in stability once the angle reaches 180°. There exists a previously unreported phase in two dimensions—the pack phase, for low Ro and moderate to high Ra. This type of flock is characterized by ‘follow-my-leader’ behaviour which leads to long strings of boids with moderately high values of the polarization. The swarm phase is characterized by continuous cycling of boids towards the group centre. It also possesses a sub-phase, a mill (or toroid in three dimensions) which has a non-zero value of angular momentum. The dynamic phase has a high degree of orientation, but has more lateral extent than the pack phase. The mill and dynamic phases can be seen in figure 2. Note this diagram is produced from homogeneous flocks, where all individuals are identical, rather than heterogeneous flock where the characteristics vary across individuals.

(b) Predation

To simulate predation, we sequentially introduce predatory boids, hoicks, to form the stimuli. We used eight in this study (10% of N) and allowed no more than one hoick at any given time. We chose three distinct types of predator, with total viewing angles of θ=90°, 180° and 270°, and velocity v=5.5, larger than the boids can possibly achieve. In addition, they are 10% superior to the boids in both aspects of the area constraint rules (i.e. so a hoick can be both faster and more manoeuvrable than a boid and similarly for viewing). The hoicks' movement rule is a subset of that chosen by Inada & Kawachi (2002): at each time-step they move towards the closest boid until they enter its repulsive zone. Predation is then considered successful, and both boid and hoick are removed from the simulation. The hoicks have a finite lifetime, we use 1000 time-steps, after which they are removed even if they have failed to catch a boid. This number simply rescales the probability of capture and our choice speeds up the simulation. Once all the hoicks for a given instance have been removed, the algorithm continues to step (iv) breeding 80 new boids from survivors with a small amount of mutation. We use Embedded Image in this part of the study; lower areas were found to be unable to produce boids that could see far enough to derive any benefit from group association—predation was essentially random.

(c) Foraging

Cody (1971) suggests that food distribution can drive the formation of desert mixed finch flocks. We design the stimulus with this in mind. The ‘warm up’ (step ii) occurs in a space of size (L/2)×(L/2). The space available to the flock is then doubled and a fixed amount of food is distributed into the quadrant which shares no long boundaries with the warm-up space. This decreases the randomness associated with spontaneous appearance of food—the birds must still actively seek out the food. The boids are attracted to food (via Embedded Image) within Embedded Image and consume a single unit whenever it first appears in their zone of repulsion. Once all the food has been consumed, the next generation is bred using the normalized food tally for the old flock as a discrete probability distribution, i.e. if boid i has collected fi units of food then boid i has a recurring probability, pi of parenting each new boid in the next generation ofEmbedded Image(2.5)

We found this method to be more robust than simply removing the worst performing individuals (although, of course, boids failing to find any food have zero probability of breeding) and it makes use of information that has no analogue in the predation case.

Guided by Cody's results (Cody 1971), we varied the distribution of the food by placing food at random in packets of specified sizes. As is held constant at Embedded Image, and the initial amount of food was constant at 1024 units. The simulation is deemed to be complete once seven-eighths of this food is found (for computational speed). The packets were given differing sizes in different runs, 1, 4, 16, 64 and 256 representing randomly placed sources with varying capacities to feed the boids.

3. Results

(a) Predation

The primary selection in all simulations occurs on the blind angle of the flock where a small blind angle of less than 80° (θ>281°) is quickly selected for, although with a fair degree of heterogeneity among individuals (σθ≈30°). This is consistent with experimental results suggesting that the blind angle for fish (whiting) is around 60° (Hall et al. 1986). This result is independent of the details of the hoicks. In addition, two distinct types of flock emerge: slow moving, milling groups (SM) and fast moving, dynamic groups (FD). Screen shots of these two distinct groups may be seen in figure 2.

Figure 2

Snapshot of the typical evolved flocks from the predation case showing the two different phases and their differing responses to attacks. (a) The compact, torus forming phase and its limited ability of the slow moving boids to avoid a fast moving predator. (b) The dynamic parallel phase; the flock has a high degree of orientational order and is loosely bound in space but upon attack fans out in an arc to avoid the predator. Boid heads are marked with a circle and the line indicates their current velocity. Predators are shown in greyscale and are marked with an arrow.

The FD response is evolved when mutation is sufficiently low (5% robustly forms this phase) and is more probable if the predator has a low viewing angle (90°). These boids have a high speed, meaning less interaction and a large orientational zone ro≈0.6ra resulting in the dynamic parallel phase (figure 2; Couzin et al. 2002). If the viewing area of the boids is reduced this phase is less favoured. The alternate behaviour (SM) involves boids evolving low speed and low value of the orientational parameter (Embedded Image). With the low value of Embedded Image, this creates a swarm phase (figure 2) with a degree of rotational order (i.e. a mill). The low speed allows a high turning angle, allowing the boids to interact strongly with their flock fellows as well as to individually respond rapidly to predator incursions. This behaviour is consistently found when mutation rates are high (20%) and enhanced when predators have a large viewing angle (270°).

We have examined the relative stability of these evolved behaviours. When simulations are started from one evolved state, then this state is maintained even in conditions where the other state usually evolves. This indicates that two distinct Nash equilibria—states from which no individual boid can benefit from changing its behaviour—exist on the fitness landscape of the model. The game-theoretic efficiency of the Nash equilibrium can be defined in terms of predator success; in the SM phase, predators are nearly always successful; but in the FD phase, predators are successful only 60–70% of the time. Two other parameters are evolvable: the noise σi and the weighting Embedded Image neither shows any selective pressure. The stability of the FD phase is also weakened by the adoption of smaller values of As, which is why we adopt a high value for this parameter.

(b) Foraging

Foraging promotes strong selection on both the speed of the boids, which increases rapidly to the maximum, and on the attraction radius, which increases in tandem to a value corresponding to θ∼90°. Once more, neither the noise nor the preference parameter plays a role. However, the orientational parameter varies systematically for differing food distributions (figure 3), though selection is much weaker. The variations we see in figure 3 can be explained in terms of the individual gain by being first to the food. With singly distributed food, the first boid to arrive eats it all: there is no advantage to following, so the non-flocking phase is stable, and there is no advantage of selecting a value for Embedded Image. With increased clumpiness, there is food for the ‘early boids’, so some Embedded Image increase is worthwhile giving a marginal gain in efficiency for a ‘pack’ phase. For highly clumped food, all the boids in the pack can eat and with the long, narrow viewing area, the pack as a whole is more likely to spot food than a lone individual. Here, the pressure to be first to the food is negligible; instead, being average is good enough. The result is that the boids stay more closely bound to one another and explore the space slowly and inefficiently; the pack takes longer to find the food and these simulations took almost 50% longer.

Figure 3

Evolution of the ratio of the interaction radii for the flocks. (a) Illustration of the final values after 2000 generations for the predation flocks. The dominant role of the mutation rates is clearly contrasted. (b) Illustration of the final values for run lasting 1000 generations in the foraging simulations. In each case, a single point represents an average of five separate runs each started from a differing random seed.

4. Discussion

We have presented an evolutionary model of flock formation. In effect, our methodology is a genetic algorithm with a goal function defined implicitly via the artificial environmental pressures we apply. Unlike work with fixed parameters and identical boids (Zheng et al. 2005), our flocks are wholly emergent from the model as all the parameters which determine the phases are evolvable. We emphasize that there is no coevolution in this model; we have adopted simple choices for the pressure in order to examine purely evolutionary effects.

Our broad results clearly show that predation risk drives the formation of stable flock formation and foraging need not. This is consistent with recent experimental findings (Hart & Freed 2005). This also provides good evidence that simple individual-based modelling described in this article has sufficient detail to be able to capture such effects. Our results may be interpreted as showing two distinct Nash equilibria: a more efficient phase and a less efficient one (figure 4).

Figure 4

Evolutionary trajectories to alternate phases. The parameters in this simulation are identical with the clump size set to 16. All that differs is that the respective groups are started from different positions in the phase space, shown as extra large symbols. There is clear contrast in the time to the location of food; the phase with low Ro (circles and diamonds) taking 50% longer than the phase with higher Ro (boxes and triangles). A point is plotted every 20 instances. The phase boundaries here are approximate and should be read in conjunction with the diagram earlier in this article (figure 1).

Predation produces tightly bound mills (SM) or dynamic groups (FD; figure 2). The circulating swarms are reminiscent of the elegant configurations formed by some schools of fish (e.g. picture in Parrish et al. 2002), with individuals constantly cycling to the centre from the outer parts. This is a local expression of the selfish herd hypothesis, with boids dynamically reducing their ‘domain of danger’ by hiding within their flock mates. The evolved flocks exhibit many of the identified patterns of escaping behaviour (Inada & Kawachi 2002), including the ‘Herd’ fleeing behaviour of the dynamic flock, where an arc is formed immediately in front of the predator. The swarm boids are heterogeneous and the groups they form are relatively noisy; this leads, upon attack, to the rapid singling out of a single, slower individual as the target and consequent short duration of attacks with the swarm structure unchanged. The fast dynamic groups display other behaviours; in particular, there is evidence of a precursor of the fountain effect (Hall et al. 1986) where the flock cycles around both sides of the predator. This is displayed by frequent splitting of the group, but the group becomes disconnected in two dimensions and reforms slowly. Further work is needed to establish the existence, or otherwise, of these manoeuvres in three dimensions.

The dynamic groups markedly reduce predator success; it seems that a range of complex manoeuvres enable these flocks to exploit a confusion effect. In the tightly bound phase, these manoeuvres are absent and the predators are invariably successful. These results complement the conclusions of Zheng et al. (2005), although our predators do not stochastically change their target boid, they pursue the nearest, allocated at each time-step, until capture, which may suppress flock manoeuvring possibilities. We have not explored different manoeuvres in detail as our primary motivation was to contrast the predatory behaviour with foraging. There is a plethora of options for future work in this regard with a variety of choices of both attack method of predator (Neill & Cullen 1974) and defence method of prey (Hall et al. 1986; Pitcher & Parrish 1993).

The foraging-evolved flocks consistently have a large viewing range and a small viewing angle of approximately 90°. A pack can be formed by the foraging behaviour—the boids follow each other in succession in the formation of a chasing pack—or the boids are widely distributed in space. For increasingly clumped food such a pack is formed, but when the food is unclumped and more uniformly distributed the packs do not form. This result is comparable to those from experimental studies (Krebbs et al. 1972; Benkmann 1988) and also the comparable work of Hancock et al. (2006). Again, further possibilities exist in methodology here such as contrasting regenerating with transient food (Cody 1971).

Comparison with evolutionary game theory is illuminating: our stable states correspond to Nash equilibria. In our model, a given boid has a fixed strategy defined by its parameters and evolved from a single stimulus, but in nature a given prey could choose between strategies according to stimuli. We have identified our observed phases with the confusion effect and the dilution or selfish herd effect but there are other observed effects, most prominently vigilance, that we have not identified. It is probable that this effect is strongly conditioned on group size; we tested our results with flocks of slightly larger and slightly smaller numbers but found no clear differences.

We note that we have crudely replicated the ‘correct’ evolutionary behaviour: boids looking for food prefer eyes looking forward, and when hunted the response is for eyes to be on the side of the head. The advantage of this modelling scheme is that we are evolving behavioural characteristics induced by model parameters which, in principle, can be compared by experiments or observations. It also enables us to attach a degree of understanding to effects that are directly evolved and to those which are simply side effects of models of this type (Murton 1971).

The individual-based model also confirms the recent result of Reluga & Viscido (2005) that an anti-predator response can emerge from a set of purely local rules in contradiction to Morton et al. (1994). This dependence on purely local rules is an important criterion for the successful implementation for any individual-based model. Though this model displays considerable richness in its behaviour, it is a matter of priority to encapsulate the key effects observed here to inform the construction of simpler models that may more effectively mimic the real biological processes.

Acknowledgments

A.J.W. would like to thank Iain Couzin and David Sumpter for various discussions and encouragement. We thank Ewen Tweedie for his contributions to the early stages of this project and Sam Yoffe for his contributions to the latter stages. The authors were supported by the EPSRC funded NANIA network under grant number GR-T11753.

Footnotes

    • Received March 6, 2007.
    • Accepted March 30, 2007.

References

View Abstract