Please enable JavaScript.
Coggle requires JavaScript to display documents.
Evolutionary Algorithms as Problem Solvers (Problems (Search Problems,…
Evolutionary Algorithms
as Problem Solvers
Problems
Search Problems
Optimisation vs Constraint Satisfaction
Black Box Model
NP Problems
Black Box Model
Components
Output
Model
Input
Optimisation
Known
model & output
Unknown
input
Example
:
Scheduling / Timetable
Satellite Structure (Design structure to max vibration resist.)
Queens Chess Problem
TSP
Modelling
Modelling problems
can be transformed into
optimisation problems
Example
:
Evolutionary ML
Prediction stock exchange
Voice control system for smart homes
Load applicant credibility (prediction models)
Known
input & output
Seek model that delivers correct output for every known input
Simulation
Often used to answer “
what-if”
questions in evolving
dynamic environments
Example:
Evolutionary economics
Weather forecast system
Impact analysis new tax systems
Known
input & model
Unknown
output
Search Problems
Search Space
Collection of all objects of
interest
including the
desired solution
Optimisation/Modelling problems search through
huge space
of possibilities
Benefit
of Classify
Search Problems
Define search spaces
Problem-Solvers
How to move through search spaces
Optimisation vs
Constraint Satisfaction
Objective Function
A way of assigning a
value
to possible solution
that reflects
its quality on scale
Constraint
Binary evaluation
telling whether
a given
requirement
holds or not
Combination
Constraint Satisfaction Problem
Obj = No
Con = Yes
Free Optimisation Problem
Obj = Yes
Con = No
Constraint Optimisation Problem
Obj = Yes
Con = Yes
No Problem
Obj = No
Con = No
NP Problems
Key Notions
Running-Time
Number of operation
the algorithm takes to terminate
(Worst case / Polynomial)
Problem Reduction
Transforming
current problem
into
another via
mapping
Problem Size
Dimensionality
of the problem at hand
Number of different
values
for the problem
variables
Classify
Class NP
Problem can be solved
Any solution can be
verified within polynomial time
by some other algorithm
Class NP-Complete
Problem belongs to
class NP
Any other problem in NP can be reduced to this problem in
polynomial time
Class P
Algorithm can solve in
polynomial time
Class NP-hard
Problem is at least as hard as any other problem in NP-complete
Solution
cannot necessarily
be verified within
polynomial time