Algoritmi genetici
Gli Algoritmi Genetici (AG) sono procedure complesse adattative finalizzate alla risoluzione di problemi di ricerca e ottimizzazione e basate concettualmente sui principi che regolano l'evoluzione naturale delle specie. Il problema che si propongono di risolvere è quindi sostanzialmente quello di cercare il punto di massimo di una certa funzione; ciò di solito non presenta particolari complicazioni nel caso questa funzione sia esplicitamente nota, ma quando questo non avviene o quando la funzione è troppo complessa per essere velocemente massimizzata con tecniche analitiche si potrebbe pensare di muoversi a caso nello spazio delle variabili fino ad esplorarlo completamente , ma ciò darebbe luogo come si può facilmente immaginare ad una procedura lunga e dispendiosa. L'idea che sta alla base degli AG è quindi quella di selezionare le soluzioni migliori e di ricombinarle in qualche modo fra loro in maniera tale che esse evolvano verso un punto di ottimo. Nel linguaggio degli AG la funzione da massimizzare prende il nome di fitness. Non esiste un termine italiano che riesca a rendere la varietà di significati espressi da quello inglese: a seconda del contesto può significare "adattamento", "adattabilità", "successo biologico", "idoneità", "competitività". Si preferisce quindi usare il termine inglese ormai largamente diffuso. Si supponga che la funzione di fitness dipenda da n variabili: F = f (x1, x2,…, xn) che di solito possono prendere valori all'interno di determinati intervalli numerici (x1, x2,…, xn appartengono a Xn ) Un set di n valori x1, x2,…, xn con le caratteristiche sopra indicate sarà allora una possibile soluzione. Come qualsiasi genere di informazione essa può essere codificata ed espressa biunivocamente in codice binario: questa idea fu introdotta originariamente da J.Holland, il padre degli AG. Una soluzione potrà quindi essere rappresentata mediante una successione (detta stringa) di 0 e 1, ad es. 100110101001110. Questo sistema di rappresentazione è particolarmente indicato quando si tratterà di "ricombinare" fra loro le diverse soluzioni, anche se non è l'unico come si vedrà in seguito. Un insieme di soluzioni forma una popolazione. Una popolazione di m individui sarà quindi un insieme di m stringhe binarie a ciascuna delle quali è associato un valore di fitness. Continuando con l'analogia genetica, la specifica sequenza di 0 e 1 che costituiscono un individuo (soluzione) è detta cromosoma. In natura gli individui si riproducono mescolando in questo modo i propri patrimoni genetici, cioè i loro cromosomi: i nuovi individui generati avranno pertanto un patrimonio genetico derivato in parte dal padre e in parte dalla madre. La selezione naturale fa sì che riescano a sopravvivere e quindi a riprodursi solo gli individui più forti, "più adatti", cioè quelli con la fitness più elevata; la fitness media della popolazione tenderà quindi ad aumentare con le generazioni, portando così la specie ad evolversi nel tempo.
Molto raramente può avvenire che un individuo possegga una nuova caratteristica che non era presente in nessuno dei genitori: si parla in questo caso di mutazione genetica. Se essa ha dato origine ad un vantaggio competitivo per l'individuo è probabile che questo si riproduca e tramandi alle generazioni successive questa nuova caratteristica, viceversa essa rimarrà un caso isolato e scomparirà in breve tempo. In maniera analoga gli AG generano una popolazione iniziale (ad esempio in modo casuale), selezionano da questa un certo numero di individui e li ricombinano fra loro in modo da dar vita ad una nuova generazione e così via finché la fitness media della specie non converge al valore dell'individuo migliore.
Di seguito verrà spiegato come questo sia realizzabile praticamente. Si supponga come in precedenza che la funzione di fitness dipenda da n parametri o variabili: queste vengono chiamate geni. L'insieme dei geni rappresentati d una stringa costituisce il genotipo. L'individuo ad esso corrispondente è detto fenotipo.Nella rappresentazione binaria si assuma che ogni gene sia rappresentabile con un certo numero p di bit. Una soluzione, cioè un individuo della specie, sarà pertanto rappresentato da una stringa di n*p cifre binarie alla quale è associato un valore di fitness. Le probabilità che un individuo si riproduca, cioè che venga estratto dalla popolazione per essere ricombinato con un altro sono proporzionali al suo valore di fitness.Una volta selezionati due individui i loro cromosomi vengono mischiati usando due tecniche, quella del crossover (CO) e quella della mutazione. La più semplice tecnica di crossover è quella detta one point: date due stringhe viene individuato un punto che separa ciascuna di esse in due parti, una testa e una coda. primo dei due nuovi individui generati è formato dalla testa del padre + la coda della madre, il secondo dalla coda del padre + la testa della madre. (vedi figura)
La probabilità che si verifichi il cross over è in genere abbastanza alta, ma può essere minore di 1. Quando non si verifica i figli saranno la copia esatta dei genitori. Un'altra tecnica molto utilizzata è quella del two points crossover: in questo caso gli individui non sono rappresentati come stringhe lineari ma come circoli, per cui si può sostituire una porzione di circolo di un individuo con quella di un altro selezionando due punti di cross over. Se le porzioni da sostituire sono più di due, ad esempio n, si dovranno determinare 2n punti di taglio(tale tecnica è quindi detta multi point).
Una terza tecnica ampiamente implementata è quella del cross over uniforme: per ogni coppia di genitori si genera una stringa binaria della stessa lunghezza chiamata maschera. Il figlio viene generato copiando il bit del padre o quello della madre a seconda che nella corrispondente posizione nella maschera vi sia uno 0 od un 1.
Queste tre sono le tecniche più utilizzate, ma molte altre ne sono state suggerite e il dibattito sul quale sia la migliore è aperto. Con ogni probabilità non ne esiste una in senso assoluto, ma la più adatta è diversa a seconda del tipo di problema da risolvere.
La mutazione consiste invece nel cambiare ciascun bit di una stringa con una certa probabilità, tipicamente molto bassa. Così come in natura, questo fenomeno aggiunge un "rumore" o una certa casualità all'intera procedura, assicurando al contempo che partendo da una popolazione generata casualmente non vi siano punti dello spazio delle soluzioni che abbiano probabilità nulla di essere esplorati. Essa avviene sugli individui della nuova generazione dopo il cross over.
I parametri principali che caratterizzano un algoritmo genetico sono quindi la probabilità di crossover e la probabilità di mutazione, oltre che la numerosità della popolazione iniziale. A priori è difficile stimare quali valori daranno le migliori performance, e l'esperienza mostra che vi è una forte dipendenza dal tipo di problema. Tipicamente però la probabilità di crossover è grande, dell'ordine del 60-80%, mentre quella di mutazione oscilla in genere fra 0,1 -1% Dal momento che la probabilità che un individuo venga selezionato per la riproduzione sono proporzionali alla sua fitness (ad esempio se f è il valore di fitness di una soluzione e F la somma dei valori di fitness di tutta la popolazione, la probabilità potrebbe essere f/F) è molto probabile che gli individui migliori vengano scelti e ricombinati, e che quindi il cromosoma migliore venga perduto. Per evitare ciò e accelerare la convergenza conviene spesso far si che l'individuo migliore di una generazione venga copiato e passi alla successiva senza subire modifiche. Tale tecnica è detta elitismo, e se le popolazioni sono abbastanza numerose può essere estesa a più di un individuo, imponendo cioè che i migliori n individui vengano clonati nella generazione successiva mentre per gli altri si procede nella solita maniera.
Gli algoritmi genetici fanno parte del più generale ambito degli ALGORITMI EVOLUTIVI: questo è un termine generico che comprende al suo interno una gamma di sistemi di risoluzione dei problemi basati sull'utilizzo del calcolatore che hanno affinità con i processi evolutivi. Essi comprendono oltre agli AG la Programmazione Evolutiva, le Strategie Evolutive, i Sistemi Classificatori e la Programmazione Genetica.
La programmazione evolutiva (evolutionary programming, EP) è una strategia stocastica di ottimizzazione che ha molte aspetti in comune con gli AG: definizione della popolazione, fitness, selezione dei migliori. A differenza di questi ultimi però non fa uso del crossover ma solo della mutazione, e questo ha come conseguenza il fatto che non si pone il problema di come codificare le soluzioni, che possono essere quindi rappresentate così come sono. Inoltre la probabilità di mutazione decresce man mano che ci si avvicina all'ottimo.
Le strategie evolutive sono tecniche simili a quella illustrata precedentemente, ma sviluppate originariamente per problemi di ingegneria civile e strutturale. La principale differenza consistono nel fatto che nella EP gli individui vengono selezionati per la mutazione con una certa probabilità proporzionale alla fitness come accade negli AG, mentre qui gli individui peggiori vengono scartati deterministicamente.
I sistemi classificatori sono operatori che lavorano in un determinato ambiente, dal quale ricevono degli imput che classificano secondo una serie di regole o e dai quali generano degli output o di istruzioni da seguire. Le istruzioni sono rappresentate da una serie di if….then. Ad esempio il problema potrebbe essere quello di ottimizzare un certo processo produttivo svolto da un macchinario regolato da un computer. Questo attraverso dei sensori riceve una serie di input come la temperatura del macchinario, o la pressione esterna, il tipo di materia prima ecc e agisce in accordo col set di regole di partenza : SE misuri certi parametri…ALLORA fai questo. Tali istruzioni non sono fisse ma se vengono codificate ad esempio in forma binaria possono evolvere come popolazioni di un AG, e la loro fitness è data dalla performance del macchinario. § La programmazione genetica è un'applicazione informatica degli AG, solo che in questo caso le soluzioni non sono stringhe binarie ma veri e propri programmi, che si usa rappresentare come alberi del tipo in figura che rappresenta il comando X+2Y Il crossover è effettuato scambiando porzioni di albero fra due individui e la mutazione non è utilizzata
Il fatto che gli Algoritmi Genetici siano per loro natura molto 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 AG si sono dimostrati più efficaci di altre tecniche come ad esempio quella del gradiente, perché la continua rimescolanza dei geni mediante cross over e mutazione impedisce che ci si fermi su un massimo (o minimo) locale.
Nella situazione in figura ad esempio procedendo con la tecnica del gradiente, partendo dal punto X ci si sposterebbe fino a B, dove la ricerca terminerebbe perché è un punto di massimo, e i punti A e C , a fitness più elevata, non verrebbero individuati.
Image processing: in questo caso il problema è quello di allineare immagini (a raggi X, da satellite ecc.) di una stessa zona prese in tempi diversi, e a tal scopo gli AG trovano un sistema di equazioni per far corrispondere ai punti della prima quelli della seconda in modo da poterli integrare in un'unica immagine. Un'altra applicazione di questo tipo è la creazione di identikit di persone sospette a partire dalla descrizione di un testimone: vengono generate all'inizio delle facce casuali, e quelle più somiglianti vengono ricombinate fra loro fino ad ottenere una descrizione il più possibile coincidente. In questo caso la funzione di fitness non è così ben definita come in precedenza perché naturalmente non ne esiste una forma "analitica", ma è il testimone stesso che seleziona i tratti somatici più somiglianti ( forma del naso, colore degli occhi e così via) e scarta gli altri , cioè fa si che i geni migliori sopravvivano e compaiano nelle generazioni future.
Ottimizzazione combinatoria: riguarda problemi in cui bisogna trovare la disposizione sequenziale ottima di una seria di oggetti. E' questo il caso del problema del commesso viaggiatore (TSP) descritto più avanti. In questi casi la funzione di fitness è ben definita ma per il fatto che le soluzioni sono sequenze di interi gli AG usati necessitano di sistemi di codifica e tecniche di cross over leggermente diverse da quelle più usate.
Bin Packing: sono problemi riguardanti la disposizione ottima di oggetti in uno spazio limitato. Questo aspetto è particolarmente importante nel campo industriale, per l'imballaggio e lo stoccaggio della merce, al fine di minimizzare lo spazio inutilizzato. Correlati a questi vi sono i problemi di allocazione ottima di risorse limitate per la massimizzazione del rendimento o la produzione.
Machine learning: nel campo dell'intelligenza artificiale gli AG sono spesso usati per istruire le macchine in determinati problemi. Il metodo usato è quello dei sistemi classificatori(vedi in descrizione del metodo): la macchina, il cui compito è quello di gestire in maniera ottimale un determinato sistema, riceve una serie di istruzioni del tipo if…then , li testa sul sistema in esame e a seconda delle performance misurate (che rappresentano pertanto la fitness dell'insieme di regole adottato), decide se tale sistema è appropriato o meno. Un tipico esempio è la gestione di processi chimici complessi, in cui vengono monitorati costantemente alcuni parametri ,che costituiscono i dati di input, dall'analisi dei quali la macchina fornisce delle indicazioni per mantenere il sistema nelle condizioni più efficienti.
Una serie di istruzioni di questo tipo potrebbe essere del genere
se temperatura > 100 gradi …allora diminuire pressione
se [reagente 1] < C….allora aggiungere reagente 2
Bibliografia
J.H.Holland. Algoritmi genetici. Le Scienze, n.289, 1992
L.Davis. Handbook of Genetic Algorithms. Van Nostrand Reinhold, 1991
SITI IN ITALIANO
www.forumteorema.com Contieni riferimenti matematici e filosofici sugli AG e l'Intelligenza Artificiale in genere
http://www.investireonline.org/genetici.html Contiene una spiegazione teorica sugli AG in generale, e una loro applicazione al campo dell'analisi finanziaria
http://www.dia.uniroma3.it/~patrigna/seminari/learning/ Una raccolta di lucidi sull'apprendimento delle macchine tramite AG
SITI IN INGLESE
http://cs.felk.cvut.cz/~xobitko/ga/ Contiene diverse applet in java con esempi di funzioni in 2D e 3D e TSP risolte con gli AG
www.geocities.com/CapeCanaveral/Lab/5337/ Sito di un ricercatore italiano che contiene numerosi link
www.aic.nrl.navy.mil/galist/ Contiene una ricca raccolta di codici sorgenti in C, C++, fortran ,VB ecc. di programmi che implementano AG, nonchè una lista di link
www.umoncton.ca Da qui è possibile scaricare un'applicazione gratuita che implementa un AG con le macro di Excel
www.aridolan.com/ oltre che sugli AG,contiene interessanti riferimenti sulla vita artificiale in genere
 |
 |
 |
