Ricerca tra la vecchia roba

Genetic Programming

Posted: Gennaio 11th, 2010 | Author: | Filed under: Ci, genetica, Programmazione | 2 Comments »

Succede che giri per la rete e vedi una cosa figa, succede che senti il bisogno impellente di riuscire a farlo anche tu (non sto parlando di fare un figlio con jessica alba) e quindi ti prodighi nel compiere il tuo destino.

Orbene, ho visto questo post in cui l’autore utilizzando algoritmi genetici riesce a riprodurre un disegno della monna lisa usando solo poligoni; non ho guardato il suo codice ma mi pare di aver capito che lo ha fatto in .NET, io l’ho scritto direttamente in C, con interfaccia creata tramite librerie cairo (in realtà uso una mia libreria che infatti va compilata a parte).

I risultati sono incoraggianti, anche se nel link originale lui pare avere dei risultati migliori (e forse più veloci); per capirci dopo una decina di ore di simulazione ho ottenuto un risultato che si può riassumere in questa immagine qua sotto


Ogni 500 mutazioni positive

 La prima immagine è quella usata come modello iniziale, le altre rappresentano il risultato ogni 500 mutazioni positive (l’immagine completa dove sono presenti le immagini ogni 100 mutazioni è questa). 

Per capirci, l’algoritmo è il seguente

  1. Inizializzo l’ambiente (rappresentato dall’immagine) e il pool genetico (rappresentato da delle strutture dati che rappresentano un tot di poligoni con un altro tot di vertici ed un determinato colore); il pool genetico è inizializzato casualmente.
  2. eseguo una mutazione casuale che può interessare la posizione relativa fra due poligoni, la posizione assoluta di un vertice di un dato poligono o infine il colore di un poligono.
  3. calcolo una specie di norma che deve darmi il valore di fitness della generazione ottenuta dalla mutazione rispetto all’ambiente (cioé nello spazio dei colori mi dice quanto si discosta l’immagine ottenuta coi poligoni da quella reale).
  4. confronto il valore della fitness di questa generazione con quella precedente, se è minore sopravvive altrimenti muore e viene usata quella precedente.
  5. torno al passo 2.

Se qualcuno vuole provare codesto codice qui di seguito le istruzioni per scaricarlo e compilarlo: usando git
$ git clone git://gitorious.org/tricks/mainline.git Tricks
$ git clone git://gitorious.org/cairo-routine/mainline.git Cairo

$ git clone git://gitorious.org/x11-routines/mainline.git X11
$ cd X11 && make x11-routine
$ cd ..
$ cd Tricks && make genetic
(si potrebbe fare direttamente make, ma ci sono altri sotto repository da abilitare, se avete voglia potete trovare tutti i miei esperimenti alla mia pagina di gitorious non deridendomi per il mio inglese ;-)).

A questo punto, dopo aver sproloquiato, vi chiederete: cosa centri tutto questo con la genetica? certo ho utilizzato termini che fanno intendere quello specifico ambito: "pool genetico", "ambiente", "generazione", "mutazione" ma i più maliziosi avranno subito pensato "hei, qui non c’è un vero ambiente bla bla bla"… beh non è proprio vero. In pratica l’ambiente, in questo universo artificiale in qui gira il programma, è rappresentato dall’immagine e dalla sua rappresentazione in pixel. Possiamo pensare all’insieme dei poligoni come ad un essere vivente che lotta contro la sua generazione successiva e perdere il confronto se il suo successore si adatta meglio all’ambiente, cioè riesce a riprodurre più fedelmente l’immagine.
 
In fondo non è diverso da quello che succede nel mondo reale, nella reale competizione per la sopravvivenza, se non che la funzione di fitness non è semplicemente il confronto con un modello ma un vero e proprio tournament contro la natura stessa. È possibile trovare una vera e propria analogia con quanto mostrato da questo programma usando gli studi di anatomia comparata (non sono sicuramente un biologo ma sin da bambino nutrivo una passione smodata per la biologia evolutiva): prendete lo schema del cuore delle classi dei vertebrati e confrontateli
  • Pesci: hanno un cuore con solo due camere (un atrio ed un ventricolo)
  • Anfibi: hanno un cuore con tre camere (due atrii ed un ventricolo)
  • Rettili: hanno 4 camere (due atrii e due ventricoli) ma nella maggioranza delle specie i ventricoli non sono separati completamente
  • Mammiferi ed uccelli: hanno quattro camere completamente indipendenti che isolano completamente la circolazione corporea da quella polmonare.

(purtroppo, pur cercando da tutte le parti, non ho trovato rappresentazioni grafiche e non sono abbastanza bravo a disegnare). Non vi sembra uno schema di "raffinazione" di un modello iniziale per espletare al meglio una certa funzione? sicuramente è ovvio che non esiste un "cuore ultimo" da raggiungere nell’evoluzione, ma una raffinazione sempre più complessa. Esempi da fare ce ne sarebbero a dozzine ma non vorrei urtare la sensibilità di qualche creazionista.

 
 P.S: se qualcuno ha qualche idea su come organizzare meglio la mutazione nell’algoritmo o l’algoritmo stesso non esiti a suggerire; del tipo che magari al posto di buttarli tutti nella mischia, si fa partire un poligono solitario in un punto a caso e lo si fa riprodurre solo se il colore corrisponde con quello dell’immagine; il figlio erediterà il colore ed eventualmente muterà… sicuramente così dovrebbe diminuire il tempo della simulazione… penso che le possibilità sono molte…
P.P.S: c’è un piccolo baco nello storage del valore della fitness, in quanto essendo un valore unsigned int ha un limite che viene superato da immagini troppo grosse (con 200×200 funge). Prossimamente lo dovrei mettere a posto.

2 Comments on “Genetic Programming”

  1. 1 Giovanni Battista Tateo said at 10:57 am on Aprile 26th, 2011:

    Ciao sembra proprio che tu abbia usato solo uno dei meccanismi fondamentali, ossia la mutazione. Penso che usando anche il crossing tra i migliori elementi del pool genetico la convergenza sarebbe stata piu’ veloce.
    Poi credo che questo possa essere catalogato come esempio di Genetic Algorithms, piuttosto che di Genetic Programming. Cosa ne dici?

    Comunque sia una applicazione veramente interessante.
    Cordiali saluti,
    Battista.

  2. 2 packz said at 8:23 pm on Giugno 23rd, 2011:

    ciao, certo sarebbe interessante eseguire il crossing, il problema è come effettuarlo: gli individui si adattano per vivere in certe zone a causa della loro dimensione e colore, un loro figlio potrebbe sicuramente migliorare la fitness ma solo essendo vincolato a stare dove c’è già il padre… tu hai qualche idea in proposito?