Computazione Naturale
AA. 2014-2015
Prof. Mario Pavone
CdL Magistrale in Informatica
Dip. Matematica ed Informatica
[email protected]
http://www.dmi.unict.it/mpavone/






Cos’è la Computazione Naturale?
Programma del corso
Obiettivi formativi
Modalità di Valutazione
Altre utili informazioni
Proposte di Elaborati Finali e/o Tesi
di Laurea
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
La
Teoria dell ’ Evoluzione (Darwin, 1859) si basa
principalmente su due punti: la selezione, che premia
gli individui più forti di una specie, e la mutazione,
che introduce diversità nel patrimonio genetico
Algoritmi Evolutivi: provano a simulare l’evoluzione
naturale/biologica per risolvere complessi problemi.
Come mai tali sistemi artificiali complessi
raggiungono buone soluzione per un dato problema ?
Finalità:
comprendere
più a fondo i processi di sviluppo dei
sistemi viventi
sviluppare sistemi artificiali che riproducono le
caratteristiche dei processi naturali
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
Sono
sistemi computazionali che prendono ispirazione
dall’evoluzione naturale
Nature Inspired Computation: SIMULANO E NON
COPIANO
Uno dei principi presi in prestito è la sopravvivenza del
migliore
Le tecniche di computazione naturale vengono utilizzati per
problemi di ottimizzazione e learning
Le tecniche di computazione naturale non richiedono alcuna
conoscenza del dominio di applicazione: SCATOLE NERE
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
Applicazioni del mondo reale richiede lo sviluppo di
sistemi adattabili
GOAL:
scrivere solo semplici regole
l’intelligenza emerge dall’interazione di queste regole
L’evoluzione è un metodo di ricerca fra un numero
vasto di possibilità
Evoluzione: metodo di adattamento ai cambiamenti
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
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
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
Stochastic optimization methods
Monte Carlo methods
Simulated Annealing
Evolutionary Algorithms
Genetic Algorithms
Evolution Strategies
Genetic Programming
Evolutionary Programming
Swarm intelligence
Artificial Immune Systems
Membrane Computing
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
Punto
di partenza: meccanismi
strumenti di ottimizzazione
dell’evoluzione
come
evolvere
una popolazione di soluzioni utilizzando operatori
ispirati alla variabilità genetica e selezione naturale
Evolutionary Strategy by Rechenberg (1965,1973) e Schwefel
(1975,1977)
Evolutionary Programming by Fogel, Owens e Walsh (1966)
Genetic Algorithm by John Holland (1960):
no
risolvere problemi specifici, ma studiare il fenomeno di
adattamento
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
GAs sono algoritmi basati sulla popolazione
GAs prendono spunto dalla genetica
popolazioni di cromosomi che si evolvono utilizzando una
simulazione della selezione naturale, assieme ad operatori di
ispirazioni genetica (incrocio, mutazione ed inversione)
Un cromosoma è composto di geni, che rappresenta un particolare
allele
Operatore di selezione consente ai cromosomi più adatti di produrre
più discendenti
Incrocio: scambia parti dei cromosomi
Mutazione: scambia casualmente i valori degli alleli
Inversione: cambia l’ordine dei geni in una sezione del cromosoma
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
Parents
Popolazione
di Soluzioni
Scambio delle
caratteristiche
dei parents
Cambiamenti
casuali
Offspring
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
Vedi: http://www.dmi.unict.it/mpavone/nc-cs
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]

conoscenza dei concetti biologici di base

capire il funzionamento dei sistemi intelligenti

capacità autonoma di implementazione EAs

problem solving
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]


Criteri:
 accertamento del livello minimo per il conseguimento
degli obiettivi formativi
 livello di maturazione nella disciplina
Esame:
1. Test scritto
2. Progetto e relazione: implementare un algoritmo
evolutivo su un dato problema
3. Discussione orale con presentazione del progetto svolto.
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
TEST SCRITTO





Consiste di 15 (30) domande a risposta
multipla
Ogni domanda può contenere una o più
risposte corrette
Per ogni risposta completamente corretta
vengono acquisiti 2 punti (1 punto)
Per ogni risposta parzialmente corretta viene
acquisito 1 punto (0 punti)
La prova scritta si considera superata se si
consegue una valutazione sufficiente
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
PROGETTO E RELAZIONE
Date le seguenti informazioni
1.
2.
3.
4.
5.
descrizione di un problema combinatorico;
un insieme di istanze del dato problema;
funzione obiettivo;
protocollo sperimentale;
elenco di alcuni algoritmi evolutivi, con specifiche
caratteristiche;
il candidato deve implementare un algoritmo scelto
dall'elenco
al
punto
(5),
che
risolva
approssimativamente le istanze date, utilizzando il
protocollo sperimentale fornito al punto (4);
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
PROGETTO E RELAZIONE
 consegna dell'elaborato con relazione;
 relazione scritta in LaTeX
 consegnare il file pdf con il codice



sorgente
LaTeX
min. 4 pag - max 12 pag
descrizione dell’algoritmo implementato, con un
introduzione, descrizione dei risultati ottenuti e
proprie conclusioni.
la consegna viene fissata 15/20 giorni successivi
alla data del punto precedente;
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
CRITERI DI VALUTAZIONE
1. originalità del lavoro prodotto;
2. complessità dell'algoritmo
implementato;
3. risultati ottenuti dall'algoritmo
implementato;
4. qualità della relazione prodotta.
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
COLLOQUIO ORALE
La terza prova consiste di una discussione orale sul
progetto sviluppato
Il candidato deve descrivere l'elaborato prodotto
tramite presentazione in powerpoint o pdf
Al candidato verrà assegnato un tempo di 10 minuti
per la sua presentazione
NOTA: La seconda e terza prova può essere sostenuta o
nello stesso appello in cui si è superata la prima prova, o
al più all’appello successivo
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
CRITERI DI VALUTAZIONE
1.
2.
3.
4.
esposizione;
sintesi di presentazione del lavoro
svolto;
qualità della presentazione prodotta;
padronanza degli argomenti esposti
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]

Recapiti:




Ricevimento


stanza 32 - 3° blocco
tel: 095 738 3038
Email: [email protected]
Mercoledì ore 11:00 – 12:30 (previo appuntamento)
Avvisi e Materiale


http://www.dmi.unict.it/mpavone/nc-cs/
Forum ufficiale del corso
Mario Pavone, AA. 2014/2015– Computazione Naturale, CdL Magistrale in Informatica, DMI, UniCt – [email protected]
Proposte Progetti Finali
Tesi di Laurea
Combinatorial Optimization Problems
 Systems & Synthetic Biology
 Computational Biology;
 Reverse Engineering Methodologies
 BioSystem Reverse Engineering
 Numerical Optimization Problems
 Operational Research
