GENETIC ALGORITHM

What are Genetic Algorithms?

Genetic algorithms are general-purpose search algorithms based upon the principles of evolution observed in nature. Even with today's high-powered computers, using an exhaustive search to find the optimal solution for even relatively small problems can be prohibitively expensive.

The genetic algorithm is a probabilistic search algorithm that iteratively transforms a set (called a population) of mathematical objects (typically fixed-length binary character strings), each with an associated fitness value, into a new population of offspring objects using the Darwinian principle of natural selection and using operations that are patterned after naturally occurring genetic operations, such as crossover (sexual recombination) and mutation.

For many problems, genetic algorithms can often find good solutions (near-optimal) in around 100 generations. This can be many times faster than an exhaustive search. For example, a chromosome containing 32 binary genes would have 4,294,967,296 possible combinations (solutions) to evaluate when using an exhaustive search. If the same problem were to be solved with a genetic algorithm of population size 50, requiring 100 generations of evolution, the genetic algorithm would only need to evaluate 5000 possible solutions.

As mentioned previously, genetic algorithms are able to find optimal or near optimal solutions by using many of the principles of evolution that can be observed in nature. These include selection, crossover, and mutation.

Genetic algorithms can be combined with neural networks to enhance their performance by taking some of the guesswork out of optimally choosing neural network parameters, inputs etc.

In general, genetic algorithms can be used in conjunction with neural networks in the following four ways:

·         They can be used to choose the best inputs to the neural network

·         Optimize the neural network parameters (such as the learning rates, number of hidden layer processing elements, etc.)

·          train the actual network weights (rather than using back-propagation)

·         Choose / modify the neural network.

Crossover and mutation are two basic operators of GA.

Binary Encoding

Crossover

In genetic algorithms, crossover is a genetic operator used to vary the programming of a chromosome from one generation to the next. It is analogous to reproduction and biological crossover, upon which genetic algorithms are based. Cross over is a process of taking more than one parent solutions and producing a child solution from them.

Single point crossover - One crossover point is selected, binary string from beginning of chromosome to the crossover point is copied from one parent, the rest is copied from the second parent.

11001011+11011111 = 11001111

Two point crossover - two crossover point are selected, binary string from beginning of chromosome to the first crossover point is copied from one parent, the part from the first to the second crossover point is copied from the second parent and the rest is copied from the first parent

11001011 + 11011111 = 11011111

Uniform crossover - bits are randomly copied from the first or from the second parent

11001011 + 11011101 = 11011111

Arithmetic crossover - some arithmetic operation is performed to make a new offspring

11001011 + 11011111 = 11001001 (AND)

Mutation

Mutation is a genetic operator used to maintain genetic diversity from one generation of a population of genetic algorithm chromosomes to the next. It is analogous to biological mutation. Mutation alters one or more gene values in a chromosome from its initial state. In mutation, the solution may change entirely from the previous solution. Hence GA can come to better solution by using mutation.

The classic example of a mutation operator involves a probability that an arbitrary bit in a genetic sequence will be changed from its original state. A common method of implementing the mutation operator involves generating a random variable for each bit in a sequence. This random variable tells whether or not a particular bit will be modified.

Bit inversion - selected bits are inverted

11001001 =>  10001001

Selection

Selection is the stage of a genetic algorithm in which individual genomes are chosen from a population for later breeding (recombination or crossover).

A generic selection procedure may be implemented as follows:

1.   The fitness function is evaluated for each individual, providing fitness values, which are then normalized. Normalization means dividing the fitness value of each individual by the sum of all fitness values, so that the sum of all resulting fitness values equals 1.

2.   The population is sorted by descending fitness values.

3.   Accumulated normalized fitness values are computed (the accumulated fitness value of an individual is the sum of its own fitness value plus the fitness values of all the previous individuals). The accumulated fitness of the last individual should be 1 (otherwise something went wrong in the normalization step).

4.   A random number R between 0 and 1 is chosen.

5.   The selected individual is the first one whose accumulated normalized value is greater than R.