GENETIC ALGORITHMS

Genetic algorithms are minimization algorithms in which the points in parameter space are encoded in fixed-length bit strings. Additional points are tried by randomly modifying bits of the strings. Therefore the minimum search is carried out in a finite region of parameter space, each parameter encoded with a suitable accuracy. For example in a search for the best center and orientation the center coordinates might be encoded with 6 bits each (ie, between 0 and 63) and the angle with 3 bits (eight orientations: 0, 22.5, 45, 77.5, 90, 112.5, 135, and 157.5 degrees). A point in parameter space is then encoded with a 15 bit string, in this example.

The strings are referred to as chromosomes and the bits as genes. The function to minimize is the "life-expectancy" V of the chromosome.

The algorithm starts with a population of N randomly selected strings. For each string the life-expectancy is evaluated.

Next a new population is "grown" by combining randomly selected pairs of chromosomes (crossover), and merging them by taking the initial part of one and the final part of the other. The gene where the split is done is randomly chosen. Furthermore it is allowed to introduce mutations: a gene can be flipped with a suitably small probability. The life-expectancy is evaluated for the new population and only the N best fitted individuals are kept for the next iteration.

The algorithm continues until the population reaches a stable state with most of the individuals at the minimum.

Probabilistic genetic algorithm

A problem with the classical genetic algorithm is the necessity of a large mutation probability at a later stage, when the genetic pool is depleted, in order to escape from a local minimum.

At each stage the life-expectancy of the current population is normalized,

v(c) = ( V(c) - min ) / ( max - min )

where min and max are the minimum and maximum of V(c) over the population of chromosomes c. The factor 1/(max - min) is actually unimportant. For each gene the mean value and the standard deviation is computed,

m[j] = N-1 ∑ c[j]
s[j] = sqrt( N-1 ∑ ( c[j] - m[j] )² )

The variance is 0 if the gene is the same in all the chromosomes, and achieves 0.5 at the maximum. A new population is obtained by constructing chromosomes in which the gene j has value 1 with probability

P[j] = ∑ c[j] V(c) / ∑ V(c)

Mutation is applied at each gene with probability

Pm[j] = po (0.5 - s[j])

Therefore depleted genes get the highest probability of mutation.

The parameters of the probabilisting genetic algorithm are



Marco Corvi - Page hosted by geocities.com.