Evolutionary computing, machine learning et alia

antonino.polimeno@unipd

Evolutionary computing, machine learning et alia

1

Motivazioni

‒ Ingegneria chimica e chimica industriale

‒ Ottimizzazione di reattori

‒ condizioni di reazione

‒ Sintesi

‒ Chimica combinatoriale, click chemistry

‒ Determinazione di strutture molecolari

‒ Protein folding

‒ Chimica farmaceutica

‒ Docking

1. R Judson, Genetic Algorithms and Their Use in Chemistry, Rev. Comp.

Chemistry 10 (1996)

2. JT Pedersen et al, Genetic algorithms for protein structure prediction, Current Opinion in Structural Biology 6, 227-231 (1996)

3. R Leardi, Genetic algorithms in chemistry, Journal of Chromatography A, 1158 226–233 (2007)

‒ Evolutionary computing

‒ Algoritmi genetici

‒ Alcuni esempi GA in chimica

‒ Un esempio specifico

‒ Machine learning

‒ Introduzione

‒ Esempi

3

Minimi locali/Massimo globale

Funzione di Rastrigin a n coordinate: minimo globale f(0)=0





1

10 co

( ) 1 0

s 2

i n

x

f n x 





  

x

Problema generale

‒ Minimizzazione dell’energia di una macromolecola

‒ Pochi minimi che corrispondono a strutture molecolari stabili

‒ Numero di minimi locali in crescita esponenziale con le dimensioni dello spazio di ricerca (n. coordinate)

‒ Classi di complessità

‒ Classe P: problemi di decisione che possono essere risolti con una macchina di Turing deterministica (computer) in un tempo che è polinomiale rispetto alla dimensione dei dati di ingresso;

‒ Classe NP: problemi di decisione le cui soluzioni positive possono essere verificate in tempo polinomiale avendo le giuste informazioni

‒ Problemi NP-completi: problemi che non apparterrebbero a P se P fosse diverso da NP.

5

?

P  NP

‒ Evolutionary computing

‒ Algoritmi genetici

‒ Alcuni esempi GA in chimica

‒ Un esempio specifico

‒ Machine learning

‒ Introduzione

‒ Esempi

Soft computing

Algoritmi evolutivi

Evolutionary programming

Genetic programming

Algoritmi genetici Machine

learning

Algoritmi genetici - 1

‒ Sono una tecnica di ottimizzazione/ricerca euristica

‒ Sono parte di una classe di tecniche dette algoritmi evolutivi che si ispirano alla biologia evoluzionistica

7

Finonacci Newton

Direct methods Indirect methods Calculus-based techniques

Evolutionary strategies

Centralized Distributed Parallel

Steady-state Generational Sequential

Genetic algorithms

Evolutionary algorithms Simulated annealing

Guided random search techniques

Dynamic programming Enumerative techniques

Search techniques

Algoritmi genetici - 2

1. Si genera una popolazione di possibili soluzioni (individui o fenotipi) al problema, rappresentate da cromosomi o genotipi o genoma; l’insieme di popolazioni forma una generazione

2. In ogni generazione si valuta la “salute”(fitness) di ogni individuo

3. Si forma una nuova generazione a partire da quella presente sulla base della loro salute e di altri criteri (vedi oltre)

4. L’algoritmo viene iterato fino ad un un numero massimo di generazioni o quando si sia ottenuto un fenotipo di salute adeguata

9

Un cromosoma può essere:

‒ Numero binario: 1011000100001

‒ Vettore di numeri reali: (1.2,-0.2,2.5,9.0)

‒ Vettore di permutazioni

‒ Lista di regole

‒ Istruzioni di programma (genetic programming)

Vocabolario minimo

‒ Spazio di ricerca: tutte le possibili soluzioni

‒ Individuo: una saluzione del problema

‒ Popolazione o generazione: insieme di individui

‒ Gene: un codice del cromosoma che codifica una caratteristica dell’individuo

‒ Genotipo: insieme di tutti i geni dell’individuo

‒ Cromosoma: un insieme di geni e di regioni non codificanti

‒ Genoma: tutti i cromosomi di un individuo

‒ Fenotipo: caratteristiche dell’individuo

N.B. definizioni proprie della genetica - Nell’ambito deli metodi GA diventano meno rigorose (cromosoma ≈ genotipo ≈ genoma)

gene

cromosoma

11

Genera la popolazione 1

Valuta la fitness degli individui

Controlla se il criterio di terminazione è raggiunto

Genera la popolazione successiva (elitismo, selezione, crossover,

mutazione etc.)

Termina

No Si

Step by step

‒ Inizializzazione

‒ La popolazione iniziale di N individui è di solito generata casualmente

‒ può contenere alcune soluzioni “buone” note a priori

‒ se M è lo spazio di ricerca, di solito N<<M

‒ Valutazione

‒ Si possono usare una o più funzioni di fitness f₁, f₂, … che sono funzioni del genotipo di ogni individuo

‒ Nuova generazione

‒ individuazione dei genitori: roulette wheel selection; elitismo

‒ riproduzione

‒ crossover

‒ mutazione

‒ Controllo e eventuale terminazione

Roulette wheel

for all members of population

sum += fitness of this individual end for

for all members of population

probability = sum of probabilities + (fitness / sum) sum of probabilities += probability

end for

loop until new population is full do this twice

number = Random between 0 and 1 for all members of population

if number > probability but less than next probability then you have been selected end for

end

create offspring end loop

13

‒ Evolutionary computing

‒ Algoritmi genetici

‒ Alcuni esempi GA in chimica

‒ Un esempio specifico

‒ Machine learning

‒ Introduzione

‒ Esempi

15

Machine learning

‒ Il machine learning (apprendimento automatico) è quella branca dell'intelligenza artificiale che

‒ riguarda lo studio, la costruzione e l'implementazione di algoritmi che permettano ai sistemi di calcolo sui quali sono implementati di imparare e fare previsioni in modo automatico …

‒ … a partire da un insieme di dati in ingresso, costruendo modelli previsionali.

‒ Una rete neurale è un processore distribuito basato sul modello del sistema nervoso centrale umano,

‒ è generalmente composta da unità computazionali elementari dette neuroni …

‒ … visti come nodi di una rete con determinate capacità di elaborazione e tra loro interconnessi (o connessi a cascata).

Reti neurali

‒ I neuroni formali sono in grado

1. di ricevere in input una combinazione di segnali dall’esterno o provenienti da altri neuroni e quindi

2. trasformarli tramite una particolare funzione chiamata funzione di attivazione, immagazzinando così i dati nei parametri della rete, in special modo nei pesi associati ad ogni connessione

3. per poi restituire in output un risultato dipendente dalla finalità per la quale la rete neurale è stata costruita (classificazione, riconoscimento, approssimazione, ecc.).

‒ I neuroni sono

1. disposti lungo delle linee orizzontali dette strati (quelli intermedi tra gli strati di ingresso ed uscita sono detti anche nascosti),

2. comunicano con i neuroni degli strati inferiori e superiori trasformando non-linearmente i segnali da strato a strato, e i loro pesi sono iterativamente “aggiustati” grazie a determinati algoritmi di apprendimento automatico

17

Deep learning

‒ Il deep learning (apprendimento profondo, talvolta tradotto con apprendimento approfondito) è una branca del machine learning che

‒ caratterizza i processi di reti neurali artificiali dotate di due o più strati (spesso chiamate multilayed o a hidden layers) …

‒ … capaci di processare informazioni in modo non-lineare (in relazione alla particolare funzione di attivazione scelta).