Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) ·...

21
Algoritmi Evolutivi e Teoria della Computabilità Prof. Mario Pavone CdL Magistrale in Informatica Dip. Matematica ed Informatica [email protected] http://www.dmi.unict.it/mpavone/

Transcript of Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) ·...

Page 1: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Algoritmi  Evolutivi  e    Teoria  della  Computabilità  

Prof.  Mario  Pavone  CdL  Magistrale  in  Informatica  Dip.  Matematica  ed  Informatica    [email protected]  http://www.dmi.unict.it/mpavone/  

Page 2: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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

Page 3: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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)

Page 4: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

ALGORITMO EVOLUTIVO

Popolazione di Soluzioni

Parents

Offspring

Scambio delle caratteristiche dei parents

Cambiamenti casuali

Page 5: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

ALGORITMO EVOLUTIVO

Popolazione di Soluzioni

Parents

Offspring

Scambio delle caratteristiche dei parents

Cambiamenti casuali

Page 6: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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

Page 7: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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

Page 8: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

TEORIA DELLA COMPLESSITÀ

Page 9: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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

Page 10: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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 +⎟

⎠

⎞⎜⎝

⎛∑−

=+

Page 11: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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.  

Page 12: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

Page 13: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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.  

Page 14: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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    

Page 15: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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

Page 16: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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.  

Page 17: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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  

Page 18: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Example:  HYPERCUBES  

Page 19: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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  

Page 20: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

Mario  Pavone,  AA.  2014/2015  –  Computazione  Naturale,  CdL  Magistrale  Informatica,  DMI,  UniCT  –  [email protected]  

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  

Page 21: Algoritmi)Evolutivi)e)) Teoria)della)Computabilità) · Mario)Pavone,)AA.)2014/2015)–Computazione)Naturale,)CdL)Magistrale)Informatica,)DMI,)UniCT)–mpavone@dmi.unict.it) Problem

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/


Universalità artificialità computabilità

Universalità artificialità computabilità

Quick Start Guide bit DMI Quick Start Guide bit DMI la funzione BY-PASS viene tenuta in memoria anche se si spegne e riaccende il veicolo o il sistema audio infinite volte, quindi

Quick Start Guide bit DMI Quick Start Guide bit DMI la funzione BY-PASS viene tenuta in memoria anche se si spegne e riaccende il veicolo o il sistema audio infinite volte, quindi

D.L. 24 gennaio 2015, n. 3 (2) - cliclavoro.gov.it · legge, laddove ciò è necessario ad assicurare la computabilità delle azioni nel ... Comma aggiunto dalla legge di conversione

D.L. 24 gennaio 2015, n. 3 (2) - cliclavoro.gov.it · legge, laddove ciò è necessario ad assicurare la computabilità delle azioni nel ... Comma aggiunto dalla legge di conversione

moove blower - IPERCERAMICA€¦ · caratteri Stiche dmi en Soinali • Wegiht and dmi en Soin S • dmi en Soin S & podi S maSSe und ge Wcihte • caracteri Stica S dmi en Soinale

moove blower - IPERCERAMICA€¦ · caratteri Stiche dmi en Soinali • Wegiht and dmi en Soin S • dmi en Soin S & podi S maSSe und ge Wcihte • caracteri Stica S dmi en Soinale

Quick Start Guide bit DMI Quick Start Guide bit DMI - Audison...La modalità BY-PASS è consigliata quando il veicolo deve subire un intervento di assistenza presso un’officina autorizzata

Quick Start Guide bit DMI Quick Start Guide bit DMI - Audison...La modalità BY-PASS è consigliata quando il veicolo deve subire un intervento di assistenza presso un’officina autorizzata

Universalità artificialità computabilità Per una storia del computer Roma II, 23 Novembre 2001 Teresa Numerico teris@mclink.it.

Universalità artificialità computabilità Per una storia del computer Roma II, 23 Novembre 2001 Teresa Numerico [email protected].

Sistemi dinamici discreti e computabilità intrinseca Marco Giunti Università di Cagliari giunti@unica.it .

Sistemi dinamici discreti e computabilità intrinseca Marco Giunti Università di Cagliari [email protected] .

VASCULOPATIE IN GRAVIDANZA Massimo Luerti, Fulvia Cellani DMI, U.O. di Ostetricia e Ginecologia 1 Ospedale Maggiore di Lodi.

VASCULOPATIE IN GRAVIDANZA Massimo Luerti, Fulvia Cellani DMI, U.O. di Ostetricia e Ginecologia 1 Ospedale Maggiore di Lodi.

Prof. Mario Pavone Computazione Naturale CdL Magistrale in Informatica SDAI – DMI – UniCt mpavone@dmi.unict.it Teoria.

Prof. Mario Pavone Computazione Naturale CdL Magistrale in Informatica SDAI – DMI – UniCt [email protected] Teoria.

Cenni sull'Architettura degli Elaboratori - units.it · Cenni sull’Architettura degli Elaboratori Eugenio G. Omodeo Dip. MatematicaeGeoscienze—DMI Trieste,08/10/2015 E. G. OmodeoCenni

Cenni sull'Architettura degli Elaboratori - units.it · Cenni sull’Architettura degli Elaboratori Eugenio G. Omodeo Dip. MatematicaeGeoscienze—DMI Trieste,08/10/2015 E. G. OmodeoCenni

SottoSistema Tecnologico di Bordo VOLUME 3 DMI - …€¦ · SPECIFICA DEI REQUISITI DI SISTEMA SSC/SCMT BL3 Volume 3 – DMI - Specifica di ergonomia Direzione Tecnica – Direzione

SottoSistema Tecnologico di Bordo VOLUME 3 DMI - …€¦ · SPECIFICA DEI REQUISITI DI SISTEMA SSC/SCMT BL3 Volume 3 – DMI - Specifica di ergonomia Direzione Tecnica – Direzione

VERBALE DELLA RIUNIONE DEL CONSIGLIO DEL ... - sites.unipg.itsites.unipg.it/v3/dmi/files/doc-dmi/consiglio... · Università degli Studi di Perugia Dipartimento di Matematica e Informatica

VERBALE DELLA RIUNIONE DEL CONSIGLIO DEL ... - sites.unipg.itsites.unipg.it/v3/dmi/files/doc-dmi/consiglio... · Università degli Studi di Perugia Dipartimento di Matematica e Informatica

INFORMATICA “UNPLUGGED”: PERCORSI DIDATTICI TRA …...CODING e ORIENTEERING . Salerno, 14/06/2017. Aaron Gaio. aaron.gaio.tn@gmail.com Università degli Studi di Palermo - DMI.

INFORMATICA “UNPLUGGED”: PERCORSI DIDATTICI TRA …...CODING e ORIENTEERING . Salerno, 14/06/2017. Aaron Gaio. [email protected] Università degli Studi di Palermo - DMI.

Teoria degli algoritmi e della computabilità Approfondimento: Un modo divertente di parlare di complessità computazionale: puzzle, matematica e algoritmi.

Teoria degli algoritmi e della computabilità Approfondimento: Un modo divertente di parlare di complessità computazionale: puzzle, matematica e algoritmi.

Computabilità e complessità - didawiki.cli.di.unipi.itdidawiki.cli.di.unipi.it/lib/exe/fetch.php/informatica/all-b/... · l’essenza computazionale di un programma ma non deve

Computabilità e complessità - didawiki.cli.di.unipi.itdidawiki.cli.di.unipi.it/lib/exe/fetch.php/informatica/all-b/... · l’essenza computazionale di un programma ma non deve

PA-DMI-01 Piano Miglioramento Qualità Assistenziale ... · Tutto il Personale Infermieristico dell' U.O.C. di Pediatria e Neonatologia 15/03/2018 Verifica Direttore di Dipartimento

PA-DMI-01 Piano Miglioramento Qualità Assistenziale ... · Tutto il Personale Infermieristico dell' U.O.C. di Pediatria e Neonatologia 15/03/2018 Verifica Direttore di Dipartimento

Scienze cognitive e computabilità: le origini Corso di Logica e Filosofia della Scienza a.a. 2013-2014.

Scienze cognitive e computabilità: le origini Corso di Logica e Filosofia della Scienza a.a. 2013-2014.

Teoria degli algoritmi e della computabilità Terza giornata: Ricerca e ordinamento ottimi. P vs NP, algoritmi di approssimazione, e il potere della randomizzazione.

Teoria degli algoritmi e della computabilità Terza giornata: Ricerca e ordinamento ottimi. P vs NP, algoritmi di approssimazione, e il potere della randomizzazione.

Scienze cognitive e computabilità: le origini

Scienze cognitive e computabilità: le origini

Computabilità - MathUniPDbaldan/Computabilita/Intro.pdf · Primo: in ogni teoria T assiomatizzabile e consistente della aritmetica elementare esistono enunciati F per i quali non

Computabilità - MathUniPDbaldan/Computabilita/Intro.pdf · Primo: in ogni teoria T assiomatizzabile e consistente della aritmetica elementare esistono enunciati F per i quali non