Transcript Evolutionary Algorithms & Protein Folding

Combinatorial Landscapes &
Evolutionary Algorithms
Prof. Giuseppe Nicosia
University of Catania
Department of Mathematics and Computer Science
[email protected]
www.dmi.unict.it/~nicosia
DMI - Università di Catania
16/07/2015
1
Talk Outline
1. Combinatorial Landscapes
2. Evolutionary Computing
DMI - Università di Catania
16/07/2015
2
1. Combinatorial Landscapes
The notion of landscape is among the rare
existing concepts which help to understand
the behaviour of search algorithms and
heuristics and to characterize the difficulty
of a combinatorial problem.
DMI - Università di Catania
16/07/2015
3
Search Space
Given a combinatorial problem P, a search
space associated to a mathematical formulation
of P is defined by a couple (S,f)
– where S is a finite set of configurations (or nodes or
points) and
– f a cost function which associates a real number to
each configurations of S.
For this structure two most common measures
are the minimum and the maximum costs.In
this case we have the combinatorial
optimization problems.
DMI - Università di Catania
16/07/2015
4
Example: K-SAT
An instance of the K-SAT problem consists of a
set V of variables, a collection C of clauses over
V such that each clause c  C has |c|= K.
The problem is to find a satisfying truth
assignment for C.
The search space for the 2-SAT with |V|=2 is
(S,f) where
– S={ (T,T), (T,F), (F,T), (F,F) } and
– the cost function for 2-SAT computes only the
number of satisfied clauses
fsat (s)= #SatisfiedClauses(F,s), s  S
DMI - Università di Catania
16/07/2015
5
An example of Search Space
Let we consider F = (A  B)  ( A  B)
A
T
T
B
T
F
fsat(F,s)
F
F
T
F
1
2
DMI - Università di Catania
1
2
16/07/2015
6
Search Landscape
• Given a search space (S,f), a search landscape
is defined by a triplet (S,n,f) where n is a
neighborhood function which verifies
n : S  2S -{ 0}
• This landscape, also called energy landscape,
can be considered as a neutral one since no
search process is involved.
• It can be conveniently viewed as weighted
graph G=(S, n , F) where the weights are
defined on the nodes, not on the edges.
DMI - Università di Catania
16/07/2015
7
Example and relevance of
Landscape
The search Landscape for the K-SAT problem
is a N dimensional hypercube with
N = number of variables = |V| .
• Combinatorial optimization problems are often
hard to solve since such problems may have
huge and complex search landscape.
DMI - Università di Catania
16/07/2015
8
Hypercubes
DMI - Università di Catania
16/07/2015
9
Solvable &
Impossible
•The New York Times, July
13, 1999 “Separating
Insolvable and Difficult”.
• B. Selman, R. Zecchina,
et al.“Determing
computational complexity
from characteristic
‘phase transitions’ ”,
Nature, Vol. 400, 8 July
1999,
DMI - Università di Catania
16/07/2015
10
Phase Transition, =4.256
DMI - Università di Catania
16/07/2015
11
Characterization of the Landscape in terms of
Connected Components
Number of solutions, number of connected components and CCs'
cardinality versus  for #3-SAT problem with n=10 variables. 16/07/2015
DMI - Università di Catania
12
CC's cardinality at phase transition (3)=4.256
Number of Solutions, number of connected components and CC's
cardinality at phase transition (3)=4.256 versus number of variables n
for #3-SAT problem.
16/07/2015
DMI - Università di Catania
13
Process Landscape
Given a search landscape (S, n, f), a process
landscape is defined by a quadruplet (S, n, f, ) where
 is a search process.
• The process landscape represents a particular view of
the neutral landscape (S, n, f) seen by a search
algorithm.
• Examples of search algorithms:
– Local Search Algorithms.
– Complete Algorithms (e. g. Davis-Putnam algorithm).
– Evolutionary Algorithms: Genetic Algorithms, Genetic
Programming, Evolution Strategies, Evolution Programming,
Immune Algorithms.
DMI - Università di Catania
16/07/2015
14
2. Evolutionary Algorithms
EAs are optimization methods based on
an evolutionary metaphor that showed
effective in solving difficult problems.
“Evolution is the natural way to program”
Thomas Ray
DMI - Università di Catania
16/07/2015
15
Evolutionary Algorithms
1. Set of candidate solutions (individuals): Population.
2. Generating candidates by:
– Reproduction: Copying an individual.
– Crossover:  2 parents   2 children.
– Mutation: 1 parent  1 child.
3. Quality measure of individuals: Fitness function.
4. Survival-of-the-fittest principle.
DMI - Università di Catania
16/07/2015
16
Main components of EAs
1. Representation of individuals: Coding.
2. Evaluation method for individuals: Fitness.
3. Initialization procedure for the 1st generation.
4. Definition of variation operators (mutation and crossover).
5. Parent (mating) selection mechanism.
6. Survivor (environmental) selection mechanism.
7. Technical parameters (e.g. mutation rates, population size).
Experimental tests, Adaptation based on measured quality,
Self-adaptation based on evolution.
DMI - Università di Catania
16/07/2015
17
Mutation and Crossover
EAs manipulate partial
solutions in their search for
the overall optimal solution .
These partial solutions or
`building blocks' correspond to
sub-strings of a trial solution - in
our case local sub-structures
within the overall conformation.
DMI - Università di Catania
16/07/2015
18
Algorithm Outline
procedure EA; {
t = 0;
initialize population (P(t), d);
evaluate P(t);
until (done) {
t = t + 1;
parent_selection P(t);
recombine (P(t), pcross);
mutate ( P(t), pmut);
evaluate P(t);
survive P(t);
}
}
DMI - Università di Catania
16/07/2015
19