New Frontiers in Theoretical Approaches to Natural Selection
I. Bit-Strings
	A. A bit-string is a series of 0s and 1s, e.g. “0100.”
		1. A bit (binary digit) is the smallest unit of data in computing,
		   with a value of either 0 or 1.
		2. A byte represents a series of eight bits.
		3. A word (or short) is two bytes or sixteen bits.
		4. A long is four bytes or thirty-two bits.
		5. A longlong is eight bytes or sixty-four bits. 
	B. Bit manipulation techniques (bitwise operators)
		1.And  – compares two strings and returns a new string consisting
		  of 1s where both strings have 1s and 0s everywhere else.
			a) Example: 1100 AND 1010 = 1000.
			b) Using a bit-mask with AND allows for the selective
			   retrieval of a certain bits.
			c) 1s in the mask return the corresponding value.
			   0s ensure that the bit is zero.
			d) Example: To test whether the last bit is a 1 or 0, use S AND 1,
			   where S is the string to test.  If the result is zero, then the
			   last bit is zero.  If the result is not zero, then the last bit
			   is one.
		2. Inclusive Or (OR) – compares two strings and returns a new string
		   consisting of 0s where both strings have 0s and 1s everywhere else.
			a) Example: 1100 OR 1010 = 1110.
		3. Exclusive Or (XOR) – compares two strings and returns a new string
		   consisting of 1s where both strings differ and 0s everywhere else.
			a) Example: 1100 XOR 1010 = 0110.
			b) Using a bit-mask with XOR allows for selective bits to be
			   flipped because any 1 in the mask will cause the corresponding
			   bit in the other term to change its value, e.g. 1 XOR 1 = 0 and
			   0 XOR 1 = 1.
		4. Left Shift (LSH) – shifts bits to the left by a specified amount, removing
		   bits on the left and adding 0s on the right.
			a) Example: 1100 LSH 2 = 0000.
			b) Can be used to generate bit masks.  0001 LSH X creates a bit-mask
			   that refers to the X-th bit (zero-indexed).
		5. Right Shift (RSH) – shifts bits to the right by a specified amount, adding
		   0s on the left and removing bits on the right.
			a) Example:1100 RSH 2 = 0011.
		6. Negation (NEG) – changes 1s to 0s and 0s to 1s. 
			a) Example: NEG 1100 = 0011.
	C. Computationally efficient method of modeling genomes
		1. Each bit represents a diallelic locus.
		2. Separate bit-strings represent separate chromosomes.
		3. Can model haploid, diploid, or polyploid genetics.
		4. Mutations are bit-flips caused by the XOR operator.
		5. Recombination
			a) Generate a bit-mask (M) in which all 1s are clustered.  This
			   represents the region that will be swapped between the two strings.
			b) The recombinant chromosomes can be generated using the following
			   formulas: R1 = (H1 AND M) OR (H2 AND NEG(M)),
				     R2 = (H1 AND NEG(M)) OR (H2 AND M),
			   where H1 and H2 are the homologous bit-strings.
			c) Example:
				(1) H1 = 1111, H2 = 0000, M = 0011
				(2) N = NEG(M) = 1100
				(3) H1 AND M = 0011
				(4) H2 AND N = 0000
				(5) R1=0011 OR 0000 = 0011
				(6) Similarly, R2 = 1100 OR 0000 = 1100
		6. In a diploid model, a phenotype bit-string can be computed from the two
		   homologous chromosomes using the OR operator.  This causes 1s to be
		   dominant to 0s. (1100 OR 1010 = 1110)
		7. Asexual reproduction is equivalent to copying bit-strings.
		8. Sexual reproduction is equivalent to generating recombinant chromosomes,
		   choosing one per pair to generate a gamete, which is then merged with
		   another gamete to form a new, complete individual.
	D. Selection in a population of bit-strings
		1. Accomplished by comparing an individuals phenotype bit-string to the
		   optimal phenotype bit-string.
		2. This optimal can be randomly generated or specified.
		3. Individuals with many differences are given low fitnesses and individuals
		   with few differences are given high fitnesses. The fitness of the i-th
		   individual is w(i)=(n(i)/N)^á , where N is the total number of bits compared,
		   n(i) is the total number of similar bits, and á is a correction factor
		   introducing epitasis.
		4. n(i) is calculated using the XOR operator.  If P is the individuals
		   phenotype and OP is the optimal, then P XOR OP produces a bit-string that
		   contains 1s where there are differences.  Counting the 0s through the use
		   of bit-masks, gives the ni of the individual.
		5. Environmental changes can be implemented by randomly changing bits in the
		   optimal string.  The greater the number of bits flipped, the greater the
		   size of shift.
		6. Environmental heterogeneity can be implemented by specifying separate optimal
		   phenotypes for separate sections of the model (demes or areas).
	E. A simple example
		1. Construct a 10x10 lattice of haploid, asexual individuals, represented by a
		   single randomly generated 8-bit-string.  Also randomly generate an optimal
		   bit-string.
		2. The probability that an individual does not survive a time step is
		   calculated by m(i)=m+(1-m)(1-w(i)), where m is the background mortality rate.
		3. Keep track of age and induce death at  T=ln(0.05)/ln(1-m).  This limit is
		   how old, fully-fit individuals will be if ninety-file percent of them have
		   been eliminated by background mortality.  This ensures that most individuals
		   will die form something other than senesce.
		4. If a cell becomes empty because of a death, randomly pick one of the
		   neighboring individuals to expand into it.  The new individual is a clone
		   of the old one with some bits changed.
		5. After a certain number of time-steps, induce changes in the optimal
		   phenotype to reflect changing conditions.
		6. Keep track of average fitness of the population, mortality, size, generation
		   time, heterozygosity, etc.
		7. Determine how changing the initial parameters affect the ability of the
		   population to recover from an environmental disturbance.
	F. Advantages
		1. Computationally efficient
		2. Flexible
		3. Individual based
		4. Stochastic
	G. Disadvantages
		1. Fitnesses are abstract.
		2. Thus, it is difficult to study process of adaptation,
		   especially pre-adaptation.
		3. Individual based
		4. Stochastic

II. Genetic Programming
	A. Individuals are not abstract but rather a collection of computer
	   commands that can do something.
	B. Individuals can be tested by getting them to perform tasks.  Fitnesses
	   are granted based on how well they perform their tasks. Examples:
		1. Compute the logarithm of a number.
		2. Transform one set of data into another.
		3. Compress data without loosing any.
		4. Predict diseases form patients’ medical data.
		5. Detect genes in genomic data.
	C. One can actually track how the population evolves to perform the task
	   and how different selection regimes compare.
	D. However, most genetic programs are used for engineering purposes and
	   not the study of selection.

III. A-Life
	A. Similar the genetic programming, but individuals are not given a specific
	   task to perform.
	B. Space (i.e. memory) and energy (i.e. processor time) represent limited
	   resources, which induce selection for how well a-life individuals can copy
	   themselves.
	C. Other resources can be included in the digital environment which individuals
	   can acquire to improve their replication.
	D. Unlike genetic programming or bit-string models, reproduction is an intrinsic
	   function.  Individuals in an a-life evolutionary model are self-replicators.
	   Their code copies itself.
	E. Often given low-level computational capabilities such as mathematical operators,
	   bitwise operators, and memory operators.
	F. However, this complexity requires that researchers design a simple founding-
	   organism that already can self-replicate.
	G. Tom Ray’s Tierra
		1. A-life experiment to study the origin of diversity
		2. Individuals competed for space and processor time.
		3. Errors generated in the execution of an individual’s code increased
		   their chances of death.
		4. Found that parasites evolved, then individuals resistant to the parasites,
		   then parasites that could circumvent the resistance.
		5. Hyper-parasites even evolved that forced parasites to replicate
		   hyper-parasites instead of themselves.
	H. Richard Lenski’s and colleagues’s Avida
		1. Used to study the evolution of complex features via adaptation.
		2. Individuals competed for space and processor time.
			a) Individuals received energy proportional to their sizes and were
			   able to use this energy to execute their code.
			b) They could also perform certain actions that gave them additional
			   energy and thus allowed them to execute faster.
		3. Looked at the evolution of complex actions by tracing the exact
		   genealogy of organisms.
		4. Found that some successful lineages used deleterious mutations to evolve
		   more complex actions and deleterious mutations could hitchhike.
		5. Found that almost half of their populations evolved the most complex
		   action rewarded.
		6. Tested different environments (reward schemes) and found that the most
		   complex action was able to evolve in a variety of conditions.
		7. Found that complex actions would not evolve if there were not simpler
		   actions that were also rewarded.

IV. References
A. Banzhaf W et al (1998) Genetic programming: an introduction. Morgan
	Kaufmann Publishers: San Francisco.
B. Lenski RE et al (2003) The evolutionary origin of complex features.
	Nature 423:139-144.
C. Ray TS (1992) Evolution, ecology and optimization of digital organisms.
	Santa Fe Institute working paper 92-08-042.
D. Schwilk DW and Kerr B (2002) Genetic niche-hiking: an alternative
	explanation for the evolution of flammability. Oikos 99 (3):431-442