Creare un Algoritmo Genetico

From UIC

Scriviamo un algoritmo genetico

Infos
Author:	active85k
Email:	active85k@hotmail.com
Website:	http://www.active85k.da.ru
Date:	16/08/2005 (dd/mm/yyyy)
Level:
Language:	Italian
Comments:

Introduzione

In questo tutorial spieghiamo come scrivere un algoritmo genetico che trova un'espressione matematica che da' come risultato un numero n prefissato. Il codice e' sviluppato in Java 1.5.

Ristrutturato il 12/04/2007 da ValerioSoft

Tools usati

• Un editor di testo (io ho usato il notepad... se avete Eclipse o qualche altro ambiente di sviluppo, meglio per voi)
• L'interprete Java v1.5 (Roarrr! :S)

URL o FTP del programma

Allegato

Essay

PRE

In rete ci sono diversi tutorial che parlano di questo tipo di algoritmi... io ne ho letti parecchi... e come tutti i tutorial che si rispettino, è bene che anche io provveda a fornire il mio di un paragrafo dedicato a una piccola introduzione. Prima di tutto è bene precisare che stiamo parlando di qualcosa che ha a che fare con l'Intelligenza Artificiale. Dalla nascita dei primi sistemi informatici, l'uomo si e' prefissato il grande traguardo di riuscire a creare un essere robotico intelligente in grado di apprendere e interagire con l'ambiente circostante. Questo tentativo ha dato origine allo studio delle reti neurali e anche alla nascita di queste procedure adattive. Il padre degli algoritmi genetici (GA) è J. Holland. La sua teoria ha gli stessi principi di quella dell'evoluzione della specie umana. Il meccanismo che utilizzeremo sara' quello di generare una popolazione di Individui che poi si evolvera' fino a quando non riuscira' a trovare una soluzione ottima per il nostro tipo di problema. Ho studiato questo tutorial con molta cura e l'obiettivo che mi sono prefissato e' quello di insegnare a capire il funzionamento di questo sistema di programmazione e ad implementarne qualche esempio dimostrativo. Il tutorial utilizza il Java come linguaggio di programmazione esemplare. La scelta non e' casuale. Il linguaggio e' noto per la sua portabilita' e a quanto ne so io, un algoritmo non cambia il suo tipo di funzionamento in funzione del sistema che lo processa. Tutto quello che vi serve e' (per adesso) un compilatore java, ovviamente il suo interprete e un pezzo di editor di testo.

POST

Benvenuti nella parte piu' noiosa di questo tutorial. E' fondamentale capire molto bene quanto scritto in questo paragrafo quindi, aprite gli occhi e iniziate a leggere come si deve. Gli Algoritmi Genetici sono delle procedure "adattive", abbastanza complesse, che hanno come scopo generale quello di risolvere problemi di ottimizzazione e ricerca, sfruttando gli stessi principi dell'evoluzione naturale delle specie. Se proprio vogliamo dirla tutta, sono un meccanismo che serve per massimizzare una funzione. Dopo questa mia affermazione, secondo qualche lettore intellettuale, e' naturale affermare che noi conosciamo gia' tecniche analitiche di massimizzazione di una funzione... ma in realta' il problema che vi sto facendo affrontare e' quello di massimizzare una funzione sconosciuta :) o magari anche solo formulata in un modo tale che una tecnica normale sarebbe dispendiosa e molto lunga. Siete quindi venuti a conoscenza del fatto che il nostro scopo e' quello di trovare un valore ottimale per una funzione semplicemente andando alla ricerca di esso. L'idea e' quello di selezionare delle soluzioni abbastanza vicine allo scopo e di ricombinarle in un certo modo tra di loro in modo tale che la soluzione ottenuta sia sempre piu' vicina al risultato rispetto alle soluzioni di partenza. Si tratta quindi di un'evoluzione.
La funzione da massimizzare prende il nome di fitness. Essa viene applicata su ciascun individuo della nostra popolazione e il suo risultato e' un numero direttamente proporzionale all'utilita' dell'individuo nel contesto (o si puo' dire anche che il valore di fitness e' direttamente proporzionale alla bravura dell'individuo). Da questo si puo' capire che gli individui migliori devono essere selezionati per l'accoppiamento secondo una legge dettata proprio dalla funzione fitness. Perche' ho detto questo? Come vi accennavo prima, un GA basa la sua ricerca della soluzione sulla base dell'accoppiamento di due soluzioni selezionate tra un gruppo di migliori. E' chiaro quindi che ogni Individuo rappresenta una possibile soluzione al nostro problema. Quando parlo di "bravura dell'individuo" mi riferisco a quanto la soluzione che esso rappresenta si avvicini a una soluzione ottimale del problema. Ogni individuo e' caratterizzato da una sequenza di geni chiamata Cromosoma. Solitamente essa e' rappresentata da una stringa binaria di bit (101000101...) che, decodificata, rappresenta una possibile soluzione al nostro problema. L'accoppiamento tra i vari individui si effettua proprio manipolando questo codice genetico (le tecniche di accoppiamento le vedremo piu' tardi). Questo processo fa evolvere la nostra popolazione fino a quando non viene individuata una soluzione.

Come vedete, la struttura generale dell'algoritmo non rappresenta niente di terrificante. Diciamo che il problema, grosso modo, e' quello di individuare un meccanismo per codificare una possibile soluzione e farla apparire come il cromosoma di un individuo. Una volta fatto questo, non ci sono piu' grossi problemi. Su uno dei tanti tutorial ho trovato un esercizio molto interessante. Io ve lo ripropongo rielabborato e soprattutto commentato in italiano (anche perche' alla quinta funzione ho rinunciato a leggere quel codice). Il problema e' quello di far fornire al programma un numero. Il programma poi si occupera' di trovare un'espressione matematica che dia come risultato il numero passato per argomento. Ad esempio noi gli diamo 70 e lui restituisce la stringa "7*5*2". Vi anticipo che il programma e' scritto forse non in modo ottimale al massimo ma certamente e' molto comprensibile (l'ho scritto apposta affinche' fosse comprensibile dopo l'esperienza passata :]). L'idea di utilizzo del programma (la classe principale si chiama ga1.java) sara' di questo tipo:

Che figata eh?
Vi garantisco che questo e' l'output del programma che mi sono preparato prima della stesura di questo documento. :D Alor... occupiamoci della procedura main cosi' ce la togliamo di mezzo:

Va bene... per questa qua non ci sono grossi problemi. Il nostro programmino java vuole un argomento nella sua linea di comando. Questo argomento e' proprio un float che poi sara' il float di input per il nostro algoritmo genetico. Gia' da come si intravede nella procedura main, l'algoritmo genetico si chiama solve, prende un int e restituisce... una stringa. Non perdiamo tempo e vediamo la struttura del nostro algoritmo genetico:

Allora ragazzi... soltanto un po' di attenzione perche' e' davvero molto semplice. Per prima cosa creo una popolazione iniziale di 20 individui completamente a caz.. ehm.. a caso. Per ogni individuo ne calcolo il fitness (ovviamente controllo se gia' a random indovino il numero :D). Una volta fatto questo, inizio a creare la prima generazione, controllando ogni fitness di ogni individuo discendente. A generazione finita, sostituisco quella nuova a quella vecchia e ripeto l'operazione per questa nuova generazione, sempre selezionando gli individui migliori per la generazione successiva. Adesso iniziamo ad analizzare i vari metodi utilizzati da questo algoritmo. La prima funzione piu' o meno interessante e' la Individuo.randomize() (che ovviamente e' statica :\). La utilizzo per generare individui a caso a partire da un numero prefissato di geni (che sono formati da 4 bit cad. - i cromosomi sono tutti della stessa lunghezza). Pero' siccome stiamo leggendo il file ga1.java, direi che e' meglio rimandare la classe Individuo a dopo e continuare con le funzioni che risiedono in ga1. Una delle istruzioni piu' importanti di questo programma e' la funzione fitness. Questa rappresenta il cuore dell'algoritmo. Come abbiamo detto prima, il valore di questa funzione e' direttamente proporzionale alla bravura dell'individuo su cui e' calcolata. Diciamo che in un algoritmo come il nostro, la bravura dell'individuo cresce insieme alla sua capacita' di avvicinarsi al numero prefissato. Quindi una funzione che viene in mente quasi immediatamente:

Non difficile. La funzione restituisce un valore piu' alto in corrispondenza di individui piu' bravi. Se l'individuo i ha azzeccato il valore n, allora ritorna 0 e abbiamo il nostro bel risultato. :D Ci siamo addentrati in questa strada, quindi continuiamo ad analizzare le funzioni che incontriamo, poi ritorniamo a leggere la funzione solve. Vediamo la' una funzione val che prende un cromosoma e restituisce un float. Il valore di ritorno di questa funzione non e' altro che la risoluzione dell'espressione matematica rappresentata da quel cromosoma. Prima di imbatterci quindi in questa funzione, spieghiamo che diamine e' 'sto cromosoma. Un cromosoma e' il codice genetico di ogni individuo e corrisponde a una possibile soluzione del nostro problema. Questo significa che, nel nostro caso, un cromosoma rappresenta una stringa contenente un'espressione matematica. Vediamo un po' di capire come ho codificato questo cromosoma. Le mie espressioni matematiche sono di questo tipo:

E' una grammatica ambigua ma l'ho usata per semplicita'. Vi spiego meglio: l'espressione matematica 4+5*2 voi la leggete 4+(5*2) perche' ovviamente il PER ha la precedenza sul PIU'. In questo programma pero' non e' cosi'. Gli operatori non hanno precedenze e vengono letti da sinistra verso destra, quindi otterremo (4+5)*2. Allora, il nostro alfabeto e' L = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *, /}. Per ognuno di questo simbolo, dobbiamo avere un corrispondente codice binario (a 4 bit di cui ne avanzano due valori). Prendiamo quindi L come se fosse un array e per ottenere il codice binario di ogni simbolo, ci basta comvertire in base 2, a 4 bit, l'indice della posizione dell'elemento stesso. In questo modo:

Molto facile anche questo. Facciamo quindi un esempio di cromosoma (l'esempio che faccio ora e' quello di un cromosoma valido.. per le eccezioni vi diro' dopo come ci comporteremo) e poi decodifichiamolo:

00101100001110100110

Puo' darsi che a prima vista non vi sembri proprio nulla ma proviamo a fare qualche giochino:

Alor: 2*3 = 6; 6+6 = 12. Allora sappiamo che se quel cromosoma si chiama c, val(c) = 12. Funziona cosi'. Siamo pronti per vedere la funzione val:

Mmmmm... un po' di riflessione. La funzione decode fa questo: decode("00101100001110100110") = "2*3+6". Pero' pensate cosa succederebbe se provassimo a calcolare il valore di un cromosoma che, decodificato, corrisponde a "**2--3**4+". Assolutamente nulla, perche' quel cromosoma NON ha senso! Per evitare questo inconveniente, ho fatto corrispondere un cromosoma valido a ogno cromosoma. Ad esempio, l'esempio sfasato che vi ho fatto io, una volta passato nella funzione validate, diventa questo: validate("**2--3**4+") = "2-3*4". Praticamente la funzione validate prende il cromosoma e, se e' sbagliato, lo corregge tirandone fuori uno sempre corretto. Una volta che abbiamo un cromosoma valido, possiamo calcolarne il risultato con cromoResult. Vediamole subito:

Ed eccovi servite anche le tre funzioni per calcolare un cromosoma. La BinToDec non ve la scrivo per due motivi:

1. perche' se non sbaglio con la parseInt e' possibile cambiare di base
2. perche', anche se il punto 1) e' falso, se non riuscite a scrivervela da soli, ESIGO che smettiate di leggere un mio tutorial sui GA!

Patti chiari... e patti scuri se no mi becco anche il razzista! Torniamo ad analizzare le altre funzioni utilizzate da solve. Prima di passare alla classe Individuo, manca solo la funzione select. Questa funzione deve selezionare un membro all'interno della popolazione e deve farlo condizionato dalla "scelta del migliore". Alor uno dei metodi mooolto utilizzati per questo genere di algoritmo e' quello della roulette. Io non ho usato quello: mi sono semplicemente limitato a scegliere, di volta in volta, l'elemento che ha il fitness migliore. Quindi diventa una cosa del genere:

Anche se non ho utilizzato il metodo della roulette, il programma funziona molto bene ugualmente. Per raggiungere numeri piu' o meno accettabili, a volte ci impiego anche 5/7 generazioni. Ovviamente questa non e' la media. Ma questi problemini ve li spiego dopo. Adess continuiamo ad analizzare i nostri metodi e prima di tutto vediamo come e' fatta la classe Individuo.

Abbiamo un costruttore molto stupido e un metodo che ritorna il cromosoma. La variabile l ci da' la lunghezza del cromosoma, espressa in geni. Visto che abbiamo deciso che un gene e' formato da 4 bit, sappiamo che un cromosoma e' formato la l*4 bit. Poi dentro questa classe ci ho messo due metodi statici: uno e' il metodo randomize che genera un individuo dal cromosoma di l geni a random. L'altro metodo e' quello che effettua il cross over tra due individui. Iniziamo con il randomize che e' davvero facile:

Una volta ricavato il numero di bit nBits = l*4 mi basta ciclare nBits volte e generare numeri a random. Se il numero generato e' pari, aggiungo uno 0 al cromosoma, altrimenti aggiungo un 1. Adesso rimane da studiare il meccanismo del crossing over che serve per far accoppiare gli individui. La nostra idea e' che da ogni accoppiamento tra due individui, ne nascano altri due. Infatti se notate dalla procedura select, dovete stare attenti anche al fatto che la popolazione iniziale deve essere composta da un numero pari di individui. Il metodo del cross over consiste nell'individuare a caso un punto di separazione all'interno del cromosoma. Questo punto viene utilizzato per dividere in due il padre e la madre che si accoppiano ottenendo, per ciascuno, una testa e una coda. Da questo accoppiamento devono nascere due individui: il primo avra' la testa del padre e la coda della madre mentre il secondo avra' la testa della madre e la coda del padre. In questo modo:

Penso che il disegno sia abbastanza chiaro. Quindi l'idea e' che la procedura di accoppiamento restituisca un array di due Individui: i figli generati dall'accoppiamento. Analizziamo subito la procedura:

No difficile. Cosa c'e' ancora da dire? Praticamente nulla! Il programma funziona. E' un programmino molto esemplare. Quando date un numero in input, non date cose terribili. Vi faccio un esempio: se date come input 31.3 e' praticamente ovvio che e' molto difficile trovare un'espressione con una divisione che generi un numero con un 3 secco nella parte decimale. Altra nota e' quella di non usare numeri moooooooolto alti, per due motivi: il primo e' perche' abbiamo 13 cromosomi compresi i segni... che dopo il validate scendono quasi sempre... poi perche' dovete solo vedere se funziona, non state sviluppando applicazioni per trenitalia.
Finalmente, fine del tutorial.
Bom!

Note finali

Se c'e' qualcuno che devo ringraziare, si tratta di Quake2.
Poi saluto il mio amico Reload85, Ntoskrnl, Leviathan, AndreaGeddon e il povero Q... tutti si dimenticano di lui nei saluti.. :( ... e' cosi' buono il Q! Il Q ha una cattiveria infernale, per quello nessuno lo saluta ;p (NdQ)

Disclaimer