Evolutionary Computation

Evolutionary Algorithms

A big class of algorithms spawning from the basic idea of genetic algorithms.
Genetic programming
Ant colony simulation and swarm behavior
Coevolution
Parallel genetic algorithms
Artificial immune systems
Evolvable hardware
Multi-objective optimization
Artificial life, adaptive behavior, robotics

Genetic Programming

A special case of genetic algorithms.
The main difference is the representation of the potential solutions or chromosomes.
For genetic programming, a chromosome is a program in some language, usually Lisp.
Typically, a chromosome is a tree where the leaves are constants and variables (terminals) and the other nodes are functions/operators.
The chromosomes are of variable length.

Chromosome

Fitness: how well the tree computes the results for a given number of training examples.
Linear representations:
Lisp:
(+ (* 2 a) x)
Postfix (Polish) notation:
2 a * x +

Operations

Crossover: Two random subtrees are chosen in the parents and exchanged.
For a fix-length string chromosome, a crossover between a chromosome and itself produces simple clones of the parent.
In GP the result of self-crossing can be different than the original.
Mutation: two types. For the first, a function replaces a function and a terminal replaces a terminal.
For the second, a whole subtree can be replaced by another subtree.

Crossover

Parents

Children

Mutation

Parent

Child by single node replacement

Child by subtree replacement

Discussion

It's like interpolating a function without knowing what the function looks like.
Can be used to derive complex behavior.
Recently there have been examples of human-competitive results.
Issue: tree bloating. Some research exists on limiting the size of the tree. A large size means that it's harder to compile, it takes more time to execute, and it 's harder to understand for a human.
Resources: www.genetic-programming.org.

Coevolution

Coevolutionary algorithms are defined by the fact that the computation of the fitness of one chromosome depends on information from the population.
Example: a poker player.
Competitive coevolution: an individual is evaluated in competition with others.
Cooperative coevolution: several individuals must cooperate to solve the problem.
For each of them, the individuals may solve the same problem or different (parts of) problems (agents).

Competitive Coevolution

The most popular of the two.
The individuals are evaluated by playing against other individuals in a lose-win system.
If they all solve one problem, the comparisons happen within one population.
If they solve different problems, then individuals from one population play against individuals from a different population.

One Population Competition

The evaluation is a tournament. Usually a score is attached to each individual.
Round Robin - each individual plays against every other individual in the population.
Random pairing - each individual is paired with one other.
Single-elimination tournament (World Cup) - start with random pairing, and the losers are eliminated. Repeat until we have a champion.
When a game is played, the score of each player is updated based on the result of the game and the score of the opponent.

Other Competition Topologies

K-Random opponents - each individual plays against K other opponents.
Must insure a balance in the number of games played by each individual.
K=n-1: RR; K = 1: random pairing.
Reported optimal K: 10 to 25 for n=128.
Hall of fame - keep a history of the best individuals so far and each individual to be evaluated plays against them.

Multiple Populations

Most usually 2 competing populations in an arms race, like predator - prey.
The individuals from one population play against individuals from the other one - they solve different problems.
The success of one population implies the failure of the other.
Progressive increase of the problem complexity.
The solutions have to deal with various cases as they compete against individuals of varying strategies. There is a continuous change in the fitness landscape.

Example of Cycling

Predator strategies:
A1: track the prey and try to catch it by approaching it
A2: track the prey while staying still and attack when the prey is close enough
Prey strategies:
B1: stay still or hidden until the predator is close enough and then run from it
B2: continuously move fast avoiding predator and walls

Some Examples

D. Floreano: Predator-prey using robots. Both robots have proximity sensors.
Predator has better vision, prey can go twice as fast. Reported performance better than simple evolution.
Robot duel: robots in an arena containing food that gives them energy. When they collide, the robot of higher energy wins.
S. Luke, L. Panait: soccer playing agents evolved through k-random opponents.

Cooperative Coevolution

One population: ant colony simulation. All of the individuals solve the same problem, but they work together to solve it. The ants leave pheromone trails to guide the others.
Multiple populations: each population solves a different problem or part of the problem. It can be implemented in parallel.
The problem is divided in subcomponents, each of them being solved by a subpopulation.
Each individual is evaluated by selecting collaborators from other populations.

Collaborative Evaluation

Optimistic: the fitness is based on the best collaborator.
Hedge: based on the average.
Pessimistic: based on the worst collaborator.
Collaboration pool size: how many collaborators we select.
Applications: Traveling salesman problem, scheduling, routing, data clustering.

Demos

Parent	Child by single node replacement	Child by subtree replacement