UNIT-IV

GENETIC ALGORITHMS (GAs)

Introduction
• A Genetic Algorithm is a search heuristic that is inspired by Charles Darwin’s theory
of natural evolution ie., Survival of the Fittest.
• This algorithm reflects the process of natural selection where the fittest individuals are
selected for reproduction in order to produce offspring of the next generation.
• GA was developed by the scientist “John Holland” in the 1960s and 1970s based on
Charles Darwin’s Theory of natural selection.

Definition
A Genetic Algorithm is a search-based optimization technique based on the principles of
Genetics and Natural selection. It is frequently used to solve optimization problems in Research
and in Machine learning.

Explanation
• In GAs, a pool or a population of possible solutions are present to the given problem.
These solutions then undergo recombination and mutation (like in natural genetics)
producing new children and the process is repeated over various generations.
• Each individual is assigned a fitness value and the fitter individuals are given a higher
chance to mate and produce more “fitter” individuals.
• In this way, we keep “Evolving” better individuals or solutions over generations till we
reach a stopping criterion.

Procedure of Genetic Algorithms

Key Components of GAs:
Five phases are considered in a genetic algorithm.
1. Initial population
2. Fitness function
3. Selection
4. Crossover
5. Mutation

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Initial Population:
• The process begins with a set of individuals which is called a Population. (Possible
solutions).
• Genes: A set of parameters (variables) or attributes of Initial population are known as
Genes.
• Chromosome: All Genes are joined into a string to form a Chromosome(solution).

Fitness Function:
The fitness function determines how fit an individual is. It gives a fitness score to each
individual.
Selection:
• The idea of selection phase is to select the fittest individuals and let them pass their
genes to the next generation.
• The primary objective of the selection operator is to emphasize the good solutions and
eliminate the bad solutions in a population while keeping the population size constant.
• A fitness value is assigned to each solution depending on how close it is actually to the
optimal solution of the problem.
There are different techniques to implement selection in Genetic Algorithms
▪ Tournament selection
▪ Roulette wheel selection
▪ Proportionate selection
▪ Rank selection
▪ Steady state selection

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Tournament Selection:
▪ Tournament selection is a method of selecting an individual from a population of
individuals.
▪ Tournament selection involves running several "tournaments" among a few individuals
chosen at random from the population.
▪ The winner of each tournament (the one with the best fitness) is selected for crossover.
▪ Weak individuals have a smaller chance to be selected if tournament size is large.

Roulette wheel and proportionate selection

▪ In a roulette wheel selection, the circular wheel is divided and a fixed point is chosen
on the wheel circumference as shown and the wheel is rotated.
▪ The region of the wheel which comes in front of the fixed point is chosen as the parent.
▪ For the second parent, the same process is repeated.

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Rank selection
• In Rank selection, first ranks the population and then every chromosome receives
fitness from this ranking.
• The worst will have fitness 1, second worst 2 etc. and the best will have fitness N
(number of chromosomes in population).

Chromosome Fitness Value Chromosome Fitness Value Chromosome Rank

1 37 1 37 1 6
2 6 3 36 3 5
3 36 4 30 4 4
4 30 6 28 6 3
5 15 5 15 5 2
6 28 2 6 2 1

%ge of
Chromosome Roulette
Wheel
1 29
3 24
4 19
6 14
5 10
2 5

Steady state selection

• In this method, a few good chromosomes are used for creating new offspring in every
iteration.
• Then some bad chromosomes are removed and the new offspring is placed in their
places.
• The rest of population migrates to the next generation without going through the
selection process.

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Crossover:
• The most popular crossover selects any two solutions strings randomly from the mating
pool and some portion of the strings is exchanged between the strings.
• The Cross over selection point is selected randomly with in the genes.
• Offspring are created by exchanging the genes of parents among themselves until the
crossover point is reached.

Binary Cross Over

Types of Crossover:
1. Single Point Crossover
2. Two Point Crossover
3. Multi Point Crossover
4. Uniform Crossover
5. Three parent Crossover
6. Shuffle Crossover
7. Average Crossover

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Single Point Crossover:
• The traditional genetic algorithm uses
single-point crossover.
• Here, a cross site or crossover point is
selected randomly along the length of the mated strings and bits next to the cross sites are
exchanged.
Two Point Crossover:
• In two-point crossover, two crossover
points are chosen and the contents between
these points are exchanged between two
mated parents.
• The contents between these points are
exchanged between the parents to produce new children for mating in the next generation.

Multi Point Crossover:

• It uses the random crossover point to combine the
parents same as per Single Point crossover.
• It first selects the two parents used for crossover and
then randomly select N crossover points
• Two offspring are created by combining the parents at
crossover point.

Uniform Crossover:
• Uniform crossover is quite different from the N-point
crossover.
• Each gene in the offspring is created by copying the
corresponding gene from one or the other parent
chosen according to a random generated binary
crossover mask of the same length as the
chromosomes.
• To generate off spring-1, Where there is a 1 in the crossover mask, the gene is copied from the
first parent, and where there is a 0 in the mask the gene is copied from the second parent.
• To generate off spring-2, Where there is a 0 in the crossover mask, the gene is copied from the
first parent, and where there is a 1 in the mask, the gene is copied from the second parent.

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Three parent Crossover:
• In this crossover technique, three parents are randomly
chosen. Each bit of the first parent is compared with
the bit of the second parent.
• If both are the same, the bit is taken for the offspring,
otherwise the bit from the third parent is taken for the
offspring.

Shuffle Crossover:
• Shuffle Crossover selects the two parents for crossover. It firstly randomly shuffles the genes in
the both parents.
• Then it applies the Single Point crossover technique by randomly selecting a point as crossover
point and then combines both parents to create two offspring.
• After performing Single point crossover, the genes in offspring are then unshuffled in same way
as they have been shuffled.

Average Crossover:
• Average Crossover is the value-based crossover
technique.
• It uses two parents to perform crossover and creates only
one offspring.
• Average Crossover creates one offspring from
taking average of the two parents.

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Mutation:
Mutation may be defined as a small random “adjustment” in the chromosome to get a new
solution. It is used to maintain and introduce diversity in the genetic population and is usually
applied with a low probability.

Types of Mutation:
1. Flip Mutation
2. Swap Mutation
3. Inversion Mutation
4. Displacement Mutation
5. Insert Mutation
6. Scramble or Shuffle Mutation

Flip Mutation:
A parent is considered and a mutation chromosome is
randomly generated. For a 1 in mutation chromosome,
the corresponding bit in parent chromosome is flipped
(0 to 1 and 1 to 0) and child chromosome is produced.

Swap Mutation:
Two random positions of the string are chosen
and the bits corresponding to those positions
are Swapped.

Inversion Mutation:
In inversion mutation, we select a subset of genes and inverse the entire string to generate
offspring.

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Displacement Mutation:
It selects set of places in the chromosome at random, removes
the genes between the selected places from the chromosome,
and then inserts them in a random place in the chromosome.

Insert Mutation:
It removes a random gene from the chromosome and then
inserts it in a randomly chosen place.

Scramble or Shuffle 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.

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Working of Genetic Algorithms

Block Diagram of Genetic Algorithm

Flowchart of Working of GA

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Initialization: The initial population of individuals is randomly generated. The way the
individuals are initialized can have a significant impact on the performance of the genetic
algorithm.
Fitness evaluation: The fitness of each individual is evaluated. The fitness function measures
how good a solution an individual is. The fitness function should be carefully designed to
reflect the specific problem being solved.
Selection: The fittest individuals are selected to reproduce. The selection method can be either
roulette wheel selection or tournament selection. Roulette wheel selection gives a higher
chance of selection to fitter individuals, while tournament selection randomly selects a group
of individuals and the fittest one is selected.
Crossover: The selected individuals are crossed over to produce offspring. The crossover
operator combines the genes of two parents to create new offspring. There are many different
crossover operators, such as single-point crossover and two-point crossover.
Mutation: Some of the offspring may be mutated. Mutation is a random change to the genes
of an individual.
Replacement: The new offspring replace the old individuals in the population.
Termination: A Genetic Algorithm will typically terminate after a predefined number of
generations, or if some stopping criterion has been met. The fittest solution in the population
is then returned as the overall best solution.

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Travelling sales man problem (TSP) using Genetic Algorithm:
• The Traveling Salesman Problem (TSP) is an algorithmic problem tasked with finding
the shortest route between a set of points and locations that must be visited.
• In the problem statement, the points are the cities a sales person might visit. The
salesman’s goal is to keep both the travel costs and the distance traveled as low as
possible.
• TSP is often used in computer science to find the most efficient route for data to travel
between various nodes.

A Classical Traveling Salesman Problem (TSP) can be defined as a problem where “starting
from a node is required to visit every other node only once in a way that the total distance
covered is minimized.”

Genetic Algorithms (GAs) are a popular approach to solving TSP because they can find near-
optimal solutions efficiently. Here's an explanation of how a GA can be applied to the TSP:
1. Encoding:
In a GA for the TSP, the first step is to represent a potential solution (tour) as a chromosome.
One common representation is a permutation of city indices, where each city appears exactly
once in the chromosome. For example, if you have five cities, a chromosome might look like
[1, 3, 5, 2, 4], indicating the order in which the cities are visited.
2. Initialization:
Generate an initial population of chromosomes randomly. Each chromosome represents a
possible tour of the cities.

3. Fitness Function:
Define a fitness function that measures how good a tour is. In the TSP, the fitness function is
typically the total distance traveled in a tour. The shorter the tour, the higher the fitness.

4. Selection:
Select individuals (chromosomes) from the population to create a mating pool for the next
generation. Individuals with higher fitness values are more likely to be selected. Various
selection methods can be used, such as roulette wheel selection, tournament selection, or rank-
based selection.

5. Crossover (Recombination):
Pair up individuals from the mating pool and create offspring through crossover
(recombination). Crossover operators combine the genetic information of two parent tours to
produce one or more child tours.

6. Mutation:
Apply mutation operators to some of the offspring tours. Mutation introduces small random
changes into a tour to maintain diversity in the population.

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 7. Replacement:
Replace the old population with the new generation of tours, including both parents and
offspring.

8. Termination Condition:
Check for a termination condition, which could be a maximum number of generations, a
specific fitness threshold, or a time limit. If the termination condition is met, stop the algorithm.

9. Output:
Once the algorithm terminates, return the best tour found in the final population, which
represents the solution to the TSP.

Evolutionary Programming
• Evolutionary Programming is one of the soft computing techniques in “Evolutionary
Computing”.
• It was first used by “Lawrence J. Fogel in 1960

Definition:
It is a branch of Artificial Intelligence attempts to develop software through processes of natural
selection and reproduction.

Key Components of EP:

1. Initial population
2. Mutation
3. Fitness function
4. Selection

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Explanation:
The basic Evolutionary programming methods involves 3 steps.
• Choose an initial POPULATION of trial solutions at random. The number of solutions
in a population is highly relevant to the speed of OPTIMIZATION, but no definite
answers are available as to how many solutions are appropriate (other than >1) and how
many solutions are just wasteful.
• Each solution is replicated into a new POPULATION. Each of these OFFSPRING
solutions are mutated according to a distribution of MUTATION types.
• Each OFFSPRING solution is assessed by computing it's FITNESS. This process is
continued till adequate solution is obtained.

Note:
Evolutionary Programming does not use “CROSS OVER” as a Genetic Operator.

Advantages of EP:
Global Optimization: Evolutionary algorithms are capable of finding global optima in
complex search spaces, making them suitable for optimization problems that cannot be solved
using traditional optimization methods.
Robustness: Evolutionary algorithms are able to handle noisy or changing
environments, as well as deal with uncertainty in the optimization process, making them a
robust approach to solving complex problems.
Diversity: Evolutionary algorithms maintain a diverse population of solutions, which helps to
avoid being trapped in local optima.
Simple Representation: Evolutionary algorithms often use simple representations for
solutions, making them easy to implement and understand.

Applications of EP:
• Traffing Routing and Planning
• Pharmaceutical Design
• Cancer Detection
• Military Planning
• Signal Processing
• Medical Sector
• Data Mining
• Risk Management

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Working principle of GA Machine Learning Classifier System (GA-LCS):

Genetic Algorithm Machine Learning Classifier System (GA-LCS):

• A GA machine learning classifier system (LCS) is a type of machine learning system
that uses a genetic algorithm (GA) to learn a set of rules that can be used to classify
data.

• The GA is a search heuristic that follows the process of natural selection to find optimal
or near-optimal solutions to problems.

• In an LCS, each rule is represented as a chromosome. The GA maintains a population

of chromosomes and iteratively applies selection, crossover, and mutation operators to
produce new offspring chromosomes. The selection operator selects chromosomes
from the population based on their fitness. The crossover operator combines two
chromosomes to create a new offspring chromosome. The mutation operator randomly
flips bits in a chromosome.

• The fitness of a chromosome is measured by how well the rule represented by the
chromosome performs on a given training dataset.

• For example, if the LCS is being trained to classify emails as spam or not spam, the
fitness of a chromosome could be measured by how accurately the rule classifies emails
in the training dataset.

• After each iteration of the GA, the population of chromosomes is updated to include
the new offspring chromosomes. The GA continues to iterate until a satisfactory
solution is found, or until a predefined number of iterations have been completed.

• Once the GA has found a satisfactory solution, the rules represented by the
chromosomes in the population can be used to classify new data.

Working Procedure of GA-LCS

The GA LCS works by iteratively applying the following steps:
▪ Initialization: A random population of chromosomes is generated. Each
chromosome represents a rule for classifying data.
▪ Fitness Function: The fitness of each chromosome is evaluated by classifying the
data in the training dataset using the rule represented by the chromosome.
▪ Selection: The fittest chromosomes are selected from the population.
▪ Crossover: The selected chromosomes are combined using the crossover operator
to create new offspring chromosomes.
▪ Mutation: The mutation operator is applied to the offspring chromosomes.
▪ Replacement: The offspring chromosomes replace the least fit chromosomes in the
population.

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 Block diagram of Working Procedure of GA-LCS

▪ Steps 2-6 are repeated until a satisfactory solution is found or until a predefined
number of iterations have been completed.
▪ Once the GA LCS has been trained, the rules represented by the chromosomes in
the final population can be used to classify new data.

Example: Classify emails as spam or not spam using Genetic Algorithm Machine
Learning Classifier System.

➢ Start with a random population of chromosomes. Each chromosome represents

a rule for classifying emails.
➢ Evaluate the fitness of each chromosome by classifying the emails in the
training dataset using the rule represented by the chromosome.
➢ Select the fittest chromosomes from the population.
➢ Combine the selected chromosomes using the crossover operator to create new
offspring chromosomes.
➢ Apply the mutation operator to the offspring chromosomes.
➢ Update the population of chromosomes to include the new offspring
chromosomes.
➢ Repeat steps 2-6 until a satisfactory solution is found or until a predefined
number of iterations have been completed.

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru
 ➢ The rules represented by the chromosomes in the final population can be used
to classify new emails as spam or not spam.
Advantages of GA-LCS:
• GA LCSs is able to learn complex relationships between input and output variables.
• GA LCSs is able to generate rules that are easy to understand and interpret.
• GA LCSs is relatively robust to noise in the training data.

Disadvantages of GA-LCS:
• GA LCSs can be slow to train, especially for large datasets.
• GA LCSs can be difficult to tune.

Applications of GA-LCS:
• Spam filtering: GA LCSs have been used to develop spam filters that are able to
identify spam emails with high accuracy.
• Medical diagnosis: GA LCSs have been used to develop medical diagnosis systems
that are able to diagnose diseases with high accuracy and interpretability.
• Financial trading: GA LCSs have been used to develop trading strategies that are
able to generate profits in the financial markets.

Differences Between Traditional Algorithm and Genetic Algorithm

Aspect Traditional Algorithm Genetic Algorithm (GA)
Method Follows a fixed set of steps Mimics natural evolution
Searches locally, may get Searches widely, explores
Solution Search
stuck on a bad solution many possible solutions
Works best for simpler, Good for complex and
Problem Type
straightforward problems messy problems
Usually faster but can miss Slower but more likely to
Speed
better solutions find better solutions
Less adaptable, can’t handle Highly adaptable, evolves
Adaptability
changes easily with changes
Direct and fixed (e.g., Uses population, random
Process
calculate, compare, repeat) selection, and mutations
Well-defined, simple Complex problems with
Best Used For
problems many variables
Usually requires less Can be more resource-
Cost
computing power intensive
May take longer but
Finds solutions faster but
Convergence explores a variety of
can stop at suboptimal ones
solutions

Soft Computing Techniques - UNIT-IV by Mr. Ashok Kumar Bandla, Associate Professor & IQAC Coordinator, RCE(A), Eluru