Algoritmi genetici: che cosa sono

Gli algoritmi genetici sono una famiglia di modelli computazionali ispirati alle teorie darwiniane dell’evoluzione. Definiti così, probabilmente non vi diranno nulla, per cui procederemo con una spiegazione più semplice (spero) di cosa siano gli algoritmi genetici e di quale sia il loro utilizzo. Tanto per cominciare, gli algoritmi genetici sono utilizzati dai computer su altri programmi, per cui nessun essere vivente ne subisce danni e non hanno nulla in comune con l’ingegneria genetica. Sono invece una tecnica per trovare soluzioni a particolari problemi che, usando altri algoritmi più tradizionali, sarebbero di difficile soluzione. In particolare, gli algoritmi genetici sono molto usati nel campo dell’intelligenza artificiale. Ma cos’è un algoritmi genetico e perché è genetico? Adesso ci arriviamo. Un algoritmo è un sistema di calcolo che serve a dare una risposta a un determinato problema. Un esempio di algoritmo che conoscete molto bene e che probabilmente usate molto spesso è quello che permette di scoprire la strada più breve tra un punto A e un punto B (pensate a Google Map o a un qualsiasi navigatore). In questo caso, l’algoritmo di ricerca registra il punto di partenza, il punto di arrivo e “prova” le varie strade che congiungono i due punti, fino ad aver trovato la strada ottimale. Allo stesso modo, un algoritmo può risolvere problemi di altra natura, tentando varie soluzioni fino a che non ha trovato quella migliore. Un algoritmo genetico cerca di ottimizzare e migliorare questa ricerca, utilizzando una soluzione ispirata alla biologia e all’evoluzione. Come in natura sopravvivono e si moltiplicano gli esemplari più adatti al loro ambiente, così in un algoritmo genetico sono le soluzioni più adatte a essere portate avanti, fino a che non si arriva alla soluzione ottimale per il problema. Quando si trova di fronte a un problema, un algoritmo genetico produce una prima “generazione” di possibili soluzioni al problema, composte in maniera puramente casuale. Dopo averle prodotte, le valuta sulla base del risultato a cui si deve arrivare: chi ci è andato più vicino, avrà maggiori probabilità di sopravvivere e riprodursi, tramandando alla prossima generazione il proprio patrimonio genetico. Di generazione in generazione, dunque, la popolazione dovrebbe arrivare sempre più vicina alla soluzione ottimale del problema, fino a trovare la risposta (che in questo caso non è necessariamente 42). Un algoritmo genetico produce dunque una popolazione virtuale, il cui scopo nella vita è trovare la soluzione a un problema. Grazie al meccanismo di selezione dei migliori, ogni generazione ottiene risultati migliori rispetto alla precedente, fino ad arrivare a un punto dove non è più possibile migliorarsi: quella sarà la soluzione ottimale. Entriamo più nello specifico. Il problema iniziale è scomposto in una serie di piccoli elementi, ognuno dei quali rappresenta un possibile frammento della soluzione: questi elementi sono chiamati geni. Una sequenza di geni rappresenta una possibile soluzione ed è chiamata genoma. Ogni genoma è contenuto in un cromosoma, che è un “individuo” della popolazione. Un algoritmo genetico crea dunque una popolazione di cromosomi, combinando in modo casuale i geni di cui dispone. Dopo averli creati, esamina il genoma dei vari cromosomi e guarda quanto questo genoma sia vicino alla soluzione che deve trovare: più il genoma è vicino e più alte saranno le probabilità che quel cromosoma si possa riprodurre. La riproduzione consiste nel selezionare due cromosomi, prelevare da ognuno una parte del suo genoma e unirlo, per creare un nuovo cromosoma, che sarà composto in parti più o meno uguali dal genoma dei due genitori. Di tanto in tanto, a questa fase può essere applicata una mutazione, che consiste spesso nell’invertire la posizione di due geni all’interno del genoma: un processo che vuole imitare quanto accade in natura e che serve a introdurre una novità, per evitare che a ripetersi siano sempre gli stessi modelli. Dopo aver prodotto in questo modo una nuova generazione di cromosomi, si riparte col processo di valutazione e riproduzione. Tutto ciò può sembrare molto dispendioso e lungo, ma in realtà un algoritmo genetico di solito ottiene risultati in tempi molto più brevi, rispetto a un algoritmo di altro tipo. Inoltre, può trovare soluzioni anche a quei problemi che sarebbe difficile sottoporre ad algoritmi più tradizionali. Un esempio classico di applicazione degli algoritmi genetici è il problema del commesso viaggiatore (in inglese Traveling Salesman Problem, abbreviato in TSP). Il problema è il seguente: un commesso viaggiatore deve visitare un certo numero di città, una dopo l’altra, e deve farlo seguendo la strada più breve, senza ripassare mai per la stessa città. Un algoritmo genetico lo risolve in questo modo. Ogni città corrisponde a un gene. Il genoma di ogni cromosoma sarà dunque formato da una sequenza diversa delle città da attraversare: un possibile itinerario, insomma, cioè una possibile soluzione. Per valutare un cromosoma, si guarderà la lunghezza totale del percorso che rappresenta, ossia la distanza che c’è tra ogni città, seguendo l’ordine in cui sono disposte nel suo genoma. Il nostro scopo è quello di trovare il percorso più breve, quindi i cromosomi con una distanza complessiva più bassa saranno i “migliori”, mentre quelli con una distanza complessiva più alta saranno i “peggiori”. I cromosomi che rappresentano un percorso più breve avranno maggiori probabilità di produrre i cromosomi della prossima generazione: in questo modo, a ogni generazione ci si dovrebbe avvicinare sempre più al traguardo ideale, ossia un cromosoma che possieda tutte le città, disposte in modo da ridurre al minimo la distanza da percorrere. La fase di riproduzione consisterà nell’unire i genomi di due cromosomi, per produrre un cromosoma che sia la sintesi dei loro percorsi, mentre la mutazione consisterà nello scambiare di posizione due città, all’interno del percorso.