Page 21 - Algorithm Collections for Digital Signal Processing Applications using MATLAB

1. Artificial Intelligence 9

2. GENETIC ALGORITHM

A basic element of the Biological Genetics is the chromosomes.
Chromosomes cross over each other. Mutate itself and new set of
chromosomes is generated. Based on the requirement, some of the
chromosomes survive. This is the cycle of one generation in Biological
Genetics. The above process is repeated for many generations and finally
best set of chromosomes based on the requirement will be available. This is
the natural process of Biological Genetics. The Mathematical algorithm
equivalent to the above behavior used as the optimization technique is called
as Artificial Genetic Algorithm.
Let us consider the problem for maximizing the function f(x) subject to
the constraint x varies from ‘m’ to ‘n’. The function f(x) is called fitness
function. Initial population of chromosomes is generated randomly. (i.e.) the
values for the variable ‘x’ are selected randomly between the range ‘m’ to
‘n’. Let the values be x 1, x 2…..x L, where ‘L’ is the population size. Note that
they are called as chromosomes in Biological context.
The Genetic operations like Cross over and Mutation are performed to
obtain ‘2*L’ chromosomes as described below.
Two chromosomes of the current population is randomly selected (ie)
select two numbers from the current population. Cross over operation
generates another two numbers y1 and y2 using the selected numbers. Let
Y
the randomly selected numbers be x3 and x9. 1 is computed as r*x3+(1-
r)*x9. Similarly y 2 is computed as (1-r)*x 3+r*x 9, where ‘r’ is the random
number generated between 0 to1.
The same operation is repeated ‘L’ times to get ‘2*L’ newly generated
chromosomes. Mutation operation is performed for the obtained
chromosomes to generate ‘2*L’ mutated chromosomes. For instance the
generated number ‘y 1’ is mutated to give z 1 mathematically computed as
r 1*y, where r 1 is the random number generated. Thus the new set of
chromosomes after crossover and Mutation are obtained as [z 1 z 2 z 3 …z 2L].
Among the ‘2L’ values generated after genetic operations, ‘L’ values are
selected based on Roulette Wheel selection.