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