Genetic algorithm
Based on Darwins theory of Evolution (the fittest will
survive)
GAs are search algorithms based on the idea of natural
selection and genetics
GA looks for the best solution among a number of
possible solutions
It is a stochastic algorithm
Basic Terminologies in GA
An Individual: An individual is a single solution while
population is the set of individuals
Genes: They are the basic instructions for building GA. A
gene is a bit string of arbitrary lengths
Fitness: The fitness of an individual in GA is the value of
an objective function. The fitness function not only
indicates how good the solution is but also corresponds
to how close the chromosome is to the optimal one
Simple GA
Start with the randomly generated solution
Calculate the fitness of each chromosome in the
population
Repeat the following steps until n offsprings have been
created
Select a pair of parent chromosomes from the current population
With crossover probability Pc, the pair is chosen to form two offsprings
at randomly
Mutate the two offsprings
Replace the current population with the new population
Go to step 2
General Genetic Algorithm
The general GA is as follows
1) create a random initial state: An initial population is
created from a random selection of solutions
2). Evaluate fitness: A value of fitness is assigned to
each solution depending on how close it actually is to
solving the problem.
3)Reproduce: Those chromosomes with higher fitness
values are more likely to reproduce offsprings. The
offspring is the product of father and mother whose
combination consists of combination of genes from the
two. This process is known as crossing over. Offspring
cam mutate after reproduction. Selection, crossing over
and mutation together called as Evolution
4) Next generation: if the new generation contains a
solution that produces an output that is close enough or
equal to the desired answer, then the problem has been
solved. If not, the new generation will go through the
same process as theirs parents did. This will continue
until a solution is reached
Operators in GA
Encoding: It is a process of representing individual
genes. This process can be performed using bits,
numbers,lists etc.The most common way of encoding is
a binary string.
Selection: It is a process of choosing two parents from
the population for crossing
After deciding on an encoding, the next step is to decide
how to perform selection i.e how to choose individuals
from the population that will create offspring for next
generation and how many offsprings. According to
Darwins theory of evolution, the best ones survive to
create new offspring
Proportionate based selection: picks out individuals
based upon their fitness value relative to the fitness of
other individuals
Ordinal based selection: Depend upon their rank in the
population and independent on fitness
Crossover: It is the process of taking two parent
solutions and producing a child. Reproduction makes a
clones of good strings but does not create a new one.
Crossover is applied to a matting pool with the hope that
it creates a better offspring
Crossover proceeds in three steps
the reproduction operator selects a random pair of
two individual strings for the matting
A cross site is selected at random along the string
length
Finally, the position values are swapped between the
two strings following the cross site
Single point cross over
Parent 1
10110 010
parent2
10101 111
child1
10110 111
child2
10101 010
Mutation: After crossover, the strings are subjected to
mutation.
Flipping involves changing a 0 to 1 or 1 to 0 based on a
mutation chromosome generated.
Interchanging: the random positions of the strings are
chosen and the corresponding to these positions are
interchanged
Reversing: A random position is chosen and the bits next
to that position are reversed and child chromosome is
produced
parent
10110101
child
11110001
interchanging at 2nd & 6th
position
Parent
10110101
Mutation
chromosome
10001001
child
0011 1100
Flipping
parent
10110011
child
10110110
Reversing
Stopping condition for GA
1. Maximum generations : when specified number of
generations has evolved, the GA stops
2. Elapsed time: The genetic process will end when
specified time is elapsed.
3. No change in fitness: The genetic process will end if
there is no change to the population best fitness for a
specified number of generations
Consider the problem of maximizing the function
f(x) = x2 where x is permitted to vary between 0 and 31
unconstrained optimization problem
Solution
Step1). To start, select initial population at random. Here a population
of 4 is chosen
String No
Initial
population
X value
Fitness
prob
01100
12
144
0.1247 12.47
0.4987 1
11001
25
625
0.5411
2.1645 2
00101
25
0.0216 2.16
0.0866 0
10011
19
361
0.3126 31.26
1.2502 1
sum
1155
1.000
100
4.000
Average
288.75 0.25
25
1.000
Maximum
625
54.11
2.1645
0.5411
% prob
54.11
Expected
count
Actual
count
The expected count is calculated as fitness/ Average
Roulette wheel
31.26%
12.47%
2.16%
54.11%
Now write the matting pool based on the actual count
String No
Mating
pool
Cross over
point
Offspring
after
crossover
X value
Fitness
value
01100
01101
13
169
11001
11000
24
576
11001
11011
27
729
10011
10001
17
289
sum
1763
average
440.75
maximum
729
Now mutation is performed to produce new offspring after cross over
operation
After mutation, the values are decoded and the fitness values are
calculated
String no
offspring
Mutation
chromosome
New
offspring
X value
fitness
01101
10000
11101
29
841
1 1 0 00
00000
11000
24
576
11011
00000
11 0 1 1
27
729
10001
00100
10100
20
400
Sum
2546
Average
636.5
Maximum
841
The average fitness has increased from 288.75 to 636.5
in one generation
1 1 1 0 1 offspring is the excellent choice after one
simple GA
GA for membership functions in Fuzzy
GA can be used to determine the fuzzy membership function
1) for a particular functional mapping system, the same membership
functions and shapes are assumed for various fuzzy variables to be
defined
2) The chosen membership functions are coded into strings
3). These bit strings are concatenated together
4). The fitness function to be used here is noted
5). Fitness function is used to evaluate the fitness of each set of
membership functions
6). The process of generating and evaluating strings is carried out
until we get a convergence. Hence we get membership functions
with best fitness value using genetic algorithm
