Unit:-2 Neural Networks

2.1Introduction to Neural Networks

Neural networks are computational models inspired by the human brain, designed to recognize patterns
and make decisions based on input data. They consist of layers of interconnected nodes (neurons) that
process data through weighted connections. Here, we'll cover key foundational concepts, including
Rosenblatt's neuron, the perceptron training algorithm, the perceptron convergence theorem, activation
functions, and adaptive linear neurons.

1. Rosenblatt's Neuron (Perceptron):

This is the simplest form of artificial neuron, introduced by Frank Rosenblatt in the 1950s. It takes multiple
numerical inputs, assigns weights to each input, sums them, and applies an activation function to produce a
single output.

Here's a breakdown of its functionality:

●​ Inputs: These are numerical values representing the data being processed.
●​ Weights: These are coefficients assigned to each input, signifying their importance to the output.
●​ Summation: A weighted sum of the inputs is calculated.
●​ Activation Function: This function transforms the weighted sum into a meaningful output value. A
common activation function used in Rosenblatt's neuron is the threshold function, which outputs 1 if the
sum is greater than a threshold value and 0 otherwise.

2. Perceptron Training Algorithm:

This algorithm allows a perceptron to learn from data. It iterates through training examples, adjusts the weights
based on the difference between the desired output and the actual output of the neuron.

Here's a simplified explanation of the training process:

1.​ The perceptron receives an input and calculates the weighted sum.
2.​ The activation function is applied to get the output.
3.​ The difference between the desired output (correct answer) and the actual output (perceptron's
prediction) is calculated (error).
4.​ The weights are adjusted proportionally to the error, bringing the output closer to the desired value.
5.​ Steps 1-4 are repeated for all training examples until the perceptron achieves a satisfactory level of
accuracy.

3. Perceptron Convergence Theorem:

This theorem states that a single perceptron can learn and perfectly classify any set of linearly separable data. In
simpler terms, if the data can be separated by a straight line in the input space, a perceptron can be trained to
correctly classify it. However, for more complex datasets that are not linearly separable, a single perceptron is
limited.

4. Activation Functions:
Page 1 of 5
These are mathematical functions applied to the weighted sum of inputs in an artificial neuron. They introduce
non-linearity into the network, allowing it to learn more complex patterns. Here are some commonly used
activation functions:

●​ Threshold Function: Outputs 1 if the input is greater than a threshold, 0 otherwise (used in Rosenblatt's
neuron for simple binary classification).
●​ Sigmoid Function: Outputs a value between 0 and 1, often used for representing probabilities.
●​ Tanh Function: Outputs a value between -1 and 1, similar to the sigmoid function but with a steeper
slope.
●​ ReLU (Rectified Linear Unit): Outputs the input directly if it's positive, otherwise outputs 0. This
function is popular due to its computational efficiency.

5. Adaptive Linear Neural Networks (ADALINE):

This is a single-layer neural network introduced by Bernard WidrSow in the 1960s. It builds upon the
perceptron by using a linear combination of inputs and a continuous, differentiable activation function (like the
sigmoid function). This allows ADALINE to use a more robust learning algorithm called the Widrow-Hoff rule
for weight updates, overcoming some limitations of the perceptron training algorithm.

Overall, these concepts lay the foundation for understanding more complex neural network architectures that
are widely used in various applications today.

2.2 Multi-Layer Neural Networks and Backpropagation:

Multi-layer neural networks (MLNNs) extend the capabilities of single-layer perceptrons by introducing hidden
layers between the input and output layers. This allows them to learn more complex relationships between
inputs and outputs, making them powerful tools for various tasks.
1. Universal Approximation Theorem:
This theorem informally states that a sufficiently large MLNN with one hidden layer and a specific activation
function (like sigmoid or tanh) can approximate any continuous function to an arbitrary degree of accuracy.
This implies that MLNNs are theoretically capable of learning a wide range of complex patterns.
2. Backpropagation Training Algorithm:
Backpropagation is a crucial learning algorithm that allows MLNNs to train effectively. It addresses the
limitations of training single perceptions on non-linearly separable data. Here's a simplified overview:

●​ Forward Pass: The input data propagates through the network, with each layer applying its weights and
activation function. The final output is obtained.
●​ Error Calculation: The difference (error) between the network's output and the desired output is calculated.
●​ Backward Pass: The error is propagated backward through the network layer by layer. The weights are adjusted
proportionally to their contribution to the error, using techniques like gradient descent.
●​ Iteration: The forward and backward passes are repeated for multiple training examples until the overall error on
the training data is minimized.

3. Batch learning vs Online learning:

Batch learning:
●​ The model is trained on the entire dataset at once.
Page 2 of 5
 ●​ Gradients are computed and weights are updated after processing the entire dataset.
●​ Advantages: Stable convergence and better optimization due to the use of the whole dataset.
●​ Disadvantages: Requires substantial memory and can be slow for large datasets.
Online learning
●​ The model is trained one example at a time.
●​ Weights are updated after each training example.
●​ Advantages: Can handle very large datasets and may escape local minima better.
●​ Disadvantages: Can lead to noisy updates and less stable convergence.

●​

4. Cross-validation and Generalization:

●​ Cross-validation: This technique helps prevent overfitting, a situation where the network performs well
on training data but poorly on unseen data. In cross-validation, the data is split into folds. The network is
trained on a subset of folds (training set) and evaluated on the remaining folds (validation set). This
process is repeated using different folds for training and validation. This helps assess the network's
ability to generalize to unseen data.
●​ Generalization: This refers to the network's ability to perform well on new data that it hasn't been
explicitly trained on. Cross-validation helps estimate and improve the network's generalization ability.
By combining MLNNs with backpropagation and careful training strategies, we can leverage the power of
neural networks for various tasks like image recognition, natural language processing, and time series
forecasting.

2.3 Radial Basis Function Networks

​ Radial Basis Function (RBF) networks are a type of artificial neural network that uses radial basis
functions as activation functions. These networks are particularly effective for interpolation in
multi-dimensional space and are used for function approximation, classification, and time-series prediction.

How RBFNs Work:

1.​ Architecture: RBFNs typically have three layers:

o​ Input layer: Receives the input data.
o​ Hidden layer: Uses radial basis functions (RBFs) as activation functions. These RBFs are
centered at specific points in the input space and their outputs depend on the distance between
the input and the center.
o​ Output layer: Produces the final output, usually a linear combination of the hidden layer
activations.
2.​ Function Approximation: RBFNs are particularly adept at approximating unknown functions from
data points. By adjusting the centers and widths of the RBFs in the hidden layer, the network can learn
the underlying relationship between the inputs and the outputs.
3.​ Training: Unlike traditional neural networks where backpropagation is used to adjust all weights, RBF
network training mainly focuses on determining the optimal parameters for the hidden layer RBFs

Page 3 of 5
 (centers and widths). The weights in the output layer are often solved using linear regression, making
training faster than some other neural network architectures.

Advantages of RBFNs:

●​ Fast Learning: Due to the simpler training process, RBFNs can learn from data relatively quickly.
●​ Universal Approximation: Similar to multi-layer neural networks with one hidden layer and non-linear
activation, RBFNs can theoretically approximate any continuous function to an arbitrary degree of
accuracy.
●​ Effective for Interpolation: RBFNs excel at finding a function that passes exactly through a set of data
points (interpolation problems).

Disadvantages of RBFNs:

●​ Choice of Centers and Spreads: Selecting appropriate centers and spreads is critical and can be
challenging.
●​ Scalability: The number of hidden neurons can become large for complex problems, leading to
increased computational cost.
●​ Memory Usage: Storing the centers and spreads for a large number of radial basis functions can require
significant memory.
●​ Selection of RBF Parameters: Choosing the right number, centers, and widths of RBFs can be
challenging and can significantly impact the network's performance.
●​ Overfitting: Like other neural networks, RBFNs are susceptible to overfitting if not trained carefully
with techniques like cross-validation.

Applications of RBFNs:

●​ Function approximation and regression problems

●​ Time series forecasting
●​ System control
●​ Robotics
●​ Financial modeling

RBF Network Variations:

●​ Normalized Hidden Unit Activations: This approach improves stability and generalization by
normalizing the outputs of hidden layer units.
●​ Soft Competition: Introduces a competition mechanism among hidden units based on their activations.
Units with outputs closer to the desired outcome have a greater influence on the final output.

In conclusion, RBFNs are a powerful tool for function approximation and various applications. Their fast
learning speed and strong theoretical foundation make them a valuable choice for specific tasks. However,
careful consideration of RBF parameters and training strategies is crucial to achieve optimal performance.

The Interpolation Problem

The interpolation problem involves constructing a function that exactly fits a set of given data points. RBF
networks can solve this problem by determining appropriate weights and radial basis functions that interpolate
the data.
Page 4 of 5
Training Algorithm
Steps

1.​ Select Centers: Choose the centers cj\mathbf{c}_jcj​for the RBFs, often done through clustering techniques like
k-means.
2.​ Compute RBF Values: Calculate the RBF values for each input data point.
3.​ Linear Weight Calculation: Solve a linear system to determine the weights that minimize the error between the
network output and the actual output.

The training process involves:

1.​ Input Layer: Receives input vectors.

2.​ Hidden Layer: Applies radial basis functions to the input.
3.​ Output Layer: Computes a weighted sum of the hidden layer outputs to produce the final output.

Radial Basis Function Network Variations

Radial Basis Function Network Variations:

●​ Normalized Hidden Unit Activations: This technique normalizes the sum of activations from all
hidden units. This can improve the stability and performance of the network.
●​ Soft Competition: This approach introduces a competition mechanism among hidden units. Units that
contribute more to the output receive a higher weight, promoting sparsity and potentially faster training.

Kernel Regression
Kernel regression is a non-parametric technique to estimate the conditional expectation of a random variable.
The idea is to predict the value of a dependent variable based on a weighted sum of the observed values, where
the weights are given by a kernel function. In the context of RBF networks, it can be described as:

Page 5 of 5
 Unit :-1 Introduction to Computational Intelligence
Intelligent systems are systems that can reason, learn, and act autonomously. They are inspired by the human brain and
nervous system, and they are designed to solve problems that are difficult or impossible for traditional computers. There
are many different types of intelligent systems, including:
Expert systems are systems that contain knowledge about a specific domain and can use that knowledge to solve
problems.
Machine learning systems are systems that can learn from data without being explicitly programmed.
Natural language processing systems are systems that can understand and generate human language.
Robotics systems are systems that can sense and manipulate their environment.

A.​Intelligent Systems
Intelligent Systems are designed to emulate aspects of human intelligence. These systems can process
information, learn from data, make decisions, and solve problems. They find applications in robotics,
natural language processing, expert systems, and more.

Computational Intelligence (CI)

Page 1 | 5
 Computational Intelligence involves the use of nature-inspired computational methodologies and
approaches to create intelligent systems. It includes methods that can handle imprecise, uncertain, and
incomplete information. The main paradigms in CI include:

Paradigms in Computational Intelligence

The paradigms in Computational Intelligence involve different methodologies and approaches for
problem-solving:

1.​ Supervised Learning​ In supervised learning, the model is trained on a labeled dataset, which means
that each training example is paired with an output label. This is commonly used in classification and
regression tasks.

2.​ Unsupervised Learning​ In unsupervised learning, the model is trained on data without labeled
responses. The goal is to infer the natural structure present within a set of data points. Clustering and
dimensionality reduction are typical tasks.

3.​ Reinforcement Learning​ This paradigm involves an agent learning to make decisions by performing
actions in an environment to maximize cumulative reward. It is extensively used in robotics, game
playing, and autonomous systems.

4.​ Hybrid Systems​ Combining multiple CI techniques to leverage their complementary strengths.
For instance, neuro-fuzzy systems integrate neural networks and fuzzy logic, and evolutionary neural
networks use evolutionary algorithms to optimize neural network architectures.

B.​Natural Immune System

The human immune system is a complex network of cells, tissues, and organs that work together to defend the body
against pathogens (such as bacteria, viruses, and parasites) and other foreign substances. Here's an overview of the key
components and theories related to the immune system

Page 2 | 5
 ●​ Natural Immune System: This is your body's defense system against infections and illnesses. It's a
complex network of organs, cells, and tissues that work together to identify and eliminate germs like
bacteria and viruses. The natural immune system has two main branches: the innate immune system
and the adaptive immune system.
o​ The innate immune system is the first line of defense and provides a general response to germs.
It includes physical barriers like skin and mucous membranes, white blood cells, and
inflammatory responses. The adaptive immune system is more specific and develops immunity
to specific germs over time. It includes B cells and T cells, which produce antibodies and target
infected cells directly.
●​ Antibodies:These are Y-shaped proteins produced by B cells of the adaptive immune system.
Antibodies are designed to recognize and attach to specific antigens (foreign substances) like bacteria
or viruses. Once attached, antibodies can neutralize the germ, flag it for destruction by other immune
cells, or prevent it from infecting healthy cells.
●​ Antigen:These are foreign substances that trigger an immune response. They can be molecules on the
surface of bacteria, viruses, fungi, or parasites. Antigens can also be toxins or pollen. When an antigen
enters the body, the immune system identifies it as a threat and starts producing antibodies to fight it.
●​ Lymphocytes: These are white blood cells that are the main players in the adaptive immune system.
There are two main types of lymphocytes: B cells and T cells.
o​ B cells mature in the bone marrow and produce antibodies.
o​ T cells mature in the thymus and attack infected cells directly or help regulate the immune
response.
●​ Lymphoid Organs: These are the organs and tissues where lymphocytes are produced, mature, and
stored. The major lymphoid organs include the thymus, bone marrow, spleen, and lymph nodes.
o​ The thymus is located in the chest and is responsible for maturing T cells.
o​ The bone marrow is found in the center of bones and is where B cells mature.
o​ The spleen is a fist-sized organ located in the upper left part of the abdomen that filters blood,
stores immune cells, and helps produce antibodies.
o​ Lymph nodes are small, bean-shaped structures located throughout the body that are
connected by lymphatic vessels. They filter lymph fluid, which contains white blood cells, and
help launch an immune response.
●​ Danger Theory:This theory proposes that the immune system doesn't just respond to foreign
substances (antigens), but also to signs of cellular damage or distress within the body. These danger
signals can be released by damaged or dying cells, or by pathogens (disease-causing germs) that are
trying to invade cells. By recognizing these danger signals, the immune system can initiate an
inflammatory response to isolate and destroy damaged cells or invading germs.

The natural immune system is a complex and fascinating system that helps keep us healthy. By understanding
how it works, we can take steps to support our immune system and fight off infection.

The Artificial Immune System (AIS)

The Artificial Immune System (AIS) is a field of computational intelligence inspired by the principles and processes of the
biological immune system. It aims to develop algorithms and systems that can solve complex problems in various
domains, such as anomaly detection, optimization, and machine learning. Here's an overview of the key concepts and
models in AIS, particularly focusing on the classical view model:

Page 3 | 5
 C.​ Artificial Immune Model
Artificial Immune Systems (AIS) are a subfield of Artificial Intelligence inspired by the workings of the natural
immune system. They borrow concepts from immunology to develop algorithms that can solve problems in
various domains.
There are different approaches to designing AIS, and the classical view model is one of them. This model draws
inspiration from the way T-cells in the immune system identify and eliminate "self" (healthy cells) from
"non-self" (pathogens).
Here's a breakdown of the classical view model in AIS:

●​ Antibodies (detectors): In the classical view, AIS uses detectors inspired by antibodies. These detectors
represent potential solutions to a problem.
●​ Antigens (data): The data or problem instances are mapped to antigens, which the detectors
(antibodies) interact with.
●​ Affinity function: A function determines how well a detector matches the antigen. This reflects how
suitable a potential solution is for the given data point.
●​ Selection: Detectors with high affinity for the "self" data (representing correct solutions) are selected
and potentially cloned. This mimics how the immune system selects effective T-cells.
●​ Diversity: Mechanisms are introduced to maintain diversity among the detectors. This ensures the
system can adapt to new challenges, similar to how the immune system learns to recognize new
pathogens.

Applications of Classical View AIS:

This approach is particularly useful for tasks like:

●​ Anomaly detection: Identifying unusual patterns in data, mimicking how the immune system detects
foreign agents.
●​ Pattern recognition: Classifying data points into different categories based on their characteristics.
●​ Optimization problems: Finding the best solution among a set of possibilities.

●​ Antibodies (detectors): In the classical view, AIS uses detectors inspired by antibodies. These detectors
represent potential solutions to a problem.
●​ Antigens (data): The data or problem instances are mapped to antigens, which the detectors
(antibodies) interact with.
●​ Affinity function: A function determines how well a detector matches the antigen. This reflects how
suitable a potential solution is for the given data point.
●​ Selection: Detectors with high affinity for the "self" data (representing correct solutions) are selected
and potentially cloned. This mimics how the immune system selects effective T-cells.
●​ Diversity: Mechanisms are introduced to maintain diversity among the detectors. This ensures the
system can adapt to new challenges, similar to how the immune system learns to recognize new
pathogens.

Applications of Classical View AIS:

This approach is particularly useful for tasks like:

Page 4 | 5
●​ Anomaly detection: Identifying unusual patterns in data, mimicking how the immune system detects
foreign agents.
●​ Pattern recognition: Classifying data points into different categories based on their characteristics.
●​ Optimization problems: Finding the best solution among a set of possibilities.

Page 5 | 5
 Unit 6: Deep Learning
A.​ Basic Idea: Introduction to Deep Learning

Deep learning is a subfield of artificial intelligence (AI) that's rapidly transforming how machines learn and
interact with the world. Inspired by the structure and function of the human brain, deep learning utilizes artificial
neural networks to extract meaningful patterns from massive amounts of data.

1
Common architectural principles of Deep Networks (Parameters,Layers, Activation functions, Loss functions,
Optimization algorithm, Hyper parameters)

2
3
 ​

4
5
6
Major Architectures of Deep Networks: Generative Adversarial Networks, Convolutional Neural Network (CNN
Architecture, Input layers, Convolution layers, Pooling layers, Fully connected layers), Recurrent Neural Network
(RNN architecture, Modeling the time dimension, LSTM networks)

7
8
9
10
11
12
13
14
15
16
17
18
19
20
Transformers: Encoder decoder architecture (Encoder only, Decoder only, Encoder-decoder), LLM (Large
Language Models, Pre-training, fine-tuning), Issues with RNN encoder decoder, Attention mechanism

21
22
Large Language Models (LLMs):

Imagine an LLM as a super-powered language learner. These models are trained on massive amounts of text
data, allowing them to grasp the nuances of language, including grammar, syntax, and even some aspects of
semantics. They can perform a variety of tasks, such as:

●​ Text generation: Creating different creative text formats, like poems, code, scripts, musical pieces,
emails, letters, etc.
●​ Machine translation: Converting text from one language to another.
●​ Question answering: Providing summaries or answers to questions posed in natural language.
●​ Text summarization: Condensing lengthy pieces of text into shorter summaries.

Pre-training:

Think of pre-training as giving the LLM a strong foundation in general language understanding. It involves
training the model on a vast corpus of unlabeled text data, like books, articles, or code. This data doesn't have
specific labels or tasks associated with it. During pre-training, the LLM learns to identify patterns and
relationships within language, like predicting the next word in a sequence or understanding the overall
sentiment of a piece of text.

Fine-tuning:

Here's where LLMs become true specialists. Fine-tuning takes a pre-trained LLM and tailors it for a specific
task. This involves training the model on a smaller dataset of labeled data relevant to the desired task. For
example, to create a machine translation model for French to English, you would fine-tune the LLM on a
dataset of French-English text pairs. Fine-tuning leverages the general language understanding from
pre-training and refines it for the specific task, significantly improving performance.

23
Unit 5: Computational Swarm Intelligence
Particle Swarm Optimization: Basic principles of computational swarm intelligence (Swarm in Known andUnknown
environments), Particle swarm optimization (Influence of the parameters, Turbulence factor, Boundary handling, Global
best and local best PSO), Social network structures, Basic variations (Velocity clamping, Inertia weight, Construction
coefficient, Synchronous vs Asynchronous updates, Velocity models)
Single Solution Particle Swarm Optimization: Guaranteed convergence PSO, Social based PSO, Hybrid
algorithm, Sub swarm based PSO, Multi start PSO algorithm, Repelling models, Binary PSO, Multi-objective
PSO (Leader selection mechanism)
 Optimization
Unit 4: Evolutionary Computation (8 Hrs.)
Introduction to Computation
Evolutionary Computation (EC) is a problem-solving technique inspired by biological evolution which
mimics natural selection, survival of the fittest, and reproduction.
Advantages of Computation
Effective exploration of large solution spaces.
Ability to handle complex, non-linear optimization problems.
Versatility across domains: engineering, finance, biology, Al.
Iterative refinement mirrors adaptive processes in nature.

Generic Evolutionary Algorithm

Evolution via natural selection of a randomly chosen population of individuals can be thought of as a search
through the space of possible chromosome values.
In that sense, an evolutionary algorithm (EA) is a stochastic search for an optimal solution to a given problem.
Main components of EA :
An encoding of solutions to the problem as a chromosome;
A function to evaluate the fitness, or survival strength of individuals;
Initialization of the initial population;
Selection operators; and
Reproduction operators.
Generic evolutionary Algorithm
Let t = 0 be the generation counter;
Create and initialize an Tic-dimensional population, CO, to consist of ns individuals; while stopping
condition(s) not true do
Evaluate the fitness, f (Xi (t)), of each individual, Xi(t);
Perform reproduction to create offspring; Select the
new population, C(t + 1);
Advance to the new generation, i.e. t = t + 1; end
Stopping Conditions:
1 . Terminate when no improvement is observed over a number of consecutive generations (by fitness
function)
2. Terminate when there is no change in the population
3. Terminate when an acceptable solution has been found
4. Terminate when the objective function slope is approximately zero

Biological evolution is the process through which living organisms change over successive generations,
driven by two fundamental principles: variation and natural selection.

1. Variation: Within a population of organisms, there exists genetic diversity due to mutations, genetic
recombination, and other factors. This variation results in individuals having different traits and
characteristics.
2. Natural Selection: Organisms with traits that offer advantages for survival and reproduction in their
environment are more likely to pass on their genes to the next generation. This process, known as
natural selection, leads to the gradual accumulation of beneficial traits and the elimination of less
advantageous ones.
Representation — The Chromosome
In nature, chromosomes determine an organism's traits.
Similarly, in EC, each individual (potential solution) has a chromosome that represents its
characteristics.
The chromosome, also called a genome, encodes the variables being optimized.

Ashok Kumar Pant I MIT 554 | TU | 2024 1

Global Numerical
A chromosome represents a candidate solution to an optimization problem.
Each variable in the problem is a "gene" within the chromosome.
The value assigned to a variable is an "allele."
There are two types of information in a chromosome:
Genotype: Inherited genetic makeup (which alleles the individual possesses).
Phenotype: Observable traits expressed based on the genotype and environment.

Choosing the Right Representation:

The effectiveness of an EC algorithm heavily depends on how candidate solutions are represented
(chromosomes). Different EC paradigms use various representations.
Common Representations:
• Binary Vectors: Most common in Genetic Algorithms (GAS). Each variable is encoded as a string of
Os and Is.
• Nominal Values: Each possible value for a variable is represented by a unique bit string.
• Real-Valued Representations: Used for continuous optimization problems. Continuous values (floating
points) are mapped to a discrete bit string using encoding functions.
Initial Population
Evolutionary algorithms (EAs) are stochastic, population-based search algorithms used for
optimization problems.
Generating an initial population with random values ensures a diverse representation of the search
space.
The size of the initial population impacts computational complexity and exploration abilities.
Larger populations increase diversity but also raise computational complexity per generation.
Smaller populations may limit exploration, requiring more generations to converge.
In the case of a small population, increasing the rate of mutation can help explore more of the search
space.
Balancing population size, mutation rate, and other parameters is crucial for efficient exploration and
convergence.

Fitness Function
The fitness function (denoted as f) quantifies the quality of a solution represented by a chromosome in
an evolutionary algorithm. It maps a chromosome representation to a scalar value.
The fitness function can be represented as f: Tn -+ R, where T represents the data type of chromosome
elements and n represents the chromosome dimensions.
The fitness function typically represents the objective function of the optimization problem being
solved by the EA.
Fitness functions can provide either absolute measures of fitness, directly evaluating the solution using
the objective function, or relative fitness measures, comparing an individual's performance to others in
the population.
Fitness Function
The type of optimization problem influences the fitness function design
Unconstrained: The fitness function directly corresponds to the objective function.
Constrained: Penalty functions might be added to account for constraints alongside the original
objective.
Multi-Objective: The fitness function can be a weighted sum of sub-objectives.
Dynamic/Noisy: The function might change over time or incorporate noise.

Selection
• Selection is indeed a fundamental aspect of evolutionary algorithms (EAs), mirroring the principles of
natural selection.
• It plays a crucial role in shaping the population of candidate solutions over successive generations.

Ashok Kumar Pant I MIT 554 | TU | 2024 2

Selection Steps:
• Selection of the New Population:
• Anew population of candidate solutions is selected at the end of each generation to serve as the
population of the next generation.
• The new population can be selected from only the offspring, or from both the parents and the offspring.
o The selection operator should ensure that good individuals do survive to next generations.
Reproduction:
• Offspring are created through the application of crossover and/or mutation operators.
In terms of crossover, "superior' individuals should have more opportunities to reproduce to
ensure that offspring contain genetic material of the best individuals.
• In the case of mutation, selection mechanisms should focus on "weak" individuals.

Selective Pressure
Selection operators are characterized by their selective pressure, also referred to as the takeover time, which
relates to the time it requires to produce a uniform population. It is defined as the speed at which the best
solution will occupy the entire population by repeated application of the selection operator alone. An operator
with a high selective pressure decreases diversity in the population more rapidly than operators with a low
selective pressure, which may lead to premature convergence to suboptimal solutions. A high selective
pressure limits the exploration abilities of the population.

Random selection
Random selection is the simplest selection operator, where each individual has the same probability of l/n
(where n is the population size) to be selected. No fitness information is used, which means that the best and
the worst individuals have exactly the same probability of surviving to the next generation. Random selection
has the lowest selective pressure among other selection operators.

Proportional Selection
Proportional selection, proposed by Holland, biases selection towards the most-fit individuals. A
probability distribution proportional to the fitness is created, and individuals are selected by sampling
the distribution, f(xz)
(þ(Xi)
Where, n = total number of individuals in the is the probability that x will be selected, f(x.) is the scaled
fitness of x
Two popular sampling methods used in proportional selection are

• Roulette wheel sampling

• Stochastic universal sampling

Tournament
Tournament selection selects a group of t individuals randomly from the population, where t < n (n is the total
number of individuals in the population). The performance of the selected t individuals is compared and the
best individual from this group is selected and returned by the operator. For crossover with two parents,
tournament selection is done twice, once for the selection of each parent.
Provided that the tournament size, t, is not too large, tournament selection prevents the best individual from
dominating, thus having a lower selection pressure. On the other hand, if t is too small, the chances that bad
individuals are selected increase.
Even though tournament selection uses fitness information to select the best individual of a tournament,
random selection of the individuals that make up the tournament reduces selective pressure compared to
proportional selection. However, note that the selective pressure is directly related to t. If t = n, the best
individual will always be selected, resulting in a very high selective pressure. On the other hand, if t = 1,
random selection is obtained.

Ashok Kumar Pant I MIT 554 | TU | 2024 3

Global Numerical
Rank-Based
Rank-based selection uses the rank ordering of fitness values to determine the probability of selection.
Selection is therefore independent of actual fitness values, with the advantage that the best individual will not
dominate in the selection process.
Non-deterministic linear sampling selects an individual, x., such that )), where the
individuals are sorted in decreasing order of fitness value. It is also assumed that the rank of the best
individual is 0, and that of the worst individual is n-l.
Linear ranking assumes that the best individual creates Åb offspring, and the worst individual Rw, where
Q and Åw=2-Å . The selection probability of each individual is calculated as

Where f (x.) is the rank of the x

Boltzmann
Boltzmann selection is based on the thermodynamical principles of simulated annealing. It has been
used in different ways, one of which computes selection probabilities as follows:

1
Where T is temperature parameter. A temperature schedule is used to reduce T from its initial large value to
a small value. The initial large value ensures that all individuals have an equal probability of being selected.
As T becomes smaller, selection focuses more on the good individuals.

Elitism
Elitism refers to the process of ensuring that the best individuals of the current population survive to the next
generation. The best individuals are copied to the new population without being mutated. The more individuals
that survive to the next generation, the less the diversity of the new population.

Hall of Fame
The hall of fame is a selection scheme similar to the list of best players of an arcade game. For each generation,
the best individual is selected to be inserted into the hall of fame. The hall of fame will therefore contain an
archive of the best individuals found from the first generation. The hall of fame can be used as a parent pool
for the crossover operator, or, at the last generation, the best individual is selected as the best one in the hall
of fame.

Reproduction Operators
Reproduction is the process of producing offspring from selected parents by applying crossover and/or
mutation operators.
Crossover is the process of creating one or more new individuals through the combination of genetic
material randomly selected from two or more parents.
Mutation is the process of randomly changing the values of genes in a chromosome.
Reproduction can be applied with replacement, in which case newly generated individuals replace
parent individuals only if the fitness of the new offspring is better than that of the corresponding parents.

Evolutionary Optimization
Evolutionary Optimization is a technique inspired by evolution to find optimal solutions to problems.
There are two main types of evolutionary optimization:
• Quantitative: Uses numerical measures (functions) to assess the quality of potential solutions. Examples
include minimizing distance or maximizing profit.

Ashok Kumar Pant I MIT 554 | TU | 2024 4

 • Qualitative: Relies on human judgment to evaluate solutions. This is useful when no clear numerical
measure exists, like ranking coffee blends or judging art.

Quantitative optimization can be further divided into two categories:

• Numeric optimization: Deals with finding points in a continuous space that minimize or maximize a
function.
• Combinatorial optimization: Involves finding the best combination of elements from a set, considering
factors like weight or order. E.g, knapsack problem, scheduling
Optimization - One Dimension
Let's take one-dimensional black box optimization example, the goal is to find the value of x that minimizes
the function f(x)=x2 , without prior knowledge of the function.
Note: By calculus method, Take the derivative and set it equal to zero and solve for x(x = 0). Then take
the second derivative and note that it is positive, thus the point x = O is a minimum of (x).
An evolutionary approach for finding the minimum number could be as follows;
Initialization: Start with a population of p random candidate solutions, x x .. x chosen uniformly
between -100 and +100
Mutation: Generate offspring by adding a random number from a standard Gaussian distribution to
each parent. Here, for simplicity.
Evaluation: Evaluate the fitness (score) of each solution by computing f(x.) for each i in the population.
Selection: Select the best-ranking solutions to become the parents for the next generation.

Halting Criteria: The process may stop after a certain number of generations or when the score of the best
solution falls below a threshold, such as 10-6 if it's known that zero is the minimum for f(x)=x2
Example in One Dimension
Generation 1:
1. Initialization: Generate 5 random candidate solutions, , , x3,
x4, a:5, uniformly chosen between -100 and +100.
— —23, 45, = 12, — O, = 87
2. Mutation: Generate 5 offspring by adding a random number
from a standard Gaussian distribution to each parent.
Let's say after mutation:
.T6 = —23.1, .T,7 = 45.8, = 11.3, = 0.5, = 87.2
3. Evaluation: Evaluate the fitness (score) of each solution by
computing f (Xi) = for each i in the population.
f(œl) = 529, f(œ2) = 2025, f(œ3) = 144, f(œ4) = O, f(œ5) 7569
f(œ6) = 532.81, f@7) = 2101.64, f@8) = 127.69, f(œ9) = 0.25,
= 7594.84
4. Selection: Select the 5 best-ranking solutions to become the
parents for the next generation.

Generation 2:
ChatGPT: Calculation might be wrong

Ashok Kumar Pant I MIT 554 | TU | 2024 5

Two or more Dimension
In multidimensional optimization, parents are selected from the space an , where n is the number of dimensions.
Offspring are generated by randomly varying each dimension of the parent or by combining multiple parents
through recombination methods.
Mutation and Recombination:
• Mutation involves modifying a single parent to create a single offspring, typically by randomly varying
each dimension independently.
• Recombination methods, such as crossover and blending, combine multiple parents to create offspring.
Crossover:
• In crossover, a crossover point is randomly selected, and segments of two parents are swapped to create
two new offspring.
• One-point crossover may force segments near the ends to remain together, so multipoint or uniform
crossover methods are used to exchange segments more freely.
Blending:
• Blending averages parameters of parent solutions to create offspring, providing a smoother transition
between parents.
• Weighted arithmetic means or geometric means can be used instead of simple arithmetic means.
Extension to Multiple Parents:
• Recombination methods can be extended to involve more than two parents, allowing for greater
diversity in offspring generation.
Combinatorial Example TSP Problem
• The Travelling Salesman Problem(TSP) involves visiting a set of cities once and returning home,
aiming to minimize the total distance traveled.
• The problem becomes increasingly complex(NP-hard) as the factorial function of the number of cities
determines the total number of possible solutions.
Representation and Scoring:
• Solutions can be represented as ordered lists of cities to be visited.
• The score of a solution is the total distance traveled through the cities.
Mutation and Recombination Operators:
• Various mutation and recombination operators are proposed:
• Select and replace: Randomly choose a city and replace it at another random position. Invert:
Invert the segment between two randomly chosen cities.
• Protect and randomize: Pass a segment intact from parent to offspring and randomize the remaining
cities. Partially mapped crossover (PMX) is introduced as a recombination operator, combining parts
of two parents to form an offspring.
Combinatorial
Example TSP Problem
Results and Analysis:

• Comparative studies using different operators reveal their effectiveness in finding optimal solutions.

• PMX combined with inversion shows promise, outperforming individual operators in certain scenarios.

• The need for dynamic operator selection to adapt to the evolving search process is highlighted.
Extension to Real-World Problems:

Ashok Kumar Pant I MIT 554 | TU | 2024 6

 • Combinatorial optimization extends to various real-world problems, such as logistics optimization and
feature selection in machine learning.

• These problems require tailored approaches that leverage evolutionary algorithms to efficiently explore
solution spaces.

Constraint Handling Approaches

Real-world optimization problems typically have constraints - limits on the feasible solutions.
Constraints can be hard (violating them makes the solution invalid) or soft (violating them incurs a penalty).
Approaches to handling constraints:
1. Penalty Functions:
Modify the objective function to include a penalty term for constraint violation.
Penalty increases with the severity of the violation (e.g., cost for delayed fuel truck arrival).
2. Setting Infeasible Solutions to Infinitely Bad:
o Works for hard constraints but creates uninformative areas in the search space.
3. Gradually Increasing Penalty over Generations:
o Soft constraint initially, transitions to hard constraint over time. Requires defining a
schedule for this transition.
4. Parameter Constraints:
o Ensure mutations or recombinations that violate constraints are set aside or reflected back into
the feasible range. o Advantage: Always evaluates feasible solutions.
Disadvantage: Can introduce unintended boundary effects on variation operators.
5. Problem-Specific Operators:
Design variation operators that consider the specific problem constraints.

Multi-objective optimization (MOO)

techniques that can be found in the general Evolutionary Algorithms literature can be applied to
Evolutionary Programming to solve multi-objective problems.
Weighted Aggregation Approach
One of the simplest approaches to deal with MOPs is to define an aggregate objective function as a weighted
sum of sub-objectives:
f(x) = Wkfk(x), where n 2 is the total number of sub-objectives, and u.)k e [0, 1], k=l ,...,n with Wk =1
Multi-objective optimization (MOO) techniques that can be found in the general Evolutionary Algorithms
literature can be applied to Evolutionary Programming to solve multi-objective problems.
Pareto Archived Evolution Strategy (PAES):
Candidate Solution Generation: PAES utilizes a (1 + I)-ES for generating candidate solutions.
Candidate Solution Acceptance: Candidate solutions are accepted based on dominance. If the offspring
dominates the parent, it survives to the next generation. If the parent dominates the offspring, the
offspring is rejected. If neither dominates the other, the offspring is compared with solutions in the
nondominated solutions archive.
Nondominated-Solutions Archive: PAES maintains an archive of nondominated solutions. The size of
the archive is limited. When an offspring dominates the solutions in the archive, it is included. If
dominated by any archive solutions, it's rejected. If nondominated, it's accepted based on the degree of
crowding in the objective space.
Archive Update: The archive is updated based on the dominance relationships between the candidate
solution and the archive solutions
Approach by Costa and Oliveira:
Pareto Ranking: Fitnesses of individuals are determined based on a Pareto ranking, grouping
individuals into Pareto fronts.
Fitness Assignment: Individuals in each Pareto front are assigned fitness values based on their niche
count. The niche count is the number of individuals within a distance (a share) in the objective space.

Ashok Kumar Pant I MIT 554 | TU | 2024 7

 Selection: Depending on the ES used, a certain number of individuals are selected from the population
to form the next generation. If the number of individuals in the first Pareto front exceeds a threshold,
tournament selection is used; otherwise, the best individuals are selected.
Archive Maintenance: An archive of fixed size containing nondominated solutions is maintained. At
each generation, each Pareto optimal solution is tested for inclusion based on diversity, dominance
relationships with archive solutions, and distance from archive solutions.

Niching
Niching in Evolutionary Strategies (ES) is a technique used to find multiple solutions to a problem,
particularly in scenarios with multiple local optima (peaks) in the fitness landscape. Here's a breakdown of
two niching approaches for ES:
Multipopulation ES with Clusters by Aichholzer et al.:
This method utilizes multiple subpopulations (T) to explore different regions of the search space.
Each individual has a lifespan of K generations within its subpopulation.
Recombination:
One parent is chosen from the current subpopulation using roulette wheel selection.
The second parent is selected from any subpopulation, but with a bias towards individuals from closer
subpopulations. This promotes exploration within clusters formed around local optima.
Niching
Dynamic Niching Algorithm by Shir and Bäck:
This algorithm identifies fitness peaks using a peak identification algorithm, with each peak
corresponding to a niche.
In each generation, mutation is applied to individuals, and then a dynamic peak identification algorithm
identifies niches.
Individuals are assigned to their closest niche, and recombination is applied within niche boundaries.
Niches are populated with offspring, ensuring diversity and exploration of multiple solutions.
New niches are generated at each generation, allowing for continuous exploration of diverse solutions.

Parameters
Strategy parameters are used to control the amount of change that is introduced into an individual during
mutation.
Static strategy parameters:
In this approach, the strategy parameters are fixed for the entire evolutionary run. This is the simplest
approach, but it can be difficult to find good values for the strategy parameters that will work well for all
problems.

Dynamic strategy parameters:

In this approach, the strategy parameters are changed over the course of the evolutionary run. This can be
done in a number of ways, such as by adapting the strategy parameters to the fitness of the individual or to
the distance of the individual from the best individual in the population.

Ashok Kumar Pant I MIT 554 | TU | 2024 8

Dynamic strategy Approaches
Fitness-Based Adjustment
Adjust strategy parameters based on individual fitness.
Weaker individuals are mutated more, encouraging exploration, while stronger individuals are
mutated less, allowing for exploitation.
Distance-Based Adjustment
Adjust strategy parameters based on the distance from the best individual or search space
boundaries.
Encourages exploration by increasing mutations for individuals far from the best solution.
Combination Approaches
Combine fitness information with other factors like boundary constraints or population statistics
to adjust strategy parameters.
Global Information Utilization
Use global information like the maximum and minimum fitness values of the population to
adjust strategy parameters.
Helps in adapting strategy parameters based on the overall fitness landscape.

Self Adaptation
The ability of an evolutionary algorithm to adjust its variation operators during the search process to
improve performance.
In evolutionary algorithms, parameters such as mutation rates or step sizes significantly impact the
algorithm's performance.
Self-adaptation involves allowing these parameters to evolve over time during the optimization process.
The problem: Standard EAS use fixed parameters for variation operators (e.g., mutation step size). This can
lead to a trade-off between exploration (finding new areas) and exploitation (refining good solutions)

Self Adaptation - Solutions

1 . The 1/5 Rule (heuristic):
o Aims for a 1/5 success rate for mutations (balancing exploration and
exploitation).
o It suggests adjusting the mutation step size based on this success rate.
2. Self-adapting Mutation Step Size:
Mutation step size is encoded as part of the solution along with the objective
parameters.
o Larger step size for successful mutations is likely to be inherited by offspring.
This allows the EA to learn the appropriate step size for different regions of the search space.
3. Meta-Evolution on Probabilities of Variation Operators:
o Self-adaptation can be applied to control:
o The probability of applying a variation operator (e.g., crossover vs. mutation).
o The parameters of a variation operator (e.g., length of inversion in TSP).
4. Meta-Evolution on Combinations of Variation Operators:
o Self-adaptation can be used to combine different variation operators dynamically.
o Example: Balancing Gaussian mutation (exploitation) and Cauchy mutation (exploration) based
on progress.
5. Fitness Distributions of Variation Operators:
o Analyze the distribution of offspring fitness after applying a variation operator.
This can help decide:
o How well a variation operator performs.
o Whether it's worth including the operator.
o How to set or adapt its pararnqtqrârnar

Ashok Kumar Pant I MIT 554 | TU | 2024 9

Elements of Evolutionary Algorithms
Evolutionary algorithms require careful design of solution encoding, fitness function, selection method and
genetic operators to tackle specific optimization problems.

Encoding Of Solution Candidates

Encoding of solution candidates is an important aspect of evolutionary algorithms (EAs). A good encoding
can significantly impact the efficiency and effectiveness of an EA in finding optimal solutions.
There are several desirable properties that an encoding should have:
Similar phenotypes should be represented by similar genotypes. This means that solutions that are close
together in the solution space should also have similar encodings. This makes it easier for the EA to
explore the search space and find good solutions.
Similarly encoded candidate solutions should have similar fitness. This means that solutions that have
similar encodings should also have similar fitness values. This helps the EA to select better solutions
during the selection process.
The search space Q should be closed under the used genetic operators. This means that the genetic
operators should only produce new solutions that are also valid solutions in the problem domain.
Otherwise, the EA may explore invalid regions of the search space and waste time.
N-Queen Problem
In the n-queens problem,where the goal is to place n queens on an n x n chessboard such that no two queens
threaten each other, the encoding we chose, namely using an array of n integer numbers with values in
{O,...,n—l}, is much better than representing the placement of the queens by a binary array with n 2 elements,
in which each element refers to a square of the n x n chessboard and encodes whether this square is occupied
by a queen (bit is 1) or not (bit is O). The reason is that our encoding already rules out candidate solutions
with more than one queen in the same rank (row) and thus considerably reduces the search space. In addition,
it ensures that there are always exactly n queens on the board, while with a binary encoding the genetic
operators we employed (standard mutation and one-point crossover) may produce a candidate solution with
more or less queens.
An even better encoding than the one we chose is to restrict the candidate solutions to permutations of the
numbers {O,...,n—l}. Such an encoding not only guarantees that each rank contains exactly one queen, but at
the same time that each column contains exactly one queen. Hence it reduces the search space even further,
making the task much easier for the evolutionary algorithm
Hamming Cliffs
Similar phenotypes should be represented by similar genotypes.

Epistasis
Similarly encoded candidate solutions should have a similar fitness.
In biology epistasis means the phenomenon that one allele of a gene (the so-called epistatic gene) suppresses
the effect of all possible alleles of another gene.
In evolutionary algorithms, epistasis refers to the interaction between genes in a chromosome, where
modifying one gene can significantly affect the fitness of the solution candidate, potentially leading to
difficulties in optimization.
The issue:
• In high epistasis cases, a small change in the genotype (chromosome) can cause a large change in the
phenotype (solution candidate) and its fitness. This violates the assumption that gradual
improvements are possible through minor genetic modifications.
Epistasis - Example TSP
Low Epistasis Encoding:
Represented by a permutation of cities, where each city's position in the permutation corresponds
to its visitation order in the round trip.
Modifying genes (swapping cities) results in comparable changes in fitness, regardless of which
genes are swapped.
Changes to the tour are localized, affecting only nearby cities, as the rest of the tour remains
unaffected.
High Epistasis Encoding:

Ashok Kumar Pant I MIT 554 | TU | 2024 10

 Specified by a list of numbers indicating the position of the next city to visit after deleting already
visited cities.
Modifying a single gene can drastically alter a significant portion of the trip, especially genes closer
to the beginning of the chromosome.
Even minimal genetic modifications can lead to substantial changes in the entire trip, rendering
the optimization problem difficult for evolutionary algorithms.

Closedness of search Space

If possible, the search space Q should be closed under the used genetic operators.
Generally, we say that an individual lies outside of the search space if
• its chromosome cannot be meaningfully interpreted or decoded,
• the represented candidate solution does not fulfill certain basic requirements,
• the represented candidate solution is evaluated incorrectly by the fitness function.

Approaches to Maintaining a Closed Search Space:

Choose or design a different encoding, which does not suffer from this problem. Note that this may
require enlarging the search space.
Choose or design encoding-specific genetic operators under which the search space is closed. That is,
find genetic operators which ensure that only elements of the search space can be produced.
Use repair mechanisms, with which an individual outside the search space is modified in such a way
that it is brought back into the search space.
Accept individuals outside the search space in the evolutionary algorithm, but introduce a penalty term
that reduces the fitness of such individuals, so that the selection process is endowed with a clear
tendency to eliminate them.
Closedness of search Space
Example: N-Queen Problem
Different encoding: Already discussed
Encoding-specific genetic operators: Instead of standard mutation, one may use gene pair swaps as a
mutation operation. Likewise, a permutation preserving crossover operation can be designed. These
choices ensure that the search space (i.e., the set of permutations of {1 ,...,n—l}) becomes closed under
the genetic operators.
Repair mechanisms: If a genetic operator produced a chromosome that is not a permutation, repair it,
that is, modify it in such a way that it becomes a permutation. For example, find and remove duplicate
occurrences of the same column numbers and append the missing numbers.
Penalty term: Allow the population to contain chromosomes that are not permutations, but add a penalty
term to the fitness function, which reduces the fitness of such non-permutations. For example, the fitness
could be reduced by the number of missing column numbers, possibly multiplied by a weighting factor

Genetic Operators
Mutation Operators
Genetic one-parent operators are generally referred to as mutation or variation operators. Such operators
mainly serve the purpose to introduce an element of local search, that is, to produce a solution candidate that
is (very) similar to its parent.
Different types of mutation operators include:
Bit Mutation: Used for binary encoded chromosomes, where randomly selected bits are flipped.
Gaussian Mutation: Applied to chromosomes represented by real-valued numbers, where random
numbers from a Gaussian distribution are added to each gene.
Self-adaptive Gaussian Mutation: Each chromosome has its own mutation step width, which evolves
over generations based on its performance.

Ashok Kumar Pant I MIT 554 | TU | 2024 11

Crossover
Crossover operators combine information from two parent individuals to generate offspring with traits
inherited from both parents. They promote exploration by recombining good solutions and potentially
exploiting synergies between them.

Ashok Kumar Pant I MIT 554 | TU | 2024 12

Common types of crossover operators include:
One-point Crossover: A single random point is selected, and the tails of the two parents are exchanged.
Two-point Crossover: Two random points are chosen, and the intermediate section is swapped between
parents.
Uniform Crossover: Each gene is chosen from one parent or the other with equal probability.
Shuffle Crossover: Genes are shuffled before crossover and then re-shuffled afterward to maintain
order.
Permutation-preserving Crossover: Ensures that offspring remains a permutation of the original set,
crucial for problems like the traveling salesman.
One-point Crossover
Algorithm 12.4 (One-point Crossover)
procedure crossover_lpoint (var r, s: array of allele); begin exchange part of two chromosomes c 4—
random element of {1 length(s) — 1}; choose cut point for i e {0 c — 1} do begin
traverse the section to exchange t t; end swap genes up to the cut point end
Crossover Example

3144361
123456 123456

5212546
Fig. 12.13 Example of one-point crossover
5214361 5142546
123456 123456
3214346
Fig. 12.14 Example of two-point crossover

Ashok Kumar Pant I MIT 554 | TU | 2024 13

Crossover Example

3 2

5 1 12 566
Fig. 12.15 Example of uniform crossover. For every gene it is determined independently whether it
is exchanged (+) or not (—)
shuffle crossover de-shuffle

123456 426513 426513 123456

Fig. 12.16 Example of shuffle crossover (which is a modified one-point crossover)

Multi-parent
These operators involve more than two parents and aim to increase diversity further.
Diagonal crossover is a recombination operator that can be applied to three or more parents and that can be
seen as a generalization of one-point crossover.
For k parent chromosomes, one randomly chooses k -1 distinct cut points in
{1 ,...,L-I}, where L is the length of the chromosomes. For i = 2,..., k the i th section (between the (i-l and
the i th cut point, where the kth cut point is the end of the chromosomes) is then shifted cyclically (i-l)
steps across the k chromosomes.
Diagonal crossover is said to lead to a very good exploration of the search space, especially for a large number
of parents (around 10—15)
Multi-parent

Fig. 12.20 Example of diagonal crossover

Ashok Kumar Pant I MIT 554 | TU | 2024 14

 1. Distinguish between RNN and Transformer. Describe the architectures of
Transformer.

ecurrent Neural Networks (RNNs) and Transformers are two types of neural network architectures
used primarily for processing sequential data, such as language, time series, or any other data that
is naturally ordered. Here's a detailed distinction between them along with an explanation of the
Transformer architecture.

Recurrent Neural Networks (RNNs)

Characteristics:

1. Sequential Processing: RNNs process input sequences one element at a time. They
maintain a hidden state that captures information about previous elements in the sequence.
2. Hidden State: The hidden state is updated at each time step based on the current input and
the previous hidden state.
3. Temporal Dependencies: RNNs are designed to capture temporal dependencies in
sequences, making them suitable for tasks like language modeling, time series prediction,
and more.
4. Vanishing/Exploding Gradient Problems: RNNs can suffer from vanishing or exploding
gradient problems during training, making it difficult to learn long-range dependencies.

Architecture:

• Input Layer: Takes the input sequence one element at a time.

• Hidden Layer: Contains recurrent connections that update the hidden state.
• Output Layer: Produces the output sequence or a single output based on the task.

Transformer Architecture

Transformers were introduced in the paper "Attention is All You Need" by Vaswani et al. in 2017.
They revolutionized the field of natural language processing by addressing some of the limitations
of RNNs.

Characteristics:

1. Parallel Processing: Unlike RNNs, Transformers process the entire input sequence
simultaneously, allowing for more efficient computation and training.
2. Attention Mechanism: Transformers rely on self-attention mechanisms to weigh the
importance of different elements in the input sequence, enabling them to capture long-
range dependencies more effectively.
3. No Recurrent Connections: Transformers do not use recurrent connections, thus avoiding
issues related to vanishing and exploding gradients.
4. Scalability: They are highly scalable and have been shown to perform exceptionally well
on a variety of tasks, including language translation, text generation, and more.

1|Page
Architecture:

Encoder-Decoder Structure:

• Encoder: Consists of a stack of identical layers (typically 6 to 12 layers).

o Input Embedding: Converts input tokens into dense vectors.
o Positional Encoding: Adds positional information to the embeddings since the
model processes all tokens simultaneously.
o Multi-Head Self-Attention: Computes self-attention scores for each token with
respect to all other tokens, allowing the model to focus on different parts of the
input sequence.
o Feed-Forward Neural Network (FFN): Applies a point-wise feed-forward
network to each position separately.
o Layer Normalization and Residual Connections: Each sub-layer is followed by
layer normalization and a residual connection to facilitate training.
• Decoder: Similar to the encoder, but with additional mechanisms to handle the output
generation.
o Masked Multi-Head Self-Attention: Prevents attending to future tokens, ensuring
the model generates outputs sequentially during inference.
o Encoder-Decoder Attention: Allows the decoder to attend to the encoder's output,
enabling it to incorporate information from the input sequence.

Key Components:

• Multi-Head Attention: Allows the model to jointly attend to information from different
representation subspaces.
o Scaled Dot-Product Attention: Computes the attention scores using the queries,
keys, and values.
o Concatenation and Linear Transformation: Combines the outputs from multiple
attention heads and projects them back into the original dimension.
• Position-wise Feed-Forward Networks: Apply two linear transformations with a ReLU
activation in between.
• Positional Encoding: Adds information about the relative or absolute position of tokens
in the sequence.

Attention Mechanism:

• Self-Attention: For each token in the input sequence, computes a weighted sum of all other
tokens, allowing the model to focus on different parts of the sequence.
• Scaled Dot-Product Attention Formula:

2|Page
 2. Explain about any two selection approaches in evolutionary algorithm. Discuss about
the significance of PSO in social network structure.

Selection in EAs mimics natural selection, where individuals with better fitness are more likely to
reproduce and pass their traits (solutions) to the next generation. Here are two common
approaches:

1. Roulette Wheel Selection: This approach assigns a probability of selection to each

individual based on its fitness. Individuals with higher fitness have a larger "slice" of the
metaphorical roulette wheel, increasing their chance of being selected. This method is
simple to implement but can be susceptible to getting stuck in local optima, favoring
already good solutions and hindering exploration of diverse options.

Selection in EAs mimics natural selection, where individuals with better fitness are more likely to
reproduce and pass their traits (solutions) to the next generation. Here are two common
approaches:

1. Roulette Wheel Selection: This approach assigns a probability of selection to each

individual based on its fitness. Individuals with higher fitness have a larger "slice" of the
metaphorical roulette wheel, increasing their chance of being selected. This method is
simple to implement but can be susceptible to getting stuck in local optima, favoring
already good solutions and hindering exploration of diverse options.
2. Tournament Selection: Here, a small group of individuals (typically 2-5) compete in a
"tournament." The fittest individual from the group is selected for reproduction. This
approach balances exploration and exploitation. It allows for good solutions to be selected
while also introducing some randomness to prevent premature convergence. Variations
like elitism can guarantee the fittest individual survives to the next generation.

Significance of PSO in Social Network Structure

Particle Swarm Optimization (PSO) is a swarm intelligence technique inspired by the collective
behavior of flocks of birds or schools of fish. It can be a valuable tool for analyzing and optimizing
social network structures due to the following reasons:

• Community Detection: PSO can be used to identify communities within a social network.
Particles can represent potential communities, and their fitness can be evaluated based on
metrics like modularity (density of connections within communities compared to between

3|Page
 them). By iteratively updating positions based on successful communities, PSO can
efficiently locate clusters of densely connected nodes.
• Influence Maximization: In social networks, identifying influential nodes is crucial for
marketing or spreading information. PSO can be adapted to find these influential nodes.
Particles represent seed sets (initial nodes for information diffusion), and their fitness can
be based on the number of nodes eventually reached through information propagation. PSO
helps identify the most influential nodes to maximize the spread of information.
• Network Optimization: PSO can be used to optimize network properties like path lengths
between nodes or network diameter (longest distance between any two nodes). By
adjusting connection strengths or network topology based on particle fitness, PSO can help
create efficient information flow or reduce communication overhead in social networks.

2. Tournament Selection: Here, a small group of individuals (typically 2-5) compete in a

"tournament." The fittest individual from the group is selected for reproduction. This
approach balances exploration and exploitation. It allows for good solutions to be selected
while also introducing some randomness to prevent premature convergence. Variations
like elitism can guarantee the fittest individual survives to the next generation.

Principle:

• A subset of individuals is randomly chosen from the population, and the fittest individual
from this subset is selected.

Steps:

1. Randomly select a predefined number of individuals (the tournament size) from the
population.
2. Determine the individual with the highest fitness in this subset.
3. Repeat the process until the desired number of individuals is selected.

Advantages:

• Can be tuned by adjusting the tournament size, balancing between selection pressure and
diversity.
• More robust against individuals with extremely high fitness values dominating the
population.

Disadvantages:

• Selection bias can be introduced if the tournament size is not properly chosen.
• Can be computationally expensive if the tournament size is large.

4|Page
Significance of PSO in Social Network Structure

Particle Swarm Optimization (PSO) is a swarm intelligence technique inspired by the collective
behavior of flocks of birds or schools of fish. It can be a valuable tool for analyzing and optimizing
social network structures due to the following reasons:

• Community Detection: PSO can be used to identify communities within a social network.
Particles can represent potential communities, and their fitness can be evaluated based on
metrics like modularity (density of connections within communities compared to between
them). By iteratively updating positions based on successful communities, PSO can
efficiently locate clusters of densely connected nodes.
• Influence Maximization: In social networks, identifying influential nodes is crucial for
marketing or spreading information. PSO can be adapted to find these influential nodes.
Particles represent seed sets (initial nodes for information diffusion), and their fitness can
be based on the number of nodes eventually reached through information propagation. PSO
helps identify the most influential nodes to maximize the spread of information.
• Network Optimization: PSO can be used to optimize network properties like path lengths
between nodes or network diameter (longest distance between any two nodes). By
adjusting connection strengths or network topology based on particle fitness, PSO can help
create efficient information flow or reduce communication overhead in social networks.

3. State decomposition theory. Illustrate the different operations in Fuzzy sets

with examples. Differentiate between batch learning and online learning.

State decomposition theory is a concept not typically used in machine learning or artificial
intelligence. It's more commonly found in control theory, particularly optimal control. Here, the
theory deals with decomposing a complex system into simpler subsystems or states. This allows
for easier analysis and design of control strategies.

For instance, imagine a robot arm with multiple joints. State decomposition theory would break
down the arm's movement into individual joint states (angles, velocities). This simplifies control
by focusing on manipulating each joint independently to achieve the desired overall motion.

2. Fuzzy Set Operations:

Fuzzy set theory deals with sets where elements have a degree of membership, ranging from 0
(completely not belonging) to 1 (completely belonging). Unlike crisp sets where membership is
binary (in or out), fuzzy sets allow for vagueness and partial membership. Here are some common
operations on fuzzy sets with examples:

• Union (OR): This represents elements belonging to either set A or set B, or both. Example:
If "Tall" is a fuzzy set for heights, the union of "Tall" and "Average" might include people
of height 1.70m to 1.90m with varying degrees of membership depending on their specific
height.

5|Page
 • Intersection (AND): This represents elements belonging to both set A and set B. Example:
The intersection of "Young" (age 18-30) and "Experienced" (work experience > 5 years)
might include people aged 25-30 with high membership and younger/older people with
lower membership depending on their experience.
• Complement (NOT): This represents elements not belonging to set A. Example: The
complement of "Cold" (temperatures below 15°C) would be "Warm or Hot" with varying
degrees of membership depending on the specific temperature.

3. Batch Learning vs. Online Learning:

These terms refer to different training paradigms for machine learning models:

• Batch Learning: In batch learning, the entire training dataset is used to update the model's
parameters in one go. This is common for tasks where data is readily available upfront.
Batch learning can be computationally expensive for large datasets but can lead to good
model performance.
• Online Learning: Here, the model is updated incrementally as it receives new data points
one at a time. This is useful for real-time applications where data is constantly streaming
in. While online learning can adapt quickly to changing data, it may not achieve the same
level of accuracy as batch learning on the entire dataset.

4. How Fuzzy c-Means can be applied in clustering? Explain.

Fuzzy c-means (FCM), also known as fuzzy C-means clustering, is a soft clustering technique used
to group data points belonging to multiple clusters with varying degrees of membership. This

6|Page
differs from traditional k-means clustering, which assigns each data point to a single, exclusive
cluster.

Here's how Fuzzy c-Means is applied in clustering:

1. Data Preprocessing (Optional): As with many algorithms, data cleaning and

normalization might be necessary to ensure features are on a similar scale and improve
clustering effectiveness.
2. Defining the Number of Clusters (c): You need to specify the desired number of clusters
the data will be divided into. This can be informed by domain knowledge or using
techniques like the elbow method to identify an optimal number of clusters based on
within-cluster variance.
3. Initialization:
o Assign an initial membership degree for each data point belonging to each cluster
(typically random values between 0 and 1). These values represent the probability
of a data point belonging to a particular cluster.
o Define the fuzziness parameter (m), typically between 1.25 and 2. This parameter
controls the fuzziness of the clusters. Higher values lead to fuzzier clusters with
more data points having partial membership in multiple clusters.
4. Iterative Loop:
o Calculate Cluster Centers (centroids): For each cluster, compute the centroid
(mean) based on the data points and their current membership degrees.
o Update Membership Degrees: For each data point, recalculate its membership
degree for each cluster based on its distance to the cluster centroids and the
fuzziness parameter (m). Data points closer to a centroid will have higher
membership degrees in that cluster.
o Termination Condition: The loop continues until a stopping criterion is met. This
can be when the membership degrees stabilize (minimal change between iterations)
or a predefined maximum number of iterations is reached.
5. Result: Each data point belongs to all clusters with a specific degree of membership,
providing a richer representation of the data compared to crisp k-means clustering.

Applications of Fuzzy c-Means:

• Customer segmentation: Fuzzy c-means can be used to segment customers based on their
purchase history or demographics, identifying groups with varying degrees of overlap (e.g.,
customers who sometimes buy both budget and premium products).
• Image segmentation: By clustering image pixels based on color or intensity, fuzzy c-
means can help identify objects with fuzzy boundaries in images.
• Medical diagnosis: Fuzzy c-means can be used to analyze patient data and identify groups
with varying risk factors for a disease.

5. Describe about Hamming cliffs in encoding of solution candidates.

7|Page
Hamming cliffs are a challenge encountered in using binary encoding for solution candidates in
optimization algorithms, particularly Genetic Algorithms (GAs). Here's how they arise:

• Binary Encoding: In GAs, solution candidates are often represented as binary strings. For
example, a solution with 3 variables (each taking values 0 or 1) would be encoded as a
string of 3 bits (e.g., "010").
• Hamming Distance: The Hamming distance between two binary strings is the number of
bit positions where they differ. For instance, the Hamming distance between "010" and
"100" is 2 (differ at the first and second bits).
• The Cliff Analogy: Imagine solutions as points on a landscape, with similar solutions
being closer together. In binary encoding, adjacent integer values can have large Hamming
distances. For example, the binary representations of 7 and 8 ("0111" and "1000") differ at
all 4 bits, even though their numerical difference is just 1. This creates a "cliff" where a
small mutation (flipping a single bit) in the binary string can cause a large jump in the
solution space.

Problems with Hamming Cliffs:

• Hinders Exploration: Genetic algorithms rely on mutation and crossover operators to

explore the solution space. Hamming cliffs make it difficult for these operators to find
better solutions. A mutation might only flip one bit, but due to the cliff, it might land in a
completely different region of the search space, potentially leading the algorithm away
from promising areas.
• Slow Convergence: Since small mutations can cause large jumps, it can take many
iterations for the GA to converge on an optimal solution. The algorithm might get stuck
bouncing around on one side of the cliff, unable to find a path to better solutions on the
other side.

Mitigating Hamming Cliffs:

• Gray Coding: An alternative encoding scheme called Gray coding can be used. Here,
adjacent integer values differ by only one bit. This eliminates Hamming cliffs and allows
mutations to explore neighboring solutions more effectively.
• Real-Valued Encoding: For problems with continuous solution spaces, using real-valued
encoding instead of binary can eliminate Hamming cliffs altogether. However, this
introduces other challenges like defining appropriate mutation and crossover operators for
real-valued representations.

6. How PSO can be implemented on multi - start fashion? Explain.

Particle Swarm Optimization (PSO) is a powerful optimization technique, but it can get stuck in
local optima, especially for complex problems. Multi-start PSO addresses this by running the
algorithm multiple times with different initial positions for the particles. Here's how it works:

8|Page
Standard PSO:

1. Initialization: Define the swarm size (number of particles), search space, and fitness
function. Initialize each particle with a random position and velocity in the search space.
2. Iteration Loop:
o Evaluate the fitness of each particle using the fitness function.
o Update each particle's personal best position (pbest) based on its current position
and the best position it has seen so far.
o Identify the global best position (gbest) from all particles' pbest positions.
o Update each particle's velocity based on its current velocity, its pbest, and gbest.
o Update each particle's position based on its new velocity.
3. Termination: The loop continues until a stopping criterion is met (e.g., maximum
iterations reached, convergence achieved).

Multi-Start PSO:

1. Run Standard PSO Multiple Times: Repeat the entire standard PSO process
(initialization, iteration loop, termination) multiple times. Each run starts with a completely
new set of randomly initialized particles in the search space.
2. Final Result: After running PSO multiple times, select the best solution found across all
runs based on the highest fitness value. This provides a higher chance of escaping local
optima and finding a better solution compared to a single run.

Benefits of Multi-Start PSO:

• Improved Exploration: By starting from different random positions, the algorithm

explores a wider range of the search space, increasing the likelihood of finding the global
optimum.
• Reduced Risk of Local Optima: Since each run starts fresh, multi-start PSO is less likely
to get trapped in suboptimal solutions.

Challenges of Multi-Start PSO:

• Increased Computation Cost: Running PSO multiple times requires more computational
resources compared to a single run.
• Tuning the Number of Starts: There's no one-size-fits-all answer for the optimal number
of restarts. Too few restarts might not provide enough exploration, while too many can be
computationally expensive.

Implementation Tips:

• Utilize parallelization techniques if possible to run multiple PSO instances concurrently

and reduce overall execution time.
• Consider adaptive approaches where the number of restarts can be adjusted based on the
problem complexity or convergence behavior observed in initial runs.

9|Page
 7. Discuss about attention mechanism in encoder – decoder.

The attention mechanism is a powerful technique used in encoder-decoder models for tasks like
machine translation and text summarization. It allows the decoder to selectively focus on relevant
parts of the input sequence encoded by the encoder, leading to more accurate and informative
outputs.

Here's a breakdown of how the attention mechanism works in an encoder-decoder architecture:

1. Encoder-Decoder Structure:

• Encoder: The encoder processes the input sequence (e.g., a sentence in machine
translation). It typically uses a recurrent neural network (RNN) or a Transformer to
generate a context vector that captures the meaning of the entire input sequence.
• Decoder: The decoder generates the output sequence one step at a time (e.g., the translated
sentence). It uses the context vector from the encoder along with the previously generated
outputs to predict the next element in the output sequence.

2. Attention Mechanism:

Here's where the magic happens:

• At each step of the decoder, the attention mechanism computes an attention score for each
element (hidden state) in the encoder's output. This score indicates how relevant each
encoder element is to predicting the current element in the output sequence.
• The attention scores are calculated based on the decoder's current hidden state and the
encoder's hidden states. Different scoring functions can be used, but they typically involve
a dot product or a compatibility function between these states.
• The attention scores are then normalized (often using softmax) to create an attention
weight for each encoder element. These weights represent the relative importance of each
encoder element in the current context.
• Finally, the decoder uses these attention weights to create a context vector specifically
tailored for the current output element. This context vector is a weighted sum of the
encoder's hidden states, where the weights are the attention weights.
• The decoder then combines this context vector with its current hidden state and potentially
the previously generated output to predict the next element in the output sequence.

Benefits of Attention Mechanism:

• Focus on Relevant Information: The attention mechanism allows the decoder to focus on
the most relevant parts of the input sequence for each output element. This is particularly
beneficial for long sequences where not all parts are equally important for generating the
output.

10 | P a g e
 • Improved Accuracy: By attending to the most relevant information, the attention
mechanism helps the model generate more accurate and informative outputs.
• Long Sequence Handling: The attention mechanism allows the model to effectively
handle long sequences by focusing on relevant parts instead of relying solely on the
potentially limited capacity of the encoder's final hidden state.

8. Define velocity clamping. Discuss how artificial immune system is inspired

with biological immune system.

Velocity clamping is a technique used in optimization algorithms, particularly those employing

particle swarm optimization (PSO). It limits the maximum velocity a particle can have in the search
space.

Why use velocity clamping?

• Prevent Out-of-Bounds: Without clamping, particles could have very large velocities,
causing them to fly past optimal regions or even outside the defined search space
altogether. This can lead to wasted computations and potential instability in the algorithm.
• Control Search Granularity: Clamping allows you to control the exploration vs.
exploitation trade-off. Lower clamping values restrict particle movement, promoting
exploitation of promising areas. Higher clamping values allow for larger jumps,
encouraging exploration of the search space.

How does velocity clamping work?

1. Define Maximum Velocity: A threshold value for the maximum allowed velocity is set
for each dimension of the search space.
2. Clipping the Velocity: After calculating the velocity update based on the standard PSO
formula, each component of the velocity vector is compared to the maximum velocity
threshold.
3. Clamping: If any component exceeds the threshold, it's clipped to the threshold value. This
ensures the particle's movement stays within the desired bounds.

Benefits of velocity clamping:

• Improved Stability: Clamping prevents particles from escaping the search space, leading
to more stable and predictable behavior of the algorithm.
• Targeted Search: By controlling the exploration-exploitation balance, clamping can help
the algorithm focus on promising areas more effectively.

2. Artificial Immune Systems (AIS) Inspired by Biological Immune System

The biological immune system is a complex network of cells and organs that defends the body
against pathogens like bacteria and viruses. Artificial immune systems (AIS) draw inspiration from

11 | P a g e
this biological counterpart to create computational algorithms for solving various optimization and
pattern recognition problems.

Here are some key aspects of the biological immune system that inspire AIS:

• Diversity: The immune system maintains a diverse population of immune cells, each with
specific recognition capabilities. Similarly, AIS often use diverse populations of candidate
solutions to explore the search space effectively.
• Learning and Memory: The immune system learns from past encounters with pathogens,
developing memory to respond more effectively to future threats. AIS can incorporate
learning mechanisms to improve their performance over time based on past successes and
failures.
• Self/Non-Self Recognition: The immune system can differentiate between the body's own
cells (self) and foreign invaders (non-self). AIS can be designed to identify "healthy" or
optimal solutions within a search space and eliminate or adapt "unhealthy" solutions.
• Antibody Selection: The immune system selects and amplifies effective antibodies
(proteins that bind to pathogens) during an immune response. AIS can use selection
mechanisms to favor promising candidate solutions based on their fitness in the problem
domain.

Applications of AIS:

• Anomaly Detection: AIS can be used to identify abnormal patterns in data, mimicking the
immune system's ability to detect foreign invaders.
• Fault Diagnosis: AIS can be applied to diagnose faults in systems by learning patterns
associated with normal and faulty behavior.
• Optimization Problems: AIS can be used for various optimization tasks, such as
scheduling, resource allocation, and data clustering, by drawing inspiration from the
immune system's ability to find optimal solutions.

9. Describe the back propagation algorithm.

Backpropagation is an algorithm used to train artificial neural networks, especially feed-forward

neural networks. It's an iterative process that efficiently calculates the gradient of a loss function
with respect to the weights and biases of the network. This gradient information is then used to
update these weights and biases in a way that minimizes the loss function, leading the network to
learn and improve its performance.

Here's a breakdown of the backpropagation algorithm:

1. Forward Pass:

• The input data is fed into the network layer by layer.

• Each neuron in a layer applies an activation function (e.g., sigmoid, ReLU) to the weighted
sum of its inputs to generate its output.
• This process continues until the final output layer is reached.

12 | P a g e
2. Loss Calculation:

• The network's output is compared to the desired target output (ground truth) using a loss
function (e.g., mean squared error, cross-entropy).
• The loss function quantifies the difference between the predicted and actual outputs.

3. Backward Pass:

• This is the core of backpropagation. We calculate the error gradients for each neuron,
starting from the output layer and propagating them backward layer by layer.
• For the output layer, the error gradient is simply the derivative of the loss function with
respect to the output neurons' activations.
• For hidden layers, the error gradient is calculated by considering how the layer's activation
contributed to the overall error in the output layer, taking into account the weights
connecting it to the previous layer.

4. Weight and Bias Update:

• Using the calculated error gradients, the weights and biases of each neuron are updated
using an optimization algorithm like gradient descent.
• The update typically involves subtracting a learning rate multiplied by the error gradient
from the current weight or bias value. The learning rate controls the step size of these
updates.

5. Repeat:

• Steps 1-4 are repeated for multiple iterations (epochs) with different training data
examples.
• With each iteration, the network adjusts its weights and biases, gradually minimizing the
loss function and improving its performance on the training data.

Benefits of Backpropagation:

• Efficiently trains complex neural networks

• Allows for learning non-linear relationships in data
• Applicable to various tasks like image recognition, speech processing, and natural language
processing

Challenges of Backpropagation:

• Can be computationally expensive for large networks

• Prone to vanishing or exploding gradients, hindering learning in deep networks
• Requires careful selection of learning rate and network architecture to achieve optimal
performance.

13 | P a g e
 Unit 3
Fuzzy Logic

Fuzzy Set Theory is an extension of classical set theory, introduced by Lotfi Zadeh in 1965, to handle the
concept of partial truth, where the truth value may range between completely true and completely false. This
is particularly useful in dealing with real-world scenarios that involve uncertainty, vagueness, and
imprecision.

Fuzzy Sets:

●​ A fuzzy set is characterized by a membership function, which assigns to each element a grade of
membership ranging between 0 and 1.
●​ For a universe of discourse X, a fuzzy set A is defined as
A={(x,μA​(x))∣x∈X}
where μA​(x) is the membership function of x in A

Natural Language and Formal Models

Natural language refers to the languages humans use for everyday communication. It's characterized by its
flexibility, ambiguity, and context-dependence.

Formal models are artificial languages with strict rules and syntax used to represent information in a clear and
unambiguous way.

The Relationship Between Natural Language and Formal Models:

●​ Bridging the Gap: One of the key challenges in computer science is bridging the gap between natural
language and formal models. This field is known as Natural Language Processing (NLP).
●​ NLP Applications: NLP techniques allow computers to understand and process natural language, enabling
applications like machine translation, chatbots, and sentiment analysis.
●​ Complementary Approaches: Natural language and formal models serve different purposes. Ideally, we can
leverage the strengths of both to create more sophisticated systems that can understand and communicate
with humans in a natural way.

Fuzzy Set
•​ Classical set theory allows the membership of the elements in the set in binary terms
•​ Fuzzy set theory permits membership function valued in the interval [0, 1]
•​ Example
•​ Words like tall, young, rich are fuzzy
•​ There is no quantitative value that define the term rich
•​ For some people millionaire is rich, and some people billionaire is rich
•​ In real world there exist much fuzzy knowledge
•​ Human thinking and reasoning frequently involves fuzzy information
•​ Like answering the question in examination, which are probably true

1
Fuzzy Set (Membership function)…
•​ The membership function fully defines the fuzzy set
•​ A membership function provides a measure of the degree of the similarity of an element to a
fuzzy set
•​ Each element in the universal set U has a degree of membership, which is a real number
between 0 and 1 (including 0 and 1), in a fuzzy set S
•​ The fuzzy set S is denoted by listing the elements with their degrees of membership
•​ elements with 0 degree of membership are not included
•​ elements with 1 degree of membership are fully included
•​ elements with 0 < degree of membership <1 are partially included
•​ Suppose that R is the set of rich people with R = {0.4 Alice, 0.8 Brian, 0.2 Fred, 0.9 Oscar, 0.7
Rita}.
•​ i.e Oscar is the richest person and Fred is the poorest person among these four people

•​ Formal Definition
•​ If X is universe of discourse and a is a particular element of X, then a fuzzy set
B defined on X and can be written as a collection of ordered pairs B =
{a,(a), aX}
•​ Example
•​ Universe of discourse → CSIT students of PMC
•​ G → set of good students
•​ B → set of bad students
•​ G = {(Ram, 0.9), (Hari, 0.7), (Sam, 0.4)}
•​ D = {(Ram, 0.1), (Hari, 0.3), (Sam, 0.6)}

2
Interpretation of Fuzzy Sets
•​ Fuzzy Sets for Modeling Similarity
•​ Compare the object under consideration with one that definitely belongs to the concept under
consideration (and possibly also with one that definitely does not belong to this concept)
•​ The similarity between two objects is higher, the smaller their distance
•​ Fuzzy Sets for Modeling Preference
•​ Membership degrees convey which values (or objects) should be preferred to others
•​ Fuzzy Sets for Modeling Possibility
•​ Possibility degrees represent a flexible restriction on what is the actual state with the following
convention: μ(u) = 0 means that u is rejected as impossible, μ(u) = 1 means that u is totally possible, and
the larger μ(u) is, the more plausible u is

Representations of Fuzzy Set

•​ Definition Based on Function
•​ Levels

Representations of Fuzzy Set…

•​ Definition Based on Function
•​ Fuzzy set μ is a real function taking values in
the unit interval and can be illustrated by
drawing its graph
•​ If X is universe of discourse and a is a
particular element of X, then a fuzzy set B
defined on X and can be
written as a collection of ordered pairs
B = {a,(a), aX}
•​ Usually fuzzy sets are used for modeling
expressions — sometimes also called
linguistic expressions in order to emphasize the relation to natural language, e.g., “about 3,” “of
middle height” or “very tall” which describe an imprecise value or an imprecise interval
•​ Fuzzy sets associated with such expressions should monotonically increase up to a certain value
and monotonically decrease from this value
•​ Such fuzzy sets are called convex

Extensions of Fuzzy Set Theory

•​ In classical fuzzy set theory a membership degree is expressed by
a real number in the unit interval
•​ However, in some applications experts prefer to use linguistic
expressions instead of numbers as membership degrees
•​ In this situation one can use membership degrees that are elements
of a general lattice L (L-Fuzzy Set)
•​ The extension of fuzzy sets from the unit interval [0, 1] to a
general lattice L and the operations can be easily defined as
follows
•​ An L-fuzzy set on the universe X is a mapping μ : X → L. The
operations on the class FL(X) of L-fuzzy sets are defined point
wise by setting

3
Fuzzy Logic
•​ Include all applications and theories where fuzzy sets or concepts are involved
•​ Focuses on the field of approximate reasoning where fuzzy sets are used and propagated within an
inference mechanism as it is for instance common in expert systems

Proposition and Truth values

•​ Classical​ propositional​ logic​ deals​ with​ the​ formal​handling​ of statements
(propositions) to which one of the two truth values 1 (for true) or 0 (for false) can be assigned
•​ Typical propositions, for which the formal symbols ϕ1 and ϕ2 may stand are
•​ ϕ1 : Four is an even number.
•​ ϕ2 : 2 + 5 = 9.

•​ The assumption that a statement is either true or false is suitable for mathematical issues
•​ But for many expressions formulated in natural language such a strict separation between true and false
statements would be unrealistic
•​ If somebody promises to come to an appointment at 5 o’clock, his statement would have been false, if he
came one minute later
•​ Nobody would call him a liar, although, strictly speaking, his statement was not true
•​ Even more complicated is the statement of being at a party at about 5
•​ The greater the difference between the arrival and 5 o’clock the “less true” the statement is
•​ A sharp definition of an interval of time corresponding to “about 5” is impossible
•​ Humans are able to formulate such “fuzzy” statements, understand them, draw conclusions from them
and work with them
•​ If someone starts an approximately four-hour-drive at around 11 o’clock and is going to have lunch for
about half an hour, we can use these imprecise pieces of information and conclude at what time more or
less the person will arrive
•​ A formalization of this simple issue in a logical calculus, where statements can be either true or false
only, is not adequate

4
 t-Norm operator
•​ Triangular Norm
•​ Is a binary operation on the unit interval [0, 1], a function T: [0, 1]  [0, 1]  [0, 1], such that
for all a, b, c  [0, 1], the following four axioms are satisfied
•​ T1 : T(a, b) = T(b, a)  Commutative Property
•​ T2 : T(a, T(b, c)) = T(T(a, b), c)  Associativity Property
•​ T3 : T(a, 1) = a  Boundary Condition
•​ T4 : T(a, a) = a Idempotency
•​ T5 : T(a, b)  T(a, c) whenever b  c  Monotonicity Property, where a, b and c are
membership functions
1.​ Minimum
▪​ Tmin(A(x),  B(x)) = min ( A(x),  B(x)) =  A(x)  B(x)
2.​ Algebraic Product
▪​ Tap(A(x),  B(x)) =  A(x)  B(x)
3.​ Bounded Product
▪​ Tbp(A(x),  B(x)) = MAX(0, ( A(x) +  B(x) – 1))
4.​ Drastic Product


•​ Example
•​ A = {(a, 0.7), (b, 0.5), (c, 0.1), (d, 0.6)}
•​ B = {(b, 0.8), (c, 0.3)}

t-conorm operator
•​ Triangular conorm
•​ Is a binary operation on the unit interval [0, 1], a function T: [0, 1]  [0, 1]  [0, 1], such that
for all a, b, c  [0, 1], the following four axioms are satisfied
•​ T1 : T(a, b) = T(b, a)  Commutative Property
•​ T2 : T(a, T(b, c)) = T(T(a, b), c)  Associativity Property
•​ T3 : T(a, 0) = a  Boundary Condition
•​ T4 : T(a, b)  T(a, c) whenever b  c  Monotonicity Property, where a, b and c are
membership functions
1.​ Standard Union (Maximum)
▪​ Tmax(A(x),  B(x)) = max ( A(x),  B(x)) =  A(x)  B(x)
2.​ Algebraic Sum
▪​ Tas(A(x),  B(x)) =  A(x) +  B(x) -  A(x)  B(x)
3.​ Bounded Sum
▪​ Tbs(A(x),  B(x)) = MIN(1, ( A(x) +  B(x) ))
4.​ Drastic Union

5
 

Fuzzy Set Operations

•​ Union
•​ The union of two fuzzy sets S and T is the fuzzy set S T, where the degree of membership
of an element in S T is the maximum of the degrees of membership of this element in S and in
T
•​ ST(x) = max(S(x),T(x))
•​ Intersection
•​ The intersection of two fuzzy sets S and T is the fuzzy set S ∩ T, where the degree of
membership of an element in S ∩ T is the minimum of the degrees of membership of this element
in S and in T
•​ ST(x) = min(S(x),T(x))
•​ Complement
•​ The complement of a fuzzy set S is the set S, with the degree of the membership of an element
in S equal to 1 minus the degree of membership of this element in S • S(x) = 1 -S(x)

•​ Example (Intersection)

6
Exercise
•​ Let,
•​ Set of Rich People (R) = {0.4 Alice, 0.8 Brian, 0.2 Fred, 0.9 Oscar, 0.7 Rita}
•​ Set of Famous People (F) = {0.6 Alice, 0.9 Brian, 0.4 Fred, 0.1 Oscar, 0.5 Rita}
•​ Find the fuzzy set F R of rich or famous people
•​ Find the fuzzy set F ∩ R of rich and famous people
•​ Find Fc (the fuzzy set of people who are not famous) and Rc (the fuzzy set of people who are not
rich)
Linguistic modifiers, also known as hedges, are a powerful tool in fuzzy set theory that allow you to add
shades of meaning and nuance to membership functions. They essentially modify the shape and behavior of
the membership function, enabling you to represent concepts with even greater precision and flexibility.
Alpha Cuts
Alpha cuts, also known as α\alphaα-levels or α\alphaα-level sets, are a fundamental concept in fuzzy set
theory. They provide a way to convert a fuzzy set into a family of crisp sets, facilitating analysis and
operations on fuzzy sets.
Definition
An α\alphaα-cut of a fuzzy set A is a crisp set that contains all the elements of the universe of discourse X
whose membership degrees in A are greater than or equal to a specified threshold α\alphaα. Formally, for a
fuzzy set A with membership function μA(x), Aα​is defined as:
Aα={x∈X∣μA(x)≥α}
where α∈[0,1]
Types of Alpha Cuts
1.​ Strong α-cut:
o​ Includes only those elements whose membership degree is strictly greater than α\alphaα.
o​ Formally, the strong α-cut, Aα+​is defined as: Aα+​={x∈X∣μA​(x)>α}
2.​ Standard α\alphaα-cut:
o​ Includes elements whose membership degree is greater than or equal to α
o​ As defined earlier: Aα={x∈X∣μA(x)≥α}

7
Decomposition of a Fuzzy Set
•​ Decomposition theory delves into ways to break down complex fuzzy sets into simpler ones. This can be
helpful for analyzing and understanding intricate concepts represented by fuzzy sets
•​ The representation of an arbitrary fuzzy set A in terms of the special fuzzy set αA, which are defined in
terms of the α-cuts of A by 𝛼𝐴(𝑥) =
𝛼. 𝛼𝐴(𝑥)
•​ Referred as a decomposition of the fuzzy set A
•​ Example
•​ X = {a, b, c, d, e}
•​ Fuzzy Set (A) = {(a, 0.2), (b, 0.4), (c, 0.6), (d, 0.8), (e, 1)}

The Extension Principle:

The extension principle is a fundamental concept in fuzzy logic that establishes a connection between fuzzy sets and
classical set-theoretic operations. It essentially allows us to "map" functions between fuzzy sets and level sets.

Here's the core idea:

●​ Level Sets: Recall that alpha cuts create crisp sets (level sets) from a fuzzy set by selecting elements with a
membership degree greater than or equal to a specific alpha level.

●​ Mapping Functions: The extension principle tells us how to apply a function (e.g., addition, multiplication) to
fuzzy sets. It does this by working with their corresponding level sets.

Fuzzy Relations
Fuzzy relations extend the concept of fuzzy sets to represent relationships between elements in different sets. They
provide a powerful tool for modeling situations where the connections between elements are imprecise or have
varying degrees of strength.

Fuzzy Relation and Propositions:

Fuzzy relations can be used to express propositions about relationships between elements. Here's how:

●​ Fuzzy Statements: Instead of a binary "related" or "not related," we can use fuzzy statements like "Alice is
very good at Math" or "Bob is somewhat interested in History."

●​ Membership Functions: These statements can be translated into fuzzy relations using membership functions.
The function would assign a degree of truth (between 0 and 1) to each proposition based on the underlying
relationship.

• Crisp Relation
Crisp relations are the traditional concept of relations used in classical set theory, where the relationship
between elements is either present or absent. In contrast to fuzzy relations, crisp relations do not allow for
partial membership; an element either belongs to the relation or it does not.

8
 •​ A fuzzy relation R is a mapping from the Cartesian space XY to the interval [0, 1], where the

strength of the mapping is expressed by the membership function of the relation 𝜇𝑅 𝑥, 𝑦

Example
•​ A = {(x1, 0.6), (x2, 0.2), (x3, 0.3)}
•​ B = {(y1, 0.7), (y2, 0.3), (y3, 0.4)}

•​ 𝜇𝑅 𝑥, 𝑦 = 𝜇𝐴×𝐵 𝑥, 𝑦 = min{𝜇𝐴 𝑥 , 𝜇𝐵(𝑦)}

Fuzzy Inference
•​ Together, the fuzzy sets and fuzzy rules form the knowledge base of a fuzzy rule-based reasoning system
•​ In addition to the knowledge base, a fuzzy reasoning system consists of three other components, each
performing a specific task

1.​ Fuzzification

9
 2.​ Inferencing
3.​ Deffuzification

1.​ Fuzzification:
o​ The process of converting real-valued inputs into fuzzy values (membership values).
o​ Real-valued inputs are mapped to fuzzy sets using membership functions.
o​ Example: If the input is temperature, it can be mapped to fuzzy sets like "cold," "warm," and "hot."
2.​ Fuzzy Inference:
o​ The process of formulating the mapping from a given input to an output using fuzzy logic operators,
fuzzy rules, and compositional rule of inference.
o​ Fuzzy rules are typically in the form of "IF-THEN" statements, where the conditions and conclusions
are expressed using fuzzy sets.
o​ Example: "IF temperature is hot THEN fan speed is high."
3.​ Defuzzification:
o​ The process of converting the fuzzy output back to a real-valued output.
o​ Various methods are used for defuzzification, such as the centroid method, bisector method, mean
of maxima, etc.
o​ Example: Converting the fuzzy set representing "fan speed" back to a specific numeric value.

Fuzzy logic for real valued inputs

Fuzzy logic is a form of many-valued logic that deals with reasoning that is approximate rather than fixed
and exact. Unlike traditional binary sets (where variables may only take on the values of 0 or 1), fuzzy logic
variables may have a truth value that ranges between 0 and 1, making it suitable for handling the concept of
partial truth. This capability makes fuzzy logic particularly useful for dealing with real-valued inputs.
Fuzzy Data Analysis
•​ Fuzzy Clustering (Illustration in Class)
•​ Fuzzy Classifier (Illustration in Class)

Fuzzy Clustering
Is a type of clustering algorithm in machine learning that allows a data point to belong to more than one
cluster with different degrees of membership
•​ Unlike traditional clustering algorithms, such as k-means or hierarchical clustering, which assign each
data point to a single cluster, fuzzy clustering assigns a membership degree between 0 and 1 for each
data point for each cluster
•​ FCM (Fuzzy c-Means) Algorithm

• Fuzzy c-Means
1.​ Initialize the data points into the desired number of clusters randomly
10
 𝑛
𝑚
∑ µ𝑖𝑘 ×𝑥𝑘
2.​ Find out the centroid 𝑉𝑖𝑗 = 𝑘=1
𝑛 where, m is fuzziness parameter
𝑚
∑ µ𝑖𝑘
𝑘=1

(2)
3.​ Find out the distance of each point from the centroid

−1
𝑛
⎰ 𝑑𝑘𝑖
2
⎱
( 1
𝑚−1 )
4.​ Updating membership values µ𝑘𝑖 = ⎛ ∑ ⎞
𝑗=1
⎱ 𝑑𝑘𝑗2 ⎰
⎝ ⎠
5.​ Repeat the steps(2-4) until the constant values are obtained for the membership values or
the difference is less than the tolerance value
6.​ Defuzzify the obtained membership values

Fuzzy k-Nearest Neighbors (FKNN) is a classification technique that uses fuzzy logic to handle messy data.
It builds on the k-Nearest Neighbors (k-NN) idea but allows for data points to belong to multiple classes
with varying degrees of membership. This makes FKNN useful for situations where data is imprecise or has
fuzzy boundaries between classes.

Fuzzy Measure
•​ Consider a finite set X = {x1, x2, . . . , xn}
•​ Each xi can be a diagnostic test, a feature (e.g., color, texture, or shape) in a segmentation problem, a
particular​ pattern​recognition algorithm, and so on
•​ Let 2X denote the power set of X, that is, the set of all (crisp) subsets of X
•​ A fuzzy measure, g, is a real-valued function g : 2X → [0, 1], satisfying the following properties
1.​ g(φ) = 0 and g(X) = 1
2.​ g(A) ≤ g(B), if A ⊆ B

11
 Chapter 5
Defuzzification Methods
Fuzzy rule based systems evaluate linguistic if-then rules using fuzzification, inference and composition
procedures. They produce fuzzy results which usually have to be converted into crisp output. To
transform the fuzzy results in to crisp, defuzzification is performed.

Defuzzification is the process of converting a fuzzified output into a single crisp value with respect to a
fuzzy set. The defuzzified value in FLC (Fuzzy Logic Controller) represents the action to be taken in
controlling the process.

Different Defuzzification Methods

The following are the known methods of defuzzification.
 Center of Sums Method (COS)
 Center of gravity (COG) / Centroid of Area (COA) Method
 Center of Area / Bisector of Area Method (BOA)
 Weighted Average Method
 Maxima Methods
o First of Maxima Method (FOM)
o Last of Maxima Method (LOM)
o Mean of Maxima Method (MOM)

Center of Sums (COS) Method

This is the most commonly used defuzzification technique. In this method, the overlapping area is
counted twice.
∗
The defuzzified value is defined as :

∑ . ∑
∗
= ∑ ∑
,

Here, n is the number of fuzzy sets, N is the number of fuzzy variables, μ is the
membership function for the k-th fuzzy set.

Example

1
©Debasis Samanta, Indian Institute of Technology Kharagpur
 ∗
The defuzzified value is defined as :

∗ ∑
= ∑
,

Here, represents the firing area of rules and k is the total number of rules fired and
represents the center of area.
The aggregated fuzzy set of two fuzzy sets and is shown in Figure 1. Let the area of this two
fuzzy sets are and .
= ½ * [(8-1) + (7-3)] * 0.5 = ½ * 11 * 0.5 = 55/20=2.75
= ½ * [(9-3) + (8-4)] * 0.3 = ½ * 10 * 0.3 = 3/2 =1.5
Now the center of area of the fuzzy set is let say = (7+3)/2= 5 and
the center of area of the fuzzy set is = (8+4)/2=6.
∗ . . . ∗ . ∗
Now the defuzzified value = = = 22.75/4.25 = 5.35
. .

0.5
µ
0.4
A1
0.3

0.2
A2
0.1

0 1 2 3 4 5 6 7 8 9 x
∗

Figure 1 : Fuzzy sets and

Center of gravity (COG) / Centroid of Area (COA) Method

This method provides a crisp value based on the center of gravity of the fuzzy set. The total area
of the membership function distribution used to represent the combined control action is divided
into a number of sub-areas. The area and the center of gravity or centroid of each sub-area is
calculated and then the summation of all these sub-areas is taken to find the defuzzified value for
a discrete fuzzy set.

2
©Debasis Samanta, Indian Institute of Technology Kharagpur
 ∗
For discrete membership function, the defuzzified value denoted as using COG is defined as:

∗ ∑ .
= ∑
, Here indicates the sample element, μ is

the membership function, and n represents the number of elements in the sample.
∗
For continuous membership function, is defined as :

∗ µ
=
µ

µ 0.5

0.4 2
3
0.3

0.2

0.1 1 4 5

0 1 2 3 4 5 6 7 8 9 x

Figure 2 : Fuzzy sets C1 and C2

Example:
∗
The defuzzified value using COG is defined as:

∗ ∑
= ∑
, Here N indicates the number of sub-areas, and

represents the area and centroid of area, respectively, of sub-area.

In the aggregated fuzzy set as shown in figure 2. , the total area is divided into six sub-areas.
For COG method, we have to calculate the area and centroid of area of each sub-area.
These can be calculated as below.
The total area of the sub-area 1 is ½ * 2 * 0.5 = 0.5
The total area of the sub-area 2 is (7-3) * 0.5 = 4 * 0.5 = 2
The total area of the sub-area 3 is ½ * (7.5-7) * 0.2 = 0.5 * 0.5 *0.2 =.05
The total area of the sub-area 4 is 0.5* 0.3 = .15
The total area of the sub-area 5 is 0.5* 0.3 = .15
The total area of the sub-area 6 is ½ *1* 0.3 = .15
Now the centroid or center of gravity of these sub-areas can be calculated as

3
©Debasis Samanta, Indian Institute of Technology Kharagpur
 Centroid of sub-area1 will be (1+3+3)/3 = 7/3 =2.333
Centroid of sub-area2 will be (7+3)/2 = 10/2 = 5
Centroid of sub-area3 will be (7+7+7.5)/3 = 21.5/3 =7.166
Centroid of sub-area4 will be (7+7.5)/2 =14.5/2=7.25
Centroid of sub-are5 will be (7.5+8)/2 =15.5/2 = 7.75
Centroid of sub-area6 will be (8+8+9)/3 = 25/3 = 8.333
Now we can calculate . and is shown in table 1.

Table 1
Sub‐area number Area( ) Centroid of area( ) .
1 0.5 2.333 1.1665
2 02 5 10
3 .05 7.166 0.3583
4 .15 7.25 1.0875
5 .15 7.75 1.1625
6 .15 8.333 1.2499

∗
∑
The defuzzified value will be
∑

. . . . .
=
. . . . .

= (15.0247)/3 =5.008
∗
5.008

Center of Area / Bisector of Area Method (BOA)

This method calculates the position under the curve where the areas on both sides are equal.
The BOA generates the action that partitions the area into two regions with the same area.
∗
μ dx = ∗μ , where α = min {x| x ∈ X} and β = max {x| x ∈ X}

Weighted Average Method

This method is valid for fuzzy sets with symmetrical output membership functions and produces
results very close to the COA method. This method is less computationally intensive. Each
membership function is weighted by its maximum membership value. The defuzzified value is
defined as :

4
©Debasis Samanta, Indian Institute of Technology Kharagpur
 ∑µ .
∗
= ∑µ
Here ∑ denotes the algebraic summation and x is the element with maximum membership
function.

µ(x)

0.8

0.6

0.4

50 60 70 80 90 100 x

Figure 3: Fuzzy set A

Example:
Let A be a fuzzy set that tells about a student as shown in figure 3 and the elements with
corresponding maximum membership values are also given.
A = {(P, 0.6), (F, 0.4),(G, 0.2),(VG, 0.2), (E, 0)}
Here, the linguistic variable P represents a Pass student, F stands for a Fair student, G
represents a Good student, VG represents a Very Good student and E for an Excellent student.

Now the defuzzified value ∗ for set A will be

∗ ∗ . ∗ . ∗ . ∗ . ∗
=
. . . .
= 98/1.4=70

The defuzzified value for the fuzzy set A with weighted average method represents a Fair
student.

Maxima Methods

5
©Debasis Samanta, Indian Institute of Technology Kharagpur
 This method considers values with maximum membership. There are different maxima methods
with different conflict resolution strategies for multiple maxima.
o First of Maxima Method (FOM)
o Last of Maxima Method (LOM)
o Mean of Maxima Method (MOM)

 First of Maxima Method (FOM)

This method determines the smallest value of the domain with maximum membership value.
Example:

The defuzzified value ∗ of the given fuzzy set will be ∗ =4.

µ(x)

1.0

0.8

0.6

0.4

0.2

0 2 4 6 8 10 12 x

 Last of Maxima Method (LOM)

Determine the largest value of the domain with maximum membership value.

In the example given for FOM, the defuzzified value for LOM method will be ∗ = 8

 Mean of Maxima Method (MOM)

In this method, the defuzzified value is taken as the element with the highest membership values.
When there are more than one element having maximum membership values, the mean value of
the maxima is taken.
Let A be a fuzzy set with membership function µ (x) defined over x  X, where X is a universe of
∗
discourse. The defuzzified value is let say of a fuzzy set and is defined as,

6
©Debasis Samanta, Indian Institute of Technology Kharagpur
 ∑ 
∗
= ,
| |
Here, M = { | μ ( ) is equal to the height of the fuzzy set A} and |M| is the cardinality
of the set M.
Example
In the example as shown in Fig. , x = 4, 6, 8 have maximum membership values and hence
|M| = 3

∑ 
∗
According to MOM method, =
| |

Now the defuzzified value ∗ will be ∗

= = 6.

References:

1. N. Mogharreban and L. F. DiLalla “Comparison of Defuzzification Techniques for Analysis of Non-

interval Data”, IEEE, 06.

2. Jean J. Saade and Hassan B. Diab. “Defuzzification Methods and New Techniques for Fuzzy
Controllers”, Iranian Journal of Electrical and Computer Engineering, 2004.

3. Aarthi Chandramohan, M. V. C. Rao and M. Senthil Arumugam: “Two new and useful
defuzzification methods based on root mean square value”, Soft Computing, 2006.

4. Soft Computing by D.K. Pratihar, Narosa Publication.

7
©Debasis Samanta, Indian Institute of Technology Kharagpur