Introduction to Soft Computing
Presentation by:
C. Vinoth Kumar
SSN College of Engineering
NP- Complete (NPC)
It is non-deterministic polynomial time – a class of
decision problems.
The time required to solve the problem using any
currently known algorithm increases very quickly as
the size of the problem grows.
This means that the time required to solve even
moderately sized problems can easily reach into the
billions or trillions of years, using any amount of
computing power available today.
NP- Complete (NPC)
The list of NP-complete problems are:
• Knapsack problem
• Hamiltonian path problem
• Travelling salesman problem
• Sub-graph isomorphism problem
• Subset sum problem
• Clique problem
• Vertex cover problem
• Independent set problem
• Dominating set problem
• Graph coloring problem
• Boolean satisfiability problem, etc.
Solution to NP- Complete (NPC) Problems
A solution of the knapsack problem within any fixed
percentage of the optimal solution can be computed in
polynomial time, but finding the optimal solution is NP-
complete.
At present, all known algorithms for NP-complete
problems require time that is super-polynomial in the
input size, and it is unknown whether there are any
faster algorithms.
NP- Complete (NPC)
The following techniques can be applied to solve
computational problems in general, and they often
give rise to substantially faster algorithms:
1. Approximation: Search for an "almost" optimal one.
2. Randomization: Use randomness to get a faster average
running time, and allow the algorithm to fail with some
small probability.
3. Restriction: Restricting the structure of the input.
4. Parameterization: Fast algorithms are possible, if certain
parameters of the input are fixed.
5. Heuristic: An algorithm that works "reasonably well" in
many cases, but for which there is no proof that it is both
always fast and always produces a good result.
Introduction to Soft Computing
The discipline of computing is the systematic study of
algorithmic processes that describe and transform
information: their theory, analysis, design, efficiency,
implementation, and application.
Types of computing
1. Hard computing
2. Soft Computing
Introduction to Soft Computing
Soft Computing is a new multidisciplinary field that
was proposed by Dr. Lotfi Zadeh, whose goal was to
construct new generation Artificial Intelligence, known
as Computational Intelligence.
Dr. Zadeh defined Soft Computing in its latest
incarnation as the fusion of the fields of Fuzzy Logic,
Neuro-computing, Evolutionary and Genetic
Computing, and Probabilistic Computing into one
multidisciplinary system.
Soft Computing
The main goal of Soft Computing is to develop
intelligent machines to solve nonlinear and
mathematically un-modelled system problems.
Soft computing differs from conventional (hard)
computing in that, unlike hard computing, it is tolerant
of imprecision, uncertainty, partial truth, and
approximation (i.e., the role model for soft computing
is the human mind).
Soft Computing is term used to refer the problem in
computer science whose solution is not predictable,
uncertain and between 0 and 1.
Hard Computing Vs. Soft Computing
Hard Computing Soft Computing
Conventional computing requires a Soft computing is tolerant of
precisely stated analytical model imprecision
Often requires a lot of computation Can solve some real world problems
time in reasonably less time
Not suited for real world problems for Suitable for real world problems
which ideal model is not present
It requires full truth Can work with partial truth
Strictly sequential Parallel computations
It is precise and accurate Imprecise
Programs are to be written Evolve their own programs
High cost for solution Low cost for solution
Soft Computing
Soft computing deals with imprecision, uncertainty,
partial truth, and approximation to achieve
practicability, robustness and low solution cost.
Imprecision is a property related to the content of the
statement: Lack of precision or exactness; defect of
accuracy.
Uncertainty is a property that results from a lack of
information about the world for deciding if the
statement is true or false.
Soft Computing
The main difference between soft computing and
possibility is, possibility is used when we don't have
enough information to solve a problem but soft
computing is used when we don't have enough
information about the problem itself.
These kind of problems originate in human mind with
all its doubts, subjectivity and emotions; an example
can be determining a suitable temperature for a room
to make people feel comfortable.
It forms the basis of a considerable amount of
machine learning techniques.
Soft Computing
Components of soft computing include:
Neural networks (NN)
Support Vector Machines (SVM)
Fuzzy logics (FL)
Evolutionary computation (EC), including:
o Evolutionary algorithms
• Genetic algorithms; Differential evolution
o Meta-heuristic and Swarm Intelligence
• Ant colony optimization;
• Particle swarm optimization
Ideas about probability including:
o Bayesian network
• Chaos theory
Soft Computing
Soft computing techniques resemble biological
processes more closely than traditional techniques,
which are largely based on formal logical systems.
This resulted in the possibility of constructing
intelligent systems such as autonomous self-tuning
systems and automated designed systems.
Soft computing techniques are intended to
complement each other.
Soft Computing Constituents
SC = EC + NN + FL
Soft Evolutionary Neural Fuzzy
Computing Computing Networks Logic
Zadeh Rechenbery McCulloch Zadeh
1981 1960 1943 1965
EC = GP + ES + EP + GA
Evolutionary Genetic Evolution Evolutionary Genetic
Computing Programming Strategies Programming Algorithms
Rechenbery Koza Rechenberg Fogel Holland
1960 1992 1965 1962 1970
Soft Computing Constituents
Evolving neuro-
fuzzy systems
Neuro –fuzzy and
Genetic fuzzy
fuzzy neural
network
network
Fuzzy Logic
Neural SOFT Genetic
COMPUTING
Network Algorithms
Probabilistic
Reasoning
Modular rough Genetic Bayesian
networks network
Application Layer 1
Application Layer 2
Soft Computing Constituents
Methodologies Strengths
Neural Networks Learning and Adaptation
Knowledge Representation via
Fuzzy Set Theory
Fuzzy If - Then rules
Genetic Algorithms and
Systematic Random Search
Simulated Annealing
Conventional AI Symbolic Manipulation
Hybridization of these create a successful synergic effect; the
synergism allows to incorporate human knowledge
effectively, deal with imprecision and uncertainty and learn to
adapt to unknown or changing environments for better
performance.
Soft Computing
Soft Computing is a good option for complex systems,
where:
The system is non-linear, time-variant or ill-defined
The variables are continuous
A mathematical model is either too difficult to
encode, does not exist or is too complicated and
expensive to be evaluated
There are noisy or numerous inputs
An expert is available who can outline the rules-of-
thumb that should determine the system behavior.
Soft Computing
General areas that need these kinds of systems are:
Classification
Optimization
Data mining
Prediction
Control
Scheduling
Decision support or auto-decision making
Soft Computing – Neural Networks
Neural Networks are good at classification, data-
mining and prediction systems, where there is lots of
available potentially noisy input data, which either
needs to be classified into groups or which needs to
be mapped to an expected output.
They do, however, suffer from a lack of transparency,
as the calculation is encoded in the weights and
thresholds of multiply connected networks.
Soft Computing – Evolutionary Computing
Evolutionary Computing techniques are adapted to
optimization and design problems, where a good
solution can be recognized, but where there is no
“correct” answer.
This technique is essentially an efficient search
technique that deals well with the problem of getting
“stuck” with a sub-optimal solution.
The main difficulty with the technique is defining how
the solutions should be encoded and assessed for
their fitness.
Soft Computing – Fuzzy Logic
Fuzzy Logic systems are best suited to decision
making and control systems that have “rules-of-thumb”
that cannot be translated to hard mathematical
formulae.
These rules are used to perform a logical, non-linear
mapping between inputs and outputs, which simulates
the decision-making processes in humans.
These systems rely very heavily on being able to
determine rules that accurately describe the system.
They also need the membership functions for the
fuzzy sets used to be tuned correctly, which can also
be difficult due to their non-linear nature.
