SMARTS 2.0
Studying Adaptation in an Artificial World
Evolution in SMARTS
In the SMARTS Evolution module, generations of critters
adapt to their environment using a genetic algorithm.
Genetic algorithms are described in the next section.
Even if you are already familiar with genetic algorithms, you should read
this section because some details are particular to SMARTS.
The following section describes the program.
The Theory
Evolution
For evolution to work (either the real-life biological kind or
some more abstract kind), we need at least the following.
- There need to be "creatures" which give birth to other creatures, passing
on their traits to their offspring, and which ultimately die.
("Creatures" is in quotes because these don't really have to be biological
entities.
All they really need to be is combinations of features of some sort.
And they only need to reproduce, die, etc. in our
program, not in "real life".)
- There must be a way for traits to be passed on: an inherited
genome.
In interaction with the environment, this results in a
phenome,
an actual "body" and set of traits.
- There must be a way of evaluating the creatures' traits: some traits
aid in survival or reproduction, others are harmful, and still others may
be irrelevant.
This is "survival of the fittest", but it requires a function of some
sort that takes the creatures and returns a fitness for each one,
either directly (by providing a number) or indirectly (by permitting
the creatures to mate).
- There needs to be a way of generating new traits,
mutation,
a process by which some of the elements of the genome are randomly changed.
How it works
- Each creature is born with some combination of traits;
it may not be possible to simply figure out what combination works
best for the environment of the creatures.
Thus this is a "hard" problem, one which requires some sort of search procedure
to solve.
- Creatures live their lives. Some survive long enough to reproduce
and have offspring.
- If a particular trait or combination of traits helps creatures
reproduce or live longer (and hence be more likely to mate), creatures with that trait (those traits)
will tend to have more offspring.
- Creatures pass on (at least some of) their traits to their
offspring.
In sexual reproduction, they pass on a combination of their parents'
traits.
- As the fit creatures have a chance to reproduce, or at least reproduce
more often than the unfit creatures, the percentage of creatures with the good traits
should increase on each generation.
- There is a small probability that a new creature will end up with
some random traits which it did not inherit from its parent(s) through
mutation.
In this way new traits or combinations of traits which were not part of the
original population and are not possible through combinations of existing
individuals' genomes can be tried out in the world.
Genetic algorithms
Here is
another site where you
can learn about genetic algorithms.
- Genetic algorithms (GAs) are a search technique, a way of solving problems
using a form of reinforcement learning based on (biological) evolution.
- GAs are used for
- Parameter-oriented search problems
These are problems in which the candidate solutions consist of the settings of
multiple parameters.
Consider an old-style television with dials labeled with things like "vertical hold"
and "contrast".
Some combination of settings for these dials results in a good picture, but the
viewer is clueless about what combination is the right one.
The parameters in this case are the dials, and the
search problem is to find the right combination of settings.
To apply a GA to a problem like this, we treat each candidate solution as
a genome in a population and evaluate each in terms of its fitness, in this case,
in terms of the quality of the TV picture that results from the settings.
- Modeling biological evolution
GAs may be used to study biological evolution itself.
An artificial life simulation is set up in which the behavior of creatures depends
(at least in part) on their genomes and in which creatures pass on their traits
to their offspring.
The researcher observes how the fitness of the population varies over different
generations and what sorts of solutions the creatures evolve.
- Designing a suitable initial architecture for cognition
(say, a neural network)
Neural networks learn by adjusting their weights on their connections, but where
do the connections come from in the first place?
That is, what wires up the neural architecture in which neural network learning
takes place?
In real life, much of this is apparently the job of evolution: some neural
structure is innate.
One area of research combines GAs with neural networks: the neural network
architecture (numbers of units, patterns of connectivity joining them,
learning algorithms, etc.) is coded for in the genome, and neural network
learning adjusts the weights on the connections in the network.
- The basics: how GAs work
- Genetic encoding
First, there must be a way of representing the relevant traits in the genome.
-
The genome is usually a binary string. Features which are
not binary may be encoded in sets of positions.
For example, if we want to represent the settings of five TV dials and
each dial has eight possible settings, we could use genomes consisting of
15 bits (0s or 1s).
There would be three bits for each dial because it takes to three bits
to represent eight different numbers.
- The genome is a code.
There must be a way for it to be translated into something that is relevant
for fitness.
The most direct approach is to have a fitness function that takes the
genome itself and returns a fitness value.
This is what happens in the simple example below.
A less direct approach, more like real life, is to have the genome code for the
behavior of the creature that contains it, that is, to distinguish between
the genome and the phenome.
Fitness is then evaluated on the basis of the behavior rather than the genome
itself.
This is what we will do in our artificial world.
- Fitness function: How are individuals evaluated?
-
In most GAs, the fitness function assigns a numerical score to each
genome (or to the behavior of the phenome).
Of course the fitness function is not known or understood
by the designer of the GA;
if it were, there would be nothing to search for since the solution would
obvious.
-
Alternately the function may be built into the environment, allowing
some creatures (at least in part because of their traits)
to survive long enough to reproduce and preventing others (again because
of their traits) from reproducing.
- Selection procedure: How are individuals selected for reproduction
(crossover) on the basis of their fitness?
-
Selection is usually indirect: individuals' chance of reproducing
depends directly on their fitness.
One possibility: weighted roulette wheel.
Parents are selected probabilistically on the basis of their proportion
of the total fitness of the population.
- After fitnesses are calculated for each individual in the population,
each fitness is converted to a proportion of the total fitness.
- The fitness proportions are used to create sections of different sizes
in a "roulette wheel", each associated with a single individual.
-
The roulette wheel is spun as many times as there are individuals in the population.
Each time the ball lands in a section, a copy of the individual for that
section is added to the pool of parents.
- Pairs of parents are selected from the pool to reproduce, each producing
two offspring.
- Direct selection: more successful individuals are able to "find" mates.
- How does reproduction work?
- For each pair of parents, crossover point
is selected randomly within their genomes.
-
One of the offspring gets the first part of the genome (everything before the
crossover point) from parent A and the second part of the genome from parent
B. The other offspring gets the first part of the genome from parent B
and the second part from parent A.
- Mutation: How are new traits created?
- With a small probability (say, 0.001) each of the bits in the newly
created genomes is flipped (1 changed to 0 or 0 changed to 1).
- Mutation can create a feature that would not exist otherwise and
prevent the population from converging too soon.
- An example
Fitness for this example
is assigned on the basis of how much the bits in the genome vary.
Thus the lowest fitness is assigned to genomes in which all bits are the same,
the highest to genomes with an equal number of 0s and 1s.
Generation
|
Genomes
|
Fitness
|
Fitness proportion
|
Individuals selected for mating
with crossover points
|
1 |
01011110
10111000
00001010
00000100
|
3
4
2
1
|
0.3
0.4
0.2
0.1
|
01|011110
10|111000
10111|000
00001|010
|
2 |
10011110
01111000
00001000
10111010
|
3
4
1
3
|
0.27
0.36
0.09
0.27
|
01111|000
10111|010
0111|1000
1011|1010
|
3 |
10111000
01111010
10111000
01111010
|
4
3
4
3
|
0.29
0.21
0.29
0.21
|
10|111000
01|111010
10111|000
01111|010
|