Ceng 713, Evolutionary Computation, Lecture Notes

Genetic Algorithms

Introduction

Holland's GA

bitarray representation

fitness proportionate selection for mating

single point crossover, mutation

inversion operator introduced

Currently there are many varieties with non-binary encodings, different selection strategies and operations.

Why it works?

Schema Theorem (Holland): Short, low-order, above-average schemata (sequence of matching bits in a solution candidate) receive exponentially increasing trials in subsequent generations of a genetic algorithm.

Building Block Hypothesis (Goldberg): A genetic algorithm seeks near-optimal performance through the juxtaposition of short, low-order, high performance schemata called the building blocks.

If your problem is somewhat decomposable into small subproblems called building blocks, GA solves it better.

Many design choices affect GA's capability of:

Introduction of new building blocks

Mixing existing building blocks from different individuals

Preserving existing building blocks.

Deceptive problems: problems where combining high fit building blocks leads to a non-optimal solution.

Encoding

Genotype: how it is represented, Phenotype: what it represents

Example:
Genotype: a binary sequence of size n
Phenotype: an array of size n/8. Each byte represents an element of a vector of ASCII characters.

Encoding should:

Favor building block growth

Preserve locality.

Be closed under genetic operators (crossover of two genotypes come up with a genotype representing a valid phenotype)

General GA Structure

Initialization

fixed # iterations or local optima

sexual selection

ecological selection,
elitism,

selection from λ only, or (μ+λ)

single/multi point, uniform

Initialization

Create a random initial population

Although mutation operation provide some genetic variety in the process, it cannot ensure that the parts of the solution exists in the population.

Population size:

Sample quality of the search space

complexity of the GA

Assure all building blocks of some degree are available in the initial population.

Crossover

Combination of gene traits of two individuals to produce one or two offsprings. (Meiosis)

single point, n-points (n>1), and uniform crossover.

depending on encoding, different types of crossovers exists for encoding integrity. Like permutation preserving crossovers OX, PMX.

Single point crossover

1

0

1

1

0

1

1

1

1

0

0

1

1

0

0

1

0

0

1

1

1

0

1

1

0

1

0

0

1

1

0

1

1

0

0

1

1

1

1

0

parents

offsprings

k-points crossover

1

0

1

1

0

1

1

1

1

0

0

1

1

0

0

1

0

0

1

1

1

0

1

0

0

1

1

1

1

1

0

1

1

1

0

1

0

0

1

0

parents

offsprings

uniform crossover

1

0

1

1

0

1

1

1

1

0

0

1

1

0

0

1

0

0

1

1

1

1

1

1

0

1

0

1

1

1

0

0

1

0

0

1

1

0

1

0

parents

offsprings

Mutation

Due to errors occurred in meiosis, some codons copied with random values.

Genetic algorithms, some gene positions are changed with a random probability. Some algoritms introduce their own controlled mutations like swaps, insertions, deletions.

1

0

1

1

0

1

1

1

1

0

1

0

1

0

0

1

1

1

1

1

Selection

Selection for mating vs. selection for survival.

Mating strategies:

Truncation selection

Fitness proportionate selection (roulette wheel algorithm)

Rank selection

Tournament selection

Survival based on either:

Iλ will be the new population

Selection based on Iμ+Iλ,
some best members of Iμ and members of Iλ ,
or simply selection among the mixed population

Fitness proportionate selection:

Roulette Wheel algorithm:

Vector based

Cumulative Distribution

Selection pressure: ratio of best individual's selection probability to average selection probability.

Selection pressure and probability distribution cannot be adjusted.

Vector based roulette-wheel:

1

1

2

3

3

3

3

4

4

5

Cumulative Distribution roulette-wheel:

0.2

0.3

0.7

0.9

1.0

Rank selection:
individuals are sorted according to their fitness.
selection probability of an individual is a function of their rank.

The probability distribution is completely adjustable:

i

pi

ri

pi

ri

pi

pmax

pmin

Also non-linear distributions are possible

Tournament selection:
Pick two individuals at random and choose the better one to mate.

Simple, fitness pressure can be controlled by the size of the tournament (best of 3,4,5 etc.)

2005-09-27T12:03:42