Telecom ParisTech
Collective Intelligence
INF-390
March 2010
Lab Work
J-L. Dessalles
The aim of this lab work is
to discover Genetic Algorithms (GA) and to get an intuitive idea of why they
produce the kind of results that are observed. It is also an opportunity to
acquire some new ideas about evolutionary processes.
Evolife
A
software written
in Python is provided: Evolife. It implements two aspects of evolutionary
simulation:
-
Genetic
Algorithms
-
Darwinian
ecology
The source may be
downloaded here.
The various sources files
are described in ‘ReadMe.html’.
You’ll find also there instructions to run Evolife.
The startup
configuration is stored in simple text format in ‘Evolife.evo’.
To edit this file more conveniently, one may use the XML editor
(written in Python) which is freely available.
Open ‘Evolife.leo’ from LEO. It contains help on the
various parameters.
(a short description of the parameters is also
available in ‘Parameters.txt’)
Binary sum
The following example is
meant as a didactic approach to genetic algorithms (and certainly not as a
realistic application, as the problem is much too simple for a GA). The problem
is to maximize the number of bits set to
Load the configuration ‘Typical_SumBits.evo’ in LEO. Click on the ‘Run’ command of
Run Evolife. Observe the convergence toward the
maximum (= 100, as there are 100 bits in the genome).
Set mutation rate to zero,
and rerun the simulation. Try to explain what happens. It may be useful to
visualize the genomes and to run the simulation step by step.
Conversely, set the
mutation rate to a high value, such as 5 or 10% (i.e. 50 or 100 per thousand),
and observe what happens.
Restart Evolife with a normal mutation rate, but
now set crossover to zero. Observe the slower convergence. Observe, conversely,
how a high value for the number of crossover points (e.g. 5) changes the convergence speed.
You may study the influence
of the population size on the convergence (in number of generations).
You may choose to segment the population into several groups, and set migration
rate to a low value or even to zero.
Locate the ‘S_SumBits.py’ file (in the directory Scenarii)
and make changes so as to select the maximum number of zeros instead of ones.
You may have to change DNAFill (which defines how DNA
is initialized) to -1 or to 1. Reset to the selection of ones after having
observed the effect.
Try to make a slight
temporary modification of the programme. Open ‘DNA.py’.
Locate the ‘mutate’ function. Change it so that a mutation sets the bit to zero
97% of the time. Observe the consequence on the convergence toward 100. Note
the difference in the slope of the curve between the initial selection of
existing 1s and the slow invention of new 1s. Don’t forget to restore the
function to its initial code.
The Labyrinth
In this simple didactic
application, a mobile robot enters the above labyrinth in (1,6)
(see arrow) and looks for an exit. The simplest coding is implemented in ‘Scenarii/S_Labyrinth.py’. It consists, for each position in
the labyrinth (we suppose that its maximal dimension is known in advance), in
two bits that indicate which absolute direction to take. We thus have a 200 bit
genome for a 10x10 grid.
Load the configuration ‘Typical_Labyrinth_noshare.evo’ in LEO. The evaluation
function can be set up in the configuration. See in LEO parameters PenaltyU_turn, PenaltyWall and RewardExiting. If
walls and u_turns are the numbers of times the robot hit walls or made a U-turn,
then:
Evaluation = PenaltyWall * (MaxSteps - walls) + PenaltyU_turn
* (MaxSteps - u_turns) + RewardExit * (MaxSteps - step -1)
Run Evolife (either through LEO or after having
saved manually the configuration file as ‘Evolife.evo’)
and observe what happens for reasonable values of the parameters. Note that in
most trials, we observe a slow step by step evolution.
An alternative evaluation
function uses phenotypic sharing:
Individuals that guide their robot on the same tracks as previous individuals
are handicapped. To do this, poisonous pheromone is laid down by robots. This
has the nice side-effect of preventing robots from following cyclic paths.
Evaluation = PenaltyPoison * (MaxPheromon * MaxSteps +1 - poison) + RewardExit * (MaxSteps - step -1)
Load the configuration ‘Typical_Labyrinth_share.evo’ in LEO. Choose reasonable
values for the new parameters PenaltyPoison and MaxPheromon (the other parameters of the evaluation function
may be set to zero). Run Evolife and observe that the evolution is now much faster, as exploration of
the labyrinth is rewarded. What happens if exploration is too much rewarded?
Ecology
Individual fitness
Load the configuration ‘Typical_Favourable.evo’ in
Try a negative value for IndividualBenefit.
Collective fitness
(so-called ‘group selection’)
Set IndividualBenefit to zero and
give a positive value to CollectiveBenefit.
It means that each member of a group of K
members receives a share of Kx CollectiveBenefit,
depending on the average value of the ‘favourable’ gene. In particular, having
a high value of this gene gives a bonus to the carrier (and to its fellows). Run Evolife and observe that the convergence is much
slower than in the individual case (it is important to understand why…).
A critical parameter is the
migration rate between groups (parameter MigrationRate). Observe that a
gene that creates collective benefit has a much higher selective value in case
of endogamy, i.e. when individual are
likely to live and interact with their offspring/siblings/cousins (this is a
case of ‘kin selection’).
Reproductive vs. ecological selection
Darwinian selection may act
in several ways. Two of them are implemented in Evolife.
-
Ecological
selection: individuals get life points during their life (score). As the population is bound to a limited size, after the
breeding season, individuals randomly lose life points until there are enough
deaths to restore the population to its original size. As a consequence, fitter
individuals are less likely to die and are selected in the long run. This
selection process is controlled by SelectionPressure.
-
Reproductive
selection: individuals are ranked in their group according to their score, and
are allocated a number of offspring that depends on their rank. This is a
highly non-linear selection method. This selection process is controlled by Selectivity.
Try to combine a positive
value of CollectiveBenefit and a negative value of IndividualBenefit.
Observe that the latter is ‘diluted’ in the former, as individuals get K times CollectiveBenefit and only once IndividualBenefit.
Change selection from the ecological mode to the reproductive mode, by setting SelectionPressure
to zero and Selectivity to a reasonable
value. Observe now that the negative value of the individual penalty may have a
predominant influence.
Green beard effect
This small experiment was
proposed in
Suppose a given gene has
two effects on its carriers: (1) they get a conspicuous characteristic, like a
green beard; (2) they tend to behave altruistically toward green-bearded
individuals. Such a gene is expected to invade the population, whereas its
supposed allele (no green beard + no altruism) tends to disappear.
However, as soon as the
gene gets split in two genes with their own alleles (green beard vs. no green beard, and altruism toward
green beard vs. no altruism) then
altruism disappears.
Open the file ‘S_GreenBeard.py’ and implement the function interaction so that green bearded
individuals behave altruistically toward their green bearded fellows by helping
them: they give them life points (through the score function) at their own expense (they lose points, but less).
To do so, you need to use
functions such as:
indiv.score() (defined in Individual.py)
indiv.gene_intensity()
(defined in Genome.py)
choice() (standard in Python,
‘random’ library) to choose a partner in the list of individuals of the group
Run Evolife and observe that the GreenBeard gene
invades the population. (you need to say to
Now limit the role of the GreenBeard
gene to the appearance, and transfer the altruistic function onto the Altruist gene. Try to make sense of the
result that you might observe.
In the initial situation
where the GreenBeard
gene has the two effects, you may add a new gene that prompts its carriers to
attack green bearded individuals at their own expense (i.e. both lose points). It becomes good and bad to carry a green beard. The new gene may check (or not)
that its carrier has a green beard or not.
Complexity
This experiment explores
the (limited) ability of G.A. to solve a complexification/simplification
problem.
Load the configuration ‘Typical_Zip.evo’ in
When the 'Simplify'
parameter (see under ‘Genetic Algorithms/Zip’) is set to 0, the programme
ideally attempts to generate a random (i.e. incompressible) sequence. Try the BitString mode and the not-BitString
mode. In the latter, evolution gets more obviously trapped in many local
optima.
When the
'Simplify' parameter (see under ‘Genetic Algorithms/Zip’) is set to 1 and one
starts from a random DNA (set ‘Genetics/DNAFill’ to –1),
the programme attempts to simplify the initially random string. Observe that though simplification
does occur, the programme does not reach periodic strings. Try to understand
why.
