Evolutionary Algorithm: la genetica a supporto della tecnologia

Insieme all’apprendimento automatico, anche la genetica sta avendo un forte sviluppo negli ultimi anni. Alcuni risultati in questo campo si possono valutare grazie agli Evolutionary Algorithms (EA), ossia algoritmi sull’evoluzione che si sono sviluppati il secolo scorso, ma che stanno avendo un maggiore utilizzo grazie all’elevato miglioramento tecnologico.

 

Con il termine "algoritmo genetico" si fa riferimento ad una tecnica di ottimizzazione combinatoria basata sulla ricerca, sulla selezione naturale e sui principi della genetica. In altre parole è uno strumento di calcolo che è nato dall’ispirazione alle leggi Darwiniane sull’evoluzione naturale.

La selezione naturale rappresenta un processo che permette a una popolazione di cambiare nel corso delle generazioni, in conseguenza del fatto che gli organismi dotati di determinati caratteri vantaggiosi hanno più probabilità di sopravvivere e di riprodursi rispetto ad altri individui dotati di tratti diversi. Gli individui con i tratti ereditati più adatti all’ambiente, ossia che si adattano più facilmente all’ambiente, hanno maggiore probabilità di sopravvivere e riprodursi rispetto agli individui meno adattati.

 

Gli algoritmi genetici partono da una popolazione iniziale di soluzioni (gli individui dei sistemi biologici) che viene fatta evolvere iterativamente. Questa popolazione è generata casualmente da un algoritmo. Ad ogni iterazione, le soluzioni sono valutate da una funzione di fitness e sulla base di questa valutazione, vengono selezionate alcune di esse, privilegiando le soluzioni (genitori) con fitness maggiore. Le soluzioni selezionate vengono tra loro ricombinate (riproduzione) per generare nuove soluzioni (offspring o figli) che tendono a trasmettere le buone caratteristiche delle soluzioni genitori nelle successive generazioni.

Lo schema generale di un algoritmo genetico è il seguente:

 

1. Codifica delle soluzioni dello specifico problema
2. Creazione di un insieme iniziale di soluzioni (popolazione iniziale)
3. Calcola la funzione di fitness
4. Ripeti, fino alla soddisfazione di un criterio di arresto:
   - seleziona coppie (o gruppi) di soluzioni (selezione parentale)
   - ricombina i genitori generando nuove soluzioni (offsprings)
   - valuta la fitness delle nuove soluzioni
   - rinnova la popolazione, utilizzando nuove soluzioni
5. Restituisci la migliore soluzione generata

 

La soluzione migliore è quindi quella che massimizza la funzione di fitness. Tali algoritmi potrebbero sembrare di stampo essenzialmente accademico ma in realtà esistono una moltitudine di problemi che possono essere risolti con questa metodologia. L'ambito tecnologico dove questi progressi sono più visibili è il campo dei videogiochi, in cui l'utente sempre più spesso ha a che fare con personaggi che evolvono autonomamente all'interno del loro mondo. In altri casi l'evoluzione in ambienti virtuali viene usata per risolvere problemi reali ed estremamente attuali.

 

Nello specifico il campo di applicazione di questi algoritmi può rientrare in uno dei successivi domini:

• Pianificazione: include tutti quei problemi in cui si richiede di scegliere il miglior modo alternativo di impiegare un insieme finito di risorse, come ad esempio la pianificazione di rotta di una flotta dei veicoli, la pianificazione della traiettoria di un robot, la pianificazione della produzione di un impianto industriale, ecc.
• Progettazione: include quei problemi in cui si richiede di determinare una disposizione ottimale di elementi (componenti elettroniche o meccaniche, elementi architettonici) al fine di soddisfare una serie di requisiti funzionali, estetici e di robustezza.
• Simulazione e identificazione: al fine di determinare come un determinato sistema si comporterà. I sistemi studiati possono essere chimici (determinazione della struttura tridimensionale di una proteina, dell’equilibrio di una reazione), economici (simulazione delle dinamiche della concorrenza in un’economia di mercato), medici e così via.
• Controllo: che include tutti quei problemi in cui è richiesto di stabilire una strategia di controllo per un dato sistema;
• Apprendimento automatico e data mining: nei casi in cui a partire da un insieme di osservazioni, si richiede di costruire un modello del fenomeno sottostante, spesso da utilizzare per scopi di previsione.