next up previous

4.2.3 Mutation

In sexual reproduction, the situation is again more complicated. We need to insert 1s into random locations in the genomes of new offspring. Actually turning a bit to 1 is no problem -- we simply use a logical OR operation, which is the binary | operator in C. The difficult part is choosing where in the genome to insert the new mutations. If we choose a location were there is already a 1 bit, the new mutation will have no effect, and over the span of the entire simulation we will artificially extend the life of the species. Even if we check first to make sure the bit is 0, we may be artificially shortening the extinction time, since the new 1 may be at a locus where there are already 1s in other individuals and we will increase the probability of fixation at that locus.

The solution to these problems is to keep a counter, called the ``free locus pointer'' or flp, which will hold the index of the last locus to receive a mutation. When a new mutation is added, we insert it at the locus pointed to by flp and add 1 to flp:

  m = bit_mask[j];
  x[i] |= m;
  flp += 1;
Here the function word_index(p,i,j) will bind i and j to the word number and bit number, respectively, that hold locus p. Note that we count bits from the left, and the index of the first bit is 0, so bit 0 is the leftmost bit, bit 1 the next bit to the right, and so on. As an example, on a machine with 32-bit words, if we want to put a ``1'' in locus number 226, we call word_index(226,&i,&j). Locus 226 is the 2nd bit in the 7th word of the genome, since , so this call will bind i to 7 and j to 1 (since the second bit in the word has index 1).

bit_mask[] is a table of single-bit masks such that the ith entry in the table contains a word in which only the ith bit is a ``1''. For example, the mask for bit 2 is 00100..., so bit_mask[2] = 0x20000000.

When adding mutations to an individual, we can insert them into either strand since the location of a mutation does not matter. We are only interested in the total count of mutations in each individual.