BUGWORLD - Copyright 1993 Martyn Amos
1. INTRODUCTION
BugWorld is a simple introduction to the world of Genetic Algorithms
(GAs). A virtual physical environment is created within the computer,
which is then populated by various creatures, or "bugs", composed entirely
of machine instructions (cf. Tierra).
The environment may be visualized as a 2D, toroidal grid, the size of which
may be specified at the start of each simulation. At the start of each
generation, the bugs are randomly distributed over the grid.
The bugs compete for both energy and material resources. The
energy resource is represented by food items distributed around the
environment. Bugs may eat this food, which increases their energy
level. Bugs lose energy at a constant rate, and must occasionally replace
it. If a bug's energy level reaches zero, it becomes exhausted and must rest
for a certain period of time, after which its energy level is restored to
its initial value.
The material resource is represented by items of litter. The more litter
items a bug (litterbug, geddit?!) collects, the more successful it is
deemed to be. Both resources are also randomly distributed at the start
of each generation. Food and litter items are generated anew (ie. each
generations is faced with a brand-new, unique environment).
2. THE POPULATION
The genome of the population members consists of a sequence of machine
instructions that encode the organism's behaviour. There are two
species of organism - LitterBugs and Bullies. LitterBugs must move around
the environment, foraging for food and collecting litter. At the end of
each generation, certain LitterBugs are selected as parent of the next
generation.
Bullies are predators in that their sole task is to attack LitterBugs and
deplete their litter collections. Bullies do not require food and do not
breed - they have a fixed genome.
At the start of each simulation, each LitterBug has a pseudo-random genome
assigned to it.
3. THE VIRTUAL COMPUTER
Each organism has associated with it a program counter (PC) and
several registers/flags:
- memory register (integer)
- energy level register (integer)
- current direction register ([N|S|E|W])
- resting register (integer)
- litter collected register (integer)
- organism type flag ([L|B])
- exhausted flag (Boolean)
4. THE BUGWORLD LANGUAGE
The complete list of instructions is given below:
Opcode Mnemonic Interpretation
00 LOOK "Look" in the current direction. A value
corresponding to what can be seen is placed in
the memory register:
0: nothing
1: food
2: litter
3: LitterBug
4: Bully
01 MEMUP Increment value in memory register
02 MEMDOWN Decrement value in memory register
03 RESTART Jump to start of program (ie. PC = 0)
04 MOVE x Move forward with an x% probability
05 TURN x Turn left or right with an x% probability
06 JUMP x Jump to program line x
07 REMEMBER x Place x in memory register
08 REST x Rest for x cycles (consume no energy)
09 ENERGY x y If energy < x, jump to program line y
10 LESS x y If value in memory < x, jump to program line y
11 MORE x y If value in memory > x, jump to program line y
12 EQUAL x y If value in memory = x, jump to program line y
Each gene (ie. program line) consists of three components, which are
copied "en bloc". It is important to note that when an organism's genome is
first created it is only pseudo-random, in that the different fields of the
genes must remain within their defined limits. For example, the gene
04 103 ??? would be illegal, as it corresponds to MOVE 103%. This is
clearly illegal.
The Bully's fixed genome corresponds to the program below:
0 LOOK (in the current direction)
1 EQUAL 3 5 (is LitterBug visible?)
2 TURN 75% (didn't jump, so try to turn)
3 MOVE 75% (move in another direction)
4 RESTART (and then look again...)
5 MOVE 100% (move towards LitterBug)
6 RESTART (continue this process...)
5. THE SELECTION MECHANISM
Several selection schemes are implemented. The choice of mechanism can
greatly affect the rate of evolution (ie. how quickly a reasonably efficient
LitterBug evolves).
5.1 Random Selection
It is perhaps difficult to justify calling random selection of parents a
selection "strategy" at all. It simply involves choosing two members of the
population, purely at random, as parents. Each organism, regardless of its
fitness has an equal chance of selection. This mechanism is employed
mainly to demonstrate that other strategies are more effective.
5.2 Roulette Wheel Selection
The most commonly used strategy used in GA applications is probably stochastic
selection with replacement (or "roulette wheel" selection). We define the
probability that organism x is chosen as a parent as
f(x)
P(x) = ----
f(p)
where f(x) is organism's fitness
f(p) is total fitness of entire population
This method is called "roulette wheel" because each individual is assigned
a wedge of an imaginary roulette wheel, the size of the wedge being
proportional to the individual's fitness taken as a proportion of the total
fitness of the entire population. The greater an individual's fitness,
the larger the likelihood that the roulette ball will stop within that
individual's wedge, thus selecting it as a parent.
"Pure" roulette wheel selection uses this method to select both parents.
5.3 Impure Roulette Wheel Selection
This uses a combination of pure roulette wheel and random selection, one
parent being selected by each method.
5.4 Tournament Selection
Each parent is selected by selecting two individuals at random and comparing
their fitnesses. The probability that the fittest individual "wins" the
encounter and is selected as a parent is usually set to 75%. This procedure
is performed twice, once to select each parent.
6. FITNESS MEASUREMENT
So far we have assumed that a fitness measurement is available, without
discussing how it may be obtained. A reasonable measure is the amount of
litter that a LitterBug collects within a single generation, so we will
use that.
7. REPRODUCTION
Reproduction involves taking two parent LitterBugs and combining their
genomes to create an offspring's genome. When this occurs, a random section
of one parent's genome is joined to a section of the other parent's
genome, a process known as crossover.
For example, if parent A's genome is
##########
and parent B's genome is
XXXXXXXXXX
with a totally arbitrary crossover point denoted by |, we get
##########
| = ####XXXXXX
XXXXXXXXXX
as the offspring's genome.
8. MUTATION
While copying instructions during reproduction, genes are randomly altered
at some rate. The copy mutation rate is set to an artificially high
value (1%) in order to illustrate the concept.
Usually, mutation involves "flipping" one bit of the genome, but because
of the brittle nature of the genome, flipping a bit within a gene may
result in an invalid instruction. Therefore, mutation is (very) loosely
emulated by randomly creating a whole new gene and substituting it for the
one selected for mutation.
10. BUGWORLD OPERATION AND CONFIGURATION
The program must be invoked from the command line, using the following
syntax:
bugworld -c <configuration filename> [-t]
The -t flag is used to select terse statistics.
A lot of application parameters may have their values specified at the
start of each run. For ease of use, the starting configuration must be read
in from a text file. This file contains an arbitrary number of entries of
the form
<parameter name> <value> <NEWLINE>
The available parameter names and their associated range of values are
described below:
Parameter name Description Range
POPSIZE Size of initial Even number 2..200
population
GENERATIONS No. of generations to 1..1000
simulate
GENOMESIZE Size of LitterBug 7..25
genome (no. of genes)
BUGVISION LitterBug's range of 1..20
vision
BULLYVISION As above, for Bullies 1..20
SEED Random number seed Any integer
XBOUNDARY X dimension of world 50..500
YBOUNDARY Y dimension of world 20..500
FOODAMOUNT Amount of food at 100..5000
start of generation
LITTERAMOUNT As above, for litter 100..5000
SELECTION Selection mechanism 1..4
MUTATIONRATE Probability that a 0..100
gene mutates when copied
MOVES Moves per organism per 1500..10000
generation
FITTESTCHANCE Probability of fittest 0..100
organism being selected
(tournament only)
TRACE Number of organism to As POPSIZE
trace
Default values are given below:
Parameter name Default value
POPSIZE UNDEFINED
GENERATIONS UNDEFINED
GENOMESIZE 15
BUGVISION 5
BULLYVISION 5
SEED Current process' PID
XBOUNDARY 150
YBOUNDARY 60
FOODAMOUNT 300
LITTERAMOUNT 900
SELECTION 3 (Impure roulette)
MUTATIONRATE 1
MOVES 3000
FITTESTCHANCE 75
TRACE UNDEFINED
POPSIZE and GENERATIONS must be defined by the user at all times.
An example configuration file is given in the ir.cfg file.
11. STATISTICS AND TRACING
The user of the package may select the type of statistics displayed
during a simulation. If terse statistics are selected, the program
simply prints out the average fitness of the population at the end of
each generation.
If terse statistics are not selected (the default), the program displays
a header, and various statistics for each generation (generation number,
average fitness, number and fitness of fittest LitterBug and the genome
of the fittest LitterBug).
All statistics are printed to standard output (usually the terminal
screen). This may be redirected to a text file or piped to a printer.
The facility to trace the execution of an individual organism's genetic
program is available. This is mainly used for debugging purposes, but
is useful for watching an organism's interactions with its environment.
The number of the organism to be traced must be specified by the
TRACE parameter. The organism is traced for each generation and the
trace information is placed in a file named 'trace' in the current
directory.
12. CONCLUSIONS
The behaviour of the simulated population generally conforms to basic
principles of GAs, such as premature convergence. It was hoped that
"intelligent" LitterBugs that avoided predators and efficiently foraged
for food would evolve, but this didn't happen during the limited number of
runs performed, due to time constraints.
The package doesn't try to stick to formal GA principles (for example,
mutation is performed in a very crude manner), but it does illustrate
several basic concepts, such as crossover, selection and convergence.
Comments regarding this software are welcome. Please direct correspondence
to
Martyn Amos
Parallel Computation Group
Department of Computer Science
University of Warwick
COVENTRY
United Kingdom
CV4 7AL
martyn@dcs.warwick.ac.uk
