In (L. Nadel and D. L. Stein, eds.) 1993 Lectures in Complex Systems, Addison Wesley, 1995
Liane Gabora
In order for a pattern of information to evolve, we need a way of generating variations of the pattern, and a way of selectively replicating it. In Adaptation in Natural and Artificial Systems [11], Holland introduced a computational model of how these processes are carried out on patterns of genetic information in biological systems. In this paper we introduce a computational model of how they are carried out on patterns of cultural information in a society of interacting individuals.
Ideas, like genomes, are patterns that evolve; however their evolution is not subject to the same constraints, and employs different mechanisms. The generation of variation is less random in cultural evolution than in biological evolution; it reflects the accumulated knowledge of individuals, and the social structure in which they are embedded. In cultural evolution, selective replication is Lamarkian; an idea can be modified through experience after it has been phenotypically expressed. Genetic information is coded in a physical sequence of nucleotides, and contains the instructions for its own replication, whereas ideas are coded in patterns of neuron activation, and do not contain the instructions for their replication; they rely on human hosts to replicate them. Ideas that satisfy our needs or drives are preferentially learned and implemented. Thus the fitness landscape for the evolution of ideas is molded by our drives. By developing a minimal model that incorporates mechanisms which differentiate cultural evolution from biological evolution, we hope to broaden our understanding of how it is that something can evolve.
In The Selfish Gene [6], Dawkins coined the word "meme" to refer to "ideas, catch-phrases, clothes-fashions, ways of making pots or building arches." He elaborates: "Just as genes propagate themselves in the gene pool by leaping from body to body via sperm or eggs, so memes propagate themselves in the meme pool by leaping from brain to brain." Our model is called Meme and Variations because it is based on the premise that new ideas are variations of old ones; they result from tweaking or blending existing ideas [12]. We will explore the impact of three phenomena that are unique to cultural evolution. The first is knowledge-based operators: brains detect regularity and build schemas that they use to adapt the mental equivalents of mutation and recombination to their meme substrates. The second is imitation: ideas spread when members of a society observe and copy one another. This is seen in both animal and human societies [4, 15, 16]. Imitation enables individuals to share complete or partial solutions to the problems they face. The third is mental simulation: individuals can imagine what would happen if a meme were implemented before resources are spent on it. This provides them with a rudimentary form of selection before the phenotypic expression of a meme.
We will adopt the terminology of biology. Each component of a meme is referred to as a locus, and alternative forms of a locus are referred to as alleles. The processes that generate variation -- the cultural counterparts to mutation and recombination -- are referred to as operators. Forward mutation is mutation away from the initial or wild type allele, and backmutation is mutation from an alternative form back to wild type. Changes in the relative frequencies of different alleles due to random sampling processes in a finite population are referred to as drift [17]. The set of all existing patterns is referred to as the population. Following Braitenberg [6], an individual is referred to as a vehicle, and the set of all vehicles is referred to as the society.
Donald [9] has provided substantial evidence that the earliest form of culture was mimetic display. The memes in Meme and Variations represent mating displays. A meme has six loci that correspond to six body parts: left forelimb, right forelimb, left hindlimb, right hindlimb, head, and tail. Each locus has a floating point activation between -0.5 and 0.5 which determines the amount of movement (angle of rotation from rest position) of the corresponding body part when the meme is implemented. A value of 0.0 corresponds to rest position; values above 0.0 correspond to upward movement, and values below 0.0 correspond to downward movement. Floating point loci activations produce graded limb movement. However for the purpose of mutation, loci are treated as if there are only three possible alleles at each locus: stationary, up, and down. Six loci with three possible alleles each gives a total of 729 possible memes.
The neural network is an autoassociator; it learns the identity function between input and output patterns. It has six input/output units numbered 1 through 6, corresponding to the six body parts. It has six hidden units numbered 7 through 12, corresponding to the general concepts, "forelimbs", "hindlimbs", "left", right", "movement", and "symmetry" (Figure 1).
Hidden units are linked with positive weights to input/output units that are positive instances of the concepts they represent, and linked with negative weights to input/output units that represent negative instances of the memes they represent (thus "left forelimb" is positively linked to "left" and negatively linked to "right"). Hidden units that represent opposite concepts have negative connections between them. The hidden units enable the network to encode the semantic structure of a meme, and their activations are used to bias the generation of variation (Section 2.5).
The neural network starts with small random weights between input/output nodes. Weights between hidden nodes, and weights between hidden nodes and input/output nodes, are fixed at +/- 1.0. Memes are learned by training for 50 iterations using the generalized delta rule with a sigmoid activation function [10]. The relevant variables are:
aj = activation of unit j
tj = the jth component of the target pattern (the external input)
wij = weight on line from unit i to unit j
b = 0.15
q = 0.5
For the movement node, we use the absolute value of ai. The error signal, dj, is calculated as follows. For input/output units:
For hidden units:
The embodiment is a six-digit array that specifies the behavior of the six body parts. While the output of the neural network represents what the vehicle is thinking about, the embodiment represents what the vehicle is doing. A meme can not be observed and imitated by other vehicles until has been copied from the neural network to the embodiment.
An optimal meme is one in which all body parts except the head are moving, and limb movement is symmetrical. (Thus if the left forelimb is moving up, the right forelimb is moving down, and vice versa.) This is implemented as follows:
F = fitness
m = 2.5
am = activation of movement hidden node
as = activation of symmetry hidden node
ah = activation of head node
i = 1 if ah = 0.0, otherwise i = 0
F = mam + 2mas + mi
This fitness function corresponds to a relatively realistic display, but it also has some interesting properties. A vehicle that develops the general rule "movement improves fitness" risks overgeneralization since head stability contributes as much to fitness as movement at every other limb. This creates a situation that is the cultural analog of overdominance in genetics; the optimal value of this locus lies midway between the two extremes. We also have a situation analogous to bidirectional selection or underdominance; the optimal value of the tail locus lies at either of the two extremes. There is epistasis; the value of what one limb is doing depends on what its left-right counterpart is doing. Finally, since there is one optimal allele for the head, two optimal alleles for the tail, two optimal forelimb combinations, and two optimal hindlimb combinations, we have a total of eight different optimal memes. This enables us to perform a comparative analysis of diversity under different ratios of creation to imitation. Note that there are nonoptimal local maxima, corresponding to memes in which limbs are moving, but in the same direction.
The basic idea of the memetic algorithm is to translate knowledge acquired through the process of evaluating a new meme into educated guesses about what increases meme fitness. Each locus starts out with the allele for no movement, and with an equal probability of mutating to each of the other two alleles (the alleles for upward and downward movement). A new meme is not learned unless it is fitter than the currently-implemented meme, so we use the difference between these two memes to bias the direction of mutation.
Two rules of thumb are used. The first rule is: if the fitter meme codes for more movement, increase the probability of forward mutation and decrease the probability of backmutation. Do the opposite if the fitter meme codes for less movement. This rule of thumb is based on the assumption that movement can general (regardless of which particular body part is moving) can be beneficial or detrimental. This seems like a useful generalization since movement of any body part uses energy and increases the likelihood of being detected. It is implemented as follows:
am1 = activation of movement unit for currently-implemented meme
am2 = activation of movement unit for new meme
p(fmut)i = probability of forward mutation at allele i (increased movement)
p(bmut)i = probability of backward mutation at allele i (decreased movement)
IF (am2 > am1)
THEN p(fmut)i = MAX(1.0, p(fmut)i + 0.1)
ELSE IF (am2 < am1)
THEN p(fmut)i= MIN(0.0, p(fmut)i - 0.1)
p(bmut)i = 1 - p(fmut)i
The second rule of thumb biases the vehicle either toward or away from symmetrical limb movement. It has two parts. First, if in the fitter meme both members of one pair of limbs are moving either up or down, increase the probability that you will do the same with the other pair of limbs. Second, if in the fitter meme, one member of a pair of limbs is moving in one direction and its counterpart is moving in the opposite direction, increase the probability that you will do the same with the other pair of limbs. This generalization is also biologically useful, since many beneficial behaviors (walking, et cetera) entail movement of limbs in opposite directions, while others (galloping, etcetera) entail movement of limbs in the same direction. Space constraints do not permit a detailed explanation of the implementation of this rule; however, it is similar to the implementation of the first rule.
In summary, each meme is associated with a measure of its effectiveness, and generalizations about what seems to work and what does not are translated into guidelines that specify the behavior of the memetic algorithm.
Vehicles are in a two-dimensional wrap-around 10x10 grid-cell world, one vehicle per cell. Each iteration, every vehicle has the opportunity to (1) acquire a new meme through creation or imitation, (2) update the mutation operator, and (3) implement the new meme.
Vehicles have an equal probability of creating and imitating. To create a new meme, the memetic algorithm is applied to the meme currently represented on the input/output layer of the neural network. For each locus, a vehicle decides whether mutation will take place. The probability of mutation is specified globally at the beginning of a run. If it decides to mutate, the direction of mutation is stochastically determined. If the new meme has a higher fitness than the currently-implemented meme, the vehicle learns and implements the new meme.
To acquire a meme through imitation, a vehicle randomly chooses one of its eight neighbors and evaluates the fitness of the meme the neighbor is implementing. If its own meme is fitter than that of the neighbor, it chooses another neighbor, until it has either observed all eight neighbors, or found one with a fitter meme. If no meme is found, the vehicle does nothing. Otherwise, the neighbor's meme is copied to the input/output layer, and it is learned.
Since in both creation and imitation a new meme is not acquired unless it is fitter than the currently implemented meme, the new meme provides information that is used by the memetic algorithm. For example, since we arbitrarily chose a fitness function in which movement is generally beneficial, if the new meme coes for more movement than the old meme, the probability of forward mutation will almost always increase.
In the no mental simulation condition, whether the new meme was acquired through creation or imitation, it must be implemented for at least one iteration before its fitness can be assessed. In this case mutation operators are updated the following iteration.
The new meme is copied from the neural network to the embodiment. The vehicle is now implementing the new meme.
The following experiments were conducted using a mutation rate of 0.17 per locus, a 1:1 creation to imitation ratio, and all cultural evolution strategies operative, unless otherwise indicated.
Initially all vehicles are immobile. The immobility meme quickly mutates to a new meme that codes for movement of a body part. The new meme has a higher fitness and is preferentially implemented. Diversity increases as memes continue to mutate and spread through imitation. Diversity peaks when the first maximally-fit meme is found, and decreases as the society converges on maximally-fit memes (Figure 2).
The best performance is obtained with a high mutation rate: between 0.07 and 0.22 mutations per locus, or approximately one mutation per meme (Figure 3). This is probably because mental simulation ensures that poor memes are not implemented, and good memes are imitated by others, so they are unlikely to be lost through mutation from the society as a whole.
Stabilization takes longer for epistatically-linked loci than over- or underdominant loci (Figures 4 and 5).
Since we have eight optimal memes, there are many stable configurations for the distribution of memes. Figures 4 and 5 reveal the presence of drift is observed among equally-fit alleles, as predicted by Cavalli-Sforza and Feldman's mathematical model [7].
The three cultural evolution strategies--mental simulation, imitation, and knowledge-based operators -- were made inoperative one at a time to determine to their contribution to optimization speed and peak mean fitness. All three increase the rate of optimization, and mental simulation and imitation also increase peak mean fitness (Figure 6).
The highest mean fitness is achieved when both creation and imitation are employed, in a ratio of approximately 2:1 (Figure 7).
However, the fitness of the fittest meme (Figure 8) increases as a function of the ratio of creation to imitation.
Since the vehicles with the fittest memes gain nothing by imitating others, there is a trade-off between average meme fitness and fitness of the fittest meme. Interestingly, meme diversity also varies with the ratio of creation to imitation (Figure 9), ranging from 1-2 memes when p(create) = 0.25 to 10-11 memes when p(create) = 1.0. When p(create) = 0.75, the society converges on 7-8 memes; it finds all (or nearly all) of the fittest memes. A nice balance is struck between the diversifying effect of mutation and the converging effect of imitation. In future experiments in which the fitness landscape will fluctuate, maintaining diversity may prove to be more important than speed.
This program will soon run on the connection machine, which will allow us to increase the size of the artificial society to several thousand individuals. We will examine the effect of erecting complete or semipermeable barriers between different societies, and the effect of migration.
A salient feature of human behavior is self-tuning; individuals modify their behavior according to how well it satisfies their needs or drives. Drives amount to conceptual niches that guide the evolution of culture. In future experiments vehicles will have two drives: to mate, and to acquire territory. The implementation of a meme will produce a response in neighboring vehicles that satisfies one drive or the other. When a drive is satisfied by implementing a display, its strength decreases. Fitness functions are not built into vehicles; they vary with the relative strengths of the drives. Memes are expected to specialize for one drive or the other; evolving along different trajectories toward two different basins of attraction.
Vehicles will be able to monitor their success with creation and imitation, and adjust their creation/imitation ratio accordingly. Individual differences will be introduced. Those that have a flawed memetic algorithm might specialize in imitation, while those that can not correctly translate the behavior of a neighbor into input to their neural network might specialize in creation. When vehicles can recognize one another and associate each other with the fitness of their memes, a hierarchical social structure could emerge in which some vehicles are ignored while others are imitated by many.
Another plan is to add recombination: vehicles will acquire new memes by combining a meme that is being imitated with a previously-learned meme. This will allow them to specialize on different parts of a meme, and then share partial solutions. Vehicles will be able to monitor the relative effectiveness of mutation and recombination throughout a run, and adjust their frequencies accordingly.
This work differs from anthropological approaches to culture in that the goal is not to put together a detailed picture of how human culture evolved, but to abstract a general model of cultural evolution. Cavalli-Sforza and Feldman [7] have developed a mathematical theory of cultural evolution which has been extended by
Lumsden and Wilson [14]. The computational approach taken here allows us to model not only what happens, but the mechanisms that make it happen. It enables us to look for patterns that arise when these mechanisms are carried out in parallel in a society of interacting individuals, and to use relatively complex memes with more than one or two alleles.
Some interesting work has been done using a genetic algorithm to investigate the evolution of cooperation [2], and the interaction between genetic evolution, learning, and culture [3]. Hutchins and Hazelhurst used a computer model to explore the relationship between environment, internal representation of the environment, and cultural artifacts that mediate the learning of environmental regularity [13]. These studies model vertical (intergenerational) transmission. Meme and Variations differs from these approaches in that we model horizontal (intragenerational) transmission, and we look at the dynamics that emerges when a society of agents can each invent their own ideas and imitate others.
I would like to thank Dave Chalmers and David Jefferson for useful comments on a draft of this manuscript. Thanks also to the Center for the Study of the Evolution and Origin of Life (CSEOL) at UCLA for inspiration and support.