Post on 06-Feb-2018
Algoritmi Genetici
1) Selezionare le soluzioni migliori e ricombinarle in qualche modo fra loro in maniera
tale che esse evolvano verso un punto di ottimo.
2) La funzione da massimizzare prende il nome di fitness (adattamento). La funzione di fitness valuta la adattabilit dellindividuo. Essa dipende dal numero di variabili:
Esempio se la funzione dipende da 5 parametri (a,b,c,d,e) ed ogni variabile varia in
un intervallo compreso tra 1 e 10 -> lesplorazione dello spazio delle soluzioni sar
510 = circa 10 milioni
3) Ogni informazione, tipo i valori dei 5 parametri, possono essere codificati in formato
binario (il linguaggio dei computer!). Una soluzione potr quindi essere
rappresentata mediante una successione (detta stringa) di 0 e 1, ad es.
100110101001110
Gli Algoritmi Genetici (AG) sono procedure complesse adattative finalizzate alla
risoluzione di problemi di ricerca e ottimizzazione e basate concettualmente sui principi che regolano l'evoluzione naturale delle specie.
Algoritmi GeneticiPopolazione: un insieme di soluzioni.Individui: membri della popolazioneCromosoma: la sequenza di 0 e 1Geni: i valori 0 e 1 dei parametri del cromosoma
Genotipo: L'insieme dei geni rappresentati da una stringa.
Fenotipo: L'individuo ad esso corrispondente.
Nella rappresentazione binaria si assume
che ogni gene sia rappresentabile con un
certo numero p di bit. Esempio Gene1 = {0,0,1,1}
Gene2 = {0,1,0,1}
Gene3 = {1,0,1,1}
Gene4 = {1,1,0,1}
Una soluzione, cio un individuo della
specie, rappresentata da una stringa di
n*p cifre binarie (il cromosoma composto da n geni ovvero n parametri) alla quale associato un valore di fitness (F).
Algoritmi GeneticiAd ogni generazione viene scelta un porzione dellintera popolazione e viene fatta evolvere con i meccanismi di ricombinazione. Al passaggio successivo passeranno gli individui con fitness migliore ovvero gli individui pi adatti (calcolo basato sulla funzione di fitness). Un individuo selezionato se la sua fitness probabile (ad esempio se f il valore di fitness di una soluzione e F la somma dei valori di fitness di tutta la popolazione, la probabilit potrebbe essere f/F)
la fitness media della popolazione
tender quindi ad aumentare con le
generazioni, portando cos la specie
ad evolversi nel tempo.
Algoritmi Genetici
Levoluzione procede principalmente
per eventi di crossing over (due tipi) o mutazione
Per accelerare la convergenza
allipotetico massimo conviene
spesso far si che l'individuo
migliore di una generazione venga
copiato e passi alla successiva
senza subire modifiche. Tale
tecnica detta elitismo, e se le popolazioni sono abbastanza
numerose pu essere estesa a pi
di un individuo, imponendo cio che
i migliori n individui vengano clonati
nella generazione successiva
mentre per gli altri si procede nella
solita maniera.
Algoritmi Genetici
Anche in questo caso, come per MMC e SA, il problema che si propongono di
risolvere quello di cercare il lottimo globale di una certa funzione.
La funzione o il modello deve, quindi, essere noto.
Sono utili quando la funzione troppo complessa per essere velocemente
massimizzata con tecniche tipo exhaustive search.
Quando utilizzarli ? (Le Applicazioni)
Vantaggi
1) Si scelgono, rispetto agli altri tipi di ottimizzazione, quando ci sono molti
parametri che descrivono un fenomeno e tra di essi non c una evidente
correlazione.
2) La ricerca stocastica dellottimo globale viene fatta in parallelo e questo li
rende pi efficienti e meno suscettibili agli ottimi locali. Essendo in parallelo,
infatti, quello che avviene in una certa porzione della popolazione non
dipende da quello che avviene in altre parti della popolazione. In pratica
effettuano una ricerca Montecarlo molto efficiente con in pi una progressione evolutiva.
Svantaggi
Algoritmi Genetici
1) Sebbene la prospettiva di trovare lottimo globale sia efficiente la convergenza
a questo risultato pi lenta di altre tecniche di ottimizzazione. Infatti, se gi le
soluzioni della popolazioni di partenza sono vicine allottimo globale, una
ricerca con altre tecniche pi rapida e accurata. Nei GA viene perso troppo
tempo a testare e calcolare la fitness di soluzioni subottimali.
2) La natura stocastica del metodo comporta che trovare lottimo globale sia
difficile e si ha solo unapprossimazione o stima di questultimo. Trovarlo
effettivamente dovuto pi al caso (come per tutti i sistemi di ottimizzazione
per problemi complessi).
LE RETI NEURALILE RETI NEURALI
MACHINE LEARNINGMACHINE LEARNING
AI (AI (ArtificialArtificial Intelligence)Intelligence)
MotivazioneMotivazione
Quando possibile costruire delle predizioni basate su osservazioni elementari e un insieme di regole (da stabilire) abbiamo visto che si possono considerare i metodi di ottimizzazione. Questi metodi sonoin grado di generare soluzioni nuove non ancora osservate. Creano quindi delle ipotesi che spiegano il comportamento p.es. della
natura.
In bioinformatica spesso sono chiamati metodi ab initio.
In alternativa si pu pensare di costruire delle predizioni basate sullaconoscenza dei dati che abbiamo. Questi metodi sono di apprendimento o machinemachine learninglearning (come HMM, NN, SVM) e sonodi tipo knowledge-based, nel senso che richiedono una conoscenzainiziale della materia con dei training set su cui basare le propriepredizioni. Non si genera conoscenza nuova, semplicemente si usa quella
esistente per interpretare nuovi casi.
Non sono in grado di predire situazioni che non si sono ancora verificatein precedenza.
MotivazioneMotivazione
Per molti problemi di tipo biologico si hanno dati sperimentali chedeterminano certe condizioni di una proteina (p.es. Struttura
secondaria) senza per conoscere a pieno i meccanismi che lideterminano.
Quindi: Sarebbe utile avere un modo per costruire modelli chesimulino i risultati sperimentali. Questo permette di predire altri casi non
ancora realizzati.
A questo scopo sono stati sviluppati i metodi di machine learning chepermettono al computer di identificare delle regolarit ed estrapolare
regole di carattere generali.
La categoria pi conosciuta di questi metodi sono le reti neurali.
MachineMachine learninglearning
Input
Output (conosciuto)
Black box
(rete neurale)
Fase di apprendimento
Input
Predizione
Black box
(rete neurale)
Fase di predizione
Esempio: Predizione della struttura secondaria.SequenzaSequenza AA AA {{--elicaelica, , --strandstrand, , coilcoil}}
ReteRete NeuraleNeurale ((neuralneural netnet NN)NN)
Output Output ((CCHHHHCCHHHH))
Input Input ((ASCDEFGASCDEFG))
Input
Predizione
Black box
(rete neurale)
Fase di predizione
Le reti neurali artificiali sono modelli computazionali costituiti da elementi di
elaborazione (ispirati ai neuroni) connessi tra loro tramite collegamenti (ispirati alle
sinapsi) in modo da formare uno schema assimilabile ad un semplicissimo tessuto
nervoso.
Per definizione, le reti neurali artificiali sono strutture parallele e distribuite per il
trattamento dell'informazione, consistenti in elementi di elaborazione interconnessi
per mezzo di canali unidirezionali chiamati connessioni.
DEFINIZIONE DI RETE NEURALEDEFINIZIONE DI RETE NEURALE
Ogni connessione ha un peso numerico associato, il cui valore varia in base
all'esperienza maturata. I pesi diventano il principale mezzo di memorizzazione I pesi diventano il principale mezzo di memorizzazione
a lungo termine per le reti neurali e l'apprendimento di un parta lungo termine per le reti neurali e l'apprendimento di un particolare icolare
"comportamento" si ottiene in genere attraverso il loro aggiorna"comportamento" si ottiene in genere attraverso il loro aggiornamentomento.
A partire da osservazioni di carattere biologico stato definito un modello generale
di neurone artificiale che pu essere visto come una unit di elaborazione che
effettua una somma pesata dei segnali di ingresso ed esegue una trasformazione
non lineare del risultatato ottenuto.
DEFINIZIONE DI RETE NEURALEDEFINIZIONE DI RETE NEURALE
Un neurone (o pi semplicemente nodo) composto da:
Un insieme di collegamenti di ingresso che provengono da altre unit.
Una singola uscita che si dirama in diverse connessioni secondarie ognuna
delle quali trasporta lo stesso segnale (il segnale di uscita dell'unit).
Una funzione che definisca il segnale di uscita dell'unit stessa (o livello di
attivazione) dati gli ingressi (aj: valore d'ingresso proveniente dall'uscita dell'unita j) e i rispettivi pesi (Wj,i: peso associato al collegamento dall'unit j all'unit i).
STRUTTURA DI UN NEURONESTRUTTURA DI UN NEURONE
Il calcolo suddiviso in due componenti: in primo luogo una componente
lineare, chiamata funzione d'ingresso che effettua la somma pesata dei valori degli
ingressi allunit i. Quindi una componente non lineare g chiamata funzione di
attivazione (una funzione elementare tipo la funzione gradino, segno o la
cosiddetta sigmoide) che calcolano il valore di uscita dellunit a partire dalla
somma pesata precedente.
STRUTTURA