Soft Computing Notes
Soft Computing Notes
5. Unsupervised Learning....................................................................................45
6. Special Networks.............................................................................................81
9. Genetic Algorithm.........................................................................................173
ii
i
vi
Chapter 1: Introduction To Soft
Computing
Unit 1
1
INTRODUCTION TO SOFT COMPUTING
Unit Structure
1.0 Objectives
1.1 Computational Paradigm
1.1.1 Soft Computing v/s Hard Computing
1.2 Soft Computing
1.3 Premises of Soft Computing
1.4 Guidelines of Soft Computing
1.5 Uncertainty in AI
1.6 Application of Soft Computing
1.7 Summary
1.8 Review Questions
1.9 Bibliography, References and Further Reading
1.0 Objectives
In this chapter, we will try to learn what is soft computing, difference between
hard computing and soft computing and reason for why soft computing evolved.
At the end, some application of soft computing will be discussed.
1
SOFT COMPUTING TECHNIQUES
Computational paradigm is classified into two viz: Hard computing and soft
computing. Hard computing is the conventional computing. It is based on the
principles of precision, certainty, and inflexibility. It requires mathematical model
to solve problems. It deals withs the precise models. This model is further
classified into symbolic logic and reasoning, and traditional numerical modelling
and search methods. The basic of traditional artificial intelligence is utilised by
these methods. It consumes a lot of time to deal with real life problem which
contains imprecise and uncertain information. The following problems cannot
accommodate hard computing techniques:
1. Recognition problems
2. Mobile robot co-ordination, forecasting
3. Combinatorial problems
Soft computing deals with approximate models. This model is further classified
into two approximate reasoning, and functional optimization & random search
methods. It handles imprecise and uncertain information of the real world. It can
be used in all industries and business sectors to solve problems. Complex systems
can be designed with soft computing to deal with the incomplete information,
where the system behaviour is not completely known or the existence of measures
of variable is noisy.
2
Chapter 1: Introduction To Soft Computing
The main computing paradigm of soft computing are: Fuzzy systems, Neural
Networks and Genetic Algorithms.
Fuzzy set are for knowledge representation via fuzzy If – Then rules.
Neural network for learning and adaptivity and
Genetic algorithm for evolutionary computation.
3
SOFT COMPUTING TECHNIQUES
To achieve close resemblance with human like decision making, soft computing
aims to exploit the tolerance for approximation, uncertainty, imprecision, and
partial truth.
Approximation: the model has similar features but not same.
Uncertainty: the features of the model may not be same as that of the
entity/belief.
Imprecision: the model features (quantities) are not same as that the real
ones but are close to them.
1.5 Uncertainty of AI
4
Chapter 1: Introduction To Soft Computing
The logic controller then converts the sensor inputs into fuzzy variables that
are then defined according to these rules. Fuzzy logic techniques are used in
engine control, automatic transmissions, antiskid steering, etc.
5
SOFT COMPUTING TECHNIQUES
6
Chapter 1: Introduction To Soft Computing
1.7 Summary
In this chapter, we have learned that the soft computing is the partnership of
multiple techniques which helps to accomplish a particular task. The real-world
problem that contains uncertain and imprecise information can be solved using
soft computing techniques.
7
SOFT COMPUTING TECHNIQUES
Unit 1
2
TYPES OF SOFT COMPUTING
TECHNIQUES
Unit Structure
2.0 Objectives
2.1 Types of Soft Computing Techniques
2.2 Fuzzy Computing
2.3 Neural Computing
2.4 Genetics Algorithms
2.5 Associative Memory
2.6 Adaptive of Resonance Theory
2.7 Classification
2.8 Clustering
2.9 Probabilistic Reasoning
2.10 Bayesian Network
2.11 Summary
2.12 Review Questions
2.13 Bibliography, References and Further Reading
2.0 Objectives
The objective of this chapter is to give the overview of various soft computing
techniques.
8
Chapter 2: Types of Soft Computing
Techniques
3. Genetic Algorithms
4. Associative memory
5. Adaptive Resonance Theory
6. Classification
7. Clustering
8. Probabilistic Reasoning
9. Bayesian Network
All the above techniques are discussed in brief in the below sections.
The classical computing system involves two valued logic (true/false, 1/0,
yes/no). This system sometimes may not be able to answer some questions as
human does, as they do not have complete true answer. The computing system is
not just expected to give answers like human but also describe the reality level
calculated with the imprecision and uncertainty of the facts and rules applied.
Lofti Zadeh observed that the classical computing system was not capable to
handle subjective data representation or unclear human ideas. In 1965, he
introduced fuzzy set theory as the extension of classical set theory where
elements have degrees of memberships. It allows to determine the distinctions
among the data that is neither true nor false. It is like process of human thinking
like very hot, hot, warm, little warm, cold, too cold.
9
SOFT COMPUTING TECHNIQUES
10
Chapter 2: Types of Soft Computing
Techniques
11
SOFT COMPUTING TECHNIQUES
Artificial Neural Network (ANN) also known as neural network is the concept
inspired from human brain and the way the neurons in the human brain works. It
is computational learning system that uses a network of functions to understand
and translate a data input of one form into another form. It contains large number
of interconnected processing elements called as neuron. These neurons operate in
parallel and are configured. Every neuron is connected with other neurons by a
connection link. Each connection is associated with weights which contain
information about the input signal.
12
Chapter 2: Types of Soft Computing
Techniques
Genetic Algorithms initiated and developed in the early 1970’s by John Holland
are unorthodox search and optimization algorithms, which mimic some of the
process of natural evolution. Gas perform directed random search through a given
set of alternative with the aim of finding the best alternative with respect to the
given criteria of goodness. These criteria are required to be expressed in terms of
an object function which is usually referred to as a fitness function.
Biological Background:
All living organism consist of cell. In each cell, there is a set of chromosomes
which are strings of DNA and serves as a model of the organism. A chromosomes
consist of genes of blocks of DNA. Each gene encodes a particular pattern.
Basically, it can be said that each gene encodes a traits.
13
SOFT COMPUTING TECHNIQUES
14
Chapter 2: Types of Soft Computing
Techniques
The simplest artificial neural associative memory is the linear associator. The
other popular ANN models used as associative memories are Hopfield model and
Bidirectional Associative Memory (BAM) models.
15
SOFT COMPUTING TECHNIQUES
learning means that the network learns the significant patterns based on the inputs
only. There is no feedback. There is no external teacher that instructs the network
or tells which category a certain input belongs. The basic ART system is an
unsupervised learning model.
The model typically consists of:
a comparison field and a recognition field composed of neurons,
a vigilance parameter, and
a reset module.
Vigilance parameter:
It has considerable influence on the system memories:
o higher vigilance produces highly detailed memories,
o lower vigilance results in more general memories
Reset module:
After the input vector is classified, the Reset module compares the strength
of the recognition match with the vigilance parameter.
o If the vigilance threshold is met, then training commences.
o Else, the firing recognition neuron is inhibited until a new input
vector is applied.
16
Chapter 2: Types of Soft Computing
Techniques
Methods of Learning:
Slow learning method: here the degree of training of the recognition neuron’s
weights towards the input vector is calculated using differential equations and
is thus dependent on the length of time the input vector is presented.
Fast learning method: here the algebraic equations are used to calculate
degree of weight adjustments to be made, and binary values are used.
2.7 Classification
17
SOFT COMPUTING TECHNIQUES
Classification algorithms:
Logistic Regression
Naïve Bayes
K-Nearest Neighbour
Decision tree
Random Forest
Application of Classification:
Email Spam Detection
Speech Recognition
Identification of Cancer tumour cells
Biometric Identifications
2.8 Clustering
Clustering is type of unsupervised learning method. In this learning we draw
references from datasets consisting of input data without labelled responses.
Generally, it is used as a process to find meaningful structure, explanatory
underlying processes, generative features, and groupings inherent in a set of
examples.
Its task is to divide the population or data points into several groups. Data points
in the same group are similar to the other data point in the same group and
dissimilar to the data points in other groups.
Why Clustering?
Clustering determines the grouping among the unlabelled data present. There is
no criteria for a good clustering. It depends on the criteria that the user fits the
need of the user.
Clustering Methods:
Density-Based Methods
Hierarchical Based Methods
o Agglomerative (bottom up approach)
o Divisive (top down approach)
Partitioning Methods
Grid-based Methods
18
Chapter 2: Types of Soft Computing
Techniques
19
SOFT COMPUTING TECHNIQUES
Bayesian networks are a type of probabilistic graphical model that uses Bayesian
inference for probability computations. Bayesian networks aim to model
conditional dependence, and therefore causation, by representing conditional
dependence by edges in a directed graph. Through these relationships, one can
efficiently conduct inference on the random variables in the graph through the use
of factors.
Each node in the Bayesian network has condition probability distribution P(Xi
|Parent(Xi) ), which determines the effect of the parent on that node.
20
Chapter 2: Types of Soft Computing
Techniques
2.11 Summary
In this chapter we have learned different techniques used in soft computing.
Fuzzy system can be used when we want to deal with uncertainty and
imprecision. Adaptivity and learning abilities in the system can be build using
neural computing. To find the better solution to the problem, genetic algorithms
can be applied. The pattern can be retrieved from the memory based on the
content and not based on address is called associative memory. Find the input
patterns closest resemblances in the memory can also be done with the adaptive
resonance theory. Classification is based on supervised learning usually used for
predictions and clustering is based on unsupervised learning. Probabilistic
reasoning and Bayesian Networks are based on the probability of the event
occurring.
[Link]
Computing-CSE-TUBEpdf/
[Link]
[Link]
[Link]
_fuzzy_logic_systems.htm
21
SOFT COMPUTING TECHNIQUES
[Link]
[Link]
intelligence
[Link]
intelligence#:~:text=Probabilistic%20reasoning%20is%20a%20way,logic%
20to%20handle%20the%20uncertainty
[Link]
[Link]
[Link]
22
Chapter 3: Introduction to Artificial Neural Network & Supervised Learning Network I
UNIT 2
3
INTRODUCTION TO ARTIFICIAL
NEURAL NETWORK &
SUPERVISED LEARNING
NETWORK I
Unit Structure
3.0 Objective
3.1 Basic Concept
3.1.1 Introduction to Artificial Neural Network
3.1.2 Overview of Biological Neural Network
3.1.3 Human Brain v/s Artificial Neural Network
3.1.4 Characteristics of ANN
3.1.5 Basic Models of ANN
3.2 Basic Models of Artifical Neural Network
3.2.1 The Model Synaptic Interconnection
3.2.2 Learning Based Model
3.2.3 Activation Function
3.3 Terminologies of ANN
3.4 McCulloch Pitts Neuron
3.5 Concept of Linear Separability
3.6 Hebb Training Algorithm
3.7 Perceptron Network
3.8 Adaptive Linear Neuron
3.8.1 Training Algorithm
3.8.2 Testing Algorithm
3.9 Multiple Adaptive Linear Neurons
3.9.1 Architecture
Review Questions
23
References
SOFT COMPUTING TECHNIQUES
24
Chapter 3: Introduction to Artificial Neural Network & Supervised Learning Network I
3.0 Objectives
1. The fundamentals of artificial neural network
2. Understanding between biological neuron and artificial neuron
3. Working of a basic fundamental neuron model.
4. Terminologies and terms used for better understanding of Artificial Neural
Network
5. The basics of supervised learning and perceptron learning rule
6. Overview of adaptive and multiple adaptive linear neurons
25
SOFT COMPUTING TECHNIQUES
notes)
26
Chapter 3: Introduction to Artificial Neural Network & Supervised Learning Network I
The fact that the human brain consists of large number of neurons with numerous
interconnections that processes information. The term neural network is usually
referred to the biological neural network that processes and transmits information.
The biological neurons are part of the nervous system.
25
SOFT COMPUTING TECHNIQUES
3. Size and Complexity- The size and complexity of the brain is comparatively
higher than that of artificial neural network. The size and complexity of an
ANN is different for different applications
4. Storage Capacity – The biological neuron stores the information in its
interconnection and in artificial neuron it is stored in memory locations.
5. Tolerance- The biological neuron has fault tolerant capability but artificial
neuron has no tolerant capability. Biological neurons considers
redundancies whereas artificial neurons cannot consider redundancies.
6. Control mechanism- There is no control unit to monitor the information
processed in to the network in biological neural networks whereas in
artificial neuron model all activities are continuously monitored by a
control unit.
From the given figure above, there are two input neurons X1 and X2 transmitting
signal to the output neuron Y for receiving signal. The input neurons are
connected to the output neurons over a weighted interconnection links w1 and
26
Chapter 3: Introduction to Artificial Neural Network & Supervised Learning Network I
w2.
27
SOFT COMPUTING TECHNIQUES
For above neuron architecture , the net input has to be calculated in the
way. yin = x1w1+x2w2
where x1 and x2 are the activations of the input neurons X1 and X2 . The output
yin of the output neuron Y can be obtained by applying activations over the net
input .
y =f(yin)
The function to be applied over the net input is called activation function .
It consists of a single layer of network where the inputs are directly connected to
the output, one per node with a series of various weights.
28
Chapter 3: Introduction to Artificial Neural Network & Supervised Learning Network I
29
SOFT COMPUTING TECHNIQUES
3.2.2. Learning
The most important part of ANN is it capability to train or learn. It is basically a
process by means of which a neural net adapts for adjusting or updating the
connection weights in order to receive a desired response.
1. Supervised Learning
In Supervised learning, it is assumed that the correct target output values are
known for each input pattern. In this learning, a supervisor or teacher is needed
for error minimization. The difference between the actual and desired output
vector is minimized using the error signal by adjusting the weights until the actual
output matches the desired output.
30
Chapter 3: Introduction to Artificial Neural Network & Supervised Learning Network I
2. Unsupervised Learning
In Unsupervised learning, the learning is performed without the help of a teacher
or supervisor. In the learning process, the input vectors of similar type are
grouped together to form clusters. The desired output is not given to the network.
The system learns on its own with the input patterns.
3. Reinforcement Learning
The Reinforcement learning is a form of Supervised learning as the network
receives feedback from its environment. Here the supervisor does not present the
desired output but learns through the critic information.
1 if x >= 𝜃𝜃
f(x) =
0 if x < 𝜃𝜃
1 if x >= 𝜃𝜃
f(x) =
-1 if x < 𝜃𝜃
31
SOFT COMPUTING TECHNIQUES
Here, 𝞴𝞴 is the steepness parameter. The range of the sigmoid function is from
-1 to +1
The graphical representation is shown below for all the activation functions
32
Chapter 3: Introduction to Artificial Neural Network & Supervised Learning Network I
MP neuron model was the earliest neural network model discovered by Warren
McCulloch and Walter Pitts in [Link] is also known as Threshold Logic Unit.
The M-P neurons are connected by directed weighted paths. The activation of this
model is binary. The weights associated with the communication links may be
excitatory (weight is positive) or inhibitory (weight is negative). Each neuron has
a fixed threshold and if the net input to the neuron is greater than the threshold
then the neuron fires otherwise it will not fire.
33
SOFT COMPUTING TECHNIQUES
In ANN, linear separability is the concept wherein the separation is based on the
network response being positive or negative. A decision line is drawn to separate
positive and negative responses. The decision line is called as linear-separable
line.
Hebb or Hebb learning rule stated by Donald Hebb in 1949 states that, the
learning is performed by the change in the synaptic gap. Explaining further, he
stated “When an axon of cell A is near enough to excite cell B, and repeatedly
takes place in firing it, some growth or metabolic change takes place in one or
both the cells such that A’s efficiency, as one of the cells firing B, is increased”.
In Hebb learning, if two interconnected neurons are ‘ON’ simultaneously then the
weights associated with these neurons can be increased by changing the strength
in the synaptic gap.
34
Chapter 3: Introduction to Artificial Neural Network & Supervised Learning Network I
Perceptron Networks are single-layer feed forward networks. They are the
simplest perceptron,
Perceptron consists of three units – input unit (sensory unit), hidden unit
(associator unit) and output unit (response unit). The input units are connected to
the hidden units with fixed weights having values 1, 0 or -1 assigned at random.
The binary activation function is used in input and hidden unit. The response unit
has an activation of 1, 0 or -1. The output signal sent from the hidden unit to the
output unit are binary.
35
SOFT COMPUTING TECHNIQUES
The output of the perceptron network is given by y =f(yin) where yin is the
activation function.
The output is obtained by applying the activation function over the calculated net
input.
The weights are adjusted to minimize error when the output does not match the
desired output.
36
Chapter 3: Introduction to Artificial Neural Network & Supervised Learning Network I
Adaline is a single-unit neuron, which receives input from several units and also
from one unit, called bias. An Adeline model consists of trainable weights. The
inputs are of two values (+1 or -1) and the weights have signs (positive or
negative).
Initially random weights are assigned. The net input calculated is applied to a
quantizer transfer function (possibly activation function) that restores the output
to
+1 or -1. The Adaline model compares the actual output with the target output
and with the bias and the adjusts all the weights.
Step0: weights and bias are to be set to some random values but not zero. Set the
learning rate parameter α.
Step1: perform steps 2-6 when stopping condition is false.
Step2: perform steps 3-5 for each bipolar training pair s:t
Step3: set activations foe input units i= 1 to n.
Step4: calculate the net input to the output unit.
Step5: update the weight and bias for i=1 to n
Step6: if the highest weight change that occurred during training is smaller than a
specified tolerance then stops the training process, else continue. This is the test
for the stopping condition of a network.
It is very essential to perform the testing of a network that has been trained. When
the training has been completed, the Adaline can be used to classify input
patterns. A step function is used to test the performance of the network. The
testing procedure for the Adaline network is as follows:
Step0: initialize the weights. (The weights are obtained from the training
algorithm.)
37
SOFT COMPUTING TECHNIQUES
38
Chapter 3: Introduction to Artificial Neural Network & Supervised Learning Network I
It consists of many adalines in parallel with a single output unit whose value is
based on certain selection rules. It uses the majority vote rule. On using this rule,
the output unit would have an answer either true or false.
On the other hand, if AND rule is used, the output is true if and only if both the
inputs are true and so on.
3.9.1 Architecture
It consists of “n” units of input layer and “m” units of Adaline layer and “1” unit
of the Madaline layer. Each neuron in the Adaline and Madaline layers has a bias
of excitation “1”. The Adaline layer is present between the input layer and the
Madaline layer; the Adaline layer is considered as the hidden layer.
Review Questions
39
SOFT COMPUTING TECHNIQUES
10. State the training algorithm used for the Hebb learning networks.
REFERENCES
40
Chapter 4: Supervised Learning Network II and Associative Memory Network
Unit 2
4
SUPERVISED LEARNING NETWORK II AND
ASSOCIATIVE MEMORY NETWORK
Unit Structure
4.0 Objective
4.1 Backpropagation Network
4.2 Radial Basis Function
4.3 Time Delay Neural Network
4.4 Functional Link Network
4.5 Tree Neural Network
4.6 Wavelet Neural Network
4.7 Overview of Associative Memory
4.8 Training Algorithm for Pattern
Association Auto associative Memory Network
Hetro associative Memory
Network Bi-directional Associative
Memory Hopfield Networks
Iterative Auto associative Memory Network
Temporal Associative Memory Network
Review Questions
4.0 Objectives
39
SOFT COMPUTING TECHNIQUES
Time delay networks are basically feed-forward neural networks except that the
input weights has a tapped delay line associated to [Link] TDNN, when the output
is being fed back through a unit delay into the input layer, the net computed is
equivalent to an infinite impulse response filter.
A neuron with a tapped delay line is called a Time delay neural network unit and
a network which consists of TDNN units is called a Time delay neural network.
Application od TDNN is speech recognition.
41
SOFT COMPUTING TECHNIQUES
These networks are basically used for pattern recognition problems. It uses
multilayer neural network at each decision-making node of a binary classification
for extracting a non-linear feature.
The decision nodes are circular nodes and the terminal nodes are square nodes.
The splitting rule decides whether the pattern moves to the right or left.
42
Chapter 4: Supervised Learning Network II and Associative Memory Network
Example- Tree neural networks can be used for waveform recognition problem.
Fig: Wavelet Neural network with translation, rotation, dilation and wavelon
memories. The recall is through association of the key pattern with the help
of information memorized. Associative memory makes a parallel search
with a stored data file. The concept behind this type of search is to retrieve
the stored data either completely or partially.
44
Chapter 5: Unsupervised Learning
Unit 3
5
UNSUPERVISED LEARNING
Unit Structure
5.0 Introduction
5.0 Introduction
For example, when net has been trained to classify the input patterns into any one
of the output classes, say, P, Q, R, S or T, the net may respond to both the classes,
45
SOFT COMPUTING TECHNIQUES
P and Q or R and S. In the case mentioned, only one of several neurons should
fire, i.e., respond. Hence the network has an added structure by means of which
the net is forced to make a decision, so that only one unit will respond. The
process for achieving this is called competition. Practically, considering a set of
students, if we want to classify them on the basis of evaluation performance, their
score may be calculated, and the one whose score is higher than the others should
be the winner. The same principle adopted here is followed in the neural networks
for pattern classification. In this case, there may exist a tie; a suitable solution is
presented even when a tie occurs. Hence these nets may also be called
competitive nets, the extreme form of these competitive nets is called winner-
take-all.
The name itself implies that only one neuron in the competing group will possess
a nonzero output signal at the end of competition.
There exist several neural networks that come under this category. To list out a
few: Max net, Mexican hat, Hamming net, Kohonen self-organizing feature map,
counter propagation net, learning vector quantization (LVQ) and adaptive
resonance theory (ART).
The learning algorithm used ·m most of these nets is known as Kohonen learning.
In this learning, the
units update their weights by forming a new weight vector, which is a linear
combination of the old weight vector and the new input vector. Also, the learning
continues for the unit whose weight vector is closest to the input vector. The
weight updation formula used in Kohonen learning for output cluster unit j is
given as
where 𝑥 is the inpuc vector; 𝑤Θ𝑗𝑗 the weight vector for unit 𝑗𝑗; 𝛼 the learning rate
whose value decreases monotonically as training continues. There exist two
methods to determine the winner of the network during competition. One of the
methods for determining the winner uses the square of the Euclidean distance
between the input vector and weight vector, and the unit whose weight vector is
at the smallest Euclidean distance from the input vector is chosen as the winner.
The next method uses the dot product of the input vector and weight vector. The
dot product between the input vector and weight vector is nothing but the net
inputs calculated for the corresponding duster units.
46
Chapter 5: Unsupervised Learning
The unit with the largest dot product is chosen as the winner and the weight
updation is performed over it because the one with largest dot product
corresponds to the smallest angle between the input and weight vectors, if both
are of unit length.
These competitive nets arc those where the weights remain fixed, even during
training process. The idea of competition is used among neurons for enhancement
of contrast in their activation functions. These are
Maxnet
The Maxnet serves as a sub net for picking the node whose input is larger.
Architecture of Maxnet
weighted interconnections. The weights between the neurons are inhibitory and
fixed. The Maxnet with this structure can be used as a subnet to select a particular
node whose net input is the largest.
47
SOFT COMPUTING TECHNIQUES
0: Initial weights and initial activations are ser. The weight is set as [0 < 𝜀𝜀 <
Step
and
𝑤𝑖𝑖𝑗𝑗 = { 1 if 𝑖𝑖 = 𝑗𝑗
−𝜀𝜀 if 𝑖𝑖 ≠ 𝑗𝑗
3: Save the acrivarions obtained for use in the next iteration. For 𝑗𝑗 = 1 to 𝑚,
Step
This interconnection pattern is repeated for several other neurons in the layer.
48
Chapter 5: Unsupervised Learning
The architecture of Mexican hat is shown in Figure 5·2, with the interconnection
pattern for node Xi. The
neurons here are arranged in linear order; having positive connections between Xi
and near neighboring units, and negative connections between Xi and farther
away neighboring units. The positive connection region is called region of
cooperation and the negative connection region is called region of competition.
The size of these regions depends on the relative magnitudes existing between the
positive and negative weights and also on the topology of regions such as linear,
rectangular, hexagonal grids, ere. In Mexican Hat, there exist two symmetric
regions around each individual neuron.
The individual neuron in Figure 5-2 is denoted by Xi. This neuron is surrounded
by other neurons Xi+ 1,
Xi-1, Xi+2, Xi-2, The nearest neighbors to the individual neuron Xi are Xi+1, Xi-
1. Xi+2• and Xi-2·
Hence, the weights associated with these are considered to be positive and are
denoted by WI and w2. The
farthest neighbors m the individual neuron Xi are taken as Xi+3 and Xi-3, the
weights associated with these are negative and are denoted by w3. It can be seen
chat Xi+4 and Xi-4 are not connected to the individual neuron Xi, and therefore no
weighted interconnections exist between these connections. To make it easier, the
units present within a radius of 2 [query for unit] to the unit Xi are connected with
positive weights, the units within radius 3 are connected with negative weights
and the units present further away from radius 3 are not connected in any manner
co the neuron Xi.
49
SOFT COMPUTING TECHNIQUES
The flowchart for Mexicann hat is shown in Figure 5-3. This dearly depicts the
flow of the process performed in Mexican Hat Network.
50
Chapter 5: Unsupervised Learning
The various parameters used in the training algorithm are as shown below.
X𝑖𝑖+𝑘 and X𝑓𝑓−𝑘 are conniected to the individual units X𝑖𝑖 for 𝑘 = 1 to 𝑅2 .
X𝑖𝑖−𝑘
0 ⩽ 𝑘 ⩽ 𝑅1, 𝑤𝑘 = positive
𝑅1 ⩽ 𝑘 ⩽ 𝑅2, 𝑤𝑘 = negative
𝑡 = external input signal
𝑥 = vector of accivation
𝑥0 = vecior of activations at previous time step
Here the iteration is started only with the incoming of the external signal
presented to the network.
Initialize weights as
Initialize 𝑥0 = 0.
Step 1: Input the external signal s:
𝑥 =𝑠
𝑥0𝑖𝑖 = 𝑥𝑖𝑖
𝑐
𝑅1 −𝑅
𝑥 =𝑐 ∑ +𝑐
1−1
𝑥 + 𝑥
51
∑ 𝑥
SOFT COMPUTING TECHNIQUES
𝑅2
𝑖𝑖 1 0𝑖𝑖 𝑘=−𝑅 0𝑖𝑖+ 2 0𝑖𝑖+𝑘
𝑘=−𝑅 + 2 𝑘 𝑘=𝑅1+
1 1
52
Chapter 5: Unsupervised Learning
𝑥0𝑖𝑖 = 𝑥𝑖𝑖
𝑡=𝑡+1
The positive reinforcement here has the capacity to increase the activation of
units with larger initial activations and the negative reinforcement has the
activation function used here for unit Xi at a particular time instant ′′𝑡′′ is given
capacity’ to reduce the activation of unis with smaller initial activations. The
by
The Hamming network selects stored classes, which are at a maximum Hamming
distance (H) from the
noisy vector presented at the input (Lippmann, 1987). The vectors involved in
this case are all binary and
vectors (the weight vector for an output unit in a clustering net is exemplar vector
or code book vector for the pattern of inputs, which the net has placed on that
duster unit) is most similar to an input vector (represented as an n~tuple). The
weights of the net are determined by the exemplar vectors. The difference
between the tom! number of components and the Hamming distance between the
53
SOFT COMPUTING TECHNIQUES
vectors gives the measure of similarity between the input vector and stored
54
Chapter 5: Unsupervised Learning
exemplar vectors’ is already discussed the Hamming distance between the two
vectors is the number of components in which the vectors differ.
x.y=a-d
where a is the number of components in which the vectors agree, d the number of
components in which the vectors disagree. The value "a - d" is the Hamming
distance existing between two vectors. Since, the total number of components is
n, we have,
𝑛=𝑎+𝑑
i.e., 𝑑 =𝑛−𝑎
On simplification, we get
𝑥⋅𝑦 = 𝑎−𝑑
𝑥⋅𝑦 = 𝑎 − (𝑛 − 𝑎)
𝑥⋅𝑦 = 2𝑎 − 𝑛
2𝑎 = 𝑥 ⋅𝑦
+𝑛
𝑎 =1 1
(𝑥 ⋅ 𝑦) (𝑛)
+ 2
2
From the above equation, it is clearly understood that the weights can be set to
one- half the exemplar vector and bias can be set initially to n/2. By calculating
the unit with the largest net input, the net is able to locate a particular unit that is
closest to the exemplar. The unit with the largest net input is obtained by the
Hamming net using Maxnet as its subnet.
55
SOFT COMPUTING TECHNIQUES
56
Chapter 5: Unsupervised Learning
𝑛
𝑏𝑗𝑗 =
2
Step 1: Perform Steps 2-4 for each inpuc vector
i.e.,
𝜔
Step 4: Maxnet is found to iterate for finding the exemplar that best matches the
inpur patterns.
55
SOFT COMPUTING TECHNIQUES
56
Chapter 5: Unsupervised Learning
On the other hand, if the input vector is two-dimensional, the inputs, say x(a,
b), can arrange themselves
The topological preserving property is observed in the brain, bur nor found in
any other artificial neural network.
Consider a linear array of cluster units as in Figure 5-7. The neighborhoods of the
units designated by "o" of radii Ni(k1), Ni(k2) and Ni(k,), k1 > k, > k,, where k1
= 2, k2 = 1, k3 = 0.
For a rectangular grid, a neighborhood (Ni) of radii k1, k2, and k3 is shown in
Figure 5-8 and for a
hexagonal grid the neighborhood is shown in Figure 5-9. In all the three cases
(Figures 5-7-5-9), the unit with “#” symbol is the winning unit and the other units
are indicated by "o." In both rectangular and hexagonal grids, k1 >k2 > k3, where
k1 = 2, k2 = 1, k3 = 0.
For rectangular grid, each unit has eight nearest neighbors but there are only
six neighbors for each unit in
the case of a hexagon grid. Missing neighborhoods may just be ignored. A typical
architecture of Kohonen self-organizing feature map (KSOFM) is shown in
Figure 5-10.
57
Chapter 5: Unsupervised Learning
57
SOFT COMPUTING TECHNIQUES
58
Chapter 5: Unsupervised Learning
Step 0: - Initialize the weights 𝑤𝑖𝑖𝑖𝑖 : Random values may be assumed. They can
be chosen as the same range of values as the component if input vector. If
information related to distribution of clusters is known, the initial weights. can bet
taken to reflect that prior knowledge.
Step 3: Compute the square of the Euclidean distance, i.e., for each 𝑗𝑗 = 1
to 𝑚,
𝑛 𝑚
2
𝐷(𝑗𝑗) = ∑ ∑ (𝑥𝑖𝑖 − 𝑤𝑖𝑖𝑖𝑖 )
𝑖𝑖=1 𝑖𝑖=1
Step 4: Find the winning unit index J, so that D(J) is minimum. (In Steps 3 and 4
, dot product method can also be used to find the winner, which is basically the
calculation of net input, and the winner will be the one with the largest dot
product.)
Step 5: For all units 𝑗𝑗 within a specific neighborhood of 𝐽 and for all 𝑖𝑖,
calculate the new weights:
Or
59
SOFT COMPUTING TECHNIQUES
The extension of Kohonen feature map for a multilayer network involve the
addition of an association layer to the output of the self-organizing feature map
layer. The output node is found to associate the desired output values with certain
input vectors. This type of architecture is called as Kohonen self-organizing
motor map and layer that is added is called a motor map in which the
movement command,
Figure 5-12. Here, the feature map is a hidden layer and this acts as a
competitive network which classifies the input vectors.
LVQ is a process of classifying the patterns, wherein each output unit represents a
particular class. Here, for each class several units should be used. The output unit
weight vector is called the reference vector or code book vector for the class
which the unit represents. This is a special case of competitive net, which uses
supervised learning methodology. During the training the output units are found
to be positioned to approximate the decision surfaces of the existing Bayesian
classifier. Here, the set of training patterns with known classifications is given to
the network, along with an initial distribution of the reference vectors. When the
60
Chapter 5: Unsupervised Learning
training process
61
SOFT COMPUTING TECHNIQUES
Figure 5-13 shows the architecture of LVQ. From Figure 5-13 it can be noticed
that there exists input layer with "n" unit; and output layer with "m" units. The
layers are found to be fully interconnected with weighted linkage acting over the
links.
The parameters used for the training process of a LVQ include the following:
2
The Euclidean distance of jh outpui unit is 𝐷(𝑗𝑗) = ∑(𝑥𝑖𝑖 − 𝑤𝑖𝑖𝑗𝑗 ) . The
flowchart indicaring the flow of training process is shown in Figure 5 − 14.
62
Chapter 5: Unsupervised Learning
Step 0: Initialize the reference vectors. This can be done using the
following steps.
From the given sec of training vectors, take the first " 𝑚 " (number of
clusters) training vectors and use them as weighc vectors, the
remaining vectors can be used for training.
Assign the initial weights and classifications random.1y.
K -means chustering mechod.
vector 𝑥.
63
Step 3: Calculate the Euclidean distance; for 𝑖𝑖 = 1 to 𝑛, 𝑗𝑗 = 1 to 𝑚,
SOFT COMPUTING TECHNIQUES
64
Chapter 5: Unsupervised Learning
𝑛 𝑚
2
𝐷(𝑗𝑗) = ∑ ∑ (𝑥𝑖𝑖 − 𝑤𝑖𝑖𝑗𝑗 )
𝑖𝑖=1 𝑗𝑗=1
(The stopping conditions may be fixed number of epochs or if learning rate has
reduced to a negligible value.)
They are multilayer networks based on the combinations of the input, output and
clustering layers. The applications of counter propagation nets are data
compression, function approximation and pattern association. The counter
propagation network is basically constructed from an instar-outstar model. This
model is a three-layer neural network that performs input-output data mapping,
producing an output vector yin response to an input vector x, on the basis of
competitive learning. The three layers in an instar-outstar model are the input
layer, the hidden (competitive) layer and the output layer. The connections
between the input layer and the competitive layer are the instar structure, and the
connections existing between the competitive layer and the output layer are the
outstar structure.
There are two stages involved in the training process of a counter propagation net.
The input vectors are
65
SOFT COMPUTING TECHNIQUES
Full counter propagation net (full CPN) efficiently represents a large number of
vector pairs x:y by adaptively constructing a look-up-table. The approximation
here is x*.y*, which is based on the vector pairs x:y, possibly with some distorted
or missing elements in either vector or both vectors. The network is defined to
approximate a continue function, defined on a compact set A. The full CPN
works best if the inverse function f -1 exists and is continuous. The vectors x and y
propagate through the network in a counter flow manner to yield output vectors
x* and y*, which are the approximations of x and y, respective. During
competition, the winner can be determined either by Euclidean distance or by dot
product method. In case of dot product method, the one with the largest net input
is the winner. Whenever vectors are to be compared using the dot product metric,
they should be normalized. Even though the normalization can be performed
without loss of information by adding an extra component, yet to avoid the
complexity Euclidean distance method can be used. On the basis of this, direct
comparison can be made between the full CPN and forward-only CPN.
As already discussed, the training of CPN occurs in two phases. In the input
phase, the units in the duster layer and input layer are found to be active. In CPN,
no topology is assumed for the cluster layer units; only the winning units are
allowed to learn. The weight pupation learning rule on the winning duster units is
66
Chapter 5: Unsupervised Learning
In the second phase of training, only the winner unit J remains active in the
cluster layer. The weights between the winning cluster unit J and the output units
are adjusted so that the vector of activations of the units in the Y-output layer is
y* which is an approximation to the input vector y and X* which is an
approximation to the input vector x. The weight updating for the units in the Y-
output and X-output layers are
The general structure of full CPN is shown in Figure 5-15. The complete
architecture of full CPN is shown in Figure 5-16.
The four major components of the instar-outstar model are the input layer, the
instar, the competitive layer and the outstar. For each node i in the input layer,
there is an input value xi;. An instar responds maximally to the input vectors from
a particular duster. All the instar are grouped into a layer called the competitive
layer.
67
SOFT COMPUTING TECHNIQUES
68
Chapter 5: Unsupervised Learning
69
SOFT COMPUTING TECHNIQUES
Step 0: Set the initial weighrs and the initial learning rate.
Step 2: For each of the training input vector pair 𝑥: 𝑦 presented, perform Steps
3 − 5.
Step 3: Make the X-input layer activations to vector X. Make the Y-inpur layer
acrivations to vector Y.
𝑛 𝑚
If there occurs a tie in case of selection of winner unit, the unit with the smallest
index is the winner. Take the winner unit index as J.
Step 5: Update the weights over the calculated winner unit 𝑧𝑗𝑗 .
70
Chapter 5: Unsupervised Learning
Step 8: Perform Steps 9-15 when stopping condition is false for phase II training.
Step 9: Perform Steps 10 − 13 for each training input pair 𝑥; 𝑦. Here 𝛼 and 𝛽
are small constant values.
Step 10: Make the X-input layer activations to vector 𝑥. Make the Y-input
layer activations to vectot 𝑦.
Step 13: Update the weights from unit 𝑧𝑖𝑖 to ghe outpur layers.
pair X: Y.
Step 2: Ser X-input layer activations to vector X. Ser Y-input layer activarions
to vector Y.
Step 3: Find the cluster unit 𝑧𝑖𝑖 that is closest to the input pair.
71
SOFT COMPUTING TECHNIQUES
In case of forward-only CPN, first input vectors are presented to the input units.
The cluster layer units compete with each other using winner-take-all policy to
learn the input vector. Once entire set of training vectors has been presented, there
exist reduction in learning rate and the vectors are presented again, performing
several iterations. First the weights between the input layer and duster layer are
trained. Then the weights between the cluster layer and output layer are trained.
This is a specific competitive network, with target known. Hence, when each
input vector is presented m the input vector, its associated target vectors are
presented to the output layer. The winning duster unit sends its signal to the
output layer. Thus each of the output unit has a computed signal (wjk) and die
target value (yk). The difference between these values is calculated; based on this,
the weights between the winning layer and output layer are updated. The weight
updation from input units to cluster units is done using the learning rule given
below:
For i= 1 to n,
be written in the form of delta rule when the activations of the cluster units (𝑧𝑖𝑖 )
The learning rule for weight updation from the duster units to output units can
where
1 if 𝑗𝑗 = 𝐽
𝑧𝑖𝑖 = {
0 if 𝑗𝑗 ≠ 𝐽
This occurs when 𝑤𝑖𝑖𝑘 is interprered as the computed output (i.e., 𝑦𝑘 = 𝑤𝑖𝑖𝑘 ).
72
Chapter 5: Unsupervised Learning
73
SOFT COMPUTING TECHNIQUES
Step 1: Perform Steps 2-7 when stopping condition for phase I training is false.
𝑋𝑋.
Step 3: Set the X-input layer acrivations to vector
Step 4: Compute the winning cluster unit (𝐽). If dot product mechod is used, find
the cluster unit zy Step wich the largest net input:
𝑛
74
Chapter 5: Unsupervised Learning
lidean distance is used, find the cluster unit 𝑧𝑗𝑗 square of whose distance
from put pattetn is smallest:
𝑛
2
𝐷𝑗𝑗 = ∑ (𝑥𝑖𝑖 − 𝑣𝑖𝑖𝑗𝑗 )
𝑖𝑖=1
e exists a tie in the selection of winner unit, the unit with the smallest index
sen as the winner.
𝛼(𝑡 + 1) = 0.5𝛼(𝑡)
1: Find the winning cluster unit (J) [use formulas as in Step 4].
𝛽(𝑡 + 1) = 0.5𝛽(𝑡)
Step 0: Set initial weights. (The initial weights here are the weights obtained during
training.)
𝑦𝑘 = 𝑤𝑗𝑗𝑘
time. On the basis of this, the stability of the net is defined as that wherein a
pattern is not presented (o previous cluster units the stability may be achieved by
reducing the learning rates. The ability of the network to respond to a new pattern
equally at any stage of learning is called as plastic: ART nets are designed to
possess the properties, stability and plasticity. The key concept of ART is that the
The processing neuron (F1) layer consists of two portions: Input portion and
interface portion input portion may perform some processing based on the inputs
1. The interface portion of the F1 layer combines the input from input portion of
it receives. This is especially performed in the case of ART 2 compared to ART
F1 and F2 layers for comparing the similarity of the input signal with the weight
vector for the interface portion 25 F (b).
There exist two sets of weighted interconnections for controlling the degree of
bottom-up weights are used for the connection from F1( b) layer to F2 tayer and
similarity between the units in the interface portion and the cluster layer. The
are represented by 𝛿𝛿𝑖𝑖𝑖𝑖(𝑓𝑓 th F1 unit to jhF2 unit). The iop-down weights are
used for the connection from F2 layer to F1 ( b) layer and are repiesented by
𝑡𝜇‾ (𝑗𝑗 th F2 unit to 𝑖𝑖 th F1 anic). The competitive Jayer in this cose is the
input pattern, and the activations of all other F2 urnis are mate zero The interface
cluster layct and the duster unit wich largest net input is the victim to learn the
units combinc the data from input and cluster layer units. On the basis of the
similarity between the top-
77
SOFT COMPUTING TECHNIQUES
down weight vector and input vector, the cluster unit may be allowed to learn the
signals receives from interface portion and input portion of the F1 layer. When
input pattern. This decision is done by-esset mechanism unit on the basis of the
duster unit is not allowed to learn, it is inhibited and a new cluster unit is selected
as the victim.
going to be the F2 unit (that is nor inhibited) with the largest input.
Step 5: Find the victim unit to learn the current input pattern. The victim unit is
Step 6: F1 (b) units combine their inputs from F1 (a) and F2.
rejected (inhibited); go to Step 4. If reser is false, then che carrent victim unit is
Step7: Test for reset condition. Step If reset is true, then the current victim unit is
condition.
input unit (𝐹1 unit) and output unit (𝐹2 unit)-aiong with the reser control unit
vectors. As discussed generally, the ART 1 net consists of two fields of units-
There exist two sets of weighted interconnection patch between F1 and F2 layers.
for controlling the degree of similarity of patterns placed on the same cluster unit.
The supplemental unic present in the net provides the efficient neural control of
the leatning process. Carpenter and Grossberg have designed ART 1 network as a
real-time system. In ART 1 network, ic is not necessary to present an input
pattern in a particular order; it can be presented in any order. ART 1 network can
be practically implemented by analog circuits governing the differential
equations, i. Q. the bottom-up and top down weights are controlled by differential
equations.)ART 1 network runs throughout autonomously. It does nor require any
78
Chapter 5: Unsupervised Learning
external control signals and can run stably with infinite patterns of input data.
79
SOFT COMPUTING TECHNIQUES
ART 1 network is trained using fast learning method, in which the weights reach
equilibrium during each learning trial. During this resonance phase, the
activations of F units do not change; hence the equilibrium weights can be
determined exactly The ART 1 network performs well with perfect binary input
patterns, but is sensitive to noise in the input dara. Hence care should be taken to
handle the noise.
1 Computational units.
2 Supplemental units.
Computational units
1 Input units (F1 unit − both input portion and interface portion).
5-22. Here each unit present in the input portion of F1 layer (i, e. , F1(a) layer
cluster). The basic architecture of ART I (computational unit) is shown in Figure
F1( b) layer unit). Reset control unit has connections from each fF1(a) and
unic) is connected to the respective unic in the interface portion of E layer (i.e.,
F1( b) units. Also, each unit in F1( b) layer is connected through two weighted
interconnection pachs to each unic in F2 layer and the reser control unit is
connected to every F2 unit. The Xi unit of F1(b) layer is connected to Yj unit of F2
layer through bottom-up weight (bij) and the Yj unit of F2 is connected to Xi unit
of F1 through top-down weights (tji). Thus ART 1 includes a bottom-up
competitive learning system combined with a top-down outstar learning system.
In Figure 5 − 22 for simplicity only the weighted interconnections 𝑏𝑖𝑖𝑖𝑖 and 𝑡𝑖𝑖𝑖𝑖
cluster layer (𝐹2 layer) unit is a competitive layer, where only the uninhibited
are shown, the other units’ weighted interconnections are in a similar way. The
80
Chapter 5: Unsupervised Learning
and 0 < 𝜌 ≤ 1
Step 0: initialize the parameters:
Initialize the
weights: 𝛼
0 < 𝑏𝑖𝑖𝑖𝑖 (0) < and 𝑡𝑖𝑖𝑖𝑖 (0) = 1
𝛼−1+𝑛
input.
Step 3: Set activations of all F2 units to zero. Set the activations of F1(2) units to
input vectors.
∥ 𝑠 ∥= ∑ 𝑠𝑖𝑖
𝑖𝑖
𝑥1 = 𝑠𝑖𝑖
81
SOFT COMPUTING TECHNIQUES
Step 6: for each F2 pode thar is not inhibited, the following rule should hold: If
𝑦; ≠ −1, then 𝑦‾𝑗𝑗 = ∑𝑏𝑖𝑖𝑗𝑗𝑥𝑖𝑖
Step 8 : Find J for 𝑦𝑗𝑗 ≥ 𝑦𝑗𝑗 for all nodes 𝑗𝑗. If 𝑦𝑗𝑗 = −1, then all the
nodes are inhibited and note that this pattern cannot be clustered.
∥ 𝑥 ∥= ∑ 𝑥𝑖𝑖
𝑖𝑖
Step 11: Test for reset condition. If ∥ 𝑥 ∥/∥ 𝑠 ∥< 𝜌, then inhibit node 𝐽, 𝑦𝑗𝑗 =
−1. Go back to step 7 again. Else if ∥ 𝑥 ∥/∥ 𝑠 ∥≥ 𝜌, then procced to the next
step (Step 12).
Step 13: Test for stopping condition. The following may be the stopping
conditions:
a. No change in weights.
b. No reset of units.
c. Maximum number of epochs reached.
82
Chapter 5: Unsupervised Learning
fed back to the top and bottom input layers. The complexity in the F1 layer is
essential because continuous-valued input vectors may be arbitrarily dose
together. The F1 layer consists of normalization and noise suppression parameter,
in addition to comparison of the bottom-up and top-down signals, needed for the
reset mechanism.
The supplemental unit " N′′ between units 𝑊𝑊 and 𝑋𝑋 receives signals from all "
𝑊𝑊 " units, computes the no run of vector 𝑤 and sends this signal to each of the
𝑋𝑋 units. This signal is inhibitory signal. Each of this (X1, … , X𝑖𝑖 , … , X𝑛) also
receives excicatory signal from the corresponding 𝑊𝑊 unit. In a similar way,
there exists supplemental units between 𝑈 and 𝑉, and 𝑃 and 𝑄𝑄, performing
the same operation as done between W and X. Each X unit and Q unit is
connecred to V unit. The connections between Pj of the F1 layer and Y𝑗𝑗 of the
F2 layer show the weighted
winning F2 unics’ activation is 𝑑(0 < 𝑑 < 1). There exists normalization
interconnections, which multiplies the signals transmitted over those pachs. The
to unit length.
The operations performed in F2 layer are same for both ART 1 and ART 2. The
units in F2 layer compete with each other in a winner-take-all policy to learn each
83
SOFT COMPUTING TECHNIQUES
input pattern. The testing of reset condition differs for ART 1 and ART 2
networks. Thus, in ART 2 network, some processing of the input vector is
necessary because the magnitudes of the real valued input vectors may vary more
than for the binary input vectors.
84
Chapter 5: Unsupervised Learning
𝑢 𝑣𝑖
𝑤 = ; = + 𝑎𝑢 ;
𝑖
𝑠
𝑒+∥ 𝑣
𝑗𝑗 𝑖𝑖 𝑖𝑖 𝑖𝑖
∥
𝑃=𝑢 ; 𝑥 𝑤𝑖
= ;𝑖
𝑖𝑖 𝑖𝑖 𝑖𝑖 𝑒+∥ 𝑤 ∥′ 𝑞 = ; 𝑣
𝑝𝑖 𝑖
85
= 𝑓𝑓(𝑥 ) + 𝑏𝑓𝑓(𝑞 )
SOFT COMPUTING TECHNIQUES
𝑖𝑖
𝑒+∥ 𝑝 𝑖𝑖 𝑖𝑖 𝑖𝑖
86
Chapter 5: Unsupervised Learning
In ART 2 networks, norms are calculated as the square root of the sum of
the squares of the respective values.
𝑦𝑗𝑗 = ∑ 𝑏𝑖𝑖𝑗𝑗𝑝𝑖𝑖
𝑗𝑗=1
Step 6: Find F2 unit Y𝑗𝑗 wich largest signal J is defined such that 𝑦𝑗𝑗 ≥ 𝑦𝑗𝑗 , 𝑗𝑗 = 1
𝑚 ).
(o
𝑢𝑣𝑖 𝑤 𝑖 𝑖 + 𝑐P𝑖
P = ; = + 𝑑𝑡 ; =
𝑖
𝑖
𝑢 𝑟
𝑖𝑖
𝑐+∥ 𝜈𝜈 𝑖𝑖 𝑖𝑖 𝑗𝑗 𝑖𝑖
𝑒+∥ 𝑢 ∥÷ 𝑐 ∥ 𝑝 ∥
∥
If ∥ 𝑟 ∥≥ (𝜌 − 𝑒), then
𝑤 = 𝑠 + 𝑎𝑢 ; = 𝑤𝑖 :𝑖
𝑥
𝑖𝑖 𝑖𝑖 𝑖𝑖 𝑒+∥ 𝑤 ∥
𝑖𝑖
𝑞 𝑝=
𝑖 𝑖 ; 𝑣 = 𝑓𝑓(𝑥 ) + 𝑏𝑓𝑓(𝑞 )
𝑖𝑖
𝑒+∥ 𝑝 𝑖𝑖 𝑖𝑖 𝑖𝑖
𝑢 =𝑣𝑖 𝑖 :
𝑤 = + 𝑎𝑢 ;
𝑠
𝑖𝑖 𝑐+∥ 𝜈𝜈 𝑖𝑖 𝑖𝑖 𝑖𝑖
∥
𝑃𝑖𝑖 𝑤𝑖
= ;
𝑖
= + ;
𝑖
𝑒+∥ 𝑤 ∥
𝑢 𝑖 𝑑𝑡𝑗𝑗𝑖𝑖 𝑥𝑖𝑖
87
𝑞 𝑃= 𝑣; = 𝑓𝑓(𝑥 ) + 𝑏𝑓𝑓(𝑞 )
SOFT COMPUTING TECHNIQUES
𝑖 𝑖
𝑖𝑖
𝑒+∥ 𝑝 𝑖𝑖 𝑖𝑖 𝑖𝑖
epochs.
88
Chapter 6: Special
Networks
Unit III
6
SPECIAL NETWORKS
Unit Structure
This process eventually makes the metal's global energy function reach an
absolute minimum value. If the metal's temperature is reduced quickly, the energy
of the metallic lattice will be higher than this minimum value because of the
existence of frozen lattice dislocations that would otherwise disappear due to
thermal agitation.
81
SOFT COMPUTING TECHNIQUES
old
With simulated annealing, a system changes its state from the original state SA
to a new state SA new with a probability P given by
1
P=
1 + exp (−Δ𝐸𝐼𝑇)
where Δ𝐸 = 𝐸old − 𝐸new (energy change = diffecence in new energy and old
energy) and 𝑇 is the nonnegative parameter (acts like temperature of a physical
system). The probability P as a function of change in energy (Δ𝐸) obtained for
different values of the temperature 𝑇 is shown in Figure 6 − 1.
From Figure 6 − 1, it can be noticed that the probability when Δ𝐸 > 0 is
always higher than the probability when Δ𝐸 < 0 for any temperature.
𝑋𝑋˙ = (𝑋𝑋1 , … , 𝑋𝑋𝑛 ) that minimizes some function 𝑓𝑓(𝑋𝑋) called cost
An optimization problem seeks to find some configuration of parameters
82
Chapter 6: Special Networks
Figure 6-2 shows the simulated annealing between a stone and a hill.
Figure 6.1 Probability “P” as a function in energy (AE) for different values
of temperature T
83
SOFT COMPUTING TECHNIQUES
The early optimization technique used in artificial neural networks is based on the
Boltzmann machine. When the simulated annealing process is applied w the
discrete Hopfield network, it becomes a Boltzmann machine. The network is
configured as the vector of the states of the units, and the stares of the units are
binary valued with probabilities state transition. The Boltzmann machine
described in this section has fixed weights wij. On applying the Boltzmann
machine to a constrained optimization problem, the weights represent the
constraints of the problem and the quantity to be optimized. The discussion here
is based on the fact of maximization of a consensus function (CF).
The Boltzmann machine consists of a set of units (Xi, and Xj) and a set of bi-
directional connections between pairs of units. This machine can be used as an
associative memory. If the units Xi; and Xj are connected, then wij≠0. There
exists symmetry in the weighted interconnections based on the directional nature.
It can be represented as wij=wji. There also may exist a self-connection for a unit
(wij). For unit Xi, its State xi; may be either 1 or 0. The objective of the neural net
is to maximize the CF given by
The maximum of the CF can be obtained by letting each unit attempt to change
its state (alter between " 1 "and " 0 " or " 0 " and " 1 "). The change of state can
be done either in parallel or sequential manner. However. in this case ail the
where 𝑥𝑗𝑗 is the current srate of unit 𝑋𝑋𝑖𝑖 . The variation in coefficient (1 − 2𝑥𝑖𝑖)
is given by
If unit 𝑋𝑋𝑖𝑖 were to change its activations, then the resulting change in the CF
can be obtained from the information that is local to unit 𝑋𝑋𝑖𝑖 . Generally, 𝑋𝑋𝑖𝑖
does not change its state, but if the scates are changed, then this increases the
consensus of the net.
84
Chapter 6: Special Networks
The probability of the nerwork that accepts a change in the state for unit 𝑋𝑋𝑖𝑖 is
given by
1
AF(𝑖𝑖, 𝑇) =
1 + exp
[−ΔCF(𝑖𝑖)/𝑇]
Step 3: Integers 𝐼 and 𝐽 are chosen random values berween 1 and 𝑛. (Unit
𝑈𝑙,𝑗𝑗 is the current victim to change its state.}
85
SOFT COMPUTING TECHNIQUES
Step 6: Decide whether to accept the change or not. Let 𝑅 be a random number
between 0 and 1.
Gaussian machine is one which includes Boltzmann machine, Hopfield net and
other neural networks. The Gaussian machine is based on the following three
parameters:
The steps involved in the operation of the Gaussian net are the following:
where 𝜃𝜃; is the threshold and ∈ the random noise which depends on temperature
86
𝑇.
Chapter 6: Special Networks
87
SOFT COMPUTING TECHNIQUES
√2𝜋𝜎2
where 𝑥𝑖𝑖 = ΔCF(𝑖𝑖). The noise which is found to obey a logistic rather than a
Gaussian distribution produces a Gaussian machine that is identical to Boltmann
machine having Metropolis accepcance function, i.e., the output set to 1 with
probability,
1
AF(𝑖𝑖, T) =
1 + exp 𝑖(−𝑥 /𝑇)
𝑖
88
Chapter 6: Special Networks
Δ𝑥𝑖𝑖 = −𝑥𝑖𝑖 +
net𝑖𝑖
𝑤𝑖𝑖𝑗𝑗 𝑣𝑗𝑗 + 𝜃𝜃𝑖𝑖 + 𝜖𝜖
𝑁
The Cauchy acceptance function can be obtained by integrating the Cauchy noise
distribution:
∞
1 𝑇𝑑𝑥 1 1 𝑥𝑖𝑖
∫ = + arctan ( ) = AF (𝑖𝑖, 𝑇)
0 𝜋 𝑇2 + (𝑥 −𝑖𝑖 𝑥 )2 2 𝜋 𝑇
where 𝑥𝑖𝑖 = Δ𝐶𝐹(𝑖𝑖). The cooling schedule and temperature have to be
considered in both Cauchy and Gaussian machines.
Step 0: For each training input pattern 𝑥(𝑝), 𝑝 = 1 to 𝑃, perform Steps 1 and 2.
Step1: Create pattern unit 𝑧𝑘 (hidden-layer- 1 unit). Wcight vecror for unit 𝑧𝑘 is
𝑤𝑘 = 𝑥(𝑝)
given by
Cascade correlation is a network which builds its own architecture as the training
progresses. Figure 6-5 shows the cascade correlation architecture. The network
begins with some inputs and one or more output nodes, but it has no hidden
nodes. Each and every input is connected to every output node. There may be
linear units or some nonlinear activation function such as bipolar sigmoidal
activation function in the output nodes. During training process, new hidden
nodes are added to the network one by one. For each new hidden node, the
correlation magnitude between the new node's output and the residual error signal
is maximized. The connection is made to each node from each of the network's
original inputs and also from every preexisting hidden node. During the time
when the node is being added to the network, the input weights of the hidden
nodes are-frozen, and only the output connections are trained repeatedly. Each
new node thus adds a new one-node layer to the network.
90
Chapter 6: Special Networks
Figure 6.5. Cascade architecture after two hidden nodes have been added
In Figure 6-5, the vertical lines sum all incoming activations. The rectangular
boxed connections are frozen and "0" connections are trained continuously. In the
beginning of the training, there are no hidden nodes, and the network is trained
over the complete training set. Since there is no hidden node, a simple learning
rule, Widrow-Hofflearning rule, is used for training. After a certain number of
training cycles, when there is no significant error reduction and the final error
obtained is unsatisfactory, we try to reduce the residual errors further by adding a
new hidden node. For performing this task, we begin with a candidate node that
receives trainable input connections from the network's external inputs and from
all pre- existing hidden nodes. The output of this candidate node is not yet
connected to the active network. After this, we run several numbers of epochs for
the training set. We adjust the candidate node's input weights after each -epoch to
maximize C which is defined as
𝐶 = ∑ {∑ (𝑣 − 𝑣⃗ )(𝐸 − 𝐸‾ ) ∣
𝑗𝑗 𝑗𝑗,𝑖𝑖 𝑜
𝑖𝑖 𝑗𝑗
where 𝑖𝑖 is the network output at which error is measured, 𝑗𝑗 the raining partern,
𝑣 the candidate node’s output value, 𝐸0 the residual output error at node 0, 𝜈𝜈‾ the
value of 𝜈𝜈 averaged over all patterns, ̅𝐸̅ ̅, the value of 𝐸
𝑜 𝑜
averaged over all patterns. The value " 𝐶 " measures the correlation between the
∂𝑐
∂𝑤𝑖𝑖 = ∑ 𝜎𝑖𝑖 − 𝐸 𝑖𝑖 )𝑑𝑗𝑗 𝐼𝑚,𝑗𝑗
‾
(𝐸𝑗𝑗,𝑖𝑖
𝑗𝑗,𝑖𝑖
where 𝜎𝑖𝑖 is the sign of the correlation between the candidate’s value and output
𝑖𝑖; 𝑗𝑑′ the derivative for pattern of the candidate node’s activation function with
respect to sum of its inputs; 𝐼𝑚,𝑗𝑗 the input the candidate node receives from
𝑗
𝑚 for pattern 𝑗𝑗. When gradient ∂𝑑 ∂𝑤𝑖𝑖 is calculated, perform gradient ascent
node
to
maximize
can be applied. When 𝐶 stops improving, again a new candidate can be brought
C. As we are training only a single layer of weights, simple delta learning rule
in as a node in the active network and its input weights are frozen. Once again, all
91
SOFT COMPUTING TECHNIQUES
the output weights are trained by the delta learning rule as done previously, and
the whole cycle repeats itself until the error becomes acceptably small.
92
Chapter 6: Special Networks
2. None of the postsynaptic cells present near cell Y fire stronger than Y.
Figure 6-6 shows the connection between presynaptic cell and postsynaptic cell.
defined areas of the previous layer and also from units within its own area. The
input and output neural
elements can rake the form of positive analog values, which are proportional to
the pulse density of firing
biological neurons. The cells in the cognitron model use a mechanism of shunting
inhibition, i.e., a cell is
bound in terms of a maximum and minimum activities and is driven toward these
extremities. The area from which the cell receives input is called connectable
area. The area formed by the inhibitory cluster is called the vicinity area.
Figure 6. 7 shows the model of a cognitron. Since the connectable areas for cells
in the same vicinity are defined to overlap, but are not exactly the same, there will
be- a slight difference appearing between the cells which is reinforced so that the
gap becomes more apparent. Like this, each cell is allowed to develop its own
characteristics.
93
SOFT COMPUTING TECHNIQUES
1. S·-cell: Cells that are trained suitably to. respond to only certain features in
the previous layer.
94
Chapter 6: Special Networks
95
SOFT COMPUTING TECHNIQUES
The users have to fix the "receptive field" of each C-node before training starts
because the inputs to C-node cannot be modified. The lower level modules have
smaller receptive fields while the higher level modules indicate complex
independent features present in the hidden layer. The spreading effect used in
neocognitron is shown in Figure 6-9.
Even if the cells are not directly connected with each other, they affect each other
indirectly due to propagation effects of the network dynamics. The CNN can be
implemented by means of a hardware model. This is achieved by replacing each
cell with linear capacitors and resistors, linear and nonlinear controlled sources,
and independent sources. An electronic circuit model can be constructed for a
CNN. The CNNs are used in a wide variety of applications including image
processing, pattern recognition and array computers.
Optical neural networks interconnect neurons with light beams. Owing to this
interconnection, no insulation is required between signal paths and the light rays
can pass through each other without interacting. The path of the signal travels in
three dimensions. The transmission path density is limited by the spacing of light
sources, the divergence effect and the spacing, of detectors. A$ a result, all signal
paths operate simultaneously, and true data rare results are produced. In
holograms with high density, the weighted strengths are stored.
96
Chapter 6: Special Networks
These stored weights can be modified during training for producing a fully adaptive
system. There are two classes of this optical neural network. They are:
1. electro-optical multipliers;
2. holographic correlators.
Figure 6-11 shows a system which can multiply a nine-element input vector by a
9 X 7 matrix, which
produces a seven-element NET vector. There exists a column of light sources that
passes its rays through a lens; each light illuminates a single row of weight shield.
The weight shield is a photographic film where transmittance of each square (as
shown in Figure 6-11) is proportional to the weight. There is another lens that
focuses the light from each column of the shield m a corresponding
photoelectron. The NET is calculated as
where NETk is the net output of neuron k; wik the weight from neuron i to neuron
k; xi the input vector
column of the weight matrix. The output vector set is equal to the produce of the
input vector with weight
97
SOFT COMPUTING TECHNIQUES
In holographic correlators, the reference images are stored in a thin hologram and
are retrieved in a coherently illuminated feedback loop. The input signal, either
noisy or incomplete, may be applied to the system and can simultaneously be
correlated optically with all the stored reference images. These. correlations can
be threshold and are fed back to the input, where the strongest correlation
reinforces the input image. The enhanced image passes around the loop
repeatedly, which approaches the stored image more closely on each pass, until
the system gets stabilized on the desired image. The best performance of optical
correlators is obtained when they are used for image recognition. A generalized
optical image recognition system with holograms is shown in Figure 6- 12.
98
Chapter 6: Special Networks
The system input is an image from a laser beam. This passes through a beam
splitter, which sends it to the threshold device. The image is reflected, then gets
reflected from the threshold device, passes back to the beam splitter, then goes to
lens 1, which makes it fall on the first hologram. There are several stored images
in first hologram. The image then gets correlated with each stored image. This
correlation produces light patterns. The brightness of the patterns varies with the
degree of correlation. The projected images from lens 2 and mirror A pass
through pinhole array, where they are spatially separated. From this array, light
patterns go to mirror B through lens 3 and then are applied to the second
hologram. Lens 4 and mirror C then produce superposition of the multiple
correlated images o1nto the back side of the threshold device.
The front surface of the threshold device reflects most strongly that pattern which
is brightest on its rear surface. Its rear surface has projected on it the set of four
correlations of each of the four stored images with the input image. The stored
image that is similar to the input image possesses highest correlation. This
reflected image again passes through the beam splitter and reenters the loop for
further enhancement. The system gets converged on the stored patterns most like
the input pattern.
As it is well known that the biological nervous system has inspired the
development of the artificial neural network models. On looking into the depth of
working of biological neurons, it is noted that the working of these neurons and
their computations are performed in temporal domain and the neuron firing
depends on the timing between the spikes stimulated in the neurons of the
brain. These fundamental biological understandings of the neuron operation lead
the pathway to the development of spiking neural networks (SNN). SNNs fall
under the category of third-generation neural networks and this is more closely
related to the biological counterparts compared to the first- and second-generation
neural networks. These developed spiking neural networks use transient pulses
for performing the computations and require communications within the layers of
the network designed. There exist different spiking neural models and their
classification is based on their level of abstraction.
99
SOFT COMPUTING TECHNIQUES
Moreover, SNNs add a new dimension, the temporal axis, to the representation
capacity and the processing abilities of neural networks. There are many different
models one could use to model both the individual spiking neurons and also the
nonlinear dynamics of the system. Neurons communicate with spikes, also known
as action potentials. Since all spikes art identical (1-2 ms of duration and 100 mV
of amplitude), the information is encoded by the liming of the spikes and not the
spikes themselves. Basically, a neuron is divided into three parts: the dendrites,
the soma and the axon. Generally speaking, the dendrites receive the input signals
from the previous neurons. The received input signals are processed in the soma
and the output signals are transmitted at the axon. The synapse is between every
two neurons; if a neuron j sends a signal across the synapse to neuron i, the
neuron that sends the signal is called pre-synaptic neuron and the neuron that
receives the signal is called post-synaptic neuron. Every neuron is surrounded by
positive and negative ions. In the inner surface of the membrane there is an excess
of negative charges and on the outer surface there is an excess of positive charges.
Those charges create the membrane potential.
u’= a(bv-u)
known neuronal firing patterns with the appropriate values for the variables a, b, c
and d.
1 The parameter a describes the time scale of the recovery variable u. Smaller
values result in slower recovery. A typical value is a = 0.02.
The IZ neuron uses voltage as its modelling variable. When the membrane
voltage v(f) reaches 30 mV, a spike is emitted and the membrane voltage and the
recovery variable are reset according to IZ neuron model equations. For I ms of
simulation, this model takes 13 FLOPS. Figure 7-2 illustrates the IZ neuron
model firing.
Fig- 6.14-The Izhikevich Spiking Neuron Model. In the top graph, there exists
the membrane potential of the neuron. In the middle graph, there is the
membrane recovery variable. Finally, the bottom plot represents the action
pre- synaptic spikes.
10
Chapter 6: Special Networks
The SNN with N neurons is assumed to be fully connected and hence the output
of each neuron I is connected to every other neuron. The synaptic strength of
these connections are given by the N x N matrix W where W[i, j] is the strength
between the output of neuron j and the input of neuron i. Thus W[i, :] represents
the synapses at the input of neuron i, whereas W[:, j] represents the synapse
values connected to the outputs of neuron j. Each neuron has its own static
parameters and varying state values. The set P represents the set of possible
constant parameters and I is the set of neuron states. The set of possible inputs to
the neurons is denoted by R. The neuron updated function f:(P, S, R) -> (S, [0,1 ])
takes input parameters as the neuronal states and inputs and produces the next
neuronal state and binary output.
Izhikevich used a random input for each neuron in the range N(0,1), a zero mean
and unit variance that is normally distributed. This input results in random
number of neurons firing each time, depending not only on the intensity of the
stimulus, but also on their randomly initialized parameters. After the input layer,
one or more layers are connected in a feed-forward fashion. A spike occurs
anytime the voltage reaches 30 mV. While the neurons communicate with spikes,
the input current Ii of the neuron i is equal to
𝐼𝑖𝑖 = ∑𝑛 𝑤𝑖𝑖𝑗𝑗 𝛿𝛿𝑗𝑗 + ∑𝑚 𝑤𝑘𝑘𝐼𝑘(𝑡)
𝑗𝑗=1 𝑘=1
When the input current signal changes, the response of the Izhikevich neuron also
changes, generating different firing rates. The neuron is responded during “T” ms
with an input signal and it gets fired when its membrane potential reaches a
specific value, generating an action potential (spike) or a train of spikes. The
firing rate is evaluated as
103
SOFT COMPUTING TECHNIQUES
Firing rate = 𝑇
Number of spikes
10
Chapter 6: Special Networks
In population encoding, analog input values are represented into spike times using
population coding. Multiple Gaussian receptive fields are used so that the input
neurons encode an input value into spike times. The firing time is computed
based on the intersection of Gaussian function. The center of the Gaussian
function is calculated using
with the variable interval of [𝐼min𝘍 𝐼max]. The parameter " 𝛽 " controls the
width of each Gaussian receptive field.
105
SOFT COMPUTING TECHNIQUES
Each SNN consists of a set of neurons (I, J), a set of edges (E ⸦ I x J), input
neurons i ⸦ I and output neurons j ⸦ J. For each non-input neuron, i ϵ I, with
threshold function Vth and potential u(t), each synapse {i, j} ϵ E will have a
response function εij and weight wij. The structures of neurons tend to be fully
connected feed forward neural network. The source neuron V will fire and
propagate spikes along all directions. Formally, a spike train is defined as a
sequence of pulses. Each target neuron w that receives a spike experiences an
increase in potential at time t, similar as wj,w . εj,w (i-t).
10
∫− 𝛿𝛿(𝑥)𝑑𝑥
Chapter 6: Special Networks
=1
−
. Every
pulse is taken as a single point in time. The objective is to train the desired target
107
SOFT COMPUTING TECHNIQUES
firing times {𝑡𝑓𝑓} and that of the actual firing times {𝑡𝑎}. The least mean squares
error function is chosen and is defined by
1 2
𝐸 = ∑ (𝑡𝛼 − 𝑡𝑓𝑓 )
2 𝑗𝑗∈𝑟
connection 𝑘 from neuron 𝑖𝑖 to 𝑗𝑗 with weight 𝑤𝑝∗. 𝜂𝜂 " is the learning rate
In error-back propagation algorithm, each synaptic terminal is taken as a separate
parameter. The basic weight adaptation functions for neurons in the output layer
hidden laver are given by
𝑖𝑖∈𝑡𝑗𝑗 𝑙 𝑝𝑝 𝛿𝛿𝑡𝑎
𝛿𝛿
𝐸 = −𝜂𝜂𝑦𝑦𝑖𝑖𝑘 (𝑡𝑎 ) ⋅ 𝛿𝛿𝑗𝑗
Δ𝑤𝑖𝑖𝑗𝑗𝑘 = −𝜂𝜂
𝛿𝛿𝑖𝑖𝑗𝑗𝑘 𝛿𝛿𝑗𝑗 (𝑡𝑎 )
𝛿𝛿𝑖𝑖 = 𝛿𝛿𝑡𝑤𝑎
𝛿𝛿𝑥 (𝑡 ) ∑𝑗𝑗∈𝑟𝑖𝑖 𝛿𝛿𝑡
𝛿𝛿𝑗𝑗
𝑖𝑖 𝑎 𝑎
Δ𝑤ℎ𝑖𝑖𝑘 = −𝜂𝜂𝑦𝑦ℎ𝑘 (𝑡𝑎 ) ⋅ 𝛿𝛿𝑗𝑗
The training process involves modifying the thresholds of the neuron firing and
synaptic weights. The algorithmic steps involved in learning through Spike-Prop
Algorithm are as follows:
Step 1: The threshold is chosen and the weights are initialized randomly
between 0 and 1.
Step 2: In feed-forward stage, each input synapse receives input signal and
transmits it to the next neuron (i.e., hidden units). Each hidden unit with
SNN function calculated is sent to the output unit which in return
calculates the spike function as the response for the given input. The firing
time of a neuron ta is found. The time to first spike of the output neurons is
compared with that of the desired time tfi of the first spike.
Step 3: Perform the error-back propagation learning process for all the layers. The
equations are transformed to partial derivatives and the process is carried
out.
104
Chapter 6: Special Networks
Step 4: Calculate δj using actual and desired firing time of each output neuron.
105
SOFT COMPUTING TECHNIQUES
Step 5; Calculate δi employing the actual and desired firing times of each hidden
neuron and δj values.
Step 6: Update weights: For output layer, calculate each change in weight.
layer.
Where Δt = (tpre – tpost) the time delay between the pre synaptic spike and the post
synaptic spike. If the pre-synaptic spike occurs before the post synaptic spike, the
weight of the synapse should be increased. If the pre synaptic spike occurs after
the post-synaptic spike, then the weight of the synapse gets reduced. STDP
learning can be used for Inhibitory or excitatory neurons.
layers like feed forward networks. CNN architecture is designed to possess the
107
SOFT COMPUTING TECHNIQUES
structure of a two-dimensional input image, that is, CNN's key advantage is that
its input consists of images and this representation of images designs the
architecture in a practical way. The neurons in CNN arc arranged in 3
dimensions: height, width, and depth. The information pertaining to "depth" is an
activation volume and it represents the third dimension. This architectural design
of CNN is carried out with the local connections and possesses weights which art
subsequently followed by certain pooling operations. CNN’s can be trained in an
easy manner and these have minimal parameters for the same number of hidden
units than that of the other fully interconnected networks considered for
comparison, figure 7-3 shows the arrangement of neurons in three dimensions in
a convolutional neural network. As a regular neural network, the convolutional
neural network is also made up of layers, and each and every layer transforms an
input 3D volume to an output 3D volume along with certain differentiable
activation functions with or without any parameters.
It is well noted that the convolutional neural network is a sequence of layers and
each and every layer in CNN perform transformation of one volume activations to
the other by employing a differentiable function. CNN consists of three major
layers:
1. Convolutional layer
2. Pooling layer
3. Fully interconnected layer (regular neural models like perceptron and BPN)
These layers exist between the input layer and output layer Input layer holds the
input values represented by the pixel values of an image. Convolutional layer
performs computation and determines output of a neuron that is connected to
local
106
Chapter 6: Special Networks
regions in the input. The computation is done by performing dot product between
their weights and a small region that is connected to the input volume. After then,
an element wise activation function is applied wherein the threshold set to zero.
Applying this activation function results no change in the size of the volume of
the layers Pooling layer carries out the down sampling operation along with the
spatial dimensions including width and height Regular fully connected layers
perform computation of the class scores (belongs to the class or nut) and result m
a specified volume size. In this manner, convolutional neural networks transform
the original input layer by laser and result in the final scores. Pooling layer
implements only a died function whereas convolutional and fully interconnected
layer implements transformation on functions and as well on the weights and
biases of the neurons.
107
SOFT COMPUTING TECHNIQUES
108
Chapter 6: Special Networks
CNN b nude up of the three individual layers and this subsection presents the
details on designing each of these lasers specifying their connectivities and hyper
parameters.
In CNN network model, at the convolutional layer, each neuron gets connected
only to a local region of the input volume. The spatial extent of this neuronal
109
SOFT COMPUTING TECHNIQUES
With respect to the number of neurons in the output volume, three hyper-
parameters are noted to control the size of the output volume - depth, stride and
zero-padding. The depth of the output volume refers to the number of filters to be
used, wherein each learning searches the existence of difference in the input. The
stride is to be specified for sliding the filter.
strides
The movement of the filter is specified by the above equation. This representation
of the strides results in smaller output volumes spatially. At times it is required to
pad the input volume with zeros around the border, hence, the other hyper-pa-
rameter is the size of this zero-padding. Zero-padding allows controlling the
spatial size of the output volumes. It should be noted that if all neurons presented
in the single depth slice employ the same weight vector, then in every depth slice,
the forward pass of the convolutional layer can be computed as the convolution of
the neuronal weights with that of the input volume. Thus, the sets of weights are
referred in CNN as filter that gets convolved with the input. The limitation of this
approach is that it uses lots of memory, as certain values in the input volume arc
generated repeatedly for multiple times.
110
Chapter 6: Special Networks
1 will
111
SOFT COMPUTING TECHNIQUES
Between the successive convolutional layers, pooling layers are placed. The
presence of pooling layer between the convolutional layers is to gradually
decrease the spatial size of the parameters and to reduce the computation in the
network. This placement of pooling layer also controls the occurrence of over
fitting. The pooling layer works independently on depth slice of the input as well
as resizes them spatially. Commonly employed pooling layer is the one with the
filter size of 2 x 2 applied with a stride of 2 down samples. The down sampling
occurs for every depth slice in the input by 2 along the height and width. The
dimension of the depth parameter remains unaltered in this case. Pooling sizes
with higher receptive fields are noted to be damaging. Generally used pooling
mechanism is the “max pooling”.
Apart from this operation, the pooling layer can also perform functions like mean
pooling or even L2-norm pooling. In the backward pass of a pooling layer, the
process is only to route the gradient to the input that possessed the highest value
in the forward pass. Hence, at the time of forward pass of the pooling layer, it is
important to track the index of the activation function (probably “max”) so that
the gradient routing is carried out effectively by a back-propagation network
algorithm.
The main difference between the fully connected and the convolutional layer is
that the neurons present in the convolutional layer get connected only to a local
region in the input and the neurons in the convolutional voluminous structure
share their parameters. The neurons in both fully connected and convolutional
112
Chapter 6: Special Networks
layers calculate the dot products and hence their functional form remains the
same. Therefore it is
113
SOFT COMPUTING TECHNIQUES
possible to perform conversion between the fully connected and the convolutional
layers.
Considering any convolutional layer, there exists a fully connected layer which
implements one and the same forward pass function. The weight matrix will be a
large one and possesses zero entities except at specific blocks (no self-connection
and existence of local connectivity') and the weights in numerous blocks tend to
be equal (parameter sharing). Also, fully connected layer can be converted into
convolutional layer; here the filter size will be set equal to the size of the input
volume and the output will be a single depth column fit across the input volumes.
This gives the same result as that of the initial fully connected layer. In both these
conversions, the process of converting a fully connected layer to a convolutional
layer is generally in practice.
1. The input layer should be designed in such a way that it should be divisible
by 2.
2. The convolutional layer should employ small size filters, specifying the
stride. The convolutional layer should not alter the spatial dimensions of
the input.
3. The pooling layer down samples the spatial dimensions of the input.
Commonly used pooling is the max-pooling with a 2 x 2 receptive fields
and a stride of 2. Receptive field size is accepted until 3x3 and if it exceeds
above 3, the pooling becomes more aggressive and tends to lose
information. This results in poor performance of the network.
From all the above, it is clearly understood that the convolutional layers preserve
the spatial size of their input. On the other hand, the pooling layers are
responsible for down sampling the volumes spatially. Alternatively, if strides
greater than 1 or zero-padding are not done to the input in convolutional layers,
then it is very important to track the input volumes through the entire CNN
architecture and ensure that all the strides and filters work in a proper manner.
Smaller strides are generally better in practice. Padding actually improves the
performance of the network. When the convolutional layer does not zero-pad
the inputs and only
114
Chapter 6: Special Networks
performs authenticate convolutions, then the volume size will reduce by a smaller
amount after each convolution process.
In the past few years, there were numerous CNN models developed and
implemented for various applications. Few of them include
1. LeNet: The first convolutional neural network model named after the
developer LeCun. It is applied to read zip codes, digits and so on.
3. ZFNetf: It was developed in the year 2013 by Zeiler and Fergus and hence
named as ZFNet. In this network model, the convolutional layers in the
middle are expanded and the stride and filter size are made smalt in the first
layer.
4. VGGNet: It was modeled in the year 2014 by Karen and Andrew. It has
phenomenal impact on the depth of the network and it was noted that depth
of network parameter plays a major role for better performance.
5. GoogLeNet It was developed in the year 2014 from Google by Szegedy and
team. This net contributed an Inception module wherein the numbers of
parameters in the model are reduced. This network employs mean pooling
instead of fully connected layers at the top of the convolutional network. As
a result, more number of parameters arc eliminated in this case.
6. ResNet: It was modeled in the year 2015 by Kaiming and team, and hence
called as Residual Network. This network is the default convolutional
neural network. It employs batch normalization and the architecture also
docs not consider fully connected layers at the end of the network.
115
SOFT COMPUTING TECHNIQUES
The prominent researcher behind the concept of deep learning neural networks is
Professor Hinton from University of Toronto who managed to develop a special
program module for constituting the formulation of molecules to produce an
effective medicine. Minton's group employed deep learning artificial intelligence
methodology to locate the combination of molecules required for the composition
of medicine with very limited information on source data. Apple and Google have
transformed themselves with deep learning concepts and this can be noted
through Apple Siri and Google Street view, respectively.
The learning process in deep learning neural network takes place in two steps. In
the first step, the information about the input data’s internal structure is obtained
from the existing large array of unformatted data. This extraction of the internal
structure is carried out by an auto-associator unit via unsupervised training layer-
116
Chapter 6: Special Networks
by-layer, then the formatted data obtained from the unsupervised multi-layer
neural network gets processed through a supervised network module employing
the already available neural network training methods. It is to be noted that the
amount of unformatted data should be as large as possible and the amount of
formatted data can be smaller in size (but this need not be an essential criteria).
6.14.1. Network Model and Process Flow of Deep Learning Neural Network
The growth of deep learning neural networks is its deep architecture that contains
multiple hidden layers and each hidden layer carries out a non-linear
transformation between the layers. DLNNs get trained based on two features:
Ev = fΘ (xv)
The reconstruction operation is carried out at the decoder neural network and its
function is given by “gΘ". This reconstruction function maps the data set “xv”
from the low-dimensional space into the high-dimensional space. The
reconstructed form is given by
𝑥̂ v = gθ(Ev)
the reconstruction error E(x, 𝑥̂ ) for that many numbers of training samples. E(x,
The ultimate goal of these encoder and decoder neural networks is to minimize
117
SOFT COMPUTING TECHNIQUES
1
𝐸 (xv,g’θ(fΘ (xv)))
∑𝑁
δae(θ,θ’) =
𝑁 𝑣=1
The encoding and decoding functions of the DLNN will be present along with a
non-linearity and are given by
gΘ (x) = faf_d
(b+WxT)
Where faf_e and faf_d refer to the encoder activation function and the decoder
activation function, respectively, “b" indicates the bias of the network, and W and
WT specify the weight matrices of the DLNN model.
E(x, 𝑥̂ ) =|| x- 𝑥̂ ||
In order to carry out the pre-training of a DLNN model, the “N" auto-encoders
developed in previous module should be stacked. For the given input signal xv
input layer along with the first hidden layer of DLNN arc considered as the
encoder neural network of the first auto-encoding process. When the first auto-
encoder is noted to be trained by minimizing the reconstruction error, the first
trained parameter set θ1, of the encoder neural network is employed to initialize
the first hidden layer of the DLNN and the first encode vector is obtained by
E1v = fΘ (xv)
Now, the input data becomes the encode vector E 1v. The first and second hidden
layers of the DLNN are considered as the encoder neural network for the second
auto-encoder. Subsequently, the second hidden layer of the DLNN gets initialized
by that of the second trained auto-encoder. This process gets continued upto the
N- th auto-encoder that gets trained for initializing the final hidden layer of the
[Link] model. The final or the N-th encode vector in generalized form for the
vector xv is obtained by
ENv = fΘ (EvN-1)
where “θN” denotes the Nth trained parameter set of the encoder neural network.
Thus, in this way, all the DLNN s hidden layers get pre trained by means of the N
stacked auto encoders. It is well noted that the process of pre-training avoids local
minima and improves generalization aspect of the problem under consideration.
118
Chapter 6: Special Networks
Figure 7-5 shows the fundamental architecture of the deep learning neural
network.
119
SOFT COMPUTING TECHNIQUES
The above completes the pre-training process of DLNN and the next process is
𝑦𝑣 = 𝑓𝑓𝜃𝜃 (𝐸′ )
𝑣 N
where 𝜃𝜃𝑁+1 denotes the trained parameter set of the output layer. Here.
back propagation network (BPN) algorithm is employed for minimizing the error
case the output target of 𝑥𝑥 is 𝑡2, then the error criterion is given by
of the output by carrying out the parameter adjustments in DLNN backwards. In
1 ∞
MSE (Ψ ) = ′
∑ 𝐸(𝑦∗, 𝑡∗)
𝑁
⋯1
where Ψ =∣ 𝜃𝜃1 , 𝜃𝜃2 , 𝜃𝜃1 , … , 𝜃𝜃𝑁+1 }
120
Chapter 6: Special Networks
Step 2: Obtain the training data sets to feed into the DLNN model and initialize
the necessary parameters.
Step 5: Initialize i-th hidden layer parameter of DLNN employing the parameters
of the auto encoder.
Step 6: Check whether “i” is greater than “N". If no carry out step 4; if yes go to
the next step.
Step 8: Fine tune the parameters of DLNN through the BBN algorithm.
Step 9: With the final fine-tuned DLNN model go to the next step.
achieved.
Step 12: Stop the process on meeting termination condition. The termination
condition is the number of iterations or reaching the minimal mean square
error.
Encoders are built so as to receive the possible exact configuration of the input at
the output end. These encoders belong to the category of auto associator neural
units, Auto associator modules, are designed to perform the generating part as
well as the synthesizing part. Encoders discussed in this section belong to the
synthesized module of auto associator and tor the generation part, a variation of
Boltzmann machine as presented in special networks.
An auto encoder is configured to be all open layer neural network Auto encoder
for its operation sets its target value equal to that of the Input vector. A model of
an auto encoder is as shown in figure 7.6. The encoder model attempts to find
approximation of a defined function authenticating that the feedback of a neural
121
SOFT COMPUTING TECHNIQUES
122
Chapter 6: Special Networks
parameters. The encoder is also capable of compressing the data once the given
input signal gets passed to that of the output of the network. The compression is
possible in an auto encoder if there exists hidden interconnections or a sort of
characteristics correlation. In this manner, auto encoder behaves m a similar
manner as the principal component analysis and achieves data reduction (possible
compression) in the input side.
On the other hand, when the auto encoder is trained with the stochastic gradient
descent algorithm and the where the number of hidden neurons becomes greater
than the number of inputs, it results in the possible decrease in the error values.
So, it is applied for various function analysis and compression applications
123
SOFT COMPUTING TECHNIQUES
Another variation in the encoder configuration is the denoting auto encoder. Here,
the variation exists in the training process. On training the deep learning neural
network for denoising encoder, corrupted or denoised data (substituted wiih “0"
values) can be given as input. further to this, during the same time, the coned data
can be compared with that of the output data. The advantage of this mechanism is
that it paves way to restore the damaged data.
124
Chapter 6: Special Networks
∂𝑖𝑖 = [∂𝑖𝑖1 , ∂𝑖𝑖2 , ∂𝑖𝑖3 , … , ∂𝑖𝑖𝑛 ]𝑇 − weight vector that connects 𝑖𝑖 th hidden
neuron and output neurons
The fact that a regular single-layer feed forward neural network with 𝑁 hidden
neurons, each with activation function 𝑓𝑓(𝑥), approximates 𝑁 training samples
with zero error, meaning
∑ ∥𝑂𝑗𝑗 − 𝑇𝑗𝑗∥ = 0
𝑖𝑖=1
𝑁ˆ
𝐻∂=𝑇
Where
1
and 𝑇 […
∂=[ …
⋯ = ]
] 𝑡𝐼
…
∂ 𝑇
𝑁 𝑖𝑖,𝑚 𝑖𝑖 𝑁‾ …𝑚
125
SOFT COMPUTING TECHNIQUES
126
Chapter 6: Special Networks
The related works carried out by Huang in the year 2004 biases tiated that single-
layer feed forward neural network with randomly assigned input weights, hidden
laser biases and non-zero actuation function universally appropriates any
continuous function on any input data sets. Hung also suggested that an
alternative way for training single-layer feed forward neural network is by finding
a least square solution ∂’ of the linear system given by equation H∂ = T. The
unique minimum norm least square solution is given by
∂ = H+T
For a given training vector pair 𝑁 = {(𝑥, 𝑡)}, with 𝑥1 ∈ 𝑅𝑛, 𝑡𝑖𝑖 ∈ 𝑅𝑚, 𝑖𝑖 = 1,
… , 𝑁, activation function 𝑓𝑓(𝑥) and hidden neuroa 𝑁ˆ , the algorithm is as
follows:
𝐻 = 𝑓𝑓 ⋅ (𝑥 ⊕ 𝑤 + 𝑏)
127
SOFT COMPUTING TECHNIQUES
∂˙ = 𝐻 ∗ 𝑇
Huang initially proposed ELM in the year 2004 and subsequently numerous
researchers worked on ELM and developed certain improved ELM algorithms.
ELM was enhanced over the years to improve the network training speed, to
avoid local and global minima, to reduce iteration time, to overcome the difficulty
in defining learning rale parameters and setting the stopping criteria.
ELM is well noted for solving regression and classification problems; it results in
better generalization performance and training speed. When considering ELM for
real applications which involve minimal data set, it may result in over-fitting
occurrences.
ELM is well known for its short training time and here the number of hidden
layer nodes are randomly selected and are analyzed for determination of their
128
Chapter 6: Special Networks
respective weights. This minimizes the calculation time with fast learning. Rong
in the year
129
SOFT COMPUTING TECHNIQUES
ELM requires more number of hidden neurons due to its random computation of
input layer weights and hidden biases. Owing on this, certain hybrid ELM
algorithms were developed by researchers to improve the generalization
capability. One of the method proposed by Zhu (2005) employs differential
evolution (DE) algorithm for obtaining the input weights and Moore-Penrose
(MP) inverse to obtain the output weights of an ELM model. Several researchers
also attempted to combine ELM with other data processing methods resulting in
new ELM learning models and applying the newly developed algorithm for
related applications.
130
Chapter 6: Special Networks
few
131
SOFT COMPUTING TECHNIQUES
of the variants of ELM models as developed by the researchers and applied for
various prediction and classification problems.
1. Signal processing
2. Image processing
3. Medical diagnosis
4. Automatic control
132
Chapter 7: Introduction to Fuzzy Logic and
Fuzzy
Unit IV
7
INTRODUCTION TO FUZZY LOGIC
AND FUZZY
Unit Structure
7.0 Objectives
7.1 Introduction to Fuzzy Logic
7.2 Classical Sets
7.3 Fuzzy Sets
7.4 Classical Sets v/s Fuzzy Sets
7.4.1 Operations
7.4.2 Properties
7.5 More Operations on Fuzzy Sets
7.6 Functional Mapping of Classical Sets
7.7 Introduction to Classical Relations & Fuzzy Relations
7.8 Cartesian Product of the Relation
7.9 Classical Relation v/s Fuzzy Relations
7.9.1 Cardinality
7.9.2 Operations
7.9.3 Properties
7.10 Classical Composition and Fuzzy Composition
7.10.1 Properties
7.10.2 Equivalence
7.10.3 Tolerance
7.11 Non-Interactive Fuzzy Set
7.12 Summary
7.13 Review Questions
7.14 Bibliography, References and Further Reading
125
SOFT COMPUTING TECHNIQUES
7.0 Objectives
We begin this chapter with introducing fuzzy logic, classical sets and fuzzy sets
followed by the comparison of classical sets and fuzzy sets.
“As the complexity of a system increases, it becomes more difficult and eventually
impossible to make a precise statement about its behavior, eventually arriving at
a point of complexity where the fuzzy logic method born in humans is the only
way to get at the problem” – Originally identified & set forth by Lotfi A. Zadeh,
Ph.D., University of California, Berkeley.
The theory of fuzzy logic is based upon the notion of relative graded membership
and so are the functions of cognitive processes. It models uncertain or ambiguous
data & provides suitable decision. Fuzzy sets that represents fuzzy logic provides
means to model the uncertainty associated with vagueness, imprecision & lack of
information regarding a problem or a plant or system.
Fuzzy logic operates on the concept of membership. The basis of the theory lies
in making the membership function lie over a range of real numbers from 0.0 to
1.0. The fuzzy set is characterized by (0.0,0,1.0). The membership value is “1” if
it belongs to the set & “0” if it not member of the set. The membership in the set
is
126
Chapter 7: Introduction to Fuzzy Logic and Fuzzy
1 𝑥 ∈𝐴
found to be binary, that is, either the element is a member of a set or not. It is
𝜒𝜒 (𝑥) = {
indicated as
A 0, 𝑥 ∉ 𝐴
E.g. The statement “Elizabeth is Old” can be translated as Elizabeth is a
𝜇(𝑂𝐿𝐷) 𝜇
member of the set of old people and can be written symbolically as
where is the membership function that can return a
value between 0.0 to 0.1 depending upon the degree of the membership.
Figure 7.2: Graph showing membership functions for fuzzy set “tall”.
𝐷𝑒𝑔𝑟𝑒𝑒𝑠}
127
SOFT COMPUTING TECHNIQUES
Fuzzy sets tend to capture vagueness exclusively via membership functions that
are mappings from a given universe of discourse X to a unit internal containing
membership value. The membership function for a set maps each element of the
set to membership value between 0 & 1 and uniquely describes that set. The
values
0 and 1 describes “not belonging to” & “belonging to” a conventional set,
respectively; values in between represent “fuzziness”. Determining the
membership function is subjective to varying degree depending on the situation.
It depends on an individual’s perception of the data in question and does not
depend on randomness.
Fuzzy logic also consists of fuzzy inference engine or fuzzy rule base to perform
approximate reasoning somewhat similar to human brain. The fuzzy approach
uses a premise that human don’t represent classes of objects as fully disjoint sets
but rather as sets in which there may be graded of membership intermediate
128
Chapter 7: Introduction to Fuzzy Logic and Fuzzy
between
129
SOFT COMPUTING TECHNIQUES
full membership and non-membership. A fuzzy set works as a concept that makes
it possible to treat fuzziness in a quantitative manner. Fuzzy sets form the
building blocks for fuzzy IF-THEN rules which have general form “IF X is A
THEN Y is B” where A and B are fuzzy sets.
The term “fuzzy systems” refers mostly to systems that are governed by fuzzy IF-
THEN rules. The IF part of an implication is called antecedent whereas the
THEN part is called consequent. The fuzzy system is a set of fuzzy rules that
converts inputs to outputs.
The fuzzy inference engine (algorithm) combines fuzzy IF-THEN rules into a
mapping from fuzzy sets in the input space X to the fuzzy sets in the output space
Y based fuzzy logic principles. From a knowledge representation viewpoint, a
fuzzy IF-THEN rule is a scheme for capturing knowledge that involves
imprecision. The main features of the reasoning using these rules is its partial
matching capability, which enables an inference to be made from a fuzzy rule
even when the rule’s condition is partially satisfied. Fuzzy systems, on one hand
is rule based system that are constructed from a collection of linguistic rules, on
other hand, fuzzy systems are non-linear mappings of inputs to the outputs. The
inputs and the outputs can be numbers or vectors of numbers. These rule-based
systems can in theory model any system with arbitrary accuracy, i.e. they work as
universal approximation.
The Achilles’ heel of a fuzzy system is it rules; smart rules gives smart systems
and other rules give less smart or dumb systems. The number of rules increases
exponentially with the dimension of the input space. This rule explosion is called
the curse of dimensionality & is general problem for mathematical models.
Collection of objects with certain characteristics is called set. A classical set/ crisp
set is defined as the collection of distinct objects. An individual entity of the set is
called as element/ member of the set. The classical set is defined in such a way
that the universe of discourse is splitted into two groups: members and non-
members. Partial membership does not exist in the case of crisp set.
Whole set: The collection of elements in the universe
Cardinal number: Number of the elements in the set.
Set: The collections of elements within the universe
Subset: The collections of elements within the set.
130
Chapter 7: Introduction to Fuzzy Logic and Fuzzy
𝐴 = {(𝑥, 𝜇𝐴(𝑥)|𝑥 ∈ 𝑈}
is given by
where
𝜇𝐴(𝑥)is the degree of membership of x in A and it indicates
the degree that x belongs to A. The membership is set to unit
interval [0,1] or 𝜇𝐴(𝑥) ∈ [0,1]. When the universe of disclosure is
discrete & finite, fuzzy set A is given as
When the universe of disclosure is continuous & infinite, fuzzy set A is given as
Universal Fuzzy Set/ Whole Fuzzy Set: If and only if the value of the
membership function is 1 for all the members under consideration. Any fuzzy set
A is defined on universe U is the subset of that universe.
Empty Fuzzy Set: If and only if the value of the membership function is 0 for all
the members under consideration.
𝜇𝐴(𝑥) = 𝜇𝐵(𝑥) 𝑥 ∈𝑈
Equal Fuzzy Set: two fuzzy set A & B are said to be equal fuzzy sets if
for all
Fuzzy Power set P(U): The collection of all fuzzy sets and fuzzy subsets on
universe U.
131
Chapter 7: Introduction to Fuzzy Logic and Fuzzy
𝐴 = {(𝑥, 𝜇𝐴(𝑥)|𝑥 ∈
x
𝑈}
belongs to A.
= max{𝜇𝐴(x), 𝜇B(x)}
The union is termed as logical
𝑓𝑓𝑜𝑟 𝑎𝑙𝑙
OR operation.
∈𝑈
𝐴𝖴𝐵
V indicates max operation
= { 𝑥| 𝑥 ∈ 𝐴 𝑜𝑟 𝑥 ∈
𝐵}
Intersection The intersection between two The intersection of fuzzy sets
sets gives all those elements in A & B is defined as:
𝜇𝐴 𝐵 (x) = 𝜇𝐴(x) 𝖠
∩
the universe that belong to
𝜇B(x)
both set A and set B. The union
= min{𝜇𝐴(x), 𝜇B(x)}
is termed as logical AND
𝑓𝑓𝑜𝑟 𝑎𝑙𝑙 𝑥 ∈ 𝑈
operation.
𝐴∩𝐵
= { 𝑥| 𝑥 ∈ 𝐴 𝑎𝑛𝑑 𝑥 ∈ 𝖠 indicates min operation
𝐵}
Complement The complement of set A is The union of fuzzy sets A &
defined as the collection of all B is defined as:
𝜇Ā (x) = 1 −
elements in the universe X
𝜇𝐴 (X)𝑓𝑓𝑜𝑟 𝑎𝑙𝑙 𝑥 ∈ 𝑈
that do not belong to set A.
Ā = { 𝑥| 𝑥 ∉ 𝐴, 𝑥 ∈
𝑋𝑋}
131
SOFT COMPUTING TECHNIQUES
7.4.2 Properties
Commutativity 𝐴 𝖴 𝐵 = 𝐵 𝖴 𝐴 𝐴𝖴𝐵 =𝐵 𝖴𝐴
Classical Sets Fuzzy Sets
𝐴∩𝐵=𝐵 ∩𝐴 𝐴∩𝐵=𝐵 ∩𝐴
𝐴 𝖴 (𝐵 𝖴 𝐶) = (𝐴 𝖴 𝐵) 𝐴 𝖴 (𝐵 𝖴 𝐶) = (𝐴 𝖴 𝐵)
𝖴𝐶 𝖴𝐶
Associativity
𝐴 ∩ (𝐵 ∩ 𝐶) = (𝐴 ∩ 𝐵) 𝐴 ∩ (𝐵 ∩ 𝐶) = (𝐴 ∩ 𝐵)
∩𝐶 ∩𝐶
Distributivity 𝐴 𝖴 (𝐵 ∩ 𝐶) = (𝐴 𝖴 𝐴 𝖴 (𝐵 ∩ 𝐶) = (𝐴 𝖴
𝐵 ) 𝐵)
∩ (𝐴 𝖴 𝐶) ∩ (𝐴 𝖴 𝐶)
𝐴 ∩ (𝐵 𝖴 𝐶) = (𝐴 ∩ 𝐴 ∩ (𝐵 𝖴 𝐶) = (𝐴 ∩
𝐵) 𝐵)
𝖴 (𝐴 ∩ 𝐶) 𝖴 (𝐴 ∩ 𝐶)
Idempotency 𝐴 𝖴 𝐴=𝐴 𝐴 𝖴 𝐴=𝐴
𝐴∩𝐴=𝐴 𝐴∩𝐴=𝐴
𝑖𝑖𝑖𝑖 𝐴 ⊆ 𝐵 ⊆ 𝐶 𝑡ℎ𝑒𝑛 𝐴 𝑖𝑖𝑖𝑖 𝐴 ⊆ 𝐵 ⊆ 𝐶 𝑡ℎ𝑒𝑛 𝐴
⊆𝐶 ⊆𝐶
Transitivity
𝐴 𝖴 ɸ = 𝐴; 𝐴 ∩ ɸ = 𝐴 𝖴 ɸ = 𝐴; 𝐴 ∩ ɸ = 𝐴
𝐴
Identity
𝐴 𝖴 𝑋𝑋 = 𝑋𝑋; 𝐴 ∩ 𝑋𝑋
𝐴 𝖴 𝑋𝑋 = 𝑋𝑋; 𝐴 ∩ 𝑋𝑋 = =𝐴
𝐴
Ā= Ā=
𝐴 𝐴
Involution
(double
| 𝐴 𝖴 𝐵| = 𝐴 𝖴 𝐵 | 𝐴 𝖴 𝐵| = 𝐴 𝖴 𝐵
negation)
|𝐴 ∩ 𝐵| = 𝐴 ∩ 𝐵 | 𝐴 ∩ 𝐵| = 𝐴 ∩ 𝐵
DeMorgan’s
Law
Law of 𝐴∩Ā=ɸ Not Followed
Contradiction
132
𝐴 𝖴 Ā = 𝑋𝑋
Chapter 7: Introduction to Fuzzy Logic and Fuzzy
133
SOFT COMPUTING TECHNIQUES
Algebraic Product: The algebraic product (A.B) of two fuzzy sets A & B is
.
Bounded Sum: The bounded sum (𝐴 ⊕ 𝐵) of two fuzzy sets A & B is defined as
𝜇𝐴 𝐵 (x) = min {1, 𝜇𝐴(x) + 𝜇B(x)}
⊕
Bounded Difference: The bounded difference (𝐴 ⊕ 𝐵) of two fuzzy sets A &
B is defined as
𝑓𝑓 : 𝑋𝑋 → 𝑌
corresponds to an element y contained Y, it is called as mapping from X to Y; i.e.
Let A & B be two sets on universe. The function theoretic forms of operation
performed between these two sets are given as follows:
Union: 𝜒𝜒𝐴 𝐵 (x) = 𝜒𝜒𝐴 (X) ∨ 𝜒𝜒B (X) = max{𝜒𝜒𝐴 (X), 𝜒𝜒B (X)} Here
𝖴 operator.
∨ is maximum
𝜒𝜒𝐴 𝐵 (x) = 𝜒𝜒𝐴 (X) 𝖠 𝜒𝜒B (X) = min{𝜒𝜒𝐴 (X), 𝜒𝜒B (X)}
Here 𝖠 ∩
Intersection:
is minimum operator.
134
Chapter 7: Introduction to Fuzzy Logic and Fuzzy
Relationship between the object are the basic concepts involved in decision
making & other dynamic system application. Relations represent mapping
between sets & connective logic. A classical binary relation represents the
presence or absences of connection or interaction or association between the
elements of two sets. Fuzzy binary relations impart degrees of strength to
connections or association. In fuzzy binary relation, the degree of association is
represented by membership grades in the same way as the degree of set
membership is represented in fuzzy set.
When r = 2, the relation is a subset of the Cartesian product A1*A2. This relation
𝜒𝜒𝛸𝛸 𝑌 1, (𝑥, 𝑦) ∈ 𝛸𝛸 ∗ 𝑌
∗ (𝑥, 𝑦) = 0,
{ (𝑥, 𝑦) ∉ 𝛸𝛸 ∗ 𝑌
A binary relation in which each element from the first set X is not mapped to
𝑅: 𝛸𝛸 →
more than one element in second set Y is called a function and is expressed as
A fuzzy relation is a fuzzy set defined on the Cartesian product of classical set
{X1,X2,X3,…Xn} where tuples (x1,x2,…,xn) may have varying degree of
135
SOFT COMPUTING TECHNIQUES
136
Chapter 7: Introduction to Fuzzy Logic and Fuzzy
This links are labelled with membership value as [𝜇𝑅(𝑥, 𝑦)]. When 𝑋𝑋 ≠
membership grades in R(X,Y). The links may also be present in the forms of arcs.
𝑌 , the link connecting the two nodes is an undirected binary graph called as
𝐛𝐛𝐛𝐛
𝑌, a node is connected to itself and directed links are used; in such case, the
fuzzy graph is called directed graph. Here, only one set off nodes corresponding
to set X is used.
The domain of binary fuzzy relation R(X,Y) is the fuzzy set, dom R(X,Y)
having the membership function as:
The range of binary fuzzy relation R(X,Y) is the fuzzy set, ran R(X,Y) having
the membership function as:
135
SOFT COMPUTING TECHNIQUES
If all the ar’s are identical and equal to A, then the Cartesian product
r
A1*A2*A3*….*Ar is denoted as A
7.9.1 Cardinality
𝑛 𝑛
*Y) describing the relation is given by
𝑛𝑃(𝑋𝑋 ∗ 𝑌) = 𝑋𝑋 ( )𝑌
2
7.9.2 Operations
relation and the complete relation are defined by the relation matrices 𝜙𝜙𝑅 𝑎𝑛𝑑
Let R & S be two separate relations on the Cartesian universe X * Y. The null
𝐸 .
𝑅
136
Chapter 7: Introduction to Fuzzy Logic and Fuzzy
137
SOFT COMPUTING TECHNIQUES
≤ 𝜒𝜒𝑆(𝑥, 𝑦)
Identity 𝜙𝜙 → 𝜙𝜙𝑅 & 𝑋𝑋 → 𝐸𝑅
Inverse The inverse of fuzzy relation R on
-1
X*Y is denoted by R .
It is relation on Y*X defined by
-1
(𝑦, 𝑥) ∈ 𝑌 ∗ 𝑋𝑋
R (y,x)= R(x,y) for all pairs
of R onto Y.
7.9.3 Properties
138
Chapter 7: Introduction to Fuzzy Logic and Fuzzy
Commutativity Commutativity
Associativity Associativity
Distributivity Distributivity
Involution Involution
Idempotency Idempotency
DeMorgan’s Law DeMorgan’s Law
Excluded middle law
139
SOFT COMPUTING TECHNIQUES
1. Max-Min Composition: 𝑇 = 𝑅 ∘ 𝑆
2. Max-product Composition: 𝑇 = 𝑅 ∘ 𝑆
Let A be fuzzy set on universe X & B be fuzzy set on universe Y. The Cartesian
For e.g., for a fuzzy set A that has three elements and a fuzzy set B has four
elements, the resulting fuzzy relation R will be represented by a matrix size 3 * 4
140
Chapter 7: Introduction to Fuzzy Logic and Fuzzy
Let R be fuzzy relation on Cartesian space X*Y and S be fuzzy relation on Cartesian
Space Y*Z.
7.10.1 Properties
7.10.2 Equivalence
𝑥𝑥𝑥) ∈ 𝑅 ∈ 𝑋𝑋
Reflexivity
𝑥𝑥𝑥)
∈𝑅
𝜒𝜒𝑅(𝑥𝑥𝑥, 𝑥𝑥𝑥) 𝑎𝑛𝑑 𝜒𝜒𝑅(𝑥𝑥𝑥, 𝜇𝑅(𝑥𝑥𝑥, 𝑥𝑥𝑥)
𝑥𝑘)
=⋋ 1 𝑎𝑛𝑑𝜇𝑅(𝑥𝑥𝑥, 𝑥𝑘)
Transitivity = 1, 𝑠𝑜 𝜒𝜒𝑅(𝑥𝑥𝑥, 𝑥𝑘) = =⋋ 2
1(𝑥𝑥𝑥, 𝑥𝑥𝑥) ⟹ 𝜇𝑅(𝑥𝑥𝑥, 𝑥𝑘) =⋋
∈ 𝑅(𝑥𝑥𝑥, 𝑥𝑘) ∈ 𝑅, 𝑠𝑜 𝑤ℎ𝑒𝑟𝑒
(𝑥𝑥𝑥, 𝑥𝑘) ⋋= min (⋋ 1,⋋ 2)
141
SOFT COMPUTING TECHNIQUES
∈𝑅
142
Chapter 7: Introduction to Fuzzy Logic and Fuzzy
7.10.3 Tolerance
Classical Composition Fuzzy Composition
A tolerance relation R1 on universe X A binary fuzzy relation that
is one where the only the properties of possesses the properties of
reflexivity & symmetry are satisfied. reflexivity and symmetry is called
fuzzy tolerance relation or
resemblance relation.
The tolerance relation can also be called The equivalence relations are a
proximity relation. special case of the tolerance relation.
An equivalence relation can be formed The fuzzy tolerance relation can be
from tolerance relation R1 by (n-1) reformed into fuzzy equivalence
compositions with itself, where n is the relation in the same way as a crisp
cardinality of the set that defines R1, tolerance relation is reformed into
here it is X crisp equivalence relation
where
143
SOFT COMPUTING TECHNIQUES
7.12 Summary
In this chapter, we have discussed the basic definitions, properties and operations
on classical sets and fuzzy sets. Fuzzy sets are tools that convert the concept of
fuzzy logic into algorithms. Since fuzzy sets allow partial membership, they
provide computer with such algorithms that extend binary logic and enable it to
take human-like decisions. In other words, fuzzy sets can be thought of as a
media through which the human thinking is transferred to a computer. One
difference between fuzzy sets and classical sets is that the former does not follow
the law of excluded middle and law of contradiction.
The relation concept is used for nonlinear simulation, classification, and control.
The description on composition of relations gives a view of extending fuzziness
into functions. Tolerance and equivalence relations are helpful for solving similar
classification problems. The noninteractivity between fuzzy sets is analogous to
the assumption of independence in probability modelling.
144
Chapter 7: Introduction to Fuzzy Logic and Fuzzy
145
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
Unit IV
8
MEMBERSHIP FUNCTIONS,
DEFUZZIFICATION, FUZZY ARITHMETIC
AND FUZZY MEASURES
Unit Structure
8.0 Objectives
8.1 Introduction to Membership Function
8.2 Features of the Membership Function
8.3 Overview of Fuzzification
8.4 Methods of Membership Value Assignment
8.4.1 Intuition
8.4.2 Inference & Rank Ordering
8.4.3 Angular Fuzzy Sets
8.4.4 Neural Network
8.4.5 Genetic Algorithm
8.4.6 Inductive Reasoning
8.5 Overview of Defuzzification
8.6 Concept of Lamba-Cuts for Fuzzy Sets (Alpha-Cuts)
8.7 Concept of Lamba-Cuts for Fuzzy Relations
8.8 Methods of Defuzzification
8.8.1 Max-membership Principle
8.8.2 Centroid Method
8.8.3 Weighted Average Method
8.8.4 Mean-Max Membership
8.8.5 Centers of Sums
8.8.6 Centers of Largest Area
8.8.7 First of Maxima, Last of Maxima
143
SOFT COMPUTING TECHNIQUES
8.0 Objectives
This chapter begins with explaining the membership function and later introduces
the concept of fuzzification, defuzzification and fuzzy arithmetic.
144
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
set A. The core has elements x of the universe such that 𝜇𝐴(𝑥) = 1. The
that region of universe that is characterized by complete membership in the
The support comprises elements x of the universe such that 𝜇𝐴(𝑥) >
as that region of universe that is characterized by a nonzero membership.
of the universe such that 0 < 𝜇𝐴(𝑥) < 1. The boundary elements are
not complete membership. The boundary comprises of those elements of x
145
SOFT COMPUTING TECHNIQUES
Figure 8.2: (A) Normal Fuzzy Set and (B) Subnormal Fuzzy Set
Normal fuzzy set: A fuzzy set whose membership function has at least one
element x in the universe whose membership value is unity.
o Prototypical element: The element for which the membership is
equal to 1.
Subnormal fuzzy set: A fuzzy set wherein no membership function has it
equal to 1.
Convex fuzzy set: A convex fuzzy set has membership function whose
membership values are strictly monotonically increasing or strictly
monotonically decreasing or strictly monotonically increasing than strictly
monotonically decreasing with increasing values for the elements in the
universe.
Nonconvex fuzzy set: the membership value of the membership function is
not strictly monotonically increasing or decreasing or strictly monotonically
increasing than decreasing.
Figure 8.3: (A) Convex Normal Fuzzy Set and (B) Nonconvex Normal Fuzzy Set
146
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
The intersection of two convex fuzzy set is also a convex fuzzy set. The element
in the universe for which a particular fuzzy set A has its value equal to 0.5 is
called crossover point of membership function. There can be more than one
crossover point in fuzzy set. The maximum value of the membership function of
the fuzzy set A is called height of the fuzzy set. If the height of the fuzzy set is
less than 1, then the fuzzy set is called subnormal fuzzy set. When the fuzzy set
A is a convex single
–point normal fuzzy set defined on the real time, then A is termed as a fuzzy
number.
Fuzzification is the process of transforming a crisp set to a fuzzy set or a fuzzy set
into a fuzzier set. This operation translates accurate crisp input value into
linguistic variables. Quantities that we consider to be accurate, crisp &
deterministic, possess uncertainty within themselves. The uncertainty arises due
to vagueness, imprecision or uncertainty.
147
SOFT COMPUTING TECHNIQUES
8.4.1 Intuition
148
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
angular fuzzy sets. The logical proposition is equated to the membership value
“1” is said to be “true” and that preposition with membership value 0 is said to be
“false”. The intermediate values between 0 & 1 correspond to proposition being
partially true or partially false.
The values of the linguistic variable vary with “θ” & their membership values are
on the μ(θ)[Link] membership value corresponding to the linguistic term can be
obtained from equation μt(θ)=[Link] (θ) where t is the horizontal projection of
radial vector
149
SOFT COMPUTING TECHNIQUES
150
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
Laws of Induction:
Given a set of irreducible outcomes of experiment, the induced probabilities
are probability consistent with all the available information that maximize
the entropy of the set.
The induced probability of a set of independent observation is proportional
to the probability density of the induced probability of single observation.
The induced rule is that rule consistent with all available information of that
minimizes the entropy
The third law stated above is widely used for development of membership function.
151
SOFT COMPUTING TECHNIQUES
Consider a fuzzy set A. The set A (0 < 𝜆 < 1), called the lamba
(𝜆) − cut (or alpha [𝛼]-cut) set, is a 𝜆
crisp
152
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
Figure 8.8 (A): First part of fuzzy output, (B) second part of fuzzy output, (C)
union of parts (A) and (B)
153
SOFT COMPUTING TECHNIQUES
Defuzzification Methods
Max-membership principle
Centroid method
Weighted average method
Mean-Max membership
Centers of Sums
Center of largest area
First of maxima, last of maxima
This method is also known as height method and is limited to peak output
functions. This method is given by the algebraic expression:
This method is also known as center of mass, center of area, center of gravity,
154
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
th
∑ denotes algebraic sum and xi is the maximum of the i membership function.
155
SOFT COMPUTING TECHNIQUES
This method is also known as the middle of maxima. The locations of the
maxima membership can be nonunique.
Figure 8.13: (A) First and (B) Second Membership functions, (C) Defuzzification
156
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
This method can be adopted when the output consists of at least two convex fuzzy
subsets which are not overlapping. The output in this case is biased towards a side
of one membership function. When output fuzzy set has at least two convex
regions then the center-of-gravity of the convex fuzzy sub region having the
largest area is used to obtain the defuzzified value x*. This value is given by:
157
SOFT COMPUTING TECHNIQUES
158
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
[𝑎1, 𝑎2) = {𝑥|𝑎1 ≤ 𝑥 < 𝑎2} is an interval closed at left end side &
open at right end.
(𝑎1, 𝑎2] = {𝑥|𝑎1 < 𝑥 ≤ 𝑎2} is an interval open at left end side &
closed at right end.
(𝑎1, 𝑎2) = {𝑥|𝑎1 < 𝑥 < 𝑎2} is an open interval, open at both left
end and right end.
We subtract the larger value out of b1 & b2 from a1. The smaller value out of b1
& b2 from a2 is subtracted.
to + ∞
[−𝑎2, −𝑎1]. Note that 𝐴 + Ā = [𝑎1, 𝑎2] + [−𝑎2, −𝑎1] = [𝑎1 − 𝑎2,
𝑎2 − 𝑎1] ≠ 0
159
SOFT COMPUTING TECHNIQUES
-1
given by
−
1 1 1 1
= [ , ] . Similarly, the inverse of A is given by A = [𝑎1,
( 𝑎 −
)𝑥 1
2 𝑎2]
𝑎1
1 1
= [ , ] . The division becomes multiplication of an inverse. For
𝑎 𝑎
2 1 division
1
by a non − negative number 𝖺> 0 i. e. ( ).
𝖺
1 1 𝑎1 𝑎
A, we obtain 𝐴 ÷𝖺= , ] = [ 2
𝐴. [ , ]
�𝖺 𝖺 𝖺
�
160
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
A fuzzy number is a normal, convex membership function on the real line R. Its
membership function is piecewise continuous. That is, every λ-cut set Aλ,
λ∈[0,1],of a fuzzy number A is a closed interval of R & the highest value
of
161
SOFT COMPUTING TECHNIQUES
( ), ( )
𝜆1 𝜆2
𝐴𝜆1 [𝑎1 𝑎2 ] 𝑓𝑓𝑟𝑜𝑚 𝑓𝑓𝑢𝑧𝑧𝑦 𝑛𝑢𝑚𝑏𝑒𝑟 𝐴
=
𝜆1 , 𝜆2
( ) ( )
𝐵𝜆1 [𝑏1 𝑏2 ] 𝑓𝑓𝑟𝑜𝑚 𝑓𝑓𝑢𝑧𝑧𝑦 𝑛𝑢𝑚𝑏𝑒𝑟 𝐵
=
Fuzzy number is an extension of the concept of intervals. Fuzzy numbers consider
them at several levels with each of these levels corresponding to each λ-cut of the
fuzzy [Link] notation Aλ1=[a1(λ1),a2(λ2)] can be used to represent a closed
interval of a fuzzy number A at a λ h -level.
162
SOFT COMPUTING TECHNIQUES
The technique for fuzzy ordering is based on the concept of possibility measure.
For a fuzzy number A, two fuzzy sets, A1 & A2 are defined. For this number, the
set of numbers that are possibly greater than or equal to A is denoted as A 1 and is
defined as
162
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
In a similar manner, the set of numbers that are necessarily greater than A is
denoted as A and is defined as
2
where ∏𝐴 and N
A
are possibility and necessity measures.
necessity measure of a fuzzy set. That is, we can calculate the possibility and
necessity measures, in the set 𝜇𝐴 of fuzzy sets B1 & B2. On the basis of this, we
obtain four fundamental indices of comparison.
T
P , is a column vector if P is a row vector, i.e.,
163
SOFT COMPUTING TECHNIQUES
The extension principle allows generalization of crisp sets into fuzzy sets
framework & extends point-to-point mappings for fuzzy sets.
164
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
known as ambiguity, we assign a value in the unit interval [0, 1] to each possible
crisp set to which the element in the problem might belong. The value assigned
represents the degree of evidence or certainty or belief of the element's
membership in the set. The representation of uncertainty of this manner is called
fuzzy measure. The difference between a fuzzy measure and a fuzzy set on a
universe of elements is that, in fuzzy measure, the imprecision is in the
assignment of an element to one of two or more crisp sets, and in fuzzy sets, the
imprecision is in the prescription of the boundaries of a set.
165
SOFT COMPUTING TECHNIQUES
X Here B is a Borel field or a σ field. Also, g satisfies rhe following three axioms
of fuzzy measures:
𝐴, 𝐵 ∈ 𝑃(𝑋𝑋), 𝑖𝑖𝑖𝑖
𝐴⊆
Monotonicity (g2): for every classical set
𝑋𝑋 ∈ 𝐵 & ∅ ∈ 𝐵
𝑖𝑖𝑖𝑖 𝐴 ∈ 𝐵, 𝑡ℎ𝑒𝑛 ~𝐴 ∈ 𝐵
𝐴∈𝐵&𝐵
∈
B is closed under set union operation, i.e. if
additive property states that when two sees A and B are disjoint, then ℎ(𝐴 𝖴 𝐵)
The fuzzy measure excludes the additive property of standard measures, h. The
The belief measure is a fuzzy measure that satisfies three axioms g1, g2 and g3
166
and an additional axiom of subadditivity. A belief measure is a function 𝑏𝑒𝑙: 𝐵
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
167
SOFT COMPUTING TECHNIQUES
The belief measure and the plausibility measure are mutually dual, so it will be
→
[0,1]𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝑚(∅ = 0)𝑎𝑛𝑑 ∑ 𝐴 𝐵 𝑚( 𝐴) =
∈ are
1. The basic probability assignments not fuzzy measures. The quantity
𝑚(𝐴) ∈ [0,1], 𝐴 ∈ 𝐵(𝐶𝑃(𝑋𝑋)) , is called A's basic probability number.
168
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
The theorem indicates fiat a probability measure on finite sets can be represented
uniquely by a function defined on the elements of the universal set X rather than
function, P: X → [0, 1] such that P(x) = m({x}). This function P(X) is called
its subsets. The probability measures on finite sets can be fully represented by a
169
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
𝑃(𝑋𝑋) are nested sets. When the focal elements of a body of evidence (E, m) are
nested, the linked belief and plausibility measures are called consonants, because
here the degrees of evidence allocated to them do not conflict with each other.
∏: 𝐵 → [0,1] & N: B → [0,1] such that ∏ & N both satisfy the axioms
g1,g2 & g3 of fuzzy measures and following axiom g7:
169
SOFT COMPUTING TECHNIQUES
𝑓𝑓: 𝑃(𝑋𝑋) → 𝑅 where R is the real line and P(X) is the set of all fuzzy subsets of
referred to as measures of fuzziness. A measure of fuzziness is a function
Axiom f1 shows that a crisp set has zero degree of fuzziness in it. Axioms f2 and
f3 are based on concept of "sharper" and "maximal fuzzy," respectively.
170
Chapter 8: Membership Functions, Defuzzification, Fuzzy Arithmetic and Fuzzy Measures
8.22 Summary
This chapter starts with the discussion about membership functions and their
features. The formation of the membership function is the core for the entire
fuzzy system operation. The capability of human reasoning is important for
membership functions. The inference method is based on the geometrical shapes
and geometry, whereas the angular fuzzy set is based on the angular features.
Using neural networks and reasoning methods the memberships are tuned in a
cyclic fashion and are based on rule structure. The improvements are carried out
to achieve an optimum solution using generic algorithms. Thus, the membership
function can be formed using any one of the methods.
Later we have discussed the methods of converting fuzzy variables into crisp
variables by a process called as defuzzification. Defuzzification process is
essential because some engineering applications need exact values for performing
the operation. Defuzzification is a natural and essential technique. Lambda-cuts
for fuzzy sets and fuzzy relations were discussed. Apart from the Lambda-cut
method, seven defuzzification methods were presented. The method of
defuzzification should be assessed on the basis of the output in the context of data
available.
171
SOFT COMPUTING TECHNIQUES
172
Chapter 9: Genetic Algorithm
UNIT 5
9
GENETIC ALGORITHM
Learning Objectives
Gives an introduction to natural evolution.
Lists the basic operators (selection, crossover, mutation) and other
terminologies used in Genetic Algorithms (GAs).
Discusses the need for schemata approach.
Details the comparison of traditional algorithm with GA.
Explains the operational flow of simple GA.
Description is given of the various classifications of GA- Messy GA,
adaptive GA, hybrid GA, parallel GA and independent sampling GA.
The variants of parallel GA (fine-grained parallel GA and coarse-grained
parallel GA) are included.
Enhances the basic concepts involved in Holland classifier system.
The various features and operational properties of genetic programming are
provided.
The application areas of GA are also discussed.
Thales R. Darwin says that "Although the belief that an organ so perfect as the
eye could have been formed by natural selection is enough to stagger any one; yet
in the case of any organ, if we know of a long series of gradations in complexity,
each good for its possessor, then, under changing conditions of life, there is no
logical impossibility in the acquirement of any conceivable degree of perfection
through natural selection."
Introduction
173
SOFT COMPUTING TECHNIQUES
was developed. Morgan experimentally found that chromosomes were the carriers
of hereditary information and that genes representing the hereditary factors were
lined up on chromosomes. Darwin's natural selection theory and natural genetics
remained unlinked until 1920s when it was proved that genetics and selection
were in no way contrasting each other. Combination of Darwin’s and Mendel’s
ideas leads to the modern evolutionary theory.
In The Origin of Species, Thales Darwin stated the theory of natural evolution.
Over many generations, biological organisms evolve according to the principles
of natural selection like "survival of the fittest" to reach some remarkable forms
of accomplishment. The perfect shape of the albatross wing, the efficiency and
the similarity between sharks and dolphins and so on are good examples of what
random evolution with absence of intelligence can achieve. So, if it works so well
in nature, it should be interesting to simulate natural evolution and try to obtain a
method which may solve concrete search and optimization problems.
174
Chapter 9: Genetic Algorithm
Biological Background
The science that deals with the mechanisms responsible for similarities and
differences in a species is called Genetics. The word "genetics" is derived from
the Greek word "genesis" meaning "to grow" or "to become. “The science of
genetics helps us to differentiate between heredity and variations and accounts for
the resemblances and differences during the process of evolution. The concepts of
GAs are directly derived from natural evolution and heredity. The terminologies
involved in the biological background of species are discussed in the following
subsections.
The Cell
Chromosomes
All the genetic information gets stored in the chromosomes. Each chromosome is
build of deoxyribonucleic acid (DNA). In humans, chromosomes exist in pairs
(23 pairs found). The chromosomes are divided into several parts called genes.
Genes code the properties of species, i.e., the characteristics of an individual. The
possibilities of combination of the genes for one property are called alleles, and a
gene can take different alleles. For example, there is a gene for eye colour, and all
the different possible alleles are black, brown, blue and green (since no one has
red or violet eyes!). The set of all possible alleles present in a particular
population forms a gene pool. This gene pool can determine all the different
possible variations for the future generations. The size of the gene pool helps in
determining the diversity of the individuals in the population. The set of all the
genes of a specific species is called genome. Each and every gene has a unique
position on the genome called
175
SOFT COMPUTING TECHNIQUES
[Link] Genetics
For a particular individual, the entire combination of genes is called genotype.
The phenotype describes the physical aspect of decoding a genotype to produce
the phenotype. One interesting point of evolution is that selection is always done
on the phenotype whereas the reproduction recombines genotype. Thus,
morphogenesis plays a key role between section and reproduction. In higher life
forms, chromosomes contain two sets of genes. These are known as diploids. In
the
176
Chapter 9: Genetic Algorithm
case of conflicts between two values of the same pair of genes, the dominant one
will determine the phenotype whereas the other one, called recessive, will still be
present and
Can be passed onto the offspring. Diploid allows a wider diversity of alleles. This
provides a useful memory mechanism in changing or noisy environment.
However, most GAs concentrates on haploid chromosomes because they are
much simple to construct. In haploid representation, only one set of each gene is
stored, thus the process of determining which allele should be dominant and
which one should be recessive is avoided. Figure 9.1-3 shows the development of
genotype to phenotype.
177
SOFT COMPUTING TECHNIQUES
[Link] Reproduction
178
Chapter 9: Genetic Algorithm
ection
es is based on "Preservation of favourable variations and
able variations.” The variation refers to the differences shown
species and also by offspring's of the same parents. There are
rn than can survive, so there is a continuous struggle for life.
advantage have a greater chance of survival, i.e., the survival
mple, Giraffe with long necks can have food from tall trees as
d; on the other hand, goat and deer having smaller neck can
the ground. As a result, natural selection plays a major role in
.
179
SOFT COMPUTING TECHNIQUES
Table 9.1.1 gives a list of different expressions, which are common in natural
evolution and genetic algorithm.
Where
When the objective function is smooth and one needs efficient local optimization,
it is better to use gradient-based or Hessian-based optimization methods. The
performance and reliability of the different gradient methods vary considerably.
To discuss gradient-based local optimization, let us assume a smooth objective
function (i.e., continuous first and second derivatives). The object function is
denoted by
f(x) : KnR …….(3)
f(x)ixl
f(x) = : ……(4)
f(x)ixn
180
Chapter 9: Genetic Algorithm
The second derivatives of the object function are contained in the Hessian matrix
H(x):
……………..(5)
Few methods need only the gradient vector, but in the Newton's method we need
the Hessian matrix. The general pseudo code used in gradient methods is as
follows:
Setn=n+l.
Until || Xn – Xn-1 || < ……(6)
These gradient methods search for minimum and not maximum. Several different
methods are obtained based on the details of the algorithm.
Pn= -f(Xn)+nPn-1..................................(7)
In second method,
nPn= -f(xn).........................(8)
is used for finding search direction. The matrix n in Eq. (6) estimates the Hessian
and is updated in each iteration. When n is defined as the identity matrix, the
steepest descent method occurs. When the matrix Bn is the Hessian H (xn), we get
the Newton's method.
181
SOFT COMPUTING TECHNIQUES
n>0
182
Chapter 9: Genetic Algorithm
Random search does have a few interesting qualities. However good the obtained
solution may be, if it’s not optimal one, it can be always improved by continuing
the run of the random search algorithm for long enough. A random search never
gets stuck at any point such as a local optimum. Furthermore, theoretically, if the
search space is finite, random search is guaranteed to reach the optimal solution.
Unfortunately, this result is completely useless. For most of problems we are
interested in, exploiting the whole search space takes lot of time.
183
SOFT COMPUTING TECHNIQUES
in = eElkT …….(10)
where E stands for the energy, k is the Boltzmann constant and T is the
temperature. In the mid0l970s, Kirkpatrick by analogy of these physical
phenomena; laid out the first description of SA.
P = e -1f(y)-f(x)|lkT …….(11)
Where f(y) - f(x) is the difference of the fitness function between the new and the
old solution.
The SA behaves like a hill climbing method but with the possibility of going
downhill to avoid being trapped at local optima. When the temperature is high,
the
184
Chapter 9: Genetic Algorithm
probability of deteriorate the solution is quite important, and then a lot of large
moves are possible to explode the search space. The more the temperature
decreases, the more difficult it is to go downhill. The algorithm thus tries to climb
up from the current solution to reach a maximum. When temperature is lower,
there is an exploitation of the current solution. If the temperature is too low,
number deterioration is accepted, and the algorithm behaves just like a stochastic
hill climbing method. Usually, the SA stars from a high temperature which
decreases exponentially. The slower the cooling, the better it is for finding good
solutions. It even has been demonstrated that with an infinitely slow cooling, the
algorithm is almost certain to find the global optimum. The only point is that
infinitely slow cooling consists in finding the appropriate temperature decrease
rate to obtain a good behaviour of the algorithm.
185
SOFT COMPUTING TECHNIQUES
186
Chapter 9: Genetic Algorithm
With the success of GAs, other algorithms making use of the same principle of
natural evolution have also emerged. Evolution strategy, genetic programming
are some algorithms similar to these algorithms. The classification is not always
clear between the different algorithms, thus to avoid any confusion, they areal
gathered in what is called Evo1ationary Algorithms.
The analogy with nature gives these algorithms something exciting and
enjoyable. Their ability to deal successfully with a wide range of problem area,
including those which are difficult for other methods to solve makes them quite
powerful. However today, GAs is suffering from too much readiness. GA is a
new field, and parts of the theory still have to be properly established. We can
find almost as many opinions on GAs as there are researchers in this field. In this
document, we will generally find the most current point of view. But things
evolve quickly in GAs too, and some comments might not be very accurate in
few years.
188
Chapter 9: Genetic Algorithm
optimization problems. This warning is for those who might have the temptation
to resolve anything with GA.
189
SOFT COMPUTING TECHNIQUES
The proverb says "If we have a hammer, all the problems look like a nails.'' GAs
do work and give excellent results if they are applied properly on appropriate
problems.
Figure 9.1-7Basilosaurus.
The image shows that two fingers of the common dolphin are hypertrophied to
the detriment of the rest of the member. The basilosaurus was a hunter; it had to
be fast and precise. Through time, subjects appeared with longer fingers and
short arms.
190
Chapter 9: Genetic Algorithm
They could move faster and more precisely than before, and therefore, live longer
and have many descendants.
Holland method is especially effective because he not only considered the role of
mutation (mutations improve very seldom the algorithms), but also utilized
genetic recombination (crossover): these recombination, the crossover of partial
solutions, greatly improve the capability of the algorithm to approach, and
eventually find, the optimum.
191
SOFT COMPUTING TECHNIQUES
good features from its parents, may surpass its ancestors. Many people believe
that this mixing of genetic material via sexual reproduction is one of the most
powerful features of GAs. As a quick parenthesis about sexual reproduction, GA
representation usually does not differentiate male and female individuals (without
any perversity). As in many livings species (e.g., snails) any individual can be
either a male or a female. Infact, for almost all recombination operators, mother
and father are interchangeable.
Mutation is the other way to get new genomes. Mutation consists in changing the
value of genes. In natural evolution, mutation mostly engenders non-viable
genomes. Actually mutation is not a very frequent operator in natural evolution.
Nevertheless, in optimization, a few random changes can be a good way of
exploiting the search space quickly.
Through those low-level notions of genetic, we have seen how living beings store
their characteristic information and how this information can be passed into their
offspring. It very basic but it is more than enough to understand the GA theory.
Darwin was totally unaware of the biochemical basics of genetics. Now we know
how the genetic inheritable information is coded in DNA, RNA, and proteins and
that the coding principles are actually digital, much resembling the information
storage in computers. Information processing is in many ways totally different,
however. The magnificent phenomenon called the evolution of species can also
give some insight into information processing methods and optimization, in
particular. According to Darwinism, inherited variation is characterized by the
following properties:
1. Variation must be copying because selection does not create directly
anything, but presupposes a large population to work on.
2. Variation must be small-scaled in practice. Species do not appear suddenly.
3. Variation is undirected. This is also known as the blind watch maker
paradigm.
While the natural sciences approach to evolution has for over a century been to
analyse and study different aspects of evolution to find the underlying principles,
the engineering sciences are happy to apply evolutionary principles, that have
been heavily tested over billions of years, to arrack the most complex technical
problems, including protein folding.
192
Chapter 9: Genetic Algorithm
The nice thing when comparing GAs to other optimization methods is that the
fitness function can be nearly anything that can be evaluated by a computer or
even something that cannot In the latter case it might be a human judgment that
cannot be seated as a crisp program, like in the case of eye witness, where a
human being selects from the alternatives generated by GA. So, there are not any
definite mathematical restrictions on the properties of the fitness fraction. It may
be discrete, multimodal, etc.
193
SOFT COMPUTING TECHNIQUES
These are the major differences that exist between GA and conventional
optimization techniques.
[Link] Individuals
An individual is a single solution. Individual groups together two forms of
solutions as given below:
I. The chromosome which is the raw "genetic" information (genotype) that the
GA deals.
2. The phenotype which is the expressive of the chromosome in the terms of
the model.
194
Chapter 9: Genetic Algorithm
A chromosome should in some way contain information about the solution that it
represents. The morphogenesis function associates each genotype with its
phenotype. It simply means that each chromosome must define one unique
solution, but it does not mean that each solution is encoded by exactly one
chromosome. Indeed, the morphogenesis function is not necessarily objective,
and it is even sometimes impossible (especially with binary representation).
Nevertheless, the morphogenesis function should at least be subjective. Indeed;
101010111010110
all the candidate solutions of the problem must correspond to at least one possible
chromosome, to be sure that the whole search space can be exploited. When the
morphogenesis function that associates each chromosome to one solution is not
injective. i.e., different chromosomes can encode the same solution, the
representation is said to be degenerated. A slight degeneracy is not so worrying,
even if the space where the algorithm is looking for the optimal solution is
inevitably enlarged. Bur a too important degeneracy could be a more serious
problem. It can badly affect the behaviour of the GA, mostly because if several
chromosomes can represent the same phenotype, the meaning of each gene will
obviously not correspond to a specif1c characteristic of the solution. It may add
some kind of confusion in the search. Chromosomes encoded by bit strings are
given in Figure 9.1-10.
195
SOFT COMPUTING TECHNIQUES
[Link] Genes
Genes are the basic "instructions" for building a GA. A chromosome is a
sequence of genes. Genes may describe possible solution to a problem, without
actually being the solution. A gene is a bit string of arbitrary lengths. The bit
string is a binary representation of number of intervals from a lower bound. A
gene is the GNs representation of a single factor value for a control factor, where
control factor must have an upper bound and a lower bound. This range can be
divided into the number of intervals that can be expressed by the gene's bit string.
A bit string of length "n" can represent (2n1 - 1) intervals. The size of the interval
would be (range)/ (2n- 1).
[Link] Fitness
The fitness of an individual in a GA is the value of an objective function for its
phenotype. For calculating fitness, the chromosome has to be first decoded and
the objective function has to be evaluated. The fitness
not only indicates how good the solution is, but also corresponds to how does the
chromosome is to the optimal one.
196
Chapter 9: Genetic Algorithm
that
197
SOFT COMPUTING TECHNIQUES
criterions can be combined in a consistent way. But, for more advanced problems,
it may be useful to consider something like Pareto optimally or other ideas from
multicriterian optimization theory.
[Link] Populations
A population is a collection of individuals. A population consists of a number of
individuals being reseed, the phenotype parameters defining the individuals and
some information about the search space. The two important aspects of
population used in GAs are:
1. The initial population generation.
2. The population size.
For each and every problem, the population size will depend on the complexity of
the problem. It is often a random initialization of population. In the case of a
binary coded chromosome this means chat each bit is initialized to a random 0 or
1. However, there may be instances where the initialization of population is
carried out with some known good solutions.
Ideally, the first population should have a gene pool as large as possible in order
to be able to explode the whole search space. All the different possible alleles of
each should be present in the population. To achieve this, the initial population is,
in most of the cases, chosen randomly. Nevertheless, sometimes a kind of
heuristic can be used to seed ·the initial population. Thus, the mean fitness of the
population is already high and it may help the GA to find good solutions faster.
Bur for doing this one should be sure that the gene pool is spillage enough.
Otherwise, if the population badly lacks diversity, the algorithm will just explode
a small part of the search space and never find global optimal solutions.
The size of the population raises few problems too. The larger the population is,
the easier it is m explode the search space. However, it has been established that
the time required by a GAm converge is O (n log n) function evaluations where n
is the population size. We say that the population has converged when all the
individuals are very much alike and further improvement may only be possible by
mutation. Goldberg has also shown that GA efficiency to reach global optimum
instead of local ones is largely determined by the size of the population. To sum
up, a large population is quite useful. However, it requires much more
computational cost memory and time. Practically, a population size of around 100
individuals is quite frequent, but anyway this size can be changed according to
the time and the memory disposed on the machine compared to the quality of the
result to be reached.
198
Chapter 9: Genetic Algorithm
Chromosome 1 11100010
Chromosome 2 201111011
Population
Chromosome 3 10101010
Chromosome 4 11001100
9.1.7 Simple GA
GA handles a population of possible solutions. Each solution is represented
through a chromosome, which is just an abstract representation. Coding all the
possible solutions into a chromosome is the first part, but certainly not the most
straightforward one of a GA. A set of reproduction operators has to be
determined, coo. Reproduction operators are applied directly on the
chromosomes, and are used to perform mutations and recombination over
solutions of the problem. Appropriate representation and reproduction operators
are the determining factors, as the behaviour of the GA is extremely dependent on
it. Frequency, it can be extremely difficult to find a representation that respects
the structure of the search space and reproduction operators that are coherent and
relevant according to the properties of the problems.
199
SOFT COMPUTING TECHNIQUES
fitness should correspond to an evaluation of how good the candidate solution is.
The optimal solution is the one which maximizes the fitness function. GAs deal
with the problems that maximize the fitness function. Bur, if the problem consists
of minimizing a cost function, the adaptation is quite easy. Either the cost
function can be transformed into a fitness function, for example by inverting it; or
the selection can be adapted in such way that they consider individuals with low
evaluation functions as better. Once the reproduction and the fitness function
have been properly defined, a GA is evolved according to the same basic
structure. It starts by generating an initial population of chromosomes. This first
population must offer a wide diversity of genetic materials. The gene pool should
be as large as possible so that any solution of the search space can be engendered.
Generally, the initial population is generated randomly. Then, the GA loops over
an iteration process to make the population evolve. Each iteration consists of the
following steps:
200
Chapter 9: Genetic Algorithm
Genetic algorithms are not too hard to program or understand because they are
biological based. An example of a flowchart of a GA is shown in Figure 9.1-13.
201
SOFT COMPUTING TECHNIQUES
Fitness-proportionate selection
4. If E is mutated, then
E : 10110100 E' : 10110000
Best-fit string from previous population is lost, but the average fitness of
population is as given below:
Tables 9.1-2 and 9.1-3 show the fitness value for the corresponding chromosomes
and Figure 9.1-14 shows the Roulette wheel selection for the fitness proportionate
selection.
203
SOFT COMPUTING TECHNIQUES
[Link] Encoding
Encoding is a process of representing individual genes. The process can be
performed using bits, numbers, trees, arrays, lists or any other objects. The
encoding depends mainly on solving the problem. For example, one can encode
directly real or integer numbers.
Each chromosome encodes a binary (bit) suing. Each bit in the suing can
represent some characteristics of the solution. Every bit string therefore is a
solution but not necessarily the best solution. Another possibility is that the whole
string can represent a number. The way bit strings can code differs from problem
to problem.
Chromosome 1 110100011010
Chromosome 2 I011111111100
Figure 9.1·5.1 Binary encoding.
Chromosome 1 03467216
Chromosome 2 5.1723314
204
Chapter 9: Genetic Algorithm
Chromosome1 9CE7
Chromosome 2 3DBA
Chromosome A 153264798
Chromosomes 856723149
Permutation encoding (Figure 9.1-18) is only useful for ordering problems. Even
for this problem, some types of crossover and mutation corrections must be made
to leave the chromosome consistent (i.e., have real sequence in it).
205
SOFT COMPUTING TECHNIQUES
[Link] Selection
Selection is the process of choosing two parents from the population for crossing.
After deciding on an encoding, the next step is to decide how to perform
selection, i.e., how to choose individuals in the population that will create
offspring for the next generation and how many offspring each will create. The
purpose of selection is in emphasize fitter individuals in the-population in hopes
that their offspring have higher fitness. Chromosomes are selected from the initial
population to be parents for reproduction. The problem is how to select these
chromosomes. According to Darwin’s theory of evolution the best ones survive to
create new offspring. Figure 9.1-20 shows the basic selection process.
206
Chapter 9: Genetic Algorithm
It is also possible to use a scaling function to redistribute the fitness range of the
population in order to adapt the selection pressure. For example, if all the
solutions have their finesses in the range [999, 1000], the probability of selecting
a better individual than any other using a proportionate based method will note
important. If the fitness every individual is bringing to the range [0, 1] equitable,
the probability of selecting good individual instead of bad one will be important.
Selection has to be balanced with variation from crossover and mutation. Too
strong selection means sub-optimal highly fit individuals will take over the
population, reducing the diversity needed for change and progress; too weak
selection will result in too slow evolution. The various selection methods are
discussed in the following subsections.
207
SOFT COMPUTING TECHNIQUES
The Roulette process can also be explained as follows: The expected value of an
individual is individual’s fitness divided by the actual fitness of the population.
Each individual is assigned a slice of the Roulette wheel, the size of the slice
being proportional to the individual's fitness. The wheel is spun N times, where N
is the number of individuals in the population. On each spin, the individual under
the wheel's marker is selected to be in the pool of parents for the next generation.
This method is implemented as follows:
1. Sum the total expected value of the individuals in the population. Let it be T.
2. Repeat N times:
i. Choose a random integer "r" between 0 and T.
ii. Loop through the individuals in the population, summing the expected
values, until the sum is greater than or equal to "r." The individual
whose expected value puts the sum over this limit is the one selected.
Roulette wheel selection is easier to implement bur is noisy. The rate of evolution
depends on the variance of fitness's in the population.
208
Chapter 9: Genetic Algorithm
The best individual from the tournament is the one with the highest fitness, who is
the winner of Nu. Tournament competitions and the winner are then inserted into
the mating pool. The tournament competition is repeated until the mating pool for
generating new offspring is filled. The mating pool comprising the tournament
winner has higher average population fitness. The fitness difference provides the
selection pressure, which drives GA to improve the fitness of the succeeding
genes. This method is more efficient and leads to an optimal solution.
Let fax be the fitness of the currently available best string. If the next string has
fitness f (X:) such that f(X;)>fmax• then the new string is selected. Otherwise it is
selected with Bole/Mann
The probability that the best string is selected and introduced into the mating pool
is very high. However, Elitism can be used to eliminate the chance of any
undesired loss of information during the mutation stage. Moreover, the execution
time is less.
Elitism
The first best chromosome or the few best chromosomes are copied to the new
population. The rest is done in a classical way. Such individuals can be lost if
they are not selected to reproduce or if crossover or mutation destroys them. This
significantly improves the GA's performance.
210
Chapter 9: Genetic Algorithm
211
SOFT COMPUTING TECHNIQUES
new ones. Crossover operator is applied to the mating pool with the hope that it
creates a better offspring.
That is the simplest way how to do that is to choose randomly some crossover
point and copy everything before this point &on the first parent and then copy
everything after the crossover point from the other parent. The various crossover
techniques are discussed in the following subsections.
Child1 10110 1 1 1
Chiled2 10101 0 1 0
212
Chapter 9: Genetic Algorithm
Figure 9.1-22 illustrates single point crossover and it can be observed that the
bits next to the crossover point are exchanged to produce children. The crossover
point can be chosen randomly.
In two-point crossover, two crossover points are chosen and the contents between
these points are exchanged between two mated parents.
In Figure 9.1-23 the dotted lines indicate the crossover points. Thus the comments
between these points are
exchanged between the parents to produce new children for mating in the next
generation.
Parent1 1 10 1 1 0 1 0
Parent2 0 11 0 1 1 0 0
Originally, GAs were using one point crossover which cuts two chromosomes in
one point and splices the two halves to create new ones. But with this one-point
crossover, the head and the rail of one chromosome cannot be passed together to
the offspring. If both the head and the rail of a chromosome contain good genetic
information, none of the offspring obtained directly with one-point crossover will
share the two good features. Using a two-point crossover one can avoid this
drawback, and so it is generally considered better than one-point crossover. In
fact, this problem can be generalized to each gene position in a chromosome.
Genes that are close on a chromosome have more chance to be passed together to
the offspring
213
SOFT COMPUTING TECHNIQUES
In Figure 9.1-24, new children are produced using uniform crossover approach. It
can be noticed that while producing child 1, when there is a 1 in the mask, the
gene is copied from parent 1 else it is copied from parent 2. On producing child 2,
when there is a 1 in the mask, the gene is copied from parent 2, and when there is
a 0 in the mask, the gene is copied from the parent 1.
214
Chapter 9: Genetic Algorithm
Parent 1 10110011
Parent 2 00011010
Mask 1 11010110
Child 1 10011010
Child 2 00110011
Parent 1 11010001
Parent 2 01101001
Parent 3 01101100
Child 01101001
215
SOFT COMPUTING TECHNIQUES
Note that PPX does not work in a uniform crossover manner due tithe "deletion-
append" scheme used. Example is shown in Figure 9.1-26.
them into a left, middle and right portions. The ordered two point crossover
behaves in the following way: child 1 inherits its left and right section from·
parent l, and its middle section is determined by the genes in the middle section of
parent 1 in the order in which the values appear in parent 2. A similar process is
applied to determine child 2. This is shown in Figure 9.127.
216
Chapter 9: Genetic Algorithm
Consider the two strings shown in Figure 9.1-28, where the dots mark the
selected cross points. The marching section defines the position-wise exchanges
that must take place in both parents to produce the offspring. The exchanges are
read from the marching section of one chromosome to that of the other. In the
example illustrate in Figure 9.1-28, the numbers that exchange places are 5 and 2,
6 and 3, and 7 and 10. The resulting offspring are as shown in Figure 9.1-29.
PMX is dealt in derail in the next chapter.
Name 9 8 4 . 2 3 1 0 . 1 6 5 7 Allele 1 0 1 . 0 1 0 . 1 0 0 1
Name 8 1 0 1 . 5 6 7 . 9 2 4 3 Allele 1 1 1 . 1 1 1 . 1 0 0 1
Figure 9.1·29 partially matched crossover.
217
SOFT COMPUTING TECHNIQUES
[Link] Mutation
After crossover, the strings are subjected to mutation. Mutation prevents the
algorithm to be trapped in a local minimum. Mutation plays the tale of recovering
the lost genetic materials as well as for randomly distributing genetic information.
It is an insurance policy against the irreversible loss of genetic material. Mutation
has been traditionally considered as a simple search operator. If crossover is
supposed to exploit the current solution to find better ones, mutation is supposed
to help for the exploitation of the whole search space. Mutation isvie¥1ed as a
background operator to maintain genetic diversity in the population. It introduces
new genetic structures in the population by randomly modifying some of its
building blocks. Mutation helps escape from local minima's trap and maintains
diversity in the population. It also keeps the gene pool well stocked, thus ensuring
periodicity. A search space is said to be argotic if there is a non-zero probability
of generating any solution from any population state.
There are many different forms of mutation for the different kinds of
representation. For binary representation, a simple mutation can consist in
inverting the value of each gene with a small probability. The probability is
usually taken about 1/ L, where L is the length of the chromosome. It is also
possible to implement kind of hill climbing mutation operators that do mutation
only if it improves the quality of the solution. Such anoperawr can accelerate the
search; however, care should be taken, because it might also reduce the diversity
in the population and make the algorithm converge toward some local optima.
Mutation of a bit involves flipping a bit, changing 0 to1 and vice-versa.
[Link] 1 Flipping
Flipping of a bit involves changing 0 to 1 and 1 to 0 based on a mutation
chromosome generated. Figure 9.1-30explains mutation flipping concept. A
parent is considered and a mutation chromosome is randomly generated. For a 1
in mutation chromosome, the corresponding bit in parent chromosome is flipped
(0 to 1 and1 to 0) and child chromosome is produced. In the case illustrated in
Figure
218
Chapter 9: Genetic Algorithm
[Link].2 Interchanging
Two random positions of the string are chosen and the bits corresponding to those
positions are interchanged (Figure 9.1.31).
Parent 10110101
Child 00111100
Parent 10110101
Child 11110001
Parent 1 0 1 1 01 0 1
Child 1 0 1 1 0 11 1
[Link].3 Reversing
A random position is chosen and the bits next to that position is reversed and
child chromosome is produced (Figure 9.1-32).
219
SOFT COMPUTING TECHNIQUES
Mutation should not occur very often, because then GA will in fact change to
ralidom search.
The termination or convergence criterion finally brings the search to a halt. The
following are the few methods of termination techniques.
220
Chapter 9: Genetic Algorithm
and there is no information about "x" range. GA minimizes this function using its
operators in random specifications.
221
SOFT COMPUTING TECHNIQUES
222
Chapter 9: Genetic Algorithm
223
SOFT COMPUTING TECHNIQUES
Step 2: Obtain the decoded x values for the initial population generated. Consider
string 1.
01100 = 0 * 24 + 1 * 23 + I * 22 + 0 * 21 + 0 * 20
= 0+ 8 + 4 + 0 + 0
= 12
Thus for all the four strings the decoded values are obtained.
Step 3: Calculate the fitness or objective function. This is obtained by simply
squaring the “x”
value, since the given function is f(x) = x2 When x = 12, the fitness value is
f(x) = x2 = (12) 2 = 144
For x = 25, f(x) = x2 = (25) 2 = 625
and so on, until the entire population is computed.
Step 4: Compute the probability of selection,
𝑓𝑓(𝑥)𝑖
𝑃𝑟𝑜𝑏𝑃𝑃 =
𝑖
….(21)
∑𝑛
𝑖𝑖= 𝑓𝑓(𝑥)𝑖𝑖
1
f(x) is the summation of all the fitness value of the entire population.
Considering string l,
Fitness f (x) = 144
f (x) = 15.15
The same operation is done for all the strings. It should be noted that summation
of probability select is l.
Step 5: The next step is to calculate the expected count, which is calculated
f(X)𝑖
..... (22)
𝑖
[𝐴𝑣𝐴𝐴 𝑓𝑓(𝑥)]𝑖𝑖
as Expected count =
Where
∑𝑛 𝑓𝑓(𝑥)𝑖𝑖
(𝐴𝑣𝑔 𝑓𝑓(𝑥))𝑖𝑖 𝑖𝑖=1
�̅ ] ……………..(23)
= [ �
224
Chapter 9: Genetic Algorithm
For string 1,
Expected count = Fitness/Average = 144/288.75 = 0.4987
We then compute the expected count for the entire population. The expected
count gives an idea of which population can be selected for further processing in
the mating pool.
Step 6: Now the actual count is to be obtained to select the individuals who would
participate in the crossover cycle using Roulette wheel selection. The Roulette
wheel is formed as shown Figure 9.1-33.
The entire Raul we wheel covers 100% and the probabilities of selection as
calculated in step 4 for the entire populations are used as indicators to fit into the
Roulette wheel. Now the wheel may be spun and the number of occurrences of
population is noted to get actual count.
2. With string 2 occupying 54.11% of the Roulette wheel, it has a fair chance
of being selected twice. Thus its actual count can be considered as 2.
3. On the other hand, string 3 has the least probability percentage of 2.16%, so
their occurrence for next cycle is very poor. As a result, ire actual count is
0.
225
SOFT COMPUTING TECHNIQUES
4. String 4 with 31.26% has at least one chance for occurring while Roulette
wheel is spun, thus its actual count is 1.
The above values of actual count are tabulated as shown is Table 9.1-5.
Step 7: Now, write the mating pool based upon the actual count as shown in
Table 9.1-5.
The actual count of string no. 1 is I; hence it occurs once in the mating pool. The
actual count of string no. 2 is 2, hence it occurs twice in the mating pool. Since
the actual count of string no. 3 is 0, it does not occur in the mating pool.
Similarly, the actual count of string no. 4 being I, it occurs once in the mating
pool. Based on this, the mating pool is formed.
Parent 1 01100
Parent 2 11001
Offspring 1 01101
Offspring 2 11000
Step 9: After crossover operations. new offspring are produced and "x .. value.\
are decoded and I mess is calculated.
226
Chapter 9: Genetic Algorithm
Step 10: In this step, mutation operation is performed to produce new offspring.
After crossover operation. As discussed in Section [Link].1 mutation-Aipping
operation is performed and new offspring are produced. Table 9.1-6 shows the
new offspring after mutation. Once the offspring are obtained L after mutation,
they are decoded tax value and the fitness values are computed.
From the rabies, it can be observed how GAs combine high-performance notions
to achieve bercer performance. In the rabies, it can be noted how maximal and
average performances have improved in the new population. The population
average fitness has improved from 288.75 to 636.5 in one generation. The
maximum fitness has increased from 625 to 841 during the same period. Though
random processes make this best solution, its improvement can also be seen
successively. The best string of the initial population (1 1 0 0 1) receives no
chances for its existence because of its high, above-average performance. When
this combines at random with the next highest string (1 0 0 1 1) and is crossed at
crossover point 2 (as shown in Table 9.1-5), one of the resulting strings (1 1 0 1
1) proves to be a very best solution indeed. Thus after mutation at random, a new
offspring (1 1 1 0 1) is produced which is an excellent choice.
227
SOFT COMPUTING TECHNIQUES
3. The term f (H, t) stands for the observed average fitness of schema H in
time step t:
This probability does not change throughout the execution of the selection loop.
Moreover, each of them individuals is select::d independent of the others. Hence
the number of selected individuals. which fulfil H, is binomially distributed with
228
Chapter 9: Genetic Algorithm
sample amount m and the probability. We obtain, therefore, that the expected
number of selected individuals fulfilling H is
……(24)
If two individuals at crossed, which bmh fulfil H, the two offspring’s again fulfil
H. The number of strings fulfilling H can only decrease if one string. which fulfils
H, is crossed with a string which does not fulfil H. but, obviously, only if the
cross sire is chosen somewhere in between the specifications of H. The
probability that the cross sire is chosen within the detaining length of H is
………………..(25)
Hence the survival probability ps of H, i.e., the probability that a string fulfilling
H produces an offspring also fulfilling H. can be estimated as follows (crossover
is only done with probability):
………..(26)
Selection and crossover are carried our independently, so we may compute the
expected number of strings fulfilling H after crossover simply as
………..(27)
After crossover, the number of strings fulfilling H can only decrease if a suing
fulfilling His ahered by mutation at a specification of H. The probability that all
specifications of H remain untouthed by mutation is obviously
………..(28)
The arguments in the proof of the Sthema Theorem can be applied analogously
too many other crossover and mutation operations.
229
SOFT COMPUTING TECHNIQUES
Suppose we have a gambling machine with two slots for coins and two arms. The
gambler can deposit the coin either two the left or the right slot. After pulling the
corresponding arm, either a reward is given or the coin is lost. For mathematical
simplicity, we just work with outcomes, i.e., the difference between the reward
(which can be zero) and the value of the coin. Let us assume that the left arm
produces an outcome with mean value 2 and a variance 22 while the right arm
produces an outcome with mean value 2 and variance 12. Without loss of
generality, although the gambler does not know this, assume that 1 > 2·
Now the question arises which arm should be played. Since we do not know
beforehand which arm is associated with the higher outcome, we are faced with
an interesting dilemma. Not only must we make a sequence of decisions about
which arm to play, we have to collect, at the same time, information about which
is the bener arm. This trade-off between exploitation of knowledge and its
exploitation is the key issue in this problem and, as rums out later, in GAs, too.
where q(n) is the probability that the worst arm is the observed best arm after 2n
expetimental trials. The underlying idea is obvious: In case that we observe that
the worse arm is the best, which happens with probability q(n), the total number
of trials allothed to the right arm is N - 11. The loss is, therefore, (J1 1 -Jl2 )(N-
n). In the reverse case where we actually observe that the best arm is the best,
which happens with probability I - q(n), the loss is only whir we get less
because we
230
Chapter 9: Genetic Algorithm
………..(29)
………..(30)
………..(31)
hough the direct connection is not yet fully clear, actually comes close
to giving at least an exponentially increasing number of trials to the
best building blocks. However, one may still wonder how the two-
armed blem and GAs are related. Let us consider an arbitrary string
position. e are two sthemata of order one which have their only
specification in this According to the Sthema Theorem, the GA
implicitly decides between
231
SOFT COMPUTING TECHNIQUES
these two sthemata, where only incomplete data are available (observed average
fitness values). In this sense, a GA solves a lot of two-armed problems in parallel.
So, we may ask what a GA really processes, strings or sthemata? The answer is
surprising: Both. Now a day, the common interpretation is chat a GA processes
an enormous amount of sthemata implicitly. This is accomplished by exploiting
the currently available, incomplete information about these sthemata
continuously, while trying to explore more information about them and other,
possibly better sthemata.
………..(32)
1, < E (n - l) + l
232
Chapter 9: Genetic Algorithm
Since with the help of the index we can identify the genes uniquely, genes may be
swapped arbitrarily without changing the meaning of the string. With appropriate
genetic operations, which also change the order of the paits, the GA could
possibly group coupled genes to get her automatically.
Figure 9.1-34 (A) Messy coding and (B) positional preference; Genes with
indices 1 and 6 occur twice, the firm occurrences are used.
233
SOFT COMPUTING TECHNIQUES
Owing to the free arrangement of genes and the variable length of the encoding,
we can, however, run into. Problems, which do not occur, in a simple GA. First of
all, it can happen that there are two entries in a string, which correspond to the
same index but have conflicting alleles. The most obvious way to overcome this
"over- specification" is positional preference- the first entry, which refers to a
gene, is taken. Figure 9.1-34(B) shows an example. The reader may have
observed that the genes with indices 3 and 5 do not occur at all in the example in
Figure 9.1-34(B). This problem of “under specification" is more complicated and
its solution is not as obvious as for over=-specification. Of course, a lot of
variants are reasonable.
One approach could be to theck all possible combinations and to rake the best one
(fork missing genes, there are 2k combinations). With the objective to reduce this
effort, Goldberg ct al. have suggested using so-called competitive templates for
finding specifications for missing genes. It is nothing else than applying a local
hill climbing method with random initial value to the k missing genes.
While messy GAs usually work with the same mutation operator as simple GAs
(every allele is altered with a low probability pM), the crossover operator is
replaced by a more general cut and splice operator which also allows to mate
parents with different lengths. The basic idea is to choose cut sites for both
parents independently and to splice the four fragments. Figure 9.1-35 shows an
example.
234
Chapter 9: Genetic Algorithm
according to changes in the population- the longer the population does not
improve, the higher
235
SOFT COMPUTING TECHNIQUES
Pm = k2/ (fmax - f)
236
Chapter 9: Genetic Algorithm
237
SOFT COMPUTING TECHNIQUES
Similarly, Pc should vary directly as fmax – f1', where f1 is the larger of the fitness
value of the solutions to be crossed. The expressions for Pc and Pm now take the
forms
………..(33)
(Here k1 and k2 have to be less than 1.0 to constrain Pc and Pm to the range 0.0-
1.0.)
Note that Pc and Pm are zero for the solution with the maximum fitness. Alsop, =
k1 for a solution with f = f, and Pm = k2 for a solution with f = f. For solution with
subaverage fitness values, i.e., f < f, Pc and Pm might assume values larger than
1.0. To prevent the overshooting of Pc and Pm beyond 1.0, we also have the
following constraints:
………..(34)
where k3, k4 < 1.0.
[Link].3 Practical Considerations and Choice of Values for k1, k2, k3 and k4
In the previous subsection, we saw that for a solution with the maximum fitness
value Pc and Pm are both zero. The best solution in a population is transferred
undisrupted into the next generation. Together with the selection mechanism, this
may lead to an exponential growth of the solution in the population and may
cause premature convergence. To overcome the above-mued problem, we
introduce a default mutation rate (of 0.005) for every solution in the Adaptive
Genetic Algorithm (AGA).
We now discuss the choice of values for k1, kz, k3 and k4. For convenience, the
expressions for Pc and Pm are given as
………..(35)
where k1, k2, k3, k4 < 1.0.
238
Chapter 9: Genetic Algorithm
It has been well established in GA literature that moderately large values of Pc (0.5
< Pc < 1.0) and small values of Pm (0.001 < Pm < 0.05) are essential for the
successful working of GAs. The moderately large values of Pc promote the
extensive recombination of sthemata, while small values of Pm are necessary to
prevent the disruption of the solutions. These guidelines, however, are useful and
relevant when the values of Pc and Pm do not vary.
One of the goals of the approach is to prevent the GA from getting stuck at a local
optimum. To achieve this goal, we employ solutions with subaverage fitnesses to
search the search space for the region containing the global optimum. Such
solutions need to be completely disrupted, and for this purpose we use a value of
0.5 for k4. Since solutions with a fitness value of f should also be disrupted
completely, we assign a value of 0.5 to k2 as well.
Based on similar reasoning, we assign k1and k3 a value of 1.0. This ensures that
all solutions with a fitness value less than or equal to f compulsorily undergo
crossover. The probability of crossover decreases as the fitness value (maximum
of the fitness values of the parent solutions) tends to fmax and is 0.0 for solutions
with a fitness value equal to fmax.
The basic idea is co divide the optimization task into two complementary parts.
The GA does the coarse, global optimization while local refinement is done by
the conventional method (e.g. gradient-based, hill climbing, greedy algorithm,
simulated annealing, ere.). A number of variants are reasonable:
239
SOFT COMPUTING TECHNIQUES
In this section a novel optimization approach is used that switthes between global
and local search methods based on the local topography of the design space. The
global and local optimizers work in concert to efficiently locate quality design
points better than either could alone. To determine when it is apptopriate to
execute a local search, some characteristics about the local area of the design
space need to be determined. One good source of information is contained in the
population of designs in the GA. By calculating the relative homogeneity of the
population we can get a good idea of whether there are multiple local optima
located within this local region of the design space.
By calculating the coefficient of variance of the both the design variables and the
objective function as the optimization progresses, it can also be used as a criterion
to switch from me global to the local optimizer. As the variance of the objective
values and design variables of the population increases, it may indicate that the
optimizer is exploting new areas of the design space or hill climbing. If the
variance is decreasing, the optimizer may be converging toward local minima and
the optimization process could be made more efficient by switching to a local
search algorithm.
The second method, regression analysis, used in this section helps us determine
when to switch between the global and local optimizer. The design data present in
the current population of the GA can be used toprovide information as to the local
topography of the design space by attempting to fit models of various order to it.
models are linear and quadratic polynomials created by performing ordinary least
squares regrssion on a set of analysis data.
To make dear the use of regression analysis in this way, consider Figure 9.1-37,
which represents a complex design space. Our goal is to minimize this function,
and as a first step the GA is run. Suppose that afrer acertain number of
generarions the population consists of the sampled points shown in the figure.
Since the population of the GA is spread throughout the design space, having yet
to converge into one of the local minima, it seems logical to continue the GA for
additional generations. Ideally, before the local optimizer is run it would be
beneficial to have some confidence that its starting point is somewhere within the
mode that contains the optimum. Fitting a second-order response surface to the
data and noting the large error (the R2 value is 0.13), ther is a dear indication that
the GA is currently exploting multiple modes in the design space.
In Figure 9.1-38, the same design space is shown but afrer the GA has begun to
converge into the part of the design space containing the optimal design. Once
again a second-order approximation is fir to GA's population. The dotted line
connects the points predicted by the response surface. Note how much smaller the
error is in the approximation (the R2 is 0.96), which is a good indication that the
GA is currently exploting a single mode within the design space. At this point, the
local optimizer can be made to quickly converge to the best solution within this
area of the design space, thereby avoiding the slow convergence propenies of the
GA.
After each generarion of the global optimizer the values of the coefficient of
determination and the coefficient of variance of the enrire population are
compared with the designer specified threshold levels.
241
SOFT COMPUTING TECHNIQUES
the local search is executed when the threshold levels are exceeded,
and solution is passed back and integrated two the global search. The
scops when convergence is achieved for the global optimization
242
Chapter 9: Genetic Algorithm
It has been established chat GA's efficiency co find optimal solution is largely
determined by the population size. With a larger population size, the genetic
diversity increases, and so the algorithm is more likdy to find a global optimum!
A large population requires more memory to be scored; it has also been ptoved
that it takes a longer time to converge. If n is the population size, the convergence
is expected aft:er n log(n) function evaluations.
The use of mday's new parallel computers not only provides more storage space
but also allows the use of several processors to produce and evaluate more
solutions in a smaller amount of time. By parallelizing the algorithm, it is possible
D increase population size, reduce the computational cost, and so improve the
performance of the GA.
Probably the first attempt to map GAs to existing parallel computer architectures
was made in 1981 by John Grefensrerre. But obviously today, with the emergence
of new high-performance computing (HPC), PGA is really a flourishing area.
Researthers try to improve performance of GAs. The stake is to show that GAs
are one of the besr optimization methods to be used with HPC.
244
Chapter 9: Genetic Algorithm
245
SOFT COMPUTING TECHNIQUES
"slaves." The master processor is also responsible for collecting the result of the
evaluation. A drawback of this distributed memory implementation is that a
bottleneck may occur when slaves are idle while only the master is working. But
a simple and good use of the master processor can improve the load balancing by
distributing individuals dynamically tothe slave processors when they finish their
jobs.
This kind of global parallelization simply shows how easy it can be to transpose
any GA onto a parallel machine and how a speed-up sublinear to the number of
processors may be expected.
246
Chapter 9: Genetic Algorithm
population.
247
SOFT COMPUTING TECHNIQUES
Figure 9.1·41 A sthematic of a fine-grained PGA. This class ofPGAs has one
spadally distributed popularion, and ir can be implemented very efficiently on
massively parallel compmers.
248
Chapter 9: Genetic Algorithm
Multiple-deme PGAs are known with different names. Sometimes they are known
as "distributed" GAs, because they are usually implemented on distributed
memory MIMD computers. Since the computation to communication ratio is
usually high, they are occasionally called coarse-grained GAs. Finally,
multipledeme GAs resemble the "island model" in Population Genetics which
considers relatively isolated demes, so the PGAs are also known ·as "island"
PGAs. Since the size of the demes is smaller than the population used by a serial
GA, we would expect that lhe PGA converges faster. However, when we compare
the performance of the serial and the parallel algorithms, we must also consider
the qualicy of the solutions found in each case. Therefore, while it is true that
smaller demes converge faster, it is also true iliar the qualicy of the solution might
be poorer.
The final merhod to parallelize GAs combines multiple demes with masrerslave
or finegrained GAs. We call this class of algorithms hierarchical PGAs, because
249
SOFT COMPUTING TECHNIQUES
250
Chapter 9: Genetic Algorithm
The global [Link] model does nor assume anything about the underlying
computer architecture, and it can be implemented efficiently on shared memory
and distributed-memory computers. On a sharedmemory multiprocessor, the
popul:.tion could be sloted in shared memory and each processor can read the
individuals assigned co it and write the evaluation results back without any
conflicts.
251
SOFT COMPUTING TECHNIQUES
Probably the first systematic srudy of PGA<i with multiple populations was
Grosso's dissertation. His objective was to simulate the interaction of several
parallel subcomponents of an evolving population. Grosso simulated diploid
individuals (so there were two subcomponentS for each "gene"), and the
population was divided into five demes. Each deme exchanged individuals with
all the others with a fixed migration rate.
With conttolled expetiments, Gtosso found cha the improvement of the average
population fitness was fasrer in the smaller demes rhan in a single large panmictic
population. This confirms a longheld principle in Population Genetics: favorable
traits spread faster when the demes are small chan when the demes are large.
However, he also observed that when the demes were isolated, the rapid rise in
fitness stopped at a lower fitness value than with the large population. In other
words, the quality of the solution found after convergence was worse in the
isolated case chan in the single population.
With a low migration rate, the demes still behaved independently and exploted
different regions of the search space. The migrants did not have a significant
effect on the receiving deme and the quality of the solutions was similar to the
case where the demes were isolated. However, at intermediate migration rates the
divided population found solutions similar to those found in the panmictic
population. These observations indicate that there is a critical migration rate
below which the performance of the algorithm is obstructed by the isolation of
the demes, and above which the partitioned population finds solutions of the same
quality as the panmictic population.
It is interesting that such important observations were made so long ago, at the
same time that other systematic studies ofPGAs were underway. For example,
Tanese ptoposed a PGA with the demes connected on a fourdimensional
hypercube topology. In Tanese's algorithm, migration occurred at fixed intervals
between processors aJong one dimension of the hypercube. The migrants were
chosen ptobabilistically from the best individuals in the subpopulation, and they
replaced the worst individuals in the receiving deme. Tanese carried out
252
Chapter 9: Genetic Algorithm
three sees of
253
SOFT COMPUTING TECHNIQUES
expetiments. In the first, the interval between migrations was ser to five
generations, and the number of processors varied. In tests with two migration
rates and varying the number of processors, the PGA found results of the same
quality as the serial GA. However, it is difficulc to see from the xpetimental
results if the PGA found the solutions sooner than the serial GA, because the
range of the cimes is too large. In the second set of expetiments, Tanese varied
the mutation and crossover rates in each deme, attempting to find parameter
values to balance explotation and exploitation. The third set of expetiments
studied the effect of the exchange frequency on the search, and the results showed
thar migrating too frequendy or too infrequently degraded the performance of the
algorithm.
The multideme PGAs are popular due to the following several reasons:
l. Multiple-deme GAs seem like a simple extension of the serial GA. The
recipe is simple: take a few conventional (serial) GAs, run each of them on
a node of a parallel computer, and at some predetermined times exchange a
few individuals.
2. There is relatively little extra effort needed to convert a serial GA into a
multiple-deme GA. Most of the program of the serial GA remains the same
and only a few subtoutines need to be added co implement migration.
3. Coarse-grain parallel computers are easily available, and even when they
are not, it is easy co simulate one with a network of workstations or even on
a single processor using free software (like MPI or PVM).
There are a few important issues noted fromthe above sections. For example,
PGAs are very ptomising in termsofthegains in performance. Also, PGAsare
more complex than their serial counterpartS. In particular, the migration of
individuals from one deme to another is conttolled by several p:uameters like (a)
the topology that defines the connections between the subpopulations, (b) a
migr;uion r;Ht:: [Link] conttols how m;my individuals migrate and (c) a migration
inrerval that affecrs thefreqU<'lK·of mir.1inn. In rht.' btl' 1 1lS(h .ullll·arl· 1990
the research on PGA:; began to explote alternatives to make PGAs faster and to
understand better how they worked.
Around this time the first theorecical srudies on PGAs began to appear and the
empirical research attempted to identify favorable parameters. This section
reviews some of that early theoretical work and expetimental srudies on
254
migration and
Chapter 9: Genetic Algorithm
One of the directions in which the field matured is that PGAs began to be tested
with very large and difficult test functions.
If we want to compare this model to the island model, each neighbothood can be
considered as a different deme. But here, the demes overlap ptoviding a way w
disseminate good solutions actoss the entire population. Thus, the topology does
not need w explicitly define migration toads and migration rare.
To sum up, with parallelization of GA, all the different models ptoposed and all
the new models we can imagine by mixing those ones, can demonstrate how well
GA are adapted to parallel compmarion. In fact, the too many implementations
reponed in the literature may even be confusing. We really need to understand
what truly affects the performance of PGAs.
Fine-grained PGAs have only one population, but have a spatial structure that
limits the interactions between individuals. An individual can only compere
and mate
244
Chapter 9: Genetic Algorithm
with its neighors; but since the neighbothoods overlap good solutions may
disseminate actoss the entire population.
Some hybrids have a fine-grained GA at the lower level (see Figure 9.1-43). For
example Gruau invented a "mixed" PGA. In his algorithm, the population of each
deme was placed on a two-dimensional grid, and the demes themselves were
connected as a two-dimensior:tal toM. Migration between demes occurred at
regulae intervals, and good results were reported for a novel neucal network
design and uaining application.
245
SOFT COMPUTING TECHNIQUES
Figure 9.1-44 A sthematic of a hierarchical PGA. At the upper level this hybrid is
a mulci-deme PGA where each node is a master-slave GA.
Figure 9.1·45 This hybrid uses mulciple-deme GAs ar both the upper and the
lower levels. At the lower level the migration rate is faster and the
communicarions topology is much denser than at the upper level.
246
Chapter 9: Genetic Algorithm
We can notice chat this time the nature of the algorithm changes. An individual
can no longer breed with any other from the entire population, but only with
individuals of the same island. Amazingly, even if this algorithm has been
developed to be used on several processors, it is wonh simulating it sequentially
on one processor. It has been shown on a few problems that better results can be
achieved using this model. This algorithm is able to give different suboptimal
solutions, and in many problems, it is an advantage if we need to determine a kind
of landscape in the search space to know where the good solutions are located.
Another great advantage of the island model is iliat cite population in each island
can evolve wiili different rules. That can be used for multicriterion optimization.
On each island, selection can be made according to different fitness functions,
representing different criterions. For example it can be useful to have as many
islands as criteria, plus another central island where 'selection is done with a
multicriterion fitness function.
The migration operator allows individuals to move betwen islands, and therefore,
m mix criteria.
In lirerarure this model is sometimes also referred as the coarsegrained PGA. (In
parallelism, grain size refers m the ratio of time spent in computation and time
spent in communication; when the ratio is high the processing is called
coarsegrained). Sometimes, we can also find the term "distributed" GA, since
247
SOFT COMPUTING TECHNIQUES
248
Chapter 9: Genetic Algorithm
Technically there are three important features in the coarsegrained PGA: the
topology that defines connections between sub populations, migration rare that
conttols how many individuals migrate, migration intervals chat affect how often
the migration occurs. Even if a lot of work has been done to find optimal
mpology and migration parameters, here, intuition is still used more often than
analysis with quite good results.
Many topologies can be defined m connect the demes, but the most common
models are the island model and the steppingstones model. In the basic island
model, migration can occur between any subpopulations, whereas in the Stepping
stone demes are disposed on a ring and migration is restricted to neighbouring
demes. Works have shown that cite topology of the space is nor so important as
long as ir has high connectivity and small diameter to ensure adequate mixing as
time proceeds.
Choosing the right time for migration and which individuals should migrate
appears to be more complicated. Quite a lot of work is done on this subject, and
problems come from the following dilemmas. We can observe that species are
converging quickly in small isolated populations. Nevertheless, migrations should
occur after a time long enough for allowing the development of goods
characteristics in each subpopulation. It also appears that, immigration is a trigger
for evolutionary changes. If mjgrarion occurs after each new generation, the
algorithm is more or le equivalent to a sequencia\ GA with a larger population. In
praaice, migration occurs either after a fixed number of iterations in each deme or
at uniform periods of time. Migrants are usually selected randomly from the best
individuals in the population and they replace the worst in the receiving deme. In
fact, intuition is still mainly used to fix migration rare and migration intervals;
there is absolurely nothing rigid, each personal cooking recipe may give good
results.
249
SOFT COMPUTING TECHNIQUES
are paired for breeding based on two mate- selection sthemes (Huang, 2001):
individuals being assigned mates by natural
250
Chapter 9: Genetic Algorithm
selection only and individuals being allowed to actively choose their mares. In the
Iauer case, individuals are able to distinguish candidate mates that have the same
fitness yet have different string structures, which may lead to quite different
performance after crossover. This is nor achievable by natural selection alone
since it assigns individuals of the same fitness the same probability for being
mares, without explicitly raking into account string suucrures. In short, in the
breeding phase individuals manage to construct even more ptomising sthemata
thtough the recombination of highly fir building blocks found in the first phase.
Owing to the thatacteristic of independent sampling of building blocks that
distinguishes the ptoposed GAs from tonventional GAs, we name this type of GA
independent sampling genetic algorithms (ISGAs).
The motivation of the two phased ISGAs was partially from the messy genetic
algorithms (mGAs). The two stages employed in the mGA.s are "prtwordial
phase" and "juxtaPositional phase," in which the mGAs first emphasize candidate
building blocks based on the guess at the order k of small sthemata, then just
aposing them to build up global optima in the second phase by "cut" and "splice"
operators. However, in the first phase, the mGAs still adopt centralized selection
to emphasize some candidate sthemata; this in rum results in the loss of samples
of other potentially ptomising sthemata. By tontrast, IS GAs manage to postpone
the emphasis of candidate building blocks to the latter stage, and highlight the
fearure of independent sampling of building blocks to suppress hitchhiking in
251
SOFT COMPUTING TECHNIQUES
the first
252
Chapter 9: Genetic Algorithm
In this section, we develop a new searching strategy, BBDS, for each individual
to evolve based on the accumulated knowledge for potentially useful building
blocks. The idea is to allow each individual to probe valuable information
toncerning beneficial sthemata thtough resting its fitness increase since each time
a fitness increase of a string tould tome from the presence of useful building
blocks on it. In short, by systematically resting each bit to examine whether this
bit is associated with the fitness increase during each cycle, a cluster of bits
tonstituting potentially beneficial sthemata will be untovered. Iterating this
process guarantees the formation oflonger and longer candidate building blocks.
254
Chapter 9: Genetic Algorithm
Once these genes tome in sight simultaneously, [hey tontribute a fitness increase
w the string tontaining them; thus any .loss of one of these genes leads to the
fitness decrease of the string. This is essentially what step 2 does and after this
step we should be able to tollect a set of genes of candidate sthemata. Then at step
3, we keep the tollected genes of candidate sthel) lata fixed and randomly
generate other bits, awaiting other building blocks to appear and bring forth
another fitness in crease.
However, step 2 in this strategy only emphasizes the f1mess dtop due to a
particular bit. It ignores the possibility that the same bit leads to a new fitness rise
because many loci tould interact in an extremely non linear fashion. To rake this
into actount, the second version ofBBDS is inttoduced thtough the change in seep
2 as follows.
Step 2: Except the genes of candidate sthemata tollected, from left to right,
successively all the other bits, one at a time, evaluate the resulting string. If the
resulting fitness is less than Fit, retord this bit's position and original value as a
gene of candidate sthemata. If the resulting fitness exceeds Fit, substitute this bit's
'new' value for the old value, replace Fit by this new fitness, retord this bit's
posicion and 'new' value as a gene of candidate sthemata, andre-execute this step.
Because this version of BBDS cakes into consideration the fitness increase
resulted from that particular bit, iris expected to cake less time for detecting.
Other versions of RBDS are of tourse possible. For example, in step 2, if the same
bit resuhs in a fitness increase, ir can be retorded as a gene of candidate sthemata,
and the ptocedure tontinues to test the residual bits yetwithour tompletely
traveling back to the first bit to reexamine each bit. However, the empirical
results obtained rhus far indicate that the performance of this alternative is quire
similar to that of the second version. More expetimental results are needed to
distinguish the difference between them.
255
SOFT COMPUTING TECHNIQUES
fitness landscape. Since building blocks for some strings to leave suboptimal
regions may be embedded in other srrings, the search for ptoper maring partners
and then exploiting the building blocks on them are critical for overwhelming the
difficulty of strings being trapped in undesired regions. In Huang (2001) the
importance of mate selection has been investigated and the results showed that
the GAs is able to improve their performance when the individuals are allowed to
select maces to a larger degree.
We adopt the tournament selection stheme (Mitthell, 1996) as the tole of natural
selection and the mechanism for choosing mates in the breeding phase is as
follows:
During each mating evem, a binary tournament selection with ptobabilicy 1.0 is
performed to select the first individual out of the two fittest randomly sampled
individuals according to the following sthemes:
1. Run the binary tournament selection again to choose the partner.
2. Run another two times of the binary tournament selection to choose two
highly fit candidate partners; then the one more dissimilar to the first
individual is selected for mating.
The implementation of the breeding phase is thtough iterating each breeding cycle
which consists of (a) two parents obtained on the basis of the mateseleccion
sthemes above. (b) Two-point crossover operator (crossover rate 1.0) is applied to
these parents. (c) Both parents are replaced with both offsprings if any of the two
offsprings is better than them. Then steps (a), (b) and (c) are repeated until the
population size is reathed and this is a breeding cycle.
b = (Xi, ….,XN)
257
SOFT COMPUTING TECHNIQUES
Flat crossover: Given two parents b1 = (x1/ 2, ... , x1/N) and b2 = (x2/1, ... , x2/N), a
vector of random values from the unit interval (AJ , ... , AN) is chosen and the
offspring b = (x{, ... , xfv) is tomputed as a vector of linear tombinations in the
following way (for all i = 1, ... , N):
x1i = i - x1i + (1 - i) – x2i
Simple crossover is nothing else but classical one-point crossover for real vectors,
i.e., a crossover site k 2{ 1, ... , N- 1} is chosen and cwo offspring are created in
the following way:
b1 = (x1i, ……, x1k, x1k+1 ….,
x2N) bN = (x21, ……, x2k, x1k+1
…., x1N)
258
Chapter 9: Genetic Algorithm
259
SOFT COMPUTING TECHNIQUES
2.
Nonuniform mutation : In nonuniform mutation, the possible impact of
mutation decreases with the number of generations. Assume that fmax is the
predefined maximum number of generations. Then, with the same setup as
in random mumion, the allele xi is replaced by one of the two values
= x1+A (t,b;- x1)
:if= x;-A (r,x;- a;)
In this formula, A is a uniformly distributed random value from the unit interval.
The parameter r determines the influence of the generation index ton the
disrribution of mutation step sizes over the imerval IO,xl.
Messages are binaty strings of the same length k. More formally, a message
belongs w {0, l}k. The rule base consists of a fixed number (m) of rules
(classifiers) which tonsist of a fixed number (r) of conditions and an acrion,
where both conditions and actions are strings oflength k over the alphabet {0, 1,
*}.The asterisk plays the tole of a wildcard, a 'don't care' symbol.
A condition is matthed if and only if there is a message in the list which matthes
the tondition in all nonwildcard positions. Moreover, conditions, except the first
one, may be negated by adding a'-' prefix. Such a prefixed tondition is satisfied if
and only if there is no message in the list which marthes the string associated with
the tondition. Finally, a rule fires if and only if all the conditions are satisfied, i.e.,
the conditions are tonnected with AND. Such 'firing' rules tompere to put their
action messages on the message list.
260
Chapter 9: Genetic Algorithm
In the action pans, the wildcard symbols have a different meaning. They take
thetole of 'pass through' element. The outpm message of a firing rule, whose
action parr tontains a wildcard, is composed from the actually the reason why
Ilegations of the first conditions are not allowed. More formally; the outgoing
message m is defined as
where a is the action part of the classifier and m is the.(Ilessage which matthes the
first tondition. Formally, a classifier is a suing of the form
Cond1,|’-‘|| Cond2, ……, |’-‘ Cond,/Action
where the brackets shouJd express the optionalicy of the "-" prefixes. Depending
on the toncrete nee¢; of the task to be solved, it may be desirable to allow
messages to be preserved for the next step. More specifically, if a message is not
interpreted and removed by the effectors interface, it can make another classifier
fire in the next step. In practical applications, this is usually actomplished by
reserving a few bits of the messages for identifying the origin of the messages (a
kind of variable index called tag).
Tagging offers new opportunities to transfer information about the current step
intothe next step simply by placing ragged messages on the list, which are not
interpreted, by the output interface. These messages, which obviously tontain
information about the previous step, can support the decisions in the next step.
Hence, apptopriate use of rags permits rules to be toupled to act sequenrially. In
some sense, such messages are the memory of the system.
A single execmion cycle of the production system consists of the following steps:
1. Messages from the environment are appended tothe message list.
2. All the conditions of all classifiers are thecked against the message list w
obtain the set of firing rules.
3. The message list is erased.
4. The firing classifiers participate in a tompetition to place their messages on
the list.
5. The winning classifiers place their actions on the list.
6. The messages directed to the effectors are executed.
261
SOFT COMPUTING TECHNIQUES
This ptocedure is repeated iteratively. How step 6 is done, if these messages are
deleted or nor, and so on, depends on the toncrete implementation. It is, on the
one hand, possible to choose a representation such that the effectors can interpret
each output message. On the other hand, it is possible to direct messages
explicitly to the effectors with a special tag. If no messages are directed to the
effectors, the system is in a iliinking phase.
In rhis equation, Sar1 is the set of indices of all classifiers which are satisfied at
timet. Classifiers which get the right to post their output messages are called
winning classifiers.
262
Chapter 9: Genetic Algorithm
where w1 is the number of winning agents in the actual time step. A winning
agent pays its bid to its suppliers which share the bid among each other equally in
the simplest case:
If a winning agent has also been active in the previous step and supplies another
winning agent, the value above is additionally increased by one portion of the bid
the tonsumer offers. In the case that two winning agents have supplied each other
mutually, the portions of the bids are exchanged in the above manner. The
SHengrhs of all other classifiers Rm which are neither winning agents nor
suppliers of winning agents, are reduced by a certain factor (they pay a rax):
un,1+1 = Nn,1 (1 – T)
T is a small value lying in the interval [0, 1]. The intention of taxation is to punish
classifiers which never contribute anything to the outputof thesystem. With this
concept, redundant classifiers, which never become active, can be filtered out.
The idea behind credit assignment in general and bucket brigade in particular is w
increase the strengths of rules, which have ser the stage for later successful
actions. The problem of determining such classifiers, which were responsible for
conditions under which it was later on possible to receive a high payoff, can be
very difficult. Consider, for instance, the game of thess again, in which very early
moves can be significant for a late success or failure. In fact, the bucker brigade
algorithm can solve this problem, although strength is only transferred to the
suppliers, which were active in the previous step. Each time the same sequence is
activated, however, a little bir of the payoff is transferred one step back in the
sequence. It is easy to see that repeated successful execution of a sequence
increases the mengrhs of all involved classifiers.
263
SOFT COMPUTING TECHNIQUES
Figure 9.1-46 shows a simple example of how the bucker brigade algorithm
works. For simplicity, we consider a sequence of five classifiers which always bid
20% of their strength. Only after the fifth step, after the activation of the fifth
classifier, a payoff of 60 is received. The further development of the strengths in
this example is shown in the Table lS-7. It is easy to see from this example that
the reinforcement of the strengths is slow at the beginning, but it accelerates later.
Exactly this property tontributes much to the robustness of classifier systems -
they tend to be cautious at the beginning, trying not to rush conclusions, but, after
a certain number of similar situations, the system adopts the rules more and more.
264
Chapter 9: Genetic Algorithm
The purpose of the rule distovery system is to eliminate low-firred rules and to
replace them by hopefully better ones. The fitness of a rule is simply its strength.
Since the classifiers of a Holland classifier system themselves are strings, the
application of a GA to the problem of rule induction is straightforward, though
many variants are reasonable. Almost all variants have one thing in common: the
GA is nor invoked in each time step, but only every nth step, where 11 has to be
set such that enough information about the performance of new classifiers can be
obtained in the meantime. A. Geyer-Schuh., for instance, suggests the following
ptocedure, where the strength of new classifiers is initialized with the average
strength of the current rule base:
1. Select a subpopulation of a certain size at random.
2. Compute a new set of rules by applying the genetic operations- selection,
crossingover and muration - to this subpopularion.
3. Merge the new sub population with the rule base omitting duplicates and
replace the worst classifiers.
This process of acquiring new rules has an interesting sideffect. Iris more rhan
just the exchange of parts of conditions and actions. Since we have nor stared
restrictions for manipulating rags, the GA can retombine parts of already existing
265
SOFT COMPUTING TECHNIQUES
rags m invent new tags. In the following. rags spawn related rags establishing
new touplings. These new tags survive if they tonrribute to useful interactions. In
this sense, the GA additionally creates experience-based internal structures
autonomously.
266
Chapter 9: Genetic Algorithm
267
SOFT COMPUTING TECHNIQUES
Figure 9.1-47 below is a flowchart showing the executional steps of a run ofGP.
The flowchart shows the genetic operations of crossover, reproduction and
mutation as well as the architecrurealrering operations. This flowchart shows a
two- offspring version of the crossover operation.
268
Chapter 9: Genetic Algorithm
269
SOFT COMPUTING TECHNIQUES
270
Chapter 9: Genetic Algorithm
The fitness measure is, for many practical problems, mulriobjecrive in the sense
that it tombines two or more differem elements. The different elements of the
fitness measure are often in tompetition with one another to some degree.
The creation of the initial random population is, in effect, a blind random search
of the search space of the problem. It provides a baseline for judging future search
effons. Typically, the individual programs in generation 0 all have exceedingly
poor fitness. Nevertheless, some individuals in the population are {usually) more
fir than odters. The difference. in fitness are dten exploited by GP. GP applies
Darwinian selection and the genetic operations to create a new population of
offspring programs from the current population.
271
SOFT COMPUTING TECHNIQUES
fitness. In this ptobabilistic selection process, better individuals are favored over
inferior individuals. However, the best individual in the population is not
necessarily selected and the worst individual in the population is not necessarily
passed over.
After the genetic operations arc performed on the current population, the
population of offspring (i.e. the new generation) replaces the current population
{i.e., the now- old generation). This iterative process of measuring fitness and
performing the genetic operations· is reeated over many generations.
The run of GP terminates when the termination criterion (as provided by the fifth
preparatory step) is satisfied. The outcome of the run is specified by the method
of result designation. The best individual ever encountered during the run (i.e.,
the best-so-far individual) is typically designated as the result of the run.
[Link].1 Human-Competitive
In attempting to evaluate an automated problem-solving method, the question
arises as to whether there is any real substance tothe demonstrative problems that
are published in connection with the method. Demonstrative problems in the
fields of artificial intelligence and machine learning are often connived to
problems that circulate exclusively inside academic groups that study a particular
methodology. These problems typically have little relevance to any issues
pursued by any scientist or engineer outside the fields of artificial intelligence and
machine learning.
ln his 1983 talk entitled "Al: Where It Has Been and Where It Is Going," machine
learning pioneer Arthur Samuel said:
The aim is …… to get machines to exhibit behaviour, which of done by human,
would be assumed to involve the use of intelligence.
272
Chapter 9: Genetic Algorithm
Samuel’s statement reflects the common goat articulated by the pioneers of the
1950s in the fields of artificial intelligence and machine learning. Indeed, getting
machines to produce human like results is the reason for the existence of the
fields of artificial intelligence and machine learning. To make this goal more
concrete, we say that a result is “human-competitive” if it satisfies one or more of
the eight criteria in Table 9.1-8. These eight criteria have the desirable attribute of
being at arms-length from the fields of artificial intelligence, machine learning
and GP. That is a result cannot acquire the rating of ‘human-competitive’ merely
because it is endorsed by researchers inside the specialized fields that are
attempting to create machine intelligence, machine learning and GP. That is, a
result cannot acquire the rating of ‘human-competitive’ merely because it is
endorsed by researchers inside the specialized fields that are attempting to create
machine intelligence. Instead a result produced by an automated method must
earn the rating of human- competitive dependent of the fact that it was generated
by an automated method.
[Link].2 High-Return
What is delivered by the accrual automated operation of an artificial method in
comparison to the amount of knowledge, information, analysis and intelligence
that is pre-supplied by the human employing the method?
Table 9.1·8 Eight criteria for saying that an automatically created research is
human-competitive
Criterion
273
SOFT COMPUTING TECHNIQUES
The aim of the fields of artificial intelligence and machine learning is to get
computers to automatically generate human-competitive results with a high AI
ratio- not to have humans generate human-competitive results themselves.
[Link].3 Routine
Generality is a precondition to what we mean when we say that an automated
274
Chapter 9: Genetic Algorithm
275
SOFT COMPUTING TECHNIQUES
In the 1950s, the terms machine intelligence, artificial intelligence and machine
learning all referred to the goal of getting "machines to exhibit behaviour, which
if done by humans, would be assumed to involve the use of intelligence" {to
again quote Arthur Samuel).
However, in the intervening five decades, the terms "artificial intelligence" and
"machine learning" progressively diverged from their original goal-oriented
meaning. These terms are now primarily associated with particular methodologies
for attempting to achieve the goal of getting computers to automatically solve
problems. Thus, the term "artificial intelligence" is today primarily associated
with attempts to get computers to solve problems using methods that rely on
knowledge, logic, and various analytical and mathematical methods. The term
"machine learning" is today primarily associated with attempts to get computers
to solve problems that use a particular small and somewhat arbitrarily chosen set
of methodologies (many of which are statistical in nature). The narrowing of
these terms is in marked contrast to the broad field envisioned by Samuel at the
time when he toned the term "machine learning" in the 1950s, the thatter of the
original founders of the field of artificial indigence, and the broad vision
encompassed by Turing's term "machine intelligence." Of course, the shift in
focus from broad goals to narrow methodologies is an all too common
sociological phenomenon in academic research.
276
Chapter 9: Genetic Algorithm
In his 1948 paper, Turing identified three broad approaches by which human
competitive\'e machine intelligence might be achieved: The first approach was a
logic-driven search. Turing's interest in this approach is not surprising in light of
Turing's own pioneering work in the 1930s on the logical foundations of
computing. The second approach for achieving machine intelligence was what he
called a "cultural search" in which previously acquired knowledge is
accumulated, stored in libraries and brought to bear in solving a problem - the
approach taken by modern knowledge-based expert systems. Turing's first two
approaches have been pursued over the past 50 years by the \'past majority of
researchers using the methodologies that are today primarily associated with the
term "artificial inelegance.''
Since their only construct are nested lists programs in LISP-like languages
already have a kind of tree-like Structure. Figure 9.1-48 shows an example how
the function 3x + sin(x + I) can be implemented in a LISP like language and how
such an LISP- like Function can he split up into a tree. Let can be noted that the
tree n: presentation corresponds to the nested lists. The program consists of tonic
expressions, like variables and constants, which act as leave nodes while
functions act as no leave nodes
277
SOFT COMPUTING TECHNIQUES
< non terminal > := < deriv1 > | < deriv2> | ... | < deriv11 >;
defines how a non-terminal symbol may be expanded, where the different varies
are separated by vertical bars.
In order to get a feeling of how to work with the BNF grammar description, we
will now show step-by-step how the expression (NOT (x OR y)) can be derivated
from the above language. For simplicity, we omit quotation marks for the
terminal symbols:
1. We have to begin with the start symbol: <exp>
2. We replace hexpi with the second possible derivation:
<exp> (<neg><exp>)
278
Chapter 9: Genetic Algorithm
3. The symbol <neg> may only he expanded with the terminal symbol NOT:
(<neg> <exp>) (NOT <exp>i
Such a recursive derivation has an inherent tree structure. For the above example,
this derivation tree has been visualized in Figure 9.1.49. The syntax of modern
programming languages can be specified in BNF. Hence, our data model would
be applicable to all of them. The question is whether this is useful. Koza’s
hypothesis includes that the programming language has to be chosen such that the
given problem is solvable. This does not necessarily imply that we have no
choose the language such that virtually any solvable problem can be solved. It is
obvious that the size of the search grows with the complexity of the language. We
know that the size of the search space influences the performance of a GA – the
larger the language. We know that the size of the search space influences the
performance of a GA – the larger the slower.
279
SOFT COMPUTING TECHNIQUES
For representing rational functions with integer coefficients, [Link] sufficient to add
the division symbol "f" to the possible derivations of the binary operator <bin>.
280
Chapter 9: Genetic Algorithm
There are basically two different variants of how w generate random programs
with respect to a given BNF grammar:
The derivation tree based representation overcomes this problem in a very elegant
way. If we only exchange subtrees which start from the same nonterminal
symbol, crossover can never violate syntactical correctness. In this sense, the
derivation tree model provides implicit type checking. In order to demonstrate in
more detail how this crossover operation works, let us reconsider the example of
binary logical expressions. k parents, we take the following expressions:
(NOT (x OR y))
((NOT x) OR (x AND
y))
Figure l5-50 shows graphically how the two children (NOT (x OR (x AND y)))
((NOT x) OR y) are obtained.
281
SOFT COMPUTING TECHNIQUES
282
Chapter 9: Genetic Algorithm
283
SOFT COMPUTING TECHNIQUES
284
Chapter 9: Genetic Algorithm
The advantage of the GA approach is the ease with which it can handle arbitrary
kinds of constraints and objectives; all such things can be handled as weighted
components of the fitness function, making it easy to adapt the GA scheduler to
the particular requirements of a very wide range of possible overall objectives.
GAs have been used for problem-solving and for modeling. GA are applied to
many scientific, engineering problems, in business and entertainment including:
285
SOFT COMPUTING TECHNIQUES
structure
286
Chapter 9: Genetic Algorithm
prediction. GAs have also been used to design neural networks, to evolve
rules for learning classifier systems or symbolic production systems, and to
design and control robots.
4. Economic models: GAs have been used to model processes of innovation,
the development of bidding strategies and the emergence of economic
markets.
5. Immune system models: GAs have been used to model various aspects of
the natural immune system, including somatic mutation during an
individual's lifetime and the discovery of multi-gene families during
evolutionary time.
6. Ecologjcal models: GAs have been used to model ecological phenomena
such as biological arms races, host-parasite to evolutions, symbiosis and
resource flow in ecologies.
7. Population genetics models: GAs have been used to study questions in
population genetics, such as 'under what conditions will a gene for
recombination be evolutionarily viable?'
8. Interactions between evolution and learning. GAs have been used to study
how individual learning and species evolution affect' one another.
9. Models of social systems: GAs have been used to study evolutionary aspects
of social systems, such as the evolution of cooperation (Chughtai, 1995),
the evolution of communication and trail-following behavior in ants.
9.1.19 Summary
Genetic algorithms are original systems based on the supposed functioning of the
living. The method is very different & the classical optimization algorithms as it:
1. Uses the encoding of the parameters, not the parameters themselves.
2. Works on a population of points, not a unique one.
3. Uses the only values of the function to optimize, not their derived function
or other auxiliary knowledge.
4. Uses probabilistic transition function and not determinist ones.
GAs can even be faster in finding global maxima that conventional methods, in
particular when derivatives provide misleading information. It should be noted
that in most cases where conventional methods can be applied, GAs are much
slower because they do not take auxiliary information such as derivatives into
account. In these optimization problems, there is no need to apply a GA, which
gives less accurate solutions after much longer computation time. The enormous
potential of GAs lies elsewhere- in optimization of non-differentiable or even
discontinuous functions, discrete optimization, and program in junction.
lt has been claimed that via the operations of selection, crossover and mutation,
the GA will converge over successive generations towards the global (or near
global) optimum. This simple operation should produce a fast, useful and to bust
technique largely because of the face that GAs combine direction and chance in
the search in an effective and efficient manner. Since population implicity contain
much more information than simply the individual fitness stores, GAs combine
the good information hidden in a solution with good information from another
solution to produce new solutions with good information inherited from both
parents, inevitable}' (hopefully) leading towards optimality.
In this chapter we have also discussed the various classifications of GAs. The
class of parallel GAs is very complex, and its behavior is affected by many
parameters. It seems that the only way to achieve a greater understanding of
parallel GAs is to study individual facets independent!}', and we have seen that
some of the most influential publications in parallel GAs concentrate on only one
inspect (migration rates, communication topology or deme size) either ignoring or
making simplifying assumptions on the others. Also the hybrid GA, adaptive GA,
independent sampling GA and messy GA has been included with the necessary
information.
288
Chapter 9: Genetic Algorithm
Exercise Problems
1. Determine the maximum of function x x x5 (0.007x+ 2) using genetic
algorithm by wiring a program.
2. Determine the maximum of function exp( -3x) + sin(6 r x) using genetic
algorithm. Given range = [0.004 0.7]; bits = 6; population = 12; generations
= 36; mutation = 0.005; mutation = 0.3.
3. Optimize the logarithmic function using a genetic algorithm by writing a
program. Genetic Algorithm
289
SOFT COMPUTING TECHNIQUES
290
SOFT COMPUTING TECHNIQUES
UNIT 5
10
HYBRID SOFT COMPUTING TECHNIQUES
Learning Objectives
10.2.1 Introduction
In general, neural networks, fuzzy systems and genetic algorithms are distinct soft
computing techniques evolved from the biological computational strategies and
nature's way to solve problems.
All the above three techniques individually have provided efficient solutions to a
wide range of simple and complex problems pertaining to different domains. As
discussed these three techniques can be combined together in whole or in part, and
282
Chapter 10: Hybrid Soft Computing Techniques
may be applied to find solution to the problems, where the techniques do not
work individually. The main aim of the concept of hybridization is to overcome
the weakness in one technique. While applying it and bringing out the strength of
the other technique to find solution by combining them. Every soft computing
technique has particular computational parameters (e.g., ability to learn, decision
making) which make them suited for a particular problem and not for others. It
has to be noted that neural networks are good at recognizing patterns but they are
not good at explaining how they reach their decisions. On the contrary, fuzzy
logic is good at explaining the decisions but cannot automatically acquire the
rules used for making the decisions. Also, the tuning of membership functions
becomes an important issue in fuzzy modelling. Since this tuning can be viewed
as an optimization problem, either neural network (Hopfield neural network gives
solution to optimization problem) or genetic algorithms offer a possibility to solve
this problem. These limitations act as a central driving force for the creation of
hybrid soft computing systems where two or more techniques are combined in a
suitable manner that overcomes the limitations of individual techniques.
The importance of hybrid system is based on the varied nature of the application
domains. Many complex domains have several different component problems
each of which may require different types of processing. When there is a complex
application which has two distinct sub-problems, say for example, a signal
processing and serial shift reasoning, then a neural network and fuzzy logic can
be used for solving these individual tasks, respectively. The use of hybrid systems
is growing rapidly with successful applications in areas such as engineering
design, stock market analysis and prediction, medical diagnosis, process control,
credit card analysis, and few other cognitive simulations.
Thus, even though the hybrid soft computing systems have a great potential to
solve problems, if not applied appropriately they may result in adverse solutions.
It is not necessary that when individual techniques give good solution, hybrid
systems would give an even better solution. The key driving force is to build
highly automated, intelligent machines for the future generations using all these
techniques.
283
SOFT COMPUTING TECHNIQUES
algorithm
284
SOFT COMPUTING TECHNIQUES
In the field of fuzzy modelling research, the Neuro-fuzzy is divided into two areas:
l. Linguistic fuzzy modelling focused on imerpretability (mainly the
Mamdani model).
2. Precise fuzzy modelling focused on accuracy [mainly the Takagi-Sugeno-
Kang (TSK) model].
A fuzzy system, on the other hand, does not need learning examples as prior
knowledge; rather linguistic rules are required. Moreover, linguistic description of
the input and output variables should be given. If the knowledge is incomplete,
wrong or contradictory, then the fuzzy system must be runed. This is a time
consuming process. Table 10.2.1 shows how combining both approaches brings
out the advantages, leaving out the disadvantages.
284
Chapter 10: Hybrid Soft Computing Techniques
285
SOFT COMPUTING TECHNIQUES
286
Chapter 10: Hybrid Soft Computing Techniques
NFS can also be considered as a system of fuzzy rules wherein the system can be
initialized in the form of fuzzy rules based on the prior knowledge available.
Some researchers use five layers- the fuzzy sets being encoded in the units of the
second and the fourth layer, respectively. It is, however, also possible for these
models to be transformed into three-layer architecture.
The FNN in Figure 10.2-2(A) learns fuzzy set from the given gaining data. This is
done, usually, by fining membership functions with a neural network; the fuzzy
sets then being determined offline. This is followed by their utilization m form
the fuzzy system by fuzzy rules that are given, and not learned. The NFS in
Figure 10.2-2(8) determines, by a neural network, the fuzzy rules from the training
data. Here again, the neural networks learn offline before the fuzzy system is
initialized. The rule learning happens usually by clustering on self-organizing
feature maps. There is also the possibility of applying fuzzy clustering methods to
obtain rules.
287
SOFT COMPUTING TECHNIQUES
288
Chapter 10: Hybrid Soft Computing Techniques
arbitrary set of parameters. Thus for fuzzy systems, the optimization of these
functions in terms of generalizing the data is very important; this problem can be
solved by using neural networks.
Using learning rules, the neural network must optimize cite parameters by fixing
a distinct shape of the membership functions; for example, triangular. But
regardless of the shape of the membership functions, training data should also be
available.
The Neuro fuzzy hybrid systems can also be modelled in an another method. In
cit's case, the training data is grouped into several clusters and each duster is
designed to represent a particular rule. These rules are defined by the crisp data
points and are not defined linguistically. Hence a neural network, in this case,
might be applied to train the defined dusters. The resting can be carried out by
presenting a random resting sample to the trained neural network. Each and every
output unit will return a degree which extends to fit to the [Link] of rule.
Graphical User Interface. Based on the given input-output dam set, ANFIS mol
box
290
Chapter 10: Hybrid Soft Computing Techniques
builds a Fuzzy Inference System whose membership functions are adjusted either
using back Propagation network training algorithm or Adaline network algorithm,
which uses least mean square learning rule. This makes the fuzzy syHem to learn
from the data they model.
The Fuzzy Logic Toolbox function that accomplishes this membership function
parameter adjustment is called anfis. The actonym ANFIS derives its name from
adaptive Neuro-fuzzy inference system. The anfis function can be accessed either
from the command line or thtough dte ANFIS Editor GUI. Using a given
input/output data set, the toolbox function anfis constructs a fuzzy inference
system (FIS) whose membership function parameters are adjusted using either a
back- Propagation algorithm alone or in combination with a least squares type of
method. This enables fuzzy systems w learn from the data they are madeling.
291
SOFT COMPUTING TECHNIQUES
292
Chapter 10: Hybrid Soft Computing Techniques
6. Train th.e FIS model by clicking the Train Now button. This training
adjusts the membership function parameters and plots the training (and/or
checking data) error plot(s) in the plot region.
7. View the FIS model output versus the training, checking, or testing data
output by clicking the Test Now button. This function plots the test data
against the PIS output in the plot region.
One can also use the ANFIS Editor GUI menu bar to load an FIS training
initialization, save your trained FIS, open a new Sugeno system, or open any of
the other GUIs to interpret the trained FIS model.
293
SOFT COMPUTING TECHNIQUES
Training Data
Both anfis and ANFIS Editor GUI require the training data, trnData, as an
argument. For the target system to be modeled each tow of trndata is a desired
input/output pair; a row starts with an input vector and is followed by an output
value. So, the number of rows of trndata is equal to the number of training data
pairs. Also, because there is only one output, the number of columns of trndata is
one more than the number of inputs.
The FIS structure contains both the model structure (specifying, e.g., number of
rules in the FIS, the number of membership functions for each input, etc.) and the
parameters (which specify the shapes of the membership functions).
This means that thtoughout the learning process, at least locally, the training error
decreases. So, as the initial membership functions increasingly resemble the
optimal ones, it becomES easier for the model parameter rraining to converge. In
the setting up of these ·tnitial membership function parameters in the FIS
structure, it may be helpful to have human expenise about the target system co be
modeled.
294
Chapter 10: Hybrid Soft Computing Techniques
moderately large (more than four or five). To enable some dimension reduction in
the fuzzy inference system, the Fuzzy Logic Toolbox software ptovides a
method- a FIS structure can be generated using the clustering algorithm discussed
in Subtractive Clustering. To use this clustering algorithm, select the Sub.
Clustering option in the Generate FIS portion of the ANFIS Editor GUI, before
the FIS is generated. The data is partitioned by the subtractive clustering method
into gtoups called dusters and generates a F1S with the minimum number of rules
required to distinguish the fuzzy qualities associated with each of the clusters.
Training Options
One can choose a desired error tolerance and number of training epochs in the
ANFIS Editor GUI tool. For the command line anfis, training option trnOpt: is a
vector specifying the stopping criteria and the stepsize adaptation strategy:
1. trnOpt (1) : number of training epochs; default = 10
2. trnOpt (2) : error. tolerance; default= 0
3. trnOpt (3) : initial step-size; default= 0.01
4. trnOpt (4) : step·size decrease rate; default"' 0.9
5. trnOpt (5) : step--size increase rate; default= 1.1
The default value is taken if any element of trnOpt is missing or is an NaN. The
training process stops if the designated epoch number is reached or the error goal
is achieved, whichever comes first.
Display Options
They apply only to the command line function anfis. The display options
argument, dispOpt, is a vector of either ls or Os that specifies the information to
be displayed (print in ilie MATLAB command window) before, during, and after
the training process. To denote print this option, 1 is used and to denote do not
print this option, 0 is used.
295
SOFT COMPUTING TECHNIQUES
Method
To estimate membership function parameters, both the command line anfis and
the ANFIS Editor GUI apply either a back-Propagation form of the steepest
descent method, or a combination of back-Propagation and the least-squares
method. The choices for this argument are hybrid or backPropagation. In the
command line function, anfis, these method choices are designated by 1 and 0,
respectively.
Training Error
This is the difference between the training data output value and the output of the
fuzzy inference sysrem corresponding to the same uaining data input value (the
one associated with that training data output value.)
The root mean squared error (RMSE) of the training data set at each epoch is
recorded by the training error trnError; and fismat l is the snapshot of the FIS
structure when the training error measure is at its minimum. As the system is
trained, the ANFIS Editor GUI plots the training error versus epochs curve.
Step-Size
With the ANFIS Editor GUI, one cannot control the step-size options. The step-
size array ss records the step-size during the uaining, using the command line
anfis. If one plots ss, one gets the step-siz.e profile which serves as a reference for
adjusting the initial step-size, and the corresponding decrease and increase rates.
296
Chapter 10: Hybrid Soft Computing Techniques
The guidelines followed for updating the step-size (ss) for the command line
function anfis are:
l. If the error undergoes four consecutive reductions, increase the step-size by
multiplying it by a constant (ssinc) greater than one.
2. If the error undergoes two consecucive combinations of one increase and one
reduction, decrease the step-size by multiplying it by a constant (ssdec) less
than one.
For the initial step-size, the default value is 0.01; for ssinc and ssdec, they are 1.1
and 0.9, respectively. All the default values can be changed via the training option
for the command line anfis.
Checking Data
For testing the generalization capability of the fuzzy inference system at each
epoch, the checking data, chkData, is used. The checking data and the training
data have the same format and elements of the former are generally distinct from
those of the latter.
For learning tasks for which the input number is large and/or the data itself is
noisy, the checking data is important. A fuzzy inference system needs to track a
given input/output data set welL The model structure used for anfis is fixed,
which means that there is a tendency for the model to overfit the data on which it
is trained, especially for a large number of training epochs. In case overfitting
occurs, the fuzzy inference system may not respond well to other independent
data sets, especially if they are corrupted by noise. In these situations, a
validation or checking dam set can be useful. To cross-validate the fuzzy
inference model, this data set is used; ctoss-validation requires applying the
checking data to the model and then seeing how well the model responds to this
data.
The checking data is applied to the model at each tmining epoch, when the
checking data option is used with anfis either via the command line or using the
ANFIS Editor GUI. Once the command line anfis is invoked, the model
parameters £hat correspond to the minimum checking error are returned via the
output argument fismat2. The FIS membership function parameters computed
using the ANFIS Editor GUI when both training and checking data are loaded,
are associated with the training epoch that has a minimum checking error.
The assumptions made when using the minimum checking data error epoch to set
the membership function parameters are:
297
SOFT COMPUTING TECHNIQUES
The resulting FIS may or may not be the one which is required to be used,
depending on the behavior of the checking data error.
Fismat 2. If checking data is used for ctoss-validation, this FIS structure is the one
rhat should be used for further calculation.
Checking Error
This is the difference becween the checking data ourpuc value and the output of
the fuzzy inference system corresponding to the same checking dala input value,
which is the one associated with that checking data output value. The Toot Mean
Square Error (RMSE) is reCorded for clte checking data at each epoch, by the
checking error chkError. The snapshot of ilie FIS structure when the checking
error has its minimum value is fismat 2. The checking error versus epochs curve
is planed by the ANFIS Editor GUI, as the system is trained.
298
Chapter 10: Hybrid Soft Computing Techniques
Figure 10.2-5 shows the block diagram for the genetic-Neuro-hybrid systems.
Their drawbacks are: the large amount of memory required for handling and
manipulation of chromosomes for a given network; and also the question of
scalabiliry of this problem as the size of the networks become large.
299
SOFT COMPUTING TECHNIQUES
Also, it may be nored that the BPN determines its weight based on gradient
search technique and hence it may encounter a local minima problem. Though
genetic algorithms do nor guarantee to find global optimum solution, they are
good in quickly finding good acceptable solutions. Thus, hybridization ofBPN
with genetic algorithm is expected to ptovide many advantages compared to what
they alone can. The basic concepts and working of genetic algorithm are
discussed in Chapter
15. However, before a genetic algorithm is executed,
1. A suitable coding for the problem has to be devised.
2. A fitness function has to be formulated.
3. Parents have to be selected for reproduction and then ctossed over to
generate offspring.
[Link].1 Coding
Assume a BPN configuration n-1-m where n is the number of Neurons in the
input layer, l is the number of Neurons in the hidden layer and m is the number of
output layer Neurons. The number of weights to be determined is given by
(n + m)i
Each weight (which is a gene here) is a real number. Let dbe the number of digits
(gene length) in weight. Then a String S of decimal values having string length (n
+ m)ld is randomly generared. It is a string that represenrs weight matrices of
inpurhidden and the hidden-output layers in a linear form arranged as tow-major
or column-major depending upon the sryle selected. Thereafter a population of p
(which is the population size) chromosomes is randomly generated.
300
Chapter 10: Hybrid Soft Computing Techniques
where X and Y are the inputs and targets, respectively. Compute initial population
Io of size 'j'. Let
O10, O20, ... , Op represem 'j' chromosomes of the initial population lo. Let the
weights extracted for each of the chromosomes upto the chromosome be w10, w20,
w30, …., wp. For a number of inputs and m number of outputs, let the calculated
output of the considered BPN be
ER1 = (y11 – c11)2 + (y21 – c21)2 + (y31 – c31)2 + ….. + (yn1 – cn1)2
ER2 = (y12 – c12)2 + (y22 – c22)2 + (y32 – c32)2 + ….. + (yn2 – cn2)2
…………………………………………………………………….
…………………………………………………………………….
ERm = (y1m – c1m)2 + (y2m – c2m)2 + (y3m – c3m)2 + ….. + (ynm – cnm)2
The fitness function is further derivd from this root mean square error given by
The process has to be carried out for all the total number of chromosomes.
301
SOFT COMPUTING TECHNIQUES
[Link].5 Convergence
The convergence for genetic algorithm is the number of generations with which
the fitness value increases towards the global optimum. Convergence is the
progression towards increasing uniformiry. When about 95% of the individuals in
the population share the same fitness value then we say that a population has
converged.
The hybrid approach can be applied to several applications, which include: load
forecasting, stock forecasting, cost optimization in textile industries, medical
diagnosis, face recognition, multi-processor scheduling, job shop scheduling, and
so on.
302
Chapter 10: Hybrid Soft Computing Techniques
1. By the use offuzzy logic based techniques for imptoving genetic algorithm
behavior and modelling GA components. This is called fozzy genetic
algorithms (FGk).
2. By the application of genetic algorithms in various optimization and search
problems involving fuzzy systems.
GAs are utilized for solving different fuzzy optimization problems. For example,
fuzzy flowshop scheduling problems, vehicle routing problems with fuzzy due-
time, fuzzy optimal reliability design problems, fuzzy mixed integer
programming applied m resource distribution, job-shop scheduling problem with
fuzzy processing time, interactive fuzzy satisfying method for multi-objective 0-
1, fuzzy optimization of distribution networks, etc.
303
SOFT COMPUTING TECHNIQUES
The main objectives of optimization in fuzzy rule based system are as follows:
l. The task of finding an apptopriate knowledge base (KB) for a particular
problem. This is equivalent to parameterizing the fuzzy KB (rules and
membership functions).
2. To find those parameter values that are optimal with respect to the design
criteria.
Considering a GFRBS, one has to decide which parts of the knowledge base (KB)
are subject to optimization by the GA. The KB of a fuzzy system is the union of
qualitatively different components and not a homogeneous structure. As an
example, the KB of a descriptive Mathdani-type fuzzy system has two
components: a rule base (RB) containing the collection of fuzzy rules and a data
base (DB) containing the definitions of the scaling factors and the membership
functions of the fuzzy sets associated with the linguistic labels.
304
Chapter 10: Hybrid Soft Computing Techniques
305
SOFT COMPUTING TECHNIQUES
306
Chapter 10: Hybrid Soft Computing Techniques
Tuning the membership functions of a model working with funy variables (scatter
partitions), on the other hand, is a particular instance of knowledge base learning.
This is because, instead of referring to linguistic terms in the DB, the rules are
defined completely by their own membership functions.
307
SOFT COMPUTING TECHNIQUES
Apart from these two ART networks, the other two maps are ARTMAP and fuzzy
ARTMAP. ARTMAP is also known as Predictive ART. It combines two slightly
modified ART-1 or ART-2 units into a supervised learning structure. Here, the
first unit rakes the inpm data and the second unit rakes the correct output data.
Then
308
Chapter 10: Hybrid Soft Computing Techniques
minimum poible adjusrmem of the vigilance parameter in the fim unit is made
using the correct output data .o rhar correct classification can be made.
309
SOFT COMPUTING TECHNIQUES
2. ART MAP networks are designed to work in real-time. While BPNs are
typically designed to work off-lilne at least during their training phase.
However, the system based on ART modules learning may depend upon the
ordering of the input patterns.
10.2.6 Summary
In this chapter, the various bybrids of individual neural networks, fuzzy logic and
genetic algorithm have been discussed in detail. The advantages of each of these
techniques are combines together to give a better solution to the problem under
consideration. Each of these systems possesses certain limitations when they
operate individually and these limitations are met by bringing out the advantages
of combining these systems. The hybrid systems are found to provide better
solution for complex problems and the advent of hybrid systems makes it
applicable to be applied in various application domains.
310
Chapter 10: Hybrid Soft Computing Techniques
calculating error
rate e=y-t;
plot(e);
title (‘Error rate’)
figure
Output
0
0.3000
0.6000
0.9000
1.2000
1.5000
1.8000
2.1000
2.4000
2.7000
3.0000
3.3000
3.6000
3.9000
4.2000
4.5000
4.8000
5.1000
5.4000
5.7000
6.0000
311
SOFT COMPUTING TECHNIQUES
6.3000
6.6000
6.9000
7.2000
7.5000
7.8000
8.1000
8.4000
8.7000
9.0000
9.3000
9.6000
9.9000
10.2000
10.5000
10.8000
11.1000
11.4000
11.7000
12.0000
12.3000
12.6000
12.9000
13.2000
13.5000
13.8000
14.1000
14.4000
14.7000
15.0000
15.3000
15.6000
15.9000
5.2.2000
5.2.5000
5.2.0000
17.1000
17.4000
17.7000
312
Chapter 10: Hybrid Soft Computing Techniques
18.0000
18.3000
18.6000
18.9000
19.2000
0.9437
0.9993
0.9657
0.8457
0.6503
0.3967
0.1078
-0.1909
-0.4724
-0.7118
-0.8876
-0.9841
-0.9927
-0.9126
-0.7510
-0.5223
-0.2470
0.0504
0.3433
0.6055
0. 8137
ANFIS info:
Number of nodes: 32
313
SOFT COMPUTING TECHNIQUES
3 0.0508992
314
Chapter 10: Hybrid Soft Computing Techniques
4 0.0504776
5 0.0500581
Step size increases to 0.011000 after epoch
5. 6 0.0496406
7 0.0491837
a o.o4S7291
568 0.00105594 -
315
SOFT COMPUTING TECHNIQUES
0.8540
0.6627
0.4122
0.1247
-0.1741
-0.4574
-0.7000
-0.8801
-0.9812
-0.9941
-0.9189
-0.7623
-0.5371
-0.2629
0.0346
0.3277
0.5908
0.8024
0.9442
1.0014
0.9667
0.8443
0.6484
0.3969
0.1093
-0.1900
-0.4731
-0.7130
-0.8879
-0.9833
-0.995.2
-0.9125
-0.7521
-0.5232
-0.2457
0.0526
0.3426
0.6015
0.85.23
<end of program>
316
Chapter 10: Hybrid Soft Computing Techniques
Figure 10.2-11 illustrates the ANFIS system module; figure 10.2-12 the error me;
and Figure 10.2-13 the performance of training dam and output data. Thus ir can
be noted from Figure 10.2-13, that an f is has adapted the given inpur to sine
wave form.
module.
Source code
%input data
x= [0,l,0,0;l,0,l,l;l,l,l,2;1,0,1,3;1,0,1,4;
1,1,0,5;1,0,1,6;1,1,0,7;1.0,1,8;1,1,0,9;
0,1,1,10;1,0,0,11;1,0,0,12;1,0,0,13;0,1,1,14;
1,1,0,15;1,0,1,5.2;1,0,1,17;1,0,1,18;1,1,0,19;
1, 1, 1, 20; 1, 0, 0, 21; 1, 1, 0, 22; 1, 0, 0, 23; 1, 1, 1, 24; ]
318
Chapter 10: Hybrid Soft Computing Techniques
%target data
t:::[0;0;0;0;0;
1;1;1;1;1;
2;2;2;2;2;
3;3;3;3;3;
4;4;4;4;4; 1
%training data
trndata= [x, t);
mfs::o3;
epochs=400;
%calculating error
rate esy-t;
plot (e);
title('Error rate');
figure
319
SOFT COMPUTING TECHNIQUES
Output
X=
0 1 0 0
1 0 1 1
1 1 1 2
1 0 1 3
1 0 1 4
1 1 0 5
1 0 1 6
1 1 0 7
1 0 1 8
1 1 0 9
0 1 1 10
1 0 0 11
1 0 0 12
1 0 0 13
c 1 1 14
1 1 0 15
1 0 1 5.2
1 0 1 17
1 0 1 18
1 1 0 19
1 1 1 20
1 0 0 21
1 1 0 22
1 0 0 23
1 1 1 24
t=
0
0
0
0
0
1
1
1
1
1
2
320
Chapter 10: Hybrid Soft Computing Techniques
2
2
2
2
3
3
3
3
3
4
4
4
4
4
ANFIS info:
Number of nodes: 193
Number of linear parameters: 405
Number of nonlinear parameters: 36
Total number of parameters: 441
Number of training data paits: 25
Number of checking data paits: 0
Number of fuzzy rules: 81
Start training
ANFIS 1
0.08918
2 0.0889038
3 0.0886229
4 0.0883371
5 0.0880464
321
SOFT COMPUTING TECHNIQUES
Designated epoch number reached --> ANFIS training completed at epoch 400.
<end of program>
Figure 10.2-14 shows the degree of membership. Figure 10.2-I5 illusrmes the
surface view of the given system; Figure 10.2-5.2 the error rate; and Figure 10.2-
17 the performance of training data with output data.
322
Chapter 10: Hybrid Soft Computing Techniques
323
SOFT COMPUTING TECHNIQUES
324
Chapter 10: Hybrid Soft Computing Techniques
3. Write a [Link] program m train the given trmh table using adaptive
Neuro-fuuy hybrid technique. Source code
% Program to train the given truth table using adaptive Neuro fuzzy
%hybrid technique.
clc;
clear all;
close
all;
%input data
X = [ 0, 0, 0; 0, 0, 1; 0, 1, 1; 0, 0,1,1,1,0,0,1,1,1,0,1,1,1;]
%target data
c=[0,0,0,1,0,1,1,1]
%training
data trndata=
[x, t]; mfs=3;
mfType =
'gbellmf';
epochs=49;
figure
plotmf(fis, 'input',l);
title ('The membership function of the fuzzy’):
surfview ( fis) ;
figure
ruleview ( fis) ;
r=showrule(fis);
rl=showrule(nfis);
326
Chapter 10: Hybrid Soft Computing Techniques
X =
0 0 0
0 0 0
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
T=
0
0
0
1
0
1
1
1
ANFIS info:
Number of nodes: 78
Number of linear parameters: 108
Number of nonlinear parameters: 27
Total number of parameters: 135
327
SOFT COMPUTING TECHNIQUES
Designated epoch number reached --> ANFIS training completed at epoch 49.
Figure 10.2-18 shows the ANFIS module for the given system with specified
inputs. Figure 10.2-19 illustrates the rule viewer for the ANFIS module. Figure
10.2-20 gives the error rate. Figure 10.2-21 shows the performance of Training
data and ourpur data.
328
Chapter 10: Hybrid Soft Computing Techniques
Figure 10.2-18 ANFIS module for the given system with specified inputs.
329
SOFT COMPUTING TECHNIQUES
Source code
%Program to optimize the neural network parameters from given truth table
%using genetic algorithm
clc;
clear all;
close
all;
%input data
p = [ 0 0 1 1; 0 1 0 1 ];
330
Chapter 10: Hybrid Soft Computing Techniques
%target data
T = [ -1 1 -1 1 ];
%creating two layer net with two Neurons in hidden (1) layer
[Link] (l).size = 2;
[Link] = 2;
%initializing network
net= init(net);
[Link] = 'initlay';
331
SOFT COMPUTING TECHNIQUES
%configuring ga arguments
A= [ ]; b = [ ]; %: linear constraints
Aeq = [ ]; beq = [ ]; %linear
inequalities lb = {-2 -2 -2 -2 -2 -2]; %lower
bound
ub = [2 2 2 2 2 2]; %upper bound
%ploting ga parameters
Options = gaoptimset ('PlotFcns',{Egaplotscorediversity,Egaplotbest f)};
figure
332
Chapter 10: Hybrid Soft Computing Techniques
case 'initialize'
%selecting input weights , layer·weights and bias separately
switch(upper(in3))
case {'IW') %for input weights·
if [Link]
if [Link](in4,in5)
x=X; %Assigning ga output 'X' to input weights
%Taking first 4 ga outputs to cFeate input weight matrix 'wi'
wi(l,l)=x(l,l);
wi{1,2)=x{1,2);
wi(2,l)=x(l,3);
wi(2,2)=x(1,4);
disp(wil;
outl = wi;%Returning input layer matrix
else
outl = [ ];
end
else
505
[Link]([upper(mfilename) ' does not initialize input weights.']);
end
case {'LW'} %for layer weights
if [Link]
if [Link]{in4,in5)
x=X; %Assigning ga output 'X' to layer weights
%Taking 7th and 8th ga outputs to create layer weight matrix 'wl'
wl(l,l)=x{l, 7);
wl{1,2)=x(l,Bl;
disp (wl);
outl = wl;%Returning layer 1•1eight matrix
else
outl
[ ]; end
else
[Link]([upper(mfilename) ' does not initialize input weights.']);
end
case {'B'} %for bias
if [Link]
333
SOFT COMPUTING TECHNIQUES
if [Link]{in4)
x=X; %Assigning ga output 'X' to bias
%Taking 5th, 6th and 9th ga outputs to create bias matrix 'bl'
bl[l)=x{l,5);
bl[2)=x[1,6);
bl [3) =x(l, 9);
disp(bl);
outl = bl;
else
end
[];%Returning bias matrix
[Link]([upper(mfilename) ' does not initialize
biases.']); end
otherwise,
end
en
d
en
d
en
d
[Link]('Unrecognized value type.');
%Creating fitness function for genetic algorithm
function z = fitnesfun(e)
%The error(t-y) for all 4 i/o paits are summed to get overall error
%For 4 input target paits the overall error is divided by 4 to get average
%error value (1/4=0.25)
z=0.25*surn(abs(e));
end
Output
Optimization terminated: average change in the spread of Pareto solutions
less than [Link].
Columns 1 thtough 7
0.0280 0.0041 0.0112 0.0069 0.0050
Columns 8 thtough 9
0.0018 0.0003
The number of generations was : 102
334
Chapter 10: Hybrid Soft Computing Techniques
335
SOFT COMPUTING TECHNIQUES
Figure 10.2.22 shows the plot of the generations versus fitness value and
histogram. Figure 10.2-23 illustrates the Neural Nenvork Training Tool for the
given input and output paits. Figure 10.2-24 shows the neural network training
[Link]'Oimance. Neural necwork training state is shown in Figure 10.2-25. Figure
10.2-26 displays the performance of uaining data versus output data.
336
Chapter 10: Hybrid Soft Computing Techniques
337
SOFT COMPUTING TECHNIQUES
338
Chapter 10: Hybrid Soft Computing Techniques
Exercise Problems
1. Write a MATLAB program m train NAND gate with binary inputs and
targets (rwo input-one Output) using adaptive Neuro-fuzzy hybrid
technique.
2. Consider some alphabets of your own and recognize the assumed characters
using ANFIS Editor module in MATLAB
3. Perform Problem 2 for any assumed numeral charaaers. .
4. Design a genetic algoriilim to optimize the weights of a neural network
model while training Hybrid Soft Computing Techniques an OR gate wiili 2
bipolar inputs and 1 bipolar targets.
5. Write a MATLAB M·file program for the working of washing machine
using fuzzy genetic hybrids.
339
There are five basic types of neural network architectures. Single-layer feed-forward networks have inputs directly connected to outputs without feedback. Multi-layer feed-forward networks include hidden layers between input and output layers. Single-node networks with own feedback allow a node to feedback into itself. Single-layer recurrent networks have feedback directed back to itself or other elements. Multi-layer recurrent networks include feedback loops in multiple processing layers, allowing output from a layer to be fed back into previous layers .
In supervised learning, neural networks learn from labeled datasets, meaning the correct output is known for each input. The network uses this information to adjust its weights to minimize the error between the actual and desired outputs. Conversely, unsupervised learning involves training a neural network on data without explicit instructions on what the output should be. Instead, the model tries to identify patterns, such as clustering or associations, between data points .
Fuzzy logic systems handle imprecision and uncertainty by allowing for graded membership in sets, as opposed to traditional logic systems which require binary true or false values. In fuzzy logic, membership functions map elements to a degree of membership between 0 and 1. This allows for partial membership, reflecting the real-world complexity where conditions are not always black-and-white. Fuzzy logic uses linguistic variables and rule-based reasoning to model human-like reasoning under uncertainty .
The activation function in artificial neural networks determines the output of a neuron given its input. It introduces non-linearity into the network, allowing it to model complex patterns. Without activation functions, the network would be limited to linear transformations, which could not solve non-linear problems. Commonly used activation functions include sigmoid, hyperbolic tangent, and ReLU (Rectified Linear Unit), each with distinct properties that influence the ability to learn and the gradient descent process .
Hebbian learning is based on the idea that synaptic weights increase if two interconnected neurons are activated simultaneously. The principle can be summarized by the phrase 'cells that fire together, wire together.' When neuron A repeatedly activates neuron B, a growth or metabolic change increases A's efficiency in activating B. The synaptic weight update is calculated as Wi(new) = Wi(old) + xiy, where xi is the input from neuron i and y is the output .
The training algorithm for Adaline networks iteratively adjusts weights to minimize the error between the network's output and the target output. This process involves setting initial weights and biases, calculating the net input, and applying the delta rule to update weights based on the error. The significance lies in its ability to refine the model for accurate linear function approximation, providing a foundation for more complex learning methods in neural networks .
The input signals in a neural network are combined using weighted interconnection links denoted as w1 and w2. The net input for neuron Y is calculated using the formula yin = x1w1 + x2w2, where x1 and x2 are the activations of the input neurons X1 and X2 respectively. An activation function, f(yin), is then applied to the net input to obtain the output y .
Genetic algorithms face challenges such as premature convergence, maintaining diversity, and determining appropriate population size. To address premature convergence, mutation is used to introduce new genetic material. Maintaining diversity is crucial for avoiding local optima; methods such as fitness sharing or diverse initializations are employed. The population size is a trade-off between computational cost and search space coverage, often requiring heuristic methods or domain-specific knowledge for optimization .
Genetic algorithms simulate evolution by using a population of candidate solutions represented as chromosomes. The basic components include selection, crossover, and mutation. Selection picks fitter individuals for reproduction, crossover combines parts of two chromosomes to create offspring, and mutation introduces random changes to maintain diversity. This iterative process evolves the population towards optimal solutions by mimicking natural selection processes .
Common methods for setting membership values in fuzzy logic systems include intuition-based assignments, inference from data, and rank ordering. Neural networks and genetic algorithms can also be employed for more complex data-driven assignments. The implications of these methods range from subjective human-based decisions to more objective, data-oriented approaches, which influence the accuracy and reliability of fuzzy models in handling real-world uncertainties .