GENETIC ALGORITHM
GENETIC ALGORITHM
INTRODUCTION
● Genetic Algorithm (GA) is a search-based
optimization technique based on the principles
of Genetics and Natural Selection. It is
frequently used to find optimal or near-optimal
solutions to difficult problems that otherwise
would take a lifetime to solve.
INTRODUCTION TO
OPTIMIZATION
● Optimization is the process of making
something better.
What are Genetic Algorithms?
● Nature has always been a great source of
inspiration to all mankind. Genetic Algorithms
(GAs) are search based algorithms based on
the concepts of natural selection and genetics.
● GAs are a subset of a much larger branch of
computation known as Evolutionary
Computation.
BASIC TERMINOLOGY
● Population – It is a subset of all the possible
(encoded) solutions to the given problem.
● Chromosomes – A chromosome is one such
solution to the given problem. (46 in human)
● Gene – A gene is one element position of a
chromosome.
● Allele – It is the value a gene takes for a
particular chromosome.
Gene is a Complete manual for
1 protein
Protein is a combination of
amino acids.
3 Nucleotide = 1 amino acid
code.
Coiling
Macro-molecule
Micro-molecule
● Genotype – Genotype is the population in the computation
space. In the computation space, the solutions are
represented in a way which can be easily understood and
manipulated using a computing system.
● Phenotype – Phenotype is the population in the actual real
world solution space in which solutions are represented in
a way they are represented in real world situations.
● Decoding and Encoding – For simple problems, the
phenotype and genotype spaces are the same. However,
in most of the cases, the phenotype and genotype spaces
are different. Decoding is a process of transforming a
solution from the genotype to the phenotype space, while
encoding is a process of transforming from the phenotype
to genotype [Link] should be fast as it is carried
out repeatedly in a GA during the fitness value calculation.
Decoding and Encoding
● Fitness Function – A fitness function simply defined
is a function which takes the solution as input and
produces the suitability of the solution as the output.
In some cases, the fitness function and the objective
function may be the same, while in others it might be
different based on the problem.
● Genetic Operators – These alter the genetic
composition of the offspring. These include
crossover, mutation, selection, etc.
BASIC STRUCTURE OF GENETIC ALGORITHM
// Valid Genes
const string GENES = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP"\
"QRSTUVWXYZ 1234567890, .-;:_!\"#%&/()=?@${[]}";
// Target string to be generated
const string TARGET = "I love Pakistan";
// Create random genes for mutation
char mutated_genes()
// create chromosome or string of genes
string create_gnome()
// Class representing individual in population
class Individual
{
public:
string chromosome;
int fitness;
Individual(string chromosome);
Individual mate(Individual parent2);
int cal_fitness();
};
GA- PARENT SELECTION
Parent Selection is the process of selecting
parents who mate and recombine to
create offspring for the next generation.
Parent selection is very crucial to the
convergence rate of the GA as good
parents drive individuals to better and
fitter solutions.
GA- CROSSOVER
● one parent is selected and one or more off-
springs are produced using the genetic material
of the parents
● One Point Crossover
In this one-point crossover, a random crossover
point is selected and the tails of its two parents are
swapped to get new offspring.
● Multi Point Crossover
Multi point crossover is a generalization of the one-point
crossover wherein alternating segments are swapped to
get new off-springs.
● Uniform Crossover
In a uniform crossover, we don’t divide the chromosome into
segments, rather we treat each gene separately. In this, we
essentially flip a coin for each chromosome to decide whether or not
it’ll be included in the offspring. We can also bias the coin to one
parent, to have more genetic material in the child from that parent.
GA- MUTATION
In simple terms, mutation may be defined as a small
random tweak in the chromosome, to get a new
solution.
Mutation Operators
We describe some of the most commonly used
mutation operators.
Like the crossover operators, this is not an exhaustive
list and the GA designer might find a combination of
these approaches or a problem-specific mutation
operator more useful.
-Bit Flip Mutation
In this bit flip mutation, we select one or more
random bits and flip them. This is used for binary-
encoded GAs.
GA- MUTATION
-Random Resetting
Random Resetting is an extension of the bit flip for
the integer representation. In this, a random value
from the set of permissible values is assigned to a
randomly chosen gene.
-Swap Mutation
In swap mutation, we select two positions on the
chromosome at random and interchange the
values. This is common in permutation-based
encodings.
● Scramble Mutation
Scramble mutation is also popular with
permutation representations. In this, from the
entire chromosome, a subset of genes is chosen
and their values are scrambled or shuffled
randomly.
● Inversion Mutation
In inversion mutation, we select a subset of genes
like in scramble mutation, but instead of shuffling
the subset, we merely invert the entire string in
the subset.
GA- SURVIVOR SELECTION
• The Survivor Selection Policy determines
which individuals are to be kicked out and
which are to be kept in the next
generation.
• It is crucial as it should ensure that the
fitter individuals are not kicked out of the
population, while at the same time,
diversity should be maintained in the
population.
GA- SURVIVOR SELECTION
Age-Based Selection
In Age-Based Selection, we don’t have a notion
of fitness. It is based on the premise that each
individual is allowed in the population for a finite
generation where it is allowed to reproduce, after
that, it is kicked out of the population no matter
how good its fitness is.
For instance, in the following example, the age is
the number of generations for which the
individual has been in the population. The oldest
members of the population i.e. P4 and P7 are
kicked out of the population and the ages of the
rest of the members are incremented by one.
GA- SURVIVOR SELECTION
● Age Based Selection
GA- SURVIVOR SELECTION
Fitness-Based Selection
In this fitness-based selection, the children tend
to replace the least fit individuals in the
population. The selection of the least fit
individuals may be done using a variation of any
of the selection policies described before –
tournament selection, fitness proportionate
selection, etc.
For example, in the following image, the children
replace the least fit individuals P1 and P10 of the
population. It is to be noted that since P1 and P9
have the same fitness value, the decision to
remove which individual from the population is
arbitrary.
●
Fitness Based Selection
GA- TERMINATION CONDITION
● When there has been no improvement in the
population for X iterations.
● When we reach an absolute number of
generations.
●
When the objective function value has reached
a certain pre-defined value