Algoritmo genetico: funzionamento e applicazioni

Un algoritmo genetico (“genetic algorithm” in inglese) è un procedimento di ottimizzazione che imita i meccanismi della selezione naturale e ha come obiettivo quello di migliorare iterativamente popolazioni di soluzioni potenziali. Gli algoritmi genetici sono utilizzati in una vasta gamma di applicazioni, che spaziano dall’ottimizzazione di sistemi tecnici all’apprendimento automatico.

Che cos’è un algoritmo genetico?

Gli algoritmi genetici (o genetic algorithms, GA) sono una metodologia di ricerca utilizzata per risolvere problemi decisionali complessi, basata sui principi della selezione naturale e della genetica. Questi algoritmi appartengono alla categoria degli algoritmi evolutivi e utilizzano meccanismi che imitano il processo di selezione naturale per migliorare progressivamente le soluzioni a un problema. In sostanza, gli algoritmi genetici cercano di trovare soluzioni ottimali o soddisfacenti in spazi di soluzioni vasti e complessi, attraverso una ricerca iterativa che emula il principio di “sopravvivenza del più adatto” su cui si basa la selezione naturale. Questo processo si basa su alcune premesse:

1. Gli individui competono per risorse e per la possibilità di accoppiarsi.
2. Gli individui più forti o di maggior successo generano più discendenti.
3. I geni dei “genitori più adatti” vengono tramandati di generazione in generazione, generando discendenti con sequenze genetiche vantaggiose.
4. Poiché i migliori geni vengono tramandati a lungo termine, ogni generazione è meglio adattata all’ambiente rispetto alla precedente.

Gli algoritmi genetici generano una popolazione di individui, ognuno dei quali rappresenta una soluzione potenziale al problema. Gli individui che riescono meglio ad adattarsi al proprio ambiente sopravvivono e si riproducono. Ogni individuo è rappresentato da cromosomi, che possono essere espressi come stringhe di caratteri (bit, float, integer, ecc.), mentre i singoli cromosomi sono composti da geni che rappresentano specifici tratti, come ad esempio il colore dei capelli. Le varianti di un gene come biondo, castano o nero, sono dette alleli.

Per avvicinarsi alla soluzione ottimale, gli algoritmi genetici avviano un processo iterativo di calcolo e riproduzione. I cromosomi vengono modificati e combinati tramite diversi operatori genetici – selezione, crossover (ricombinazione) e mutazione – in modo da trovare progressivamente soluzioni migliori. In questo modo, gli algoritmi genetici combinano buone soluzioni parziali per raggiungere una soluzione globale migliore.

Come funzionano gli algoritmi genetici?

Il processo iterativo di un algoritmo genetico si suddivide generalmente nelle seguenti fasi:

1. Il problema di ottimizzazione viene codificato su un cromosoma binario.
2. L’algoritmo genetico genera una popolazione iniziale di individui, spesso casuale. Questa popolazione iniziale è chiamata generazione 0.
3. A ogni individuo viene assegnato un punteggio di fitness, sotto forma di numero reale.
4. Viene selezionato un gruppo di genitori dalla popolazione, basandosi su un metodo di selezione predefinito.
5. I discendenti vengono generati combinando le informazioni genetiche dei genitori.
6. I tratti genetici dei discendenti (gli alleli) potrebbero subire mutazioni, che potrebbero invertire i propri valori.
7. La popolazione cresce con i nuovi discendenti. Se la dimensione della popolazione supera un limite stabilito, viene applicato uno schema di sostituzione che determina quali individui non fanno più parte della soluzione.
8. Fintanto che non si soddisfa un criterio di arresto, l’algoritmo genetico ripete i passaggi 3-7 per avvicinarsi sempre più alla soluzione ottimale. Il criterio di arresto può variare; alcuni algoritmi si fermano dopo un numero prestabilito di generazioni, mentre altri continuano fino a quando non c’è più alcun miglioramento rispetto alla generazione precedente.

Punteggio di fitness

Con il termine fitness si intende l’adattabilità dell’individuo. Il punteggio di fitness di un individuo indica quanto questo è competitivo. L’obiettivo dell’algoritmo genetico è trovare l’individuo con il punteggio di fitness ideale (o quasi ideale). Gli individui con un punteggio migliore hanno maggiori probabilità di essere scelti per la riproduzione, il che porta a generazioni successive con soluzioni parziali migliori.

Quali sono gli operatori utilizzati dagli algoritmi genetici?

Gli algoritmi genetici utilizzano vari operatori per sviluppare ulteriormente la popolazione iniziale. I meccanismi di base che consentono l’evoluzione sono la selezione, la ricombinazione e la mutazione. Descriviamo questi operatori qui di seguito.

Selezione (Selection Operator)

La selezione determina quali individui avranno la possibilità di generare discendenti e quante generazioni avranno. La selezione si basa sul punteggio di fitness, privilegiando gli individui con valori migliori.

Ricombinazione (Crossover Operator)

I nuovi individui vengono creati mediante ricombinazione. I punti di crossover vengono selezionati casualmente e i geni vengono scambiati tra i genitori, creando discendenti con nuove caratteristiche. Un esempio:

• Geni del genitore 1: A|B|C|D|E|F
• Geni del genitore 2: G|H|I|J|K|L
• Geni dei discendenti: A|B|I|J|K|F

Mutazione (Mutation Operator)

L’idea di base della mutazione è l’inserimento casuale di nuovi geni nei discendenti, modificando la potenziale soluzione di un problema decisionale. Questo mantiene la varietà all’interno della popolazione e previene la convergenza prematura. Un esempio:

• Gene prima della mutazione: A|B|C|D|E|F
• Gene dopo la mutazione: A|B|L|D|T|F

In quali settori vengono utilizzati gli algoritmi genetici?

Gli algoritmi genetici sono utilizzati principalmente in settori in cui i metodi analitici tradizionali raggiungono i propri limiti. Questo è particolarmente vero per i problemi che coinvolgono spazi di soluzioni grandi e complessi. Un campo di applicazione centrale è il deep learning, in cui gli algoritmi genetici vengono utilizzati per ottimizzare i pesi delle reti neurali.

Inoltre, gli algoritmi genetici sono spesso impiegati nella pianificazione della produzione per aiutare a trovare orari ottimali e assegnazioni delle risorse. In economia e finanza, vengono utilizzati nell’ottimizzazione del portafoglio e nello sviluppo di strategie di trading complesse. Un altro campo di applicazione riguarda la regolazione degli iperparametri dei modelli nel campo dell’apprendimento automatico. Sebbene non sempre siano il metodo più efficiente, gli algoritmi genetici sono considerati una tecnica di ottimizzazione molto versatile grazie alla loro flessibilità.

Esempio pratico di utilizzo degli algoritmi genetici

Immagina che il compito di un algoritmo genetico sia di generare una stringa obiettivo, ad esempio “The fittest survive” (sopravvive il più adatto), partendo da una stringa casuale di uguale lunghezza. I caratteri (A-Z, a-z, 0-9 e simboli) rappresentano i geni, mentre la stringa stessa è il cromosoma, ossia la soluzione. Il punteggio di fitness riflette la differenza tra i caratteri della stringa e quella obiettivo. Gli individui con un punteggio inferiore (cioè meno differenze) vengono selezionati per la riproduzione. La tabella seguente mostra come potrebbe evolversi l’output:

Tuttavia, si noti che l’output potrebbe variare. Questo è dovuto al fatto che l’algoritmo genetico parte da stringhe casuali.