Intelligenza artificiale in medicina 2025 (IAM)

SELECTION OPERATORS:

Random selection: la selezione casuale è l'operatore di selezione più semplice ogni individuo ha la

➢ →

1/ns

stessa probabilità di (dove ns è la dimensione della popolazione) di essere selezionato. Non ven-

gono utilizzate informazioni di fitness, il che significa che gli individui migliori e peggiori hanno esatta-

mente la stessa probabilità di sopravvivere alla generazione successiva. La selezione casuale ha la

pressione selettiva (o tempo di acquisizione) più bassa tra i tipici operatori di selezione.

Proportional selection: la selezione proporzionale orienta la selezione verso gli individui più adatti

➢ →

ne scelgo alcuni con fitness migliore per andare consequenzialmente a migliorare. Viene creata una

distribuzione di probabilità proporzionale all'idoneità e gli individui vengono selezionati tramite cam-

pionamento della distribuzione. Il metodo di campionamento più diffuso utilizzato nella selezione pro-

porzionale è il roulette wheel sampling (campionamento della ruota

della roulette): è un esempio di operatore di selezione proporzionale

in cui i valori di fitness sono normalizzati (ad esempio dividendo ogni

fitness per il valore di fitness massimo). La distribuzione di probabi-

lità può quindi essere vista come una ruota della roulette, in cui la

dimensione di ogni fetta è proporzionale alla probabilità di selezione

normalizzata di un individuo. La selezione può essere paragonata alla

rotazione di una ruota della roulette e alla registrazione di quale fetta

finisce in cima; l'individuo corrispondente viene quindi selezionato.

Nella roulette ci sono fette più grandi o più piccole a seconda della fitness avrò più probabilità di

→

prendere quelle con fitness più alta ma non escludo quelle con fitness minore.

Tournament Selection; (più in dettaglio nelle slide)

➢ Rank-Based Selection; (più in dettaglio nelle slide)

➢ Elitism; (più in dettaglio nelle slide)

➢ Hall of Fame: la hall of fame è uno schema di selezione in cui, per ogni generazione, il miglior individuo

➢ viene selezionato per essere inserito nella hall of fame. La hall of fame conterrà quindi un archivio dei

migliori individui trovati. La hall of fame può essere utilizzata come pool di genitori per l'operatore di

crossover oppure, all'ultima generazione, il miglior individuo viene selezionato come il migliore nella

hall of fame. La riproduzione è il processo di produzione di prole da genitori selezionati applicando

operatori di crossover e/o mutazione.

1. Il crossover è il processo di creazione di uno o più nuovi individui attraverso la combinazione di mate-

riale genetico selezionato casualmente da due o più genitori.

Si parte selezionando un certo numero di genitori e si fanno delle coppie, per ogni coppia si scambiano

delle sottostringhe per generare nuove soluzioni:

2. La mutazione è il processo di modifica casuale dei valori dei geni in un cromosoma. L'obiettivo princi-

pale della mutazione è introdurre nuovo materiale genetico nella popolazione, aumentando così la di-

versità genetica. La mutazione dovrebbe essere applicata con attenzione per non distorcere il mate-

riale genetico “buono” in individui altamente adatti. Per questo motivo, la mutazione è solitamente ap-

plicata con una bassa probabilità.

Si lavora sul singolo bit estraendone in modo casuale uno o più e complementandoli: se il bit valeva 0

adesso varrà 1.

Oltre alla dimensione della popolazione, la performance di un GA è influenzata dal mutation rate (probabilità

di mutazione): pm (generalmente intorno a 0.1 o 0.05 e aumenta, ma mai 0), e dal crossover rate (probabilità

di crossover): pc.

Nei primi studi sui GA vengono usati valori molto bassi per pm e valori relativamente alti per pc e di solito i va-

lori per pm e pc vengono mantenuti statici. Tuttavia, è ampiamente accettato che questi parametri abbiano

un'influenza significativa sulle prestazioni e che le impostazioni ottimali per pm e pc possano migliorare signifi-

cativamente le prestazioni. Un'alternativa è quella di utilizzare parametri che cambiano dinamicamente.

Minore pm più rimaniamo vicini alla situazione di partenza; maggiore pm più ci svincoliamo dalle soluzioni di

partenza.

Generalmente a partire dalla popolazione iniziale si prende 80% delle soluzioni e si fanno diventare genitori, si

applicano i due operatori e si ottengono l’80% in più di soluzioni (se partivo da 100 soluzioni nella popolazione

iniziale, ne seleziono 80 (genitori) da cui otterrò altre 80 soluzioni, avendo alla fine un totale di 180 devo farlo

→

tornare a 100:

1. Tolgo quelle selezionate (i genitori) e metto al loro posto quelle che ho generato (un po’ drastico).

2. Metto insieme quelle di 180, uso operatore selezione e ne seleziono solo 100 e a questo punto ricomin-

cio: Criteri diversi:

a. Sostituzione: le nuove soluzioni sostituiscono le soluzioni padre.

b. Costruzione: dopo aver unito la vecchia popolazione con le nuove soluzioni,

viene utilizzato un operatore di selezione per costruire la nuova popolazione.

Decisioni da prendere per la costruzione di un GA: Le scelte di

questi valori

devono es-

sere fatte

tenendo

tutte conto

di tutto,

perché la

scelta di un

valore po-

trebbe con-

dizionare

quella di un

altro.

Quindi in breve:

Codifica della soluzione ogni possibile soluzione del problema viene rappresentata in una forma codificata.

→

Popolazione iniziale si genera un insieme iniziale di soluzioni (chiamate popolazioni).

→

Funzione di fitness si misura con questa funzione la qualità di ogni soluzione rispetto al problema che

→

stiamo cercando di risolvere.

Condizioni di arresto si decide quando fare terminare l’algoritmo.

→

Selezione si scelgono le soluzioni migliori da usare come base per creare nuove soluzioni.

→

Costruire nuove soluzioni si creano nuovi individui a partire da quelli selezionati, utilizzando operatori gene-

→

tici (crossover o mutazione).

Ricostruire la popolazione la popolazione nuova sostituisce quella vecchia o viene combinata con essa.

→

A questo punto l’algoritmo termina e restituisce la migliore soluzione trovata. Lez. 8

Ma come inizializzo?

Per decidere dimensione popolazione e numero di iterazioni:

Numero di soluzioni del problema senza vincoli mi fornisce una stima del numero di soluzioni pre-

➢ →

senti nello spazio delle soluzioni; (2^n)-1 con n=numero di bit.

Spazio di esplorazione: x% (cioè la % delle soluzioni che voglio esplorare) di tutte le possibili soluzioni

➢ x viene identificato come un buon compromesso tra tempo di esecuzione e soluzioni esplorate. Ge-

→

neralmente < del 15%. Non ha senso un 100%;

Dimensione popolazione iniziale * Numero di iterazioni ≈ (perché è una stima) Numero di soluzioni

➢ generate Se il peso computazionale della fitness è basso si usa un PopSize alto e NoIterations

→

basso (MA NON TROPPO BASSO); se il peso computazionale della fitness è alto si preferisce aumen-

tare NoIterations e tenere più basso PopSize. Dobbiamo ottenere un valore prossimo (perché alcune

potrebbero ripetersi e non sappiamo esattamente quante ne abbiamo) alla % di soluzioni che vogliamo

ottenere.

Per gli operatori di riproduzione:

Crossover Devo definire il numero di tagli e se tagliare random o sempre negli stessi punti;

➢ →

Mutation Devo definire quanti bit vengono complementati e la funzione con cui scegliere i bit da

➢ →

complementare;

Pc (probabilità di crossover) Assume generalmente valori molto alti, compresi tra 0.9 e 1, in fun-

➢ →

zione della numerosità dei genitori.

Pm (probabilità di mutazione) Assume generalmente valori molto bassi, compresi tra 0.05 e 0.1,

➢ →

ma se la numerosità della popolazione è bassa si può partire con valori più alti e diminuire Pm nel

corso delle iterazioni;

IMPLEMENTARE UN GA PER UN PROBLEMA SPECIFICO:

A dx dello schema abbiamo il caso di esito positivo trovo la soluzione migliore.

→

A sx dello schema c’è il caso di esito negativo bisogna capire le cause e si riparte dall’inizializzazione.

→

Il tuning dei parametri lo faccio sulla parte di definizione della popolazione. Fare tuning vorrà dire testare

→

diversi setup (diversi valori di pc e pm). Si fanno più prove mantenendo fissi i valori dei parametri, poi li cambio

e faccio di nuovo tante prove una soluzione è robusta se si ripete nel tempo valutazione della stabilità

→ →

delle soluzioni: partendo dalla stessa popolazione iniziale l'algoritmo restituisce sempre la stessa soluzione

finale (condizione ideale);

Partiamo dalla soluzione ideale: ovvero tutte le soluzioni si ripetono uguali a sé stesse (perché ogni volta alla

fine dell’algoritmo troviamo sempre la soluzione migliore).

Attenzione perché nell’ algoritmo del lab c’è il rischio di perdere la soluzione migliore in assoluto. Quella va

sempre salvata e nel caso in cui se ne trovi una migliore viene aggiornata ed è su questo che si fa il confronto

per la condizione di stop.

Vanno decisi dei criteri (=modello dei requisiti che devono possedere i risultati per poter essere definiti robu-

sti) per sapere se ci sono delle soluzioni che vanno bene e le ripetizioni dell’algoritmo devono convergere verso

la stessa soluzione.

Criteri per la valutazione della stabilità:

• Numero di soluzioni identiche;

• Numero di soluzioni con lo stesso valore di fitness (ES: se uso due variabili differenti ma esse mi danno

lo stesso risultato combinate con le variabili che rimangono non mi interessa se uso la prima o la se-

conda ma vado a vedere solo la fitness);

• Numero di soluzioni simili (con al massimo 1 o 2 bit diversi);

Numero di soluzioni simili:

Abbiamo un problema passiamo al modello usiamo GA troviamo la soluzione quella soluzione di-

→ → → →

venta la soluzione del problema.

La soluzione del GA é sempre una sequenza di 0 e 1, la soluzione del problema é il valore corrispondente

delle variabili modified se le ho modificate o yes/no se le ho usate come binarie.

Development process (sviluppo del sistema)

Classification basic

Classification nel mio dataset devo avere le classi. Dato un insieme di classi e un elemento, l'elemento

→

deve essere assegnato a una classe.

Come faccio a sapere se la classe è corretta? Lo vedo nella fase di addestramento.

Abbiamo un certo elemento (righe), potrebbe