Soft Computing
CSE3008
1/23/2022 CSE3008 Soft Computing
Outline
Overview of soft computing
List of techniques
Neural networks
Fuzzy logic
Genetic algorithms
1/23/2022 CSE3008 Soft Computing Page 2
Soft Computing
Branch of AI that deals with systems and
methodologies that can perform approximate,
qualitative, human-like reasoning
Humans can make intelligent decisions using
incomplete and imprecise information
“Soft” reasoning
Computer algorithms require complete and
precise information
“Hard” reasoning
Soft computing aims to bridge this gap
1/23/2022 CSE3008 Soft Computing Page 3
Soft vs. Hard Computing
Hard Computing Soft Computing
Complete and Approximate and
Input
exact data incomplete data
Overly-exact Solution that’s
Output
solution “good enough”
Reasoning Rational Human-like
1/23/2022 CSE3008 Soft Computing Page 4
Soft Computing
Probabilistic reasoning
Human uncertainty and randomness
Artificial neural networks (ANN)
Human brain
Fuzzy logic (FL)
Human knowledge
Evolutionary computing
Genetic algorithms (GA)
Biological evolution
1/23/2022 CSE3008 Soft Computing Page 5
Artificial Neural Networks
Human Brain
Massively parallel network of
neurons
Each individual neuron is not
intelligent
Neuron is a simple computing
element
But the brain is intelligent!
1/23/2022 CSE3008 Soft Computing
Human Brain
Brain learns by changing and adjusting
the connections between neurons
Information encoded in many ways
Connection patterns of neurons
Amplification of signals by dendrites
Transfer function and threshold values
controlling whether the cell transmits the
signal
1/23/2022 CSE3008 Soft Computing
Neuron
Receives electric impulse from other
neurons through dendrites.
If impulse strong enough, travels
through axon.
Reaches synapses and transmits to
other neurons
1/23/2022 CSE3008 Soft Computing
Artificial Neuron
ith neuron sums inputs a1… aj… an, weighted by
weights wi1… wij… win
Threshold value i controls activation
If activated, input is transformed by transfer
function fi(.) into output ai
wij Cell
Axon
body
aj fi(.) ai
Synapse
Dendrites
i
ai = fi( jwijaj - i ) = [0,1]
1/23/2022 CSE3008 Soft Computing
Artificial Neural Networks
Large arrangement of inter-connected
artificial neurons
Different classes of network
Topology of the network
Transfer function of the neurons
Learning algorithm
Different networks appropriate for
different applications
1/23/2022 CSE3008 Soft Computing
Perceptron
Simplest and most
commonly-used ANN
x1
Feed-forward ANN
x2 o1
Single-layer
x3 o2 No hidden layer
Only linearly-
separable problems
Input Hidden Output Multi-layer
layer layer layer Non-linear problems
1/23/2022 CSE3008 Soft Computing
Examples
All these neurons XOR Network
x1 1 use step functions x1
o 1
f(<0) = 0
x2 1 1
f(0) = 1 -1
-1.5 o
-0.5
AND Network -1 1
1 -0.5
x2
OR Network
-0.5
x1 1
o
x2 1
-0.5
1/23/2022 CSE3008 Soft Computing
Learning
Backpropagation algorithm
Train using a set of input-output vectors
Modify weights of network to minimize the
error
Difference between the training output vector and
the network’s actual output vector
Supervised learning
Using the entire training set = 1 epoch
1/23/2022 CSE3008 Soft Computing
Backpropagation algorithm
Start with random weights
For each epoch
Forward propagation of each input vector, to get the
network’s output vector
Compare network output to target output of
training set, and compute the network error
Starting from output layer and going backwards,
back propagate the network error to each layer
Update the input weights of each neuron in each
layer to minimise the network error
Repeat until min network error or max epoch
1/23/2022 CSE3008 Soft Computing
ANN Topologies
Feed-forward
topology x1
Information can x2 o1
only move forward
through the x3
network
Recurrent topology
Information can x1
loop back to create x2 o1
feedback loop, or
network memory x3
1/23/2022 CSE3008 Soft Computing
Feed-Forward Networks
Perceptron
Basic network
Any transfer functions
Any number of hidden layers
Radial Basis Function (RBF) Network
Special class of multi-layer perceptron
Single hidden layer with RBF (typically Gaussian)
transfer function
Useful for modelling systems with complex nonlinear
behaviour, control systems, audio-video signal
processing, …
1/23/2022 CSE3008 Soft Computing
Feed-Forward Networks
Kohonen Self-Organising Map
Fully-connected two-layer network
Unsupervised learning
Output neuron compete to activate
Neuron with highest output value wins
Winning neuron and its neighbours
have their weights updated
Creates a 2D topological mapping of
the input vectors to the output layer
x1 x2 Useful for pattern recognition,
image analysis, data mining, …
1/23/2022 CSE3008 Soft Computing
Recurrent Networks
Hopfield Network
First kind of recurrent ANN
Implements an associative
memory
x1 o1 Previous-stored patterns
“complete” current (noisy or
x2 o2 incomplete) pattern
o3 Network is attracted to stable
x3 pattern in memory
Useful for information retrieval,
pattern/speech recognition, …
1/23/2022 CSE3008 Soft Computing
Limits of ANN
Black box
What does each neuron do? What does
each weight do?
No formal design rules
How many hidden layers? How many
neurons per layer? Which transfer
functions?
Prone to overfitting
Backpropagation is slow and can
converge on local optimum
1/23/2022 CSE3008 Soft Computing
ANN Classifier
Typical application of ANN
Requires
A set of crisp, mutually-exclusive classes
A set of well-defined, measurable
attributes relevant to classification
Correctly-classified training data
Compared to Naïve Bayes Classifier
Does not require any probabilities
1/23/2022 CSE3008 Soft Computing
ANN Classifier Design
Pick network architecture based on
problem
Or simply pick perceptron
One input neuron per attribute
One output neuron per class
Add hidden layers if classification is
non-linear function of input space
Exact number of layers or neurons difficult to
discover
Train network
1/23/2022 CSE3008 Soft Computing
ANN Classifier Example
Paper on website
Classification of pixels in
aerial photograph
Classes: lake, forest or land
Input: pixel’s RGB value
Data
180 training pixels
300 testing pixels
1/23/2022 CSE3008 Soft Computing
ANN Classifier Example
Perceptron network
Good for complex classification
problems
Two hidden layers
Number of hidden layers /
neurons per hidden layer
discovered by trial-and-error
One hidden layer not precise
enough
First layer neurons input neurons
Second layer neurons
max(input neurons, output neurons)
More hidden neurons give higher
precision, need more training time
1/23/2022 CSE3008 Soft Computing
ANN Classifier Example
Classification precision: 93%
Naïve Bayes Classifier: 88%
Network later expanded to 7 classes
Water, marsh, farmland, woodland,
grassland, residential area, salina
Still has RGB input, two hidden layers
7 output neurons, more neurons on hidden
layers
Precision: 97%
Naïve Bayes Classifier: 89%
1/23/2022 CSE3008 Soft Computing
Fuzzy Logic
In crisp logic, facts are either true or
false
Truth value = {0, 1}
This is an unnatural way of doing it
Cold Warm Hot
1
0
Temperature
1/23/2022 CSE3008 Soft Computing R. Khoury (2008) Page 25
Fuzzy Logic
In fuzzy logic, facts can be partially true
and partially false
Truth value = [0, 1]
This is closer to human knowledge
Cold Warm Hot
1
0
Temperature
1/23/2022 CSE3008 Soft Computing R. Khoury (2008) Page 26
Terminology
“Cold”, “warm” and “hot” are fuzzy set
The triangle function mapping a value of
temperature to a value of cold (or warm
or hot) is called a fuzzy membership
function
The value of cold (or warm or hot) to which
a temperature is mapped is called a
membership degree
Fz[t Cold] = μCold(t): [0,1]
1/23/2022 CSE3008 Soft Computing
Fuzzy Sets vs. Probabilities
Membership degrees are not
probabilities
Both are measures over the range [0,1]
Probabilistic view: x is or is not y, and
we have a certain probability of knowing
which
Fuzzy view: x is more or less y, with a
certain degree
1/23/2022 CSE3008 Soft Computing
Fuzzy Rules
If-then rules like other logics, but with
fuzzy sets
If Cold then VentilationHigh
If Warm then VentilationLow
If Hot then VentilationMedium
Variables belong partially to antecedent,
therefore consequence activated partially
1/23/2022 CSE3008 Soft Computing
Fuzzy Controller
Typical application of fuzzy logic
Set of fuzzy rules
Define the behaviour of a system
Antecedent: variables that affect the
system
Consequent: reaction of the system
1/23/2022 CSE3008 Soft Computing
Fuzzy Controller Example
If Hot and Wet then VentilationLow
If Warm and Humid then VentilationMedium
Hot Wet VentilationLow
1 1 1
0 T 0 H 0 S
Warm Humid VentilationMedium
1 1 1
0 t T 0 h H 0 S
1/23/2022 CSE3008 Soft Computing
Fuzzy Controller Example
Defuzzification using centroid technique
Converts fuzzy consequent into crisp
value that can be used by system
Centroid merges the output fuzzy sets
and finds the center of gravity
1
0 s S
1/23/2022 CSE3008 Soft Computing
Advantages of Fuzzy Logic
Partial activation of multiple rules at
once
Achieve complex non-linear behaviour
with simple IF-THEN rules
Use linguistic variables to model words,
rules of thumb, human knowledge
1/23/2022 CSE3008 Soft Computing
Properties of Fuzzy Controllers
The rule base must be
Complete
Continuous
The rules must
Be consistent
Not interact
The rule base system must be
Robust
Stable
1/23/2022 CSE3008 Soft Computing
Limits of Fuzzy Logic
Writing the fuzzy rules
Designing the fuzzy membership
functions
Often requires work by a domain expert
1/23/2022 CSE3008 Soft Computing
Fuzzy Robot Navigation
Fuzzy controllers are very popular for
robot navigation
Eliminates need for complete world
model and complex reasoning rules
Basic robot
Known current position and target
Three sensors (front, left, right)
Left and right wheels can turn at different
speeds to make robot turn
1/23/2022 CSE3008 Soft Computing
Fuzzy Robot Navigation
Fuzzy linguistic variables of control
system
Distance: near, medium, far
Direction angle: negative, zero, positive
Speed: slow, medium, fast
Near Medium Far Negative Zero Positive Slow Medium Fast
1 1 1
0 0 0
Distance Direction Speed
1/23/2022 CSE3008 Soft Computing
Fuzzy Robot Navigation
Going to target
IF (left obstacle is far) and (front obstacle is far) and (right
obstacle is far) and (angle is zero) THEN (left speed is fast) and
(right speed is fast)
Avoiding obstacles
IF (left obstacle is far) and (front obstacle is near) and (right
obstacle is far) and (angle is zero) THEN (left speed is fast) and
(right speed is slow)
Turning corners
IF (left obstacle is medium) and (front obstacle is near) and (right
obstacle is near) and (angle is any) THEN (left speed is slow)
and (right speed is fast)
Following edges
IF (left obstacle is far) and (front obstacle is far) and (right
obstacle is near) and (angle is positive) THEN (left speed is
medium) and (right speed is medium)
1/23/2022 CSE3008 Soft Computing
Fuzzy Robot Navigation
1/23/2022 CSE3008 Soft Computing
Genetic Algorithms
Biological evolution
Species adapt to better
survive in environment
Over generations
Pairs of individuals
reproduce
Individuals mutate
Fittest individuals
survive and go on to
reproduce
Source: David M. Hillis, Derrick Zwickl, and Robin Gutell, University of Texas.
1/23/2022 CSE3008 Soft Computing
Evolutionary Computing
Introduced by John Holland in “Adaptation in
Natural and Artificial Systems”, 1975
Stochastic search technique
Like simulated annealing!
Divided in four main classes (different
representation of individuals)
Genetic algorithms
Evolution strategies
Evolutionary programming
Genetic programming
1/23/2022 CSE3008 Soft Computing
Genetic Algorithms
Simulating biological evolution in AI
Biology Genetic Algorithms
States
Individuals
Solutions to a problem
State space to explore
Environment
Problem to solve
Fitness Evaluation function
Changes from one
Operators
generation to the next
1/23/2022 CSE3008 Soft Computing
Individuals
Individuals have a chromosome
String of genes (bits)
Encodes the solution represented by the
individual
Often binary representation, but can be
anything
1 1 0 0 1 0 1 0
Length, nature of bits, meaning, varies
according to problem
1/23/2022 CSE3008 Soft Computing
Operators
To evolve, the population must change
GA typically use three operators to
change the population
Crossover (sexual reproduction)
Mutation (mutation)
Selection (natural selection)
1/23/2022 CSE3008 Soft Computing
Crossover
Select two fittest parents
Select (random) splitting point in the
chromosomes
Recombine the genes to get children
Causes slow move of the population
around state space
1 1 0 0 1 0 1 0 1 1 0 0 0 1 1 0
0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 0
1/23/2022 CSE3008 Soft Computing
Mutation
Select random child
Select random gene
Switch gene value according to
mutation rule
Depends on representation
Typically very rare (low mutation rate)
Causes large leap across state space
1 1 0 0 0 1 1 0 1 1 0 1 0 1 1 0
1/23/2022
CSE3008 Soft Computing
Selection
GA population have zero population
growth
We can’t keep them all (computer limits)
and we don’t want to (they’re useless)
But each crossover operation generates
two more, new individuals
Survival of the fittest!
Evaluate fitness of all individuals
Kill off (i.e. delete) least fit ones, keeping
only the fittest (best solutions)
Each generation, the population improves
1/23/2022 CSE3008 Soft Computing Page 48
Evolution Algorithm
Starts with random population
Evaluate fitness of all individuals
For each generation
Select fittest parents and crossover
Mutate children according to mutation rate
Evaluate fitness of new individuals
Select individuals that survive for next generation
Repeat until
Generation limit reached
An individual achieves the target fitness
1/23/2022 CSE3008 Soft Computing
Evolution Algorithm
Individuals are random, but population
converges slowly towards solution
* * *
* * ** *
x x x*
* ***
* * *
* *
* *
*
Population
fitness
Generation
1/23/2022 CSE3008 Soft Computing
Genetic Algorithm Example
8-Queen problem
Environment: state
space
Chromosome: encodes
position of queens
Fitness: number of
attacks
2 6 7 1 5 7 2 5
1/23/2022 CSE3008 Soft Computing
Genetic Algorithm Example
Crossover operation
2 6 7 1 5 7 2 5 2 6 7 3 6 5 1 5
4 8 5 3 6 5 1 5 4 8 5 1 5 7 2 5
1/23/2022 CSE3008 Soft Computing
Genetic Algorithm Example
Possible mutation operations
Complements (1-8, 2-7, 3-6,
4-5)
Swap two random genes
4 8 5 1 4 7 2 5
4 8 5 1 5 7 2 5
1/23/2022
4
CSE3008 Soft Computing
5 5 1 8 7 2 5
Limits of Genetic Algorithms
Not guaranteed to find the optimal
solution
In large complex state spaces, or with a low
mutation rate, might converge to local
optimum (premature convergence)
High mutation rate can prevent
convergence (mutation interference)
Interdependence between genes makes it
hard to find solution (epistasis)
1/23/2022 CSE3008 Soft Computing