Genetic Algorithms
Motivation
Genetic Algorithms: Motivation
Local Beam Search bears some resemblance to Natural Selection
Neighbors (Offspring) of States (Organisms) populate next generation
Likelihood of survival depends on value (fitness)
Genetic Algorithms extend this alanlogy
In each step, selected individuals reproduce
Selection probability increases with fitness (value)
There is a small probability of Mutation
Offspring usually replaces other individuals (that dies)
Applying Genetic Algorithms to a Problem
Steps for applying Genetic Algorithms to a Problem:
Define a suitable representation
Define an evaluation function (fitness function (= objective function))
(Sometimes: Define special reproduction and mutation rules (= transition function))
Population (States)
GA work on a population (search space) of Individuals (states)
Each individual is a state represented as a chromosome (e.g. string) over a set of genes (e.g. set of characters)
e.g. 8-Queens Problem:
we could use strings consisting of digits from {1, …, 8}, where i-th digit is row position of i-th queen
Fitness (Objective Function)
Fitness corresponds to objective function
old value function can be reused
in order to get non-negative fitness function, we could count the number of pairs of queens that cannot attack each other (28 - number of attacks between pairs)
Reproduction (Recombination)
= transition function how to generate neighbors
Reproduction: choose random Crossover Point in chromosome
create offspring by crossing parents at this point (1-point Crossover)
Mutation
with small probability: Mutation of offsprings occur
e.g. replace one gene in chromosome randomly
Fitness-proportionate Selection
we often want to select chromosomes based on their fitness
Fitness-Proportionate (Reproduction) = probability of choosing chromosome is proportionate to its fitness
Fitness-Antiproportionate (Removal) = removing low values
A simple Genetic Algorithm
Genetic Algorithm Example
Traveling Salesman Problem
—> find cyclic route that starts from node 0, visits each node exactly once and minimizes the overall edge cost
—> Solution: Sequence of cities starting from and ending in 0
Representation:
Genes: {1, 2, 3, 4} —> cities/nodes we have, 0 excluded as it doesn’t affect path (= start & end)
Chromosomes: strings of length 4, where i-th gene (letter) represents the node that is visited at time i (first node is fixed to be 0)
Solution: fitness is 35 (rough upper bound on max. cost) minus cost of getting from i-th to (i+1)-th node and from fifth node back to first node
Mutation: switches two genes at random
Problem with Reproduction: naive reproduction yields invalid results (see Reproduction of Permutations)
Reproduction of Permutations
Reproduction of Permutations (ordered set of numbers)
If chromosomes correspond to Permutations, naive crossover canyield invalid results
Problem can be fixed by
changing the representation
designing an additional Repair Operation that is appleid after recombination
using special Crossover Techniques for Permutations
Crossover Techniques for Permutations
Uniform-Order Crossover
select 2 parents at random
create random binary template
Child 1 is created by using genes of parent 1 at 1-positions. Fill gaps with the remaining elements according to the order given by parent 2
Child 2 is created by switching the roles of parent 1 and parent 2
Variants of Genetic Algorithms
GAs can be configured by different
Selection operators
Reproduction operators
Mutation operators
Hybrid Genetic Algorithms combine GAs with other search techniques
Memetic Algorithms apply (fast) local search algorithm to each newly created individual to make it locally optimal
Hill Climbing is well suited for this purpose because it is fast
Last changeda year ago