Algoritmi genetici – cosa sono

Questa breve serie di articoli ha l’intenzione di fornire una panoramica sugli algoritmi genetici, partendo da un quadro teorico fino ad arrivare ad una bozza di codice per la risoluzione di problemi di ottimizzazione mediante tale tecnica.

Nel processo di evoluzione di una specie, gli individui più adatti a sopravvivere in determinate condizioni sono più idonei alla riproduzione. In tal modo, i caratteri genetici si trasmettono nelle generazioni successive migliorando le caratteristiche della specie. Questo processo è l’idea sulla quale si basano gli algoritmi genetici, i quali sono sfruttati per la risoluzione di problemi di ottimizzazione. Partendo da una popolazione iniziale generata casualmente, si procede simulando l’evoluzione di una specie selezionando di generazione in generazione, solitamente secondo relazioni matematiche, gli individui più idonei alla risoluzione del problema. La riproduzione degli individui viene simulata mediante operatori volti a simulare le leggi della genetica, quali ad esempio mutazione e cross-over, analizzati più nel dettaglio in seguito.

L’analogia biologica negli algoritmi genetici si estende anche alla terminologia utilizzata:

• INDIVIDUO: Possibile soluzione del problema
• POPOLAZIONE: Insieme della soluzioni su cui ricercare contemporaneamente la soluzione
• CROMOSOMA: Codifica della soluzione nell’alfabeto scelto (è possibile utilizzare anche altre codifiche, non solo quella binaria, ad esempio reali, intere o anche miste)
• GENE: Codifica di un particolare elemento della soluzione candidata (es. parametro)
• ALLELE: Possibile valore di ogni bit della stringa
• FITNESS: Indicatore associato a ciascun individuo (set di parametri) in base alla bontà con cui è soluzione del problema. Dipende dai valori reali dei parametri che costituiscono il singolo individuo.

Analizzando la struttura dell’algoritmo, in primo luogo bisogna generare una poopolazione iniziale. Generalmente questo avviene assegnando ad ogni individuo parametri casuali, che però ovviamente rispettino i vincoli imposti dal dominio di ogni gene. È possibile introdurre ulteriori vincoli oltre a quelli imposti dai domini, per i quali solitamente si tende a non essere così restrittivi come nel caso precedente. Un esempio di questa tipologia di vincoli potrebbe essere che il valore assunto dal gene 1 sia strettamente minore del valore assunto dal gene 3. L’imporre che questo vincolo venga rispettato in tutti gli individui generati, potrebbe portare alla mancata esplorazione di alcune soluzioni possibili nel corso dell’esecuzione dell’algoritmo, motivo per cui una soluzione spesso adottata è riparare gli individui che non rispettano tale vincolo solo nel 50% dei casi.

Dopo aver creato la popolazione iniziale e riparato eventuali individui non ammissibili (seguendo la politica descritta precedentemente), si passa alla valutazione delle singole soluzioni mediante la funzione di fitness. La funzione di fitness può essere singola e ne possiamo avere più di una (in questo caso si parla di ottimizzazione multi-obiettivo). Nel caso di ottimizzazione multi-obiettivo, le diverse funzioni di fitness possono spesso essere tra di loro competitive, motivo per cui bisogna scegliere quale strategia adottare per una corretta valutazione dei singoli individui. Una possibilità spesso adottata per il confronto delle diverse funzioni multi-obiettivo è l’impiego del criterio di Pareto per il confronto di vettori, di cui si riporta di seguito la struttura.

Secondo il criterio di confronto di Pareto un vettore x si dice parzialmente minore (<p) di y se sussiste la relazione

x \text{ <p } y \iff \forall i (x_i \le y_i) \land \exist i (x_i < y_i)

In queste condizioni si dice che il vettore y domina il vettore x. Si può applicare questa definizione agli individui della popolazione generata dall’algoritmo genetico. Se un individuo produce un vettore di fitness che non è dominato da nessun altro vettore, allora l’individuo si dice non dominato o non inferiore (in questo caso si parla si soluzione PARETO-OTTIMA). Utilizzando questo approccio lo scopo dell’algoritmo diventa trovare tutte le soluzioni non dominate nello spazio definito dalle singole funzioni obiettivo. Queste soluzioni costituiscono il cosiddetto fronte di Pareto, tra le quali è possibile scegliere la soluzione che rappresenta il miglior compromesso. Il vantaggio dell’applicazione di questo criterio consiste nella possibilità di assegnare a posteriori la diversa importanza di un obiettivo rispetto a un altro, senza dover ripetere il processo di ottimizzazione.

Una volta calcolato il vettore (o matrice, nel caso di funzione multi-obiettivo) contenente i valori assunti dalle funzioni fitness relative alla popolazione iniziale, si può passare al ciclo principale dell’algoritmo. Il ciclo terminerà solo quando si raggiunge il criterio di terminazione, che può consistere semplicemente in un numero finito di iterazioni oppure si possono definire criteri che verifichino se si è raggiunta la convergenza verso una soluzione ottima. All’interno del ciclo viene generata la popolazione discendente, vengono selezionati gli individui migliori e si procede con l’iterazione.

Nella fase iniziale si selezionano gli individui per la creazione delle nuove generazioni. La selezione può avvenire seguendo diverse strategie, quali ad esempio il metodo della roulette o il metodo del torneo. Nel metodo del torneo vengono selezionati casualmente alcuni individui che partecipano al torneo, viene definito il vincitore come l’individuo avente il miglior valore della funzione fitness e si prosegue con un nuovo torneo fino a quando non si raggiunge un numero sufficiente di individui da selezionare. Il metodo della roulette invece consiste nell’estrarre un numero casuale s compreso tra 0 e 1 e, definita F_T la somma dei fitness dei singoli individui, partendo dal primo individuo si sommano le fitness relative F_P/F_T finché s < F_P/F_T . L’ultimo individuo considerato è quello selezionato. Anche in questo caso il metodo è iterato fino al raggiungimento del numero di individui da selezionare per proseguire con l’algoritmo.

Una volta selezionati gli individui genitori, si procede con l’operazione di CROSS-OVER, durante la quale vengono generati i discendenti. A partire da una coppia di genitori si genera una coppia di figli secondo il seguente algoritmo. Si scelgono a caso coppie di cromosomi genitori e si estrae a caso un numero compreso tra 0 e 1. Se è minore della probabilità di cross-over (circa 0.8) su copia nei figli il DNA dei genitori, altrimenti, si scelgono a caso una o più posizioni nel cromosoma a partire dalle quali scambiare i bit dei genitori.

I discendenti prodotti da tale operazione subiscono quindi ulteriori modifiche mediante l’operazione di MUTAZIONE. Tale operazione ha effetto solitamente solo con probabilità abbastanza piccole (intorno al 5%) e consiste nel modificare alcuni dei bit che compongono la stringa del cromosoma, complementandoli. Dato che un cromosoma può anche non essere costituito da soli bit, basti pensare alla possibilità di avere anche valori reali, è possibile proporre varianti di tale operazione, magari in cui si prevede di alterare il valore del singolo gene sommando o sottraendo una quantità contenuta all’interno di un certo range (occhio ovviamente a rispettare i vincoli derivanti dai domini dei singoli geni).

L’ultimo passo da compiere prima di completare la generazione dei discendenti consiste nel riparare eventuali individui che non rispettano i vincoli introdotti dal problema. La riparazione avviene secondo la politica espressa all’inizio dell’articolo, in cui si menzionava la necessità di non riparare tutti i geni che violano i vincoli per poter espandere l’area di esplorazione durante l’esecuzione dell’algoritmo.

Per poter completare l’iterazione dobbiamo quindi aggiornare la nuova popolazione, la quale, posta N la dimensione della popolazione originale, coinciderà con l’insieme degli N migliori individui selezionati dall’unione della popolazione originale e dei discendenti. Tale selezione può avvenire con un banale algoritmo di sorting, a seconda delle esigenze del problema in questione.

Alla terminazione dell’algoritmo si otterrà una popolazione finale, sulla quale, a seconda delle personali esigenze, possono essere svolte varie operazioni, tra le quali ad esempio estrarre il miglior individuo per ricavare il valore ottimo di fitness ottenuto dall’algoritmo. Tale valore, se ad esempio parliamo di un algoritmo di minimizzazione, non è detto che coincida con il minimo globale della nostra funzione di fitness, ma può tranquillamente esserne una buona approssimazione se l’algoritmo è stato eseguito con un numero sufficientemente elevato di parametri.

Concludendo, passiamo alla valutazione degli algoritmi genetici, verificandone vantaggi e svantaggi. Indubbiamente, tra i vantaggi ritroviamo l’adattibilità ai problemi complessi. Gli algoritmi genetici possono affrontare problemi complessi di ottimizzazione, in particolare quelli con spazi di ricerca vasti o non lineari. La loro capacità di esplorare diverse soluzioni e combinazioni di parametri li rende adatti per una vasta gamma di applicazioni. Inoltre, la possibilità di produrre diverse soluzioni ottime o approssimate per un problema, consentendo la scoperta di opzioni alternative dei trade-off tra obiettivi multipli, li rende utili nella gestione dei problemi di ottimizzazione multi-obiettivo.

Tali vantaggi sono purtroppo controbilanciati da altre caratteristiche, quali ad esempio la dipendenza dai parametri. La convergenza dell’algoritmo o la qualità delle soluzioni ottenute sono altamente influenzate da una scelta appropriata dei parametri. A seconda del tipo di criterio ottenuto per la terminazione dell’algoritmo si ha inoltre la possibilità di convergenza prematura a soluzioni locali ottimali, ignorando soluzioni migliori nel paesaggio di ricerca (questo problema risulta fortemente limitato dall’utilizzo degli operatori di selezione, cross-over e mutazione). Infine, il difetto maggiore che riscontriamo in questa tipologia di algoritmi è il tempo di esecuzione. La complessità computazione degli algoritmi genetici può aumentare in base alla dimensione del problema e alla complessità delle soluzioni. Ciò può comportare tempi di esecuzione significativi, specialmente per problemi molto grandi.