Lecture Notes: Unit 3 soft computing ECAM NSUT EAST CAMPUS

SYLLABUS: Genetic Algorithms: Concept of "Genetics" and "Evolution" and its application to
probabilistic search techniques, Basic GA framework and different GA architectures. GA operators:
Encoding, Crossover, Selection, Mutation, etc. Solving single-objective optimization problems using
GAs.

Genetic Algorithms (GAs) are a class of evolutionary algorithms that use principles of natural
selection and genetics to solve optimization and search problems. These are adaptive heuristic
search algorithms based on the principles of genetics and natural selection. These algorithms
are used to find approximate solutions to optimization and search problems by mimicking the
process of natural evolution.
The basic framework of GAs revolves around evolving a population of candidate solutions to
a given problem using genetic operations such as selection, crossover, and mutation. This
evolutionary process continues over several generations to find an optimal or near-optimal
solution.

Concepts of "Genetics" and "Evolution"

Genetics refers to the biological study of heredity and variation in organisms. In the context of
GAs, the principles of genetics such as inheritance, mutation, and recombination (crossover)
are applied to evolve solutions over time.
Evolution in nature is the process by which populations of organisms adapt and change over
generations through natural selection. Individuals that are better suited to their environment
survive and reproduce, passing their advantageous traits to the next generation. In GAs, this
concept is applied to improve candidate solutions iteratively.
Key Concepts/terminology used in GAs
Chromosomes: Represented as strings of data, which encode a possible solution to the
problem. They are analogous to DNA in biology.
Genes: Individual elements of a chromosome, representing specific traits or variables.
Population: A set of potential solutions (chromosomes) at any given iteration.
Fitness: A measure of how well a given solution (chromosome) solves the problem. Solutions
with higher fitness values are more likely to be selected for reproduction.
Selection: The process of choosing individuals from the population to reproduce based on their
fitness.
Crossover (Recombination): The process where two parent solutions combine to produce
offspring, sharing traits from both.
Mutation: A random alteration in a gene to introduce diversity in the population, preventing
premature convergence on suboptimal solutions.

Prepared by : Dr. Aarti Jain

3. The basic Genetic Algorithm framework
Initialization: A population of candidate solutions is generated randomly or using heuristic
methods.
Selection: Based on fitness, individuals are selected for reproduction. Common selection
methods include:
• Roulette Wheel Selection: Probability of selection is proportional to the fitness value.
• Tournament Selection: A subset of individuals is chosen, and the fittest among them is
selected.
• Rank-based Selection: Individuals are ranked based on fitness, and selection is
proportional to rank rather than fitness value.
Crossover (Recombination): Selected individuals undergo crossover, creating offspring by
mixing their genetic information.
Mutation: Some offspring undergo random mutations, ensuring genetic diversity in the
population.
Evaluation: The new generation is evaluated based on fitness, and the best-performing
individuals are retained.
Replacement: The new generation replaces the old one, and the process repeats until a
termination condition is met (e.g., a solution is found, or a maximum number of generations is
reached).

Genetic Algorithms as Probabilistic Search Techniques

Genetic algorithms are a form of stochastic search or probabilistic search because they explore
the solution space based on probabilistic rules rather than deterministic ones. Here’s how they
compare to traditional search methods:
Exploration vs. Exploitation: GAs balance exploring new areas of the search space (through
mutation and crossover) and exploiting known good solutions (through selection of high-
fitness individuals).
Global Optimization: Unlike greedy algorithms, which may get stuck in local optima, GAs
aim to find global optima by maintaining a diverse population and using probabilistic
mechanisms like mutation and crossover.
Parallel Search: GAs work on a population of solutions simultaneously, meaning they can
explore multiple areas of the search space in parallel. This contrasts with methods like hill-
climbing or simulated annealing that work on a single candidate solution at a time.
Strengths and Limitations of Genetic Algorithms
Strengths:
• Can handle complex and high-dimensional search spaces.
• Do not require gradient information or derivative calculations.

Prepared by : Dr. Aarti Jain

 • Work well on problems with multiple local optima (e.g., multimodal problems).
• Naturally parallel, making them suitable for distributed or cloud computing
environments.
Limitations:
• Can be computationally expensive due to maintaining and evaluating a large
population.
• May converge slowly or prematurely if diversity is lost in the population.
• Performance depends heavily on the design of the fitness function, selection
mechanism, and genetic operators (crossover and mutation).
• Require careful tuning of parameters (population size, mutation rate, etc.).
Flow chart of genetic Algorithm

Different Genetic Algorithm Architectures

Over time, different variations and architectures of GAs have been developed to address the
limitations of the basic GA framework. Below are some of the common GA architectures and
their distinguishing characteristics:

Prepared by : Dr. Aarti Jain

Steady-State GA
In a Steady-State Genetic Algorithm, instead of replacing the entire population in each
generation, only a few individuals are replaced. This type of GA maintains a stable population
size throughout the evolutionary process.

Process:
• A few individuals are selected for reproduction.
• Crossover and mutation are applied to generate offspring.
• These offspring replace the worst-performing individuals in the population.
Advantages:
• Faster convergence since fewer individuals are replaced.
• Continuous generation of new individuals allows the population to evolve gradually.
Disadvantages:
Risk of premature convergence due to limited exploration.
Generational GA
The Generational Genetic Algorithm is the classical GA architecture, where an entire
population is replaced after each generation.
Process:
• Selection, crossover, and mutation are applied to the entire population to produce a new
generation.
• The entire population is replaced by the offspring.
Advantages:
Allows more significant exploration of the search space per generation.
Disadvantages:
Computationally more expensive as the entire population is processed at once.
There may be loss of high-fitness individuals unless elitism is used.
Elitist GA
Elitism is a strategy incorporated into either generational or steady-state GAs. In this approach,
the best-performing individuals (the "elite") are preserved between generations to ensure that
good solutions are not lost.
Process:
After selection and reproduction, a certain number of the best individuals from the current
population are directly carried over to the next generation without modification.
Advantages:

Prepared by : Dr. Aarti Jain

Prevents the loss of high-fitness individuals, accelerating convergence.
Disadvantages:
Can lead to premature convergence if the elite dominate the population too quickly.
Parallel GA (PGA)
In a Parallel Genetic Algorithm, the population is divided into subpopulations (islands) that
evolve independently for a certain number of generations. Occasionally, individuals from
different subpopulations are exchanged (migration) to introduce new genetic material.
Process:
• Divide the population into isolated subpopulations.
• Run the GA independently on each subpopulation.
• Periodically allow migration (exchange of individuals) between subpopulations.
Advantages:
• Helps prevent premature convergence by maintaining diversity.
• Can be run efficiently on parallel computing architectures.
Disadvantages:
Requires proper tuning of migration frequency and population structure.
Hybrid GA
Hybrid Genetic Algorithms combine the GA framework with other optimization techniques to
improve performance. For instance, local search methods such as hill climbing or simulated
annealing can be applied to individuals during or after the genetic process to fine-tune
solutions.
Process:
Apply local optimization techniques to improve offspring after they are generated by crossover
and mutation.
Advantages:
Can significantly speed up convergence by refining solutions using local optimization.
Disadvantages:
Additional computational complexity due to the integration of multiple techniques.
Adaptive GA
In an Adaptive Genetic Algorithm, parameters such as mutation rate, crossover rate, or
population size are dynamically adjusted throughout the evolutionary process. This adaptation
allows the GA to explore more efficiently in early stages and exploit high-quality solutions
later.
Process:

Prepared by : Dr. Aarti Jain

Adjust parameters like mutation rate or crossover rate based on population diversity or other
criteria.
Advantages:
Improves convergence rates by adjusting exploration and exploitation balances dynamically.
Disadvantages:
Requires careful design of adaptive mechanisms to avoid suboptimal performance.

Genetic Algorithm (GA) Operators – Encoding, Crossover, Selection, and Mutation

Genetic Algorithms (GAs) rely on several key operators that simulate the biological processes
of reproduction and evolution. These operators—encoding, selection, crossover, and
mutation—are critical for guiding the search process and evolving a population of candidate
solutions over time.

Encoding (Representation)
Encoding refers to the way potential solutions to a problem are represented in the form of
chromosomes within the GA. A chromosome is a data structure that holds all the genes
(variables) of a candidate solution.

Types of Encoding in GA
Binary Encoding:
Representation: Solutions are represented as strings of binary digits (0s and 1s).
Example: A chromosome might be 101101 where each bit represents a specific variable.
Advantages: Simple and efficient for problems that are naturally binary (e.g., combinatorial
problems like the knapsack problem).
Disadvantages: Not well-suited for problems where decision variables are continuous or
require fine granularity.
Real-Valued Encoding:
Representation: Chromosomes consist of real numbers, where each gene corresponds to a real-
valued variable.
Example: A chromosome might be represented as [3.45, 2.1, 7.3], where each number
represents a decision variable.
Advantages: Suitable for optimization problems with continuous variables (e.g., engineering
design problems).
Disadvantages: More complex than binary encoding in terms of genetic operations (e.g.,
crossover and mutation).

Prepared by : Dr. Aarti Jain

Permutation Encoding:
Representation: Chromosomes are represented as permutations of a sequence of numbers. Each
permutation represents a different solution.
Example: A chromosome might be [3, 1, 4, 2], which could represent an ordering of tasks in a
scheduling problem.
Advantages: Commonly used in ordering problems like the traveling salesman problem (TSP).
Disadvantages: Special operators are required to ensure that valid permutations are maintained
during crossover and mutation.
Tree Encoding:
Representation: Solutions are represented as trees, where nodes represent functions or
operators, and leaves represent variables or constants.
Example: In genetic programming (a variant of GA), solutions are represented as mathematical
expressions in tree form.
Advantages: Suitable for evolving symbolic expressions or programs.
Disadvantages: Requires specialized genetic operators to manipulate tree structures.
Selection in GA
Selection is the process of choosing individuals from the population for reproduction. The main
goal of selection is to favor individuals with higher fitness, allowing them to pass on their traits
to the next generation.
Common Selection Methods:
Roulette Wheel Selection (Fitness Proportionate Selection):
Mechanism: Individuals are selected with a probability proportional to their fitness. Individuals
with higher fitness have a higher chance of being selected.
Imagine a roulette wheel divided into slices, where each slice’s size is proportional to the fitness
of the individual it represents.
Advantages: Simple and intuitive.
Disadvantages: Can lead to premature convergence if some individuals dominate the
population early on.
Tournament Selection:
Mechanism: A random subset of individuals is chosen, and the fittest individual from this subset
is selected. This process is repeated for each selection.
Advantages: More robust than roulette wheel selection, and easy to implement.
Disadvantages: The selection pressure (the strength of favoring fitter individuals) depends on
the size of the tournament.
Rank-Based Selection:

Prepared by : Dr. Aarti Jain

Mechanism: Individuals are ranked based on their fitness, and selection probabilities are
assigned based on rank rather than fitness. This prevents disproportionate advantage for the
highest-fitness individuals.
Advantages: Reduces the risk of premature convergence by giving low-fitness individuals a
chance.
Disadvantages: May slow down the convergence rate.
Elitism:
Mechanism: The best-performing individuals from the current generation are automatically
copied to the next generation without any changes.
Advantages: Guarantees that the best solutions are preserved.
Disadvantages: May reduce diversity if used excessively, leading to premature convergence.
Crossover (Recombination)
Crossover (also known as recombination) is the process by which two parent solutions are
combined to produce one or more offspring. This operator mimics biological reproduction and
is responsible for mixing genetic material from the parents to create new, potentially better
solutions.
Common Crossover Techniques:
Single-Point Crossover:
Mechanism: A random crossover point is selected on the parent chromosomes, and the genetic
material is swapped after this point.
Example: For two parent chromosomes 101|110 and 011|101, after crossover, the offspring
would be 101|101 and 011|110.
Advantages: Simple and efficient for binary-encoded chromosomes.
Disadvantages: Can disrupt tightly linked genes (epistasis) that depend on each other.
Two-Point Crossover:

Mechanism: Two crossover points are selected, and the genetic material between these points
is swapped between parents.
Example: For chromosomes 101|011|110 and 011|100|101, the result could be 101|100|110 and
011|011|101.
Advantages: Allows more flexibility and reduces disruption of gene linkages.
Disadvantages: More complex than single-point crossover.
Uniform Crossover:
Mechanism: Each gene is swapped between the parents independently with a certain
probability.

Prepared by : Dr. Aarti Jain

Example: For chromosomes 101010 and 110001, the offspring might be 111001 and 100010,
with a random mix of genes from both parents.
Advantages: Preserves diversity by mixing genes more freely than point-based methods.
Disadvantages: Can disrupt the structure of well-adapted individuals if used excessively.
Arithmetic Crossover (for Real-Valued Encoding):
Mechanism: New offspring are generated by taking a weighted average of the parents’ genes.
Example: If parents have genes 3.5 and 5.0, the offspring could inherit a gene value of 4.25 (a
linear combination).
Advantages: Useful for continuous optimization problems.
Disadvantages: Requires careful parameter tuning.
Mutation
Mutation introduces random changes to individual genes of offspring. The primary purpose of
mutation is to maintain genetic diversity in the population and to explore new areas of the
search space that might not be reachable through crossover alone.
Common Mutation Techniques:
Bit-Flip Mutation (for Binary Encoding):
Mechanism: A random bit in the chromosome is flipped (0 becomes 1, and 1 becomes 0).
Example: If the chromosome is 101010, after mutation it might become 101110.
Advantages: Simple and effective for binary-encoded chromosomes.
Disadvantages: Can be disruptive if applied too frequently.
Gaussian Mutation (for Real-Valued Encoding):
Mechanism: A small random value drawn from a Gaussian distribution is added to each gene.
Example: For a gene with value 3.45, the mutated value might be 3.47 or 3.42.
Advantages: Useful for continuous optimization problems.
Disadvantages: Requires careful tuning of the mutation rate and variance of the Gaussian
distribution.
Swap Mutation (for Permutation Encoding):
Mechanism: Two randomly chosen genes in the chromosome are swapped.
Example: If the chromosome is [1, 2, 3, 4], after mutation it might become [1, 4, 3, 2].
Advantages: Preserves the structure of permutation problems like the traveling salesman
problem.
Disadvantages: Limited to permutation encoding.

Prepared by : Dr. Aarti Jain

Inversion Mutation:
Mechanism: A random segment of the chromosome is reversed.
Example: If the chromosome is [1, 2, 3, 4, 5], after mutation it might become [1, 4, 3, 2, 5].
Advantages: Useful for maintaining order-based solutions, like routing problems.
Disadvantages: Can disrupt gene linkages.
Importance of different GA operators
i. Encoding defines how solutions are represented.
ii. Selection ensures that better solutions are more likely to reproduce.
iii. Crossover combines solutions to explore new possibilities.
iv. Mutation introduces randomness to maintain diversity and explore new solutions.

Example: Solved Single-Objective Optimization Problem Using Genetic Algorithms (GA)

Problem Statement: Consider a simple mathematical optimization problem where we want to
maximize the function:

𝑓(𝑥)=𝑥⋅sin(10⋅𝜋⋅𝑥)+1,
for 0≤x≤1
Our goal is to find the value of 𝑥 that maximizes the function f(x) using a Genetic Algorithm
(GA).
Step-by-Step Solution Using a Genetic Algorithm
Step 1: Problem Representation (Encoding)
In this case, we use binary encoding to represent the decision variable x. We will encode
x as a binary string. For simplicity, let's use 10 bits to represent x, which gives us a resolution
of
=1024 possible values for x in the range [0,1].
The binary chromosome for x can be converted to a real number using the formula:
𝑥= Decimal value of binary string
Thus, each binary string corresponds to a unique value of x in the interval [0,1].
Step 2: Initial Population
We generate an initial population of random binary strings (chromosomes). Suppose we use a
population size of 6 for illustration. The initial population might look like this:
Population={1001011101,0011011000,1110101011,0100110110,1100010101,0001111011}

Prepared by : Dr. Aarti Jain

Each chromosome represents a candidate solution for x, and we decode the binary string to get
the corresponding real value of x.
Step 3: Fitness Evaluation
The fitness function is simply the objective function evaluation corresponding real value of x
f(x)=x⋅sin(10⋅π⋅x)+1.
For each chromosome, we decode the binary string, calculate x, and then evaluate
f(x). For example:
Chromosome: 1001011101 (binary) → Decimal value: 605 → 605/1023= 0.591
Thus, f(0.591)=0.591⋅sin(10⋅π⋅0.591)+1=0.591⋅sin(18.56)+1≈1.38
Repeat this for all chromosomes in the population:
Accordingly, corresponding to Chromosome Decimal Value
f(x) are
1001011101 605 0.591 1.38
0011011000 216 0.211 1.84
1110101011 939 0.918 0.72
0100110110 310 0.303 1.83
1100010101 789 0.771 1.19
0001111011 123 0.120 1.33
Step 4: Selection
We use roulette wheel selection to choose parents for crossover. The selection probabilities are
based on the fitness values:
Total fitness =
1.38+1.84+0.72+1.83+1.19+1.33=8.29
Probabilities for each individual:
𝑃(1001011101)=1.38/8.29≈0.166 ,𝑃(0011011000)=1.84/8.29≈0.222,…
We spin the roulette wheel and select two parents for crossover. Suppose the selected parents
are 0011011000 (0.211) and 0100110110 (0.303).
Step 5: Crossover
We use single-point crossover. Suppose the crossover point is chosen after the 6th bit. The
parents are crossed over as follows:
Parent 1: 0011011000
Parent 2: 0100110110

Prepared by : Dr. Aarti Jain

After crossover:
Offspring 1: 0011010110
Offspring 2: 0100111000
Step 6: Mutation
We apply bit-flip mutation with a small probability (e.g., 1%). Suppose one mutation occurs,
flipping the 9th bit of offspring 2:
Offspring 2 before mutation: 0100111000
Offspring 2 after mutation: 0100111100
Step 7: Fitness Evaluation of Offspring
We decode the offspring and calculate their fitness:
Offspring 1: 0011010110 → 𝑥=214/1023=0.209
f(0.209)=1.84
Offspring 2: 0100111100 →
x= 1023/316 =0.309,
f(0.309)=1.84
Step 8: Replacement
The offspring replace the two least-fit individuals in the population, based on fitness.
Step 9: Repeat the Process
The algorithm repeats the process of selection, crossover, mutation, and replacement for several
generations until a termination condition is met (e.g., a maximum number of generations or a
solution with satisfactory fitness).

Final Solution
After multiple generations, the GA converges to a near-optimal solution for x. Suppose the
algorithm converges to:
x=0.211with f(0.211)=1.84
This value of x is the optimal solution found by the GA for this problem.
f(x)=x⋅sin(10⋅π⋅x)+1
f(x)≈1.84
The GA successfully found a near-optimal solution through evolutionary processes such as
selection, crossover, and mutation.

Prepared by : Dr. Aarti Jain