Post on 19-Feb-2019
Algoritmi Evolutivi e Teoria della Computabilità
Prof. Mario Pavone CdL Magistrale in Informatica Dip. Matematica ed Informatica mpavone@dmi.unict.it http://www.dmi.unict.it/mpavone/
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
COMPUTAZIONE NATURALE � Sono sistemi computazionali che prendono ispirazione
dalla Natura � Nature Inspired Computation: SIMULANO E NON
COPIANO � Sottocampo di “Intelligenza Artificiale” che coinvolge
problemi di ottimizzazione continua e combinatoria � Sono considerati come metodi di ottimizzazione globali � Le tecniche di computazione naturale vengono utilizzati
per problemi di ottimizzazione e learning � Uno dei principi presi in prestito è la sopravvivenza del
migliore � selezione del migliore � mutazione
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
COMPUTAZIONE NATURALE
� BlackBox Problems: tecniche di computazione naturale non richiedono alcuna conoscenza del dominio di applicazione
� Adatti in problemi con imprecisione, incertezza, verità parziale e approssimazione
� Principio Guida: sfruttare imprecisione, incertezza e approssimazione per ottenere trattabilità, robustezza e soluzioni low cost
� Processo iterativo: crescita e sviluppo di una popolazione => (evoluzione)
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
ALGORITMO EVOLUTIVO
Popolazione di Soluzioni
Parents
Offspring
Scambio delle caratteristiche dei parents
Cambiamenti casuali
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
ALGORITMO EVOLUTIVO
Popolazione di Soluzioni
Parents
Offspring
Scambio delle caratteristiche dei parents
Cambiamenti casuali
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
COMPUTAZIONE NATURALE
� Many aspects of such an evolutionary process are stochastic
� Changed pieces of information due to recombination and mutation are randomly chosen
�
� s e l e c t i o n o p e r a t o r s c a n b e e i t h e r deterministic, or stochastic
� individuals with a higher fitness have a higher chance to be selected � typically even the weak individuals have a
chance to become a parent or to survive
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
PERCHÉ LA COMPUTAZIONE NATURALE
� Flessibilità: applicabile a differenti problemi
� Robustezza: in grado di affrontare incertezza
� Adattivi: in grado di gestire applicazioni in ambienti dinamici attraverso l'auto-adattamento
� Autonomi: possono funzionare senza l’intervento dell’utente
� Decentrata: senza un autorità centrale
TEORIA DELLA COMPLESSITÀ
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
Problem 0 A problem is a general question to be answered,
usually possessing several parameters, or free variables, whose values are left unspecified.
0 A problem is described by giving: 0 a general description of all its parameters, and 0 a statement of what properties the answer, or solution,
is required to satisfy
0 An instance of a problem is obtained by specifying particular values for all the problem parameters
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
A Classical Example: TSP problem • The parameters of this problem consist of a finite set
C = c1, c2, . . . , cm
of "cities" and, for each pair of cities ci, cj in C, the "distance“ d(ci , cj) between them • A solution is an ordering
< cЛ(1), c Л(2) , . . . , c Л(m)>
• of the given cities that minimizes
this expression gives the length of the "tour" that starts at cЛ(1), visits each city in sequence, and then returns directly to cЛ(1) from the last city cЛ(m)
( ) ( ))1()(
1
1)1()( ,, ππππ ccdccd m
m
iii +⎟
⎠
⎞⎜⎝
⎛∑−
=+
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
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 dif4iculty of a combinatorial problem.
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
Search Space ¢ Given a combinatorial problem P, a search space associated to a mathematical formulation of P is deQined by a couple (S,f ) � where S is a Qinite set of conQigurations (or nodes or points) and � f a cost function which associates a real number to each conQigurations 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.
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
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 Qind 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 satisQied clauses
fsat (s)= #Satis4iedClauses(F,s), s ∈ S
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
An Example of SEARCH SPACE
Let we consider F = (A ∨ ¬B) ∧ (¬ A ∨ ¬B)
A B fsat(F,s) T T 1 T F 2 F T 1 F F 2
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
SEARCH LANDSCAPE ¢ Given a search space (S,f), a search landscape is deQined by a triplet (S,n,f) where n is a neighborhood function which veriQies
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 deQined on the nodes, not on the edges.
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
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
Example: HYPERCUBES
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
PROCESS LANDSCAPE ¢ Given a search landscape (S,n,f), a process landscape is
deQined 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
Mario Pavone, AA. 2014/2015 – Computazione Naturale, CdL Magistrale Informatica, DMI, UniCT – mpavone@dmi.unict.it
ALGORITHMS ¢ Algorithms are general, step-‐by-‐step procedures for solving problems
¢ For concreteness, we can think of them simply as being computer programs, written in some precise computer language.
¢ An algorithm is said to solve a problem P if that algorithm can be applied to any instance I of P and is guaranteed always to produce a solution for that instance I
¢ For example: � An algorithm does not "solve" the TSP unless it always constructs an ordering that gives a minimum length tour
BIBLIOGRAPHY M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completness, W. H. Freeman, 1st ed. (1979).
OR:
A compendium of NP optimization problems at the link:
http://www.csc.kth.se/~viggo/problemlist/