Genetic Algorithms Genetic Algorithms
Moreno Marzolla
Dip. di Informatica—Scienza e Ingegneria (DISI) Università di Bologna
http://www.moreno.marzolla.name/
Slides credit: Ozalp Babaoglu
History
● Pioneered by John Henry Holland in the 1970’s
● Got popular in the late 1980’s
● Based on ideas from Darwinian Evolution
● Can be used to solve a variety of problems that are not easy to solve using traditional techniques
Complex Systems 3
Evolution in the real world
● Each cell of a living thing contains chromosomes — strings of DNA
● Each chromosome contains a set of genes — blocks of DNA
● Each gene largely determines some physical aspect of the organism (like eye color)
● A collection of genes is called the genotype
● A collection of aspects is called the phenotype
Evolution in the real world
● Reproduction involves recombination of genes from parents and small amounts of mutation (errors) in copying
● Evolutionary biology: organism's genotype largely determines its phenotype and hence its fitness — ability to produce new offsprings and propagate its genotype
– Basis for “Darwinian Evolution”
● Evolutionary game theory: the fitness of an organism determined by its interactions with other organisms in a population
Complex Systems 5
Evolution in the real world
adaptation = variation + heredity + selection
Genetic Algorithms
● Suppose you have a problem
● You don’t know how to solve it “algorithmically”
● Can we use a computer to somehow “find” a solution?
Repeat
Generate a random feasible solution
Test the solution to evaluate its “goodness”
Until solution is good enough
Complex Systems 7
Can we use this dumb idea?
● Sometimes — yes:
– if there are only a few possible solutions
– and you have enough time
– then such a method could be used
● For most problems — no:
– many possible solutions
– with no time to try them all
– so this method can not be used
A “less-dumb” idea (GA)
Generate a set of random solutions Repeat
Test each solution in the set and rank them Remove some bad solutions from set
Duplicate (reproduce) some good solutions Make small changes to some of them
Until “best” solution is good enough
Complex Systems 9
How do you encode a solution?
● Obviously this depends on the problem!
● GA’s often encode solutions as fixed length “bit strings” (e.g. 101110, 111111, 000101)
● Each bit represents some aspect of the proposed solution to the problem
● For GA’s to work, we need to be able to “test” any string and get a “score” indicating how “good” that solution is
Adding Sex — Crossover
● Although it may work for simple search spaces, our algorithm is still very naive
● It relies on random mutation to find a good solution
● It has been found that by introducing “sex” into the algorithm better results are obtained
● This is done by selecting two parents during
reproduction and combining their genes to produce offspring
Complex Systems 11
Adding Sex - Crossover
● Two high scoring “parent” bit strings (chromosomes) are selected and are combined with some probability (crossover rate)
● Producing two new offsprings (bit strings)
● Each offspring may then be changed randomly (mutation)
Crossover - Recombination
Crossover single point -
random
0110000000 1011011111
Parent1 Parent2
0111011111
Offspring1
1010000000
Offspring2
With some high probability (crossover rate) apply crossover to the parents (typical values are 0.8 to 0.95)
Complex Systems 13
Mutation
0111011111 1010000000
Offspring1 Offspring2
0111001111 1000000000
Offspring1 Offspring2
With some small probability (the mutation rate) flip each bit in the offspring (typical values between 0.1 and 0.001)
mutate
Original offspring Mutated offspring
Many Variants of GA
● Different kinds of selection
– Tournament
– Elitism, etc.
● Different recombination
– Multi-point crossover
– 3 way crossover etc.
● Different kinds of encoding other than bit strings
– Integer values
– Ordered set of symbols
● Different kinds of mutation
Complex Systems 15
Many parameters to set
● Any GA implementation needs to decide on a number of parameters: Population size (N), mutation rate (m), crossover rate (c)
● Often these have to be “tuned” based on results
obtained - no general theory to deduce good values
● Typical values might be: N = 50, m = 0.05, c = 0.9
Example: vertex k-coloring problem
● Master Thesis of Pasquale Cautela “Un algoritmo parallelo genetico per la k-colorabilità”
● Given an undirected graph G = (V, E), assign each node a color chosen from a set {1, … k} such that:
– adjacent nodes have different colors;
– the value of k is minimum (k is called the chromatic number X(G) of G)
This graph is 3-
colorable, but not 2- colorable
Complex Systems 17
Example: vertex k-coloring problem
● A simple upper bound on the chromatic number X(G) of graph G is
where ∆(G) is the maximum degree of nodes in G
● Computing the chromatic number X(G) for an arbitrary graph G is NP-hard
– Checking whether a graph is 2-colorable can be done in polynomial time
Χ (G)≤Δ (G)+1
Genetic algorithm
● GAs are used to test whether G is k-colorable
● Chromosomes
– Vectors of n integers in {1, … k} (n is the number of nodes)
● Fitness function
– Number of conflicts (negated, best fitness is zero)
Let k = ∆(G)
while ( G is k-colorable ) do k ← k - 1;
endwhile
return X(G) = k + 1;
Complex Systems 19
Simple NetLogo model
Sample Models → Computer Science → Simple Genetic Algorithm
