Algoritmo genetico: fun­zio­na­men­to e ap­pli­ca­zio­ni

Un algoritmo genetico (“genetic algorithm” in inglese) è un pro­ce­di­men­to di ot­ti­miz­za­zio­ne che imita i mec­ca­ni­smi della selezione naturale e ha come obiettivo quello di mi­glio­ra­re ite­ra­ti­va­men­te po­po­la­zio­ni di soluzioni po­ten­zia­li. Gli algoritmi genetici sono uti­liz­za­ti in una vasta gamma di ap­pli­ca­zio­ni, che spaziano dall’ot­ti­miz­za­zio­ne di sistemi tecnici all’ap­pren­di­men­to au­to­ma­ti­co.

Che cos’è un algoritmo genetico?

Gli algoritmi genetici (o genetic al­go­ri­thms, GA) sono una me­to­do­lo­gia di ricerca uti­liz­za­ta per risolvere problemi de­ci­sio­na­li complessi, basata sui principi della selezione naturale e della genetica. Questi algoritmi ap­par­ten­go­no alla categoria degli algoritmi evolutivi e uti­liz­za­no mec­ca­ni­smi che imitano il processo di selezione naturale per mi­glio­ra­re pro­gres­si­va­men­te le soluzioni a un problema. In sostanza, gli algoritmi genetici cercano di trovare soluzioni ottimali o sod­di­sfa­cen­ti in spazi di soluzioni vasti e complessi, at­tra­ver­so una ricerca iterativa che emula il principio di “so­prav­vi­ven­za 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 pos­si­bi­li­tà di ac­cop­piar­si.
2. Gli individui più forti o di maggior successo generano più di­scen­den­ti.
3. I geni dei “genitori più adatti” vengono tra­man­da­ti di ge­ne­ra­zio­ne in ge­ne­ra­zio­ne, generando di­scen­den­ti con sequenze genetiche van­tag­gio­se.
4. Poiché i migliori geni vengono tra­man­da­ti a lungo termine, ogni ge­ne­ra­zio­ne è meglio adattata all’ambiente rispetto alla pre­ce­den­te.

Gli algoritmi genetici generano una po­po­la­zio­ne di individui, ognuno dei quali rap­pre­sen­ta una soluzione po­ten­zia­le al problema. Gli individui che riescono meglio ad adattarsi al proprio ambiente so­prav­vi­vo­no e si ri­pro­du­co­no. Ogni individuo è rap­pre­sen­ta­to da cromosomi, che possono essere espressi come stringhe di caratteri (bit, float, integer, ecc.), mentre i singoli cromosomi sono composti da geni che rap­pre­sen­ta­no specifici tratti, come ad esempio il colore dei capelli. Le varianti di un gene come biondo, castano o nero, sono dette alleli.

Per av­vi­ci­nar­si alla soluzione ottimale, gli algoritmi genetici avviano un processo iterativo di calcolo e ri­pro­du­zio­ne. I cromosomi vengono mo­di­fi­ca­ti e combinati tramite diversi operatori genetici – selezione, crossover (ri­com­bi­na­zio­ne) e mutazione – in modo da trovare pro­gres­si­va­men­te soluzioni migliori. In questo modo, gli algoritmi genetici combinano buone soluzioni parziali per rag­giun­ge­re una soluzione globale migliore.

Come fun­zio­na­no gli algoritmi genetici?

Il processo iterativo di un algoritmo genetico si suddivide ge­ne­ral­men­te nelle seguenti fasi:

1. Il problema di ot­ti­miz­za­zio­ne viene co­di­fi­ca­to su un cromosoma binario.
2. L’algoritmo genetico genera una po­po­la­zio­ne iniziale di individui, spesso casuale. Questa po­po­la­zio­ne iniziale è chiamata ge­ne­ra­zio­ne 0.
3. A ogni individuo viene assegnato un punteggio di fitness, sotto forma di numero reale.
4. Viene se­le­zio­na­to un gruppo di genitori dalla po­po­la­zio­ne, basandosi su un metodo di selezione pre­de­fi­ni­to.
5. I di­scen­den­ti vengono generati com­bi­nan­do le in­for­ma­zio­ni genetiche dei genitori.
6. I tratti genetici dei di­scen­den­ti (gli alleli) po­treb­be­ro subire mutazioni, che po­treb­be­ro invertire i propri valori.
7. La po­po­la­zio­ne cresce con i nuovi di­scen­den­ti. Se la di­men­sio­ne della po­po­la­zio­ne supera un limite stabilito, viene applicato uno schema di so­sti­tu­zio­ne 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 av­vi­ci­nar­si sempre più alla soluzione ottimale. Il criterio di arresto può variare; alcuni algoritmi si fermano dopo un numero pre­sta­bi­li­to di ge­ne­ra­zio­ni, mentre altri con­ti­nua­no fino a quando non c’è più alcun mi­glio­ra­men­to rispetto alla ge­ne­ra­zio­ne pre­ce­den­te.

Punteggio di fitness

Con il termine fitness si intende l’adat­ta­bi­li­tà dell’individuo. Il punteggio di fitness di un individuo indica quanto questo è com­pe­ti­ti­vo. 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 pro­ba­bi­li­tà di essere scelti per la ri­pro­du­zio­ne, il che porta a ge­ne­ra­zio­ni suc­ces­si­ve con soluzioni parziali migliori.

Quali sono gli operatori uti­liz­za­ti dagli algoritmi genetici?

Gli algoritmi genetici uti­liz­za­no vari operatori per svi­lup­pa­re ul­te­rior­men­te la po­po­la­zio­ne iniziale. I mec­ca­ni­smi di base che con­sen­to­no l’evo­lu­zio­ne sono la selezione, la ri­com­bi­na­zio­ne e la mutazione. De­scri­via­mo questi operatori qui di seguito.

Selezione (Selection Operator)

La selezione determina quali individui avranno la pos­si­bi­li­tà di generare di­scen­den­ti e quante ge­ne­ra­zio­ni avranno. La selezione si basa sul punteggio di fitness, pri­vi­le­gian­do gli individui con valori migliori.

Ri­com­bi­na­zio­ne (Crossover Operator)

I nuovi individui vengono creati mediante ri­com­bi­na­zio­ne. I punti di crossover vengono se­le­zio­na­ti ca­sual­men­te e i geni vengono scambiati tra i genitori, creando di­scen­den­ti con nuove ca­rat­te­ri­sti­che. Un esempio:

• Geni del genitore 1: A|B|C|D|E|F
• Geni del genitore 2: G|H|I|J|K|L
• Geni dei di­scen­den­ti: A|B|I|J|K|F

Mutazione (Mutation Operator)

L’idea di base della mutazione è l’in­se­ri­men­to casuale di nuovi geni nei di­scen­den­ti, mo­di­fi­can­do la po­ten­zia­le soluzione di un problema de­ci­sio­na­le. Questo mantiene la varietà all’interno della po­po­la­zio­ne e previene la con­ver­gen­za 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 uti­liz­za­ti gli algoritmi genetici?

Gli algoritmi genetici sono uti­liz­za­ti prin­ci­pal­men­te in settori in cui i metodi analitici tra­di­zio­na­li rag­giun­go­no i propri limiti. Questo è par­ti­co­lar­men­te vero per i problemi che coin­vol­go­no spazi di soluzioni grandi e complessi. Un campo di ap­pli­ca­zio­ne centrale è il deep learning, in cui gli algoritmi genetici vengono uti­liz­za­ti per ot­ti­miz­za­re i pesi delle reti neurali.

Inoltre, gli algoritmi genetici sono spesso impiegati nella pia­ni­fi­ca­zio­ne della pro­du­zio­ne per aiutare a trovare orari ottimali e as­se­gna­zio­ni delle risorse. In economia e finanza, vengono uti­liz­za­ti nell’ot­ti­miz­za­zio­ne del por­ta­fo­glio e nello sviluppo di strategie di trading complesse. Un altro campo di ap­pli­ca­zio­ne riguarda la re­go­la­zio­ne degli iper­pa­ra­me­tri dei modelli nel campo dell’ap­pren­di­men­to au­to­ma­ti­co. Sebbene non sempre siano il metodo più ef­fi­cien­te, gli algoritmi genetici sono con­si­de­ra­ti una tecnica di ot­ti­miz­za­zio­ne molto versatile grazie alla loro fles­si­bi­li­tà.

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” (so­prav­vi­ve il più adatto), partendo da una stringa casuale di uguale lunghezza. I caratteri (A-Z, a-z, 0-9 e simboli) rap­pre­sen­ta­no i geni, mentre la stringa stessa è il cromosoma, ossia la soluzione. Il punteggio di fitness riflette la dif­fe­ren­za tra i caratteri della stringa e quella obiettivo. Gli individui con un punteggio inferiore (cioè meno dif­fe­ren­ze) vengono se­le­zio­na­ti per la ri­pro­du­zio­ne. 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.