Algoritmi genetici

VIII parte: Le applicazioni pratichedi

Ci avviamo alla conclusione di questa lunga serie. Abbiamo visto nei dettagli gli aspetti teorici fondamentali relativi agli algoritmi genetici, analizzandone i principi, il legame con i modelli derivati dalle scienze naturali, le varianti e le procedure operative delle fasi di setup. Prima di presentare un esempio pratico Java, vediamo in questa parte a cosa servono gli algoritmi genetici.

Introduzione

Proprio in base alla particolare flessibilità che li caratterizza e che li contraddistingue da altri algoritmi, gli algoritmi genetici possono trovare molte applicazioni: alcune di queste applicazioni sono state già sperimentate nella pratica, altre invece sono ancora argomento di ricerca.
La maggior parte delle ricerche condotte sugli algoritmi genetici si sono concentrate sul trovare regole empiriche per farli funzionare in maniera ottimale. Non c'è una teoria generale che spieghi esattamene perchè un algoritmo genetico abbia determinate proprietà, ma sono state avanzate alcune ipotesi che possono parzialmente spiegarne il successo ed essere tenute in considerazione per implementare un buon algoritmo.
Il fatto che gli algoritmi genetici siano per loro natura adattivi e flessibili, e allo stesso tempo robusti, ha permesso il loro utilizzo in campi diversi: uno dei principali è naturalmente quello dell'ottimizzazione di funzioni numeriche complicate. In questo caso la fitness è ben definita perchè è proprio la funzione stessa, e in molti casi gli algoritmi genetici si sono dimostrati più efficaci di altre tecniche, come ad esempio quella del gradiente, perchè la continua rimescolanza dei geni mediante crossover e mutazione impedisce che si fermi su un massimo, o un minimo, locale.
Di seguito presentiamo una serie di aree di applicazione su cui si sono concentrati gli sforzi degli studiosi o che hanno fornito buoni risultati.

Ottimizzazione di funzioni numeriche

Molti ricercatori hanno concentrato i loro sforzi in questo settore. Gli algoritmi genetici si sono rivelati essere in grado di superare tecniche convenzionali di ottimizzazione su funzioni complicate, discontinue e disturbate.

Image Processing

Nel campo dell'elaborazione delle immagini uno dei problemi affrontati è quello di allineare le immagini da satellite di una stessa zona prese in tempi diversi.
Con immagini mediche a raggi X o con immagini satellitari, c'è spesso bisogno di allineare due immagini della stessa area, prese in istanti diversi. Comparando un campione casuale di punti nelle due immagini, un algoritmo genetico può efficacemente trovare un insieme di equazioni per adattare una immagine dentro l'altra.
Un ulteriore inusuale problema di image processing è quello di creare immagini di sospetti criminali, ossia di assistere nella creazione di identikit. L'algoritmo genetico rimpiazza il compito del tradizionale sistema photo-fit, ma usa uno schema di codifica simile: l'algoritmo genera un numero casuale di facce e il testimone seleziona le due che sono più simili a quella del sospetto. Poi queste due sono usate per creare altre facce nella generazione successiva. Il testimone, con la sua scelta, agisce come la "funzione fitness" dell'algoritmo genetico e controlla la convergenza verso l'immagine corretta, ossia quella mggiormente somigliante alla faccia del ricercato.

Ottimizzazione combinatoria

Richiede soluzioni a problemi che riguardano la disposizione di oggetti. Questo scopo è molto diverso dalle funzioni di ottimizzazione, e vengono richieste diverse tecniche di codifica e ricombinazione.
Un tipico esempio è rappresentato dal cosiddetto "problema del commesso viaggiatore", Travelling Salesman Problem (TSP) (data una serie di città interconesse da varie strade, qual è il percorso migliore, di minore distanza, che un commesso viaggiatore dovrà seguire per andare in tutte le città una e una sola volta?). In questi casi la funzione di fitness è ben definita ma, per il fatto che le soluzioni sono sequenze di interi, gli algoritmi genetici usati necessitano di sistemi di codifica e tecniche di crossover leggermente differenti da quelle usate comunemente.

Bin packing

Si occupa di determinare come disporre un certo numero di oggetti su uno spazio limitato; ha molte applicazioni pratiche nell'industria ed è stato largamente studiato. Un particolare esempio è il layout di un circuito integrato VLSI. Strettamente collegato è il job shop scheduling, o time-tabling, dove il problema è allocare un insieme di risorse (macchine, uomini, stanze) per portare a termine un insieme di compiti, come la manifattura di un dato numero di componenti. Ci sono ovvi limiti: per esempio la stessa macchina non può essere usata per fare due compiti diversi nello stesso tempo. L'"ottima allocazione" è quella che permette di finire il lavoro nel minor tempo possibile, o nel minimo tempo di inattività per ogni risorsa.

Progettazione di lavori

Progettare lavori può essere un mix di ottimizzazione combinatoria e ottimizzazione di funzioni. Un algoritmo genetico può spesso provare cose che un progettista umano non avrebbe mai pensato (gli algoritmi non hanno paura di sperimentare...) e sulle quali non ha preconcetti. Il progetto degli algoritmi genetici può essere ibridizzato con tecniche più tradizionali di ottimizzazione, oppure con sistemi esperti, per produrre un range di progetti che un ingegnere umano può poi valutare.

Machine Learning

Ci sono molte applicazioni degli algoritmi genetici per i sistemi di apprendimento; il modello usuale è quello del sistema classificatore. L'algoritmo genetico prova a evolvere (cioè a imparare) un set di se ... allora per operare in alcune particolari situazioni. Questo è stato applicato ai giochi e per risolvere labirinti e anche per modelli economici e politici.
Un uso maggiore delle tecniche del machine learning è stato fatto nel campo del controllo. In un grande sistema complesso, come una centrale chimica, ci sono molti parametri di controllo da essere aggiustati perchè il sistema continui a produrre in maniera ottimale. Generalmente, si usa l'approccio del sistema classificatore, in modo da elaborare le regole per controllare il sistema. Il fitness di un insieme di regole può essere valutato giudicando le performance del sistema reale, oppure di un modello costruito su un computer. Fogarty ha usato il primo metodo per elaborare regole per controllare il rapporto ottimale gas/aria in una fornace. Goldberg ha modellato una rete del gas per determinare una serie di regole per controllare sistemi di compressione e trovare perdite. Davis e Coombs hanno usato un approccio simile per progettare i collegamenti di una rete di telecomunicazione.

Conclusioni

Come si è potuto vedere da questo rapida carrellata, gli algoritmi genetici, o una loro combinazione con altri modelli computazionali, ben si prestano a fornire soluzioni a problemi pratici del mondo della conoscenza e della produzione industriale. Nel prossimo articolo, a mo' di esempio, vedremo una semplice implementazione Java di un algoritmo.

Riferimenti

[1] D.B. Fogel, "Evolutionary computation: toward a new philosophy of machine intelligence", IEEE Press, NewYork, 1995, ISBN 078035379X

[2] J.R Koza, "Genetic programming: on the programming of computers by means of natural selection", MIT Press, Cambridge, MA, 1992 ISBN 0262111705

[3] Alden H. Wright, "Genetic Algorithms for Real Parameter Optimization", 1991

 

 

 

Condividi

Pubblicato nel numero
137 febbraio 2009
Luana Rinaldi è nata a Napoli nel 1980. Si è laureata in Ingegneria Informatica presso l‘Università degli studi di Roma Tre, portando avanti una tesi di ricerca in bioinformatica. Dal 2000 si occupa professionalmente di analisi, progettazione e sviluppo di applicazioni in linguaggio Java con una particolare attenzione alle tecnologie…
Articoli nella stessa serie
Ti potrebbe interessare anche