Sur_Vi_Vors
a struggle for life on a grid

Abstract

This project uses GP to bread program-cooperatives that can survive and self-replicate in an artificial world.

The World

The artificial world is based on a 2D grid of 100x100 locations. Each location may contain at most one program. A location may also contain "food" and may accumulate at most one unit of food. Such food in the form of "vegetation" that naturally "grows" on the grid at random. The program-cooperatives move around on the grid, eat the food (and each other), develop and reproduce.

Individuals

An individual is a self-replicating cooperative of programs. An individual may have one or more programs, each program occupies a single grid location. All the programs of the same individuals are maintained at some proximity.

Each individual has a genome that consists of a vector of 10 genes. Each gene is a program that can be expressed zero or more times. When a program is expressed it is copied from the respective gene into a vacant grid location and connected to the creating program. The sum of all programs and their connections is the graph of the individual.

Each individual has a food counter, so whenever it eats, the counter is incremented. Whenever it expresses a gene the counter is decremented. The counter must be non-negative for the individual to reproduce. Because all individuals are "born" with their counter set to -1, they must eat at least once to become "fertile".

Execution

The execution of the system is cycle-based such that the output of cycle n is used as an input to cycle n+1. In each cycle the following phases are performed in order:

• The grid grows 2 new food units at random locations.
• Each of the grid locations is evaluated by executing the program contained at the location (if such program exists). All the individual's programs are executed independently in a "simulated parallelism", but may effect the individual's state and each other.
• The programs are moved to their new location according to their direction register and the forces exerted on them by connected programs.

Programs

A program is a tree of functions and terminals at a maximum height of 5. Each program belongs to a single individual. The program might be connected to other programs and these connections may effect its movement. Each program has a direction register that defines the direction the program seeks to move. The register has i and j components. Positive i means "down", negative means "up". Positive j means "right", negative means "left". Zero for either i or j means "here" respectively. Combinations of i and j can represent each of the 8 directions, including staying at the same place.

Functions

• eat <i> <j>
  Attempts to eat at a designated location within the 9-neighborhood of the program (directions are the same as with the direction register). If the designated location (loc) contains food, the food counter is incremented and the food is cleared from loc. If loc contains a (foreign) program of a different individual, the foreign program is killed, the eaten program is cleared from loc and the counter is incremented twice (as meat is more nutritious than vegetation...). Hence, the food counter may be increased by 3 if loc contains both: food and a foreign program. An individual's attempt to eat its own program is ignored. The function returns the change made to the food counter.
• express <i>
  Expresses the i-th gene from the individual's genome and creates a connection between this program and the newly expressed program. i is a zero-based index. If i is larger then the genome size, modulo is used to fold it back onto a valid index. The newly created program is positioned as close as possible to the creating program. If no empty location is found within a distance of 3, this function has no effect. If i is negative, then a reproduction procedure is performed (see below). If the denoted gene is an empty program this function has no effect. The function returns i.
• move <i> <j>
  Sets the direction register to the specified i and j values. The function returns 1 if the location at the designated direction is empty, or 0 if nonempty.
• +, -
  Binary arithmetic operators.
• iflte
  If little or equals.

Terminals

• c-count
  Connection count - the number of connections the program has.
• food-i
  A relative i coordinate of a nearest food location.
• food-j
  A relative j coordinate of a nearest food location.
• foreign-i
  A relative i coordinate of a nearest foreign program location.
• foreign-j
  A relative j coordinate of a nearest foreign program location.
• random
  A random integer number in range [-10, +10].

Notes:

• If more than one nearest food location exists, then one of them is selected. food-i and food-j are both referring to that selected location. The same applies to nearest foreign programs and foreign-i and foreign-j.
• The search is limited to a distance of 4 around the searching program.
• If no food is found than food-i and food-j are set to zero. The same goes for foreign-i and foreign-j.

Kill

When a program is killed:

• It is normally cleared from its grid location.
• Its connections to all other other (involved) programs are removed.
• If the program graph of the individual becomes disconnected, it is repaired by repeatedly connecting pairs of involved programs representing different disconnected subgraphs.

Reproduction

Reproduction is invoked upon an execution of the express function with a negative argument. If the food counter of the individual is negative, the function is ignored and has no effect. If the food counter is non-negative, the reproduction process takes place as follows:

• The genome of the individual is cloned to be a new individual.
• Genetic operators are applied to the genome of the new individual.
• The first non-empty program in the genome of the new individual is expressed into a random vacant grid location, and its parent is set to null.
• The food counter of the new individual is set to -1.

Mutation and crossover operators are applied to every gene during reproduction at Pm=0.02 and Pc=0.04 rates:

• mutation - a gene subtree is re-grown. A subtree may be rooted at each of the existing tree nodes including the root at the genome vector.
• crossover - a random gene i is copied faithfully from a random individual whose food counter is maximal.

Population Control

The simulation keeps a population of up to a 100 individuals, where all individuals are ordered in a queue. When an individual is created it is inserted at the tail of the queue. Whenever an individual eats, it is removed from its queue position and re-inserted at the tail of the queue. If the size of the queue reaches 101, the individual at the head of the queue is killed including all of its programs. The dead programs are left on the grid to be scavenged.

Physics

At the end of each cycle, every program is moved to its new position according to its direction register and the force exerted on it by the programs it is connected to.

The programs on the grid are scanned in a left-to-right-top-to-down order. For each program, the system calculates a "force" direction. If an adjacent location is available at that direction, the program moves there. Otherwise, the program doesn't move. If the move results in stretching the distance to a connected program beyond 4, the program doesn't move.

The direction of the force is calculated by summing up the direction register with all the "pull" forces. Each connected program at a distance greater than 2 contributes one unit vector of "pull" at its direction.

Display

The grid is displayed divided into locations. Each location indicates the existence of food and a program. An empty location is black. The food is green. An "alive" program is colored in vivid color (high saturation and luminosity) according to its gene. When a program dies, its color becomes "pale" by lowering its saturation and luminosity. Lines are drawn between programs that are connected.

Ancestor

The first self-replicator introduced to the grid is a human-designed replicator. It is added to the grid as a seed of all grid interactions.

Implementation Notes

• The simulation is implemented in Java and uses the ECJ framework to perform its genetic operations.
• All numbers above are parameters that can be easily changed and tuned.
• Some of the Java classes are reused from the Lipidia project.

Hoped-for Results

• Specialization of programs (genes).
• Diverse strategies and morphologies.
• Emergence of complex individuals.
• Surprises...

Output

• A brief research report of 3 to 4 pages of text that contains a summary of hypotheses, experiments conducted to test them, experimental results and conclusions.
• Relevant charts and plots to supplement the findings.
• Parameter set for each of the experiments to allow repeating them.
• Source files of the simulator.
• The seed ancestor individual.

(C) Copyright 2004, by Barak Naveh. All rights reserved.