01-08-2012, 10:49 AM
Nature-Inspired Algorithms
Nature-Inspired Algorithms.ppt (Size: 1.96 MB / Downloads: 32)
Estimation of Distribution Algorithm (EDA)
Use probabilistic models for recombination
Learn and sample that probabilistic models to generate new solutions
Selection and replacement strategy of GA can be used
Allow adaptation and improve expressiveness
EDA (Estimation of Distribution Algorithm)
Univate
Univariate Marginal Distribution Algorithm(UMDA) (Mühlenbein et.al, 1996)
Population Based Incremental Learning (PBIL) (Baluja, 1994)
Compact Genetic Algorithm (CGA) (Harik
et.al,1998)
Multivariate
Extended Compact Genetic Algorithm (ECGA) (Harik 1999)
Bayesian Optimization Algorithm (BOA) (Pelikan et al.,2000)
Estimation of Bayesian Networks Algorithm (EBNA) (Etxeberria et al., 1999)
Factorized Distribution Algorithm (FDA) (Mühlenbein et al.,1999)
Learning Factorized Distribution Algorithm (LFDA) (Mühlenbein et al.,1999)
Different EDA approaches
Independent variables
The easiest way to calculate an estimate of the required probability distribution is to consider all the variables in a problem as 1D and independent from each other. Then the joint probability distribution becomes the product of the marginal probabilities of the n genes (variables), i.e.
where i indexes genes, n is the # genes in a chromosome; xi is the actual value of the gene and l is the generation index
Different EDA approaches
Independent variables
‘Univariate Marginal Distribution Algorithm (UMDA)’
‘Population Based Incremental Learning (PBIL)’
‘Compact Genetic Algorithm (CGA)’
Bivariate Dependencies
Multiple Dependencies
+ Discrete vs Continuous versions
We only talk about the discrete case with independent variables
Note
It is not guaranteed that the above algorithm will give optimum solution for the graph colouring problem.
The reason is obvious.
The chromosome representation of GCP has dependency. i.e. node 1 taking black colour depends upon the colour of node 2.
But univariate EDAs do not assume any dependency so it may fail.
However, one could try
UMDA
Maintaining a population of individuals. Then it applies a selection method to create a new population.
Based on the new population, the frequencies of each gene are computed and are used to generate a new population of individuals.
This generation step is a kind of population-wise crossover operator and replaces pairwise crossover operator of the traditional GA.
Uses a probability vector p=(p1,p2,…,pn), pi is the probability of 1 in i th position
Compute p from selected individuals
Generate 1 in the position i with prob. pi
Approximates the behavior of uniform crossover of GA
Problem: Joint probability may be 0 due to some pi=0 and may converge to local optimal
Compact genetic algorithm (cGA)
Representing the population as a probability distribution over the set of solutions
Operationally equivalent to the order-one behavior of the simple GA with uniform crossover.
PBIL
The population-based incremental learning (PBIL) method was originally proposed by Baluja [Baluja, 1994]. This approach is a combination of genetic algorithms and the hill-climbing or gradient ascent method.
The object of the PBIL is to create a probability vector which, when sampled, reveals high quality solution vectors with high probability with respect to the available knowledge of the search space.
The vector of probabilities is updated at each generation. The change in the probability vector is towards the better individuals of the population and away from the worst individuals.
PBIL (Cont.)
Parameters
population size (number of samples generated)
learning rate (LR)
Number of winners
To update probabilities vector
The fittest chromosomes (Winners) are adopted: all population in the next approaches winners
Dpi = h [Ebest(chromosomesji)-pi]
Dpi:increment to vector’s ith element
Ebest(chromosomesji):the mean value of the ith
chromosome bit of all winners
h:Learning rate
PBIL Workflow
Vector of Probabilities, V
Generate sample chromosomes from V
Find fittest chromosome(s)
Increase probability of getting better chromosomes by moving V closer to current fittest chromosome(s).
Exploration & Exploitation
PBIL (Cont.)
Create a vector whose length is the same as the required chromosome and whose elements are the probabilities of a “1” in the corresponding bit position of the chromosome. This vector is intialised with 0.5 in all positions.
Generate a number of samples from the vector where the probability of a 1 in each bit position of each vector is determined by the current probability vector.
Find the fittest chromosomes from this population.
Amend the probability vector’s elements so that the probability of a “1” is increased in the positions in which the fittest chromosomes have a 1.