Newsgroup: it.comp.ia
Titolo: Della programmazione genetica

Vorrei riprendere qui un argomento interessante che era stato postato
qualche tempo fa. La programmazione genetica va oltre infatti al semplice
utilizzo dell'algoritmo genetico, per introdurre come struttura mutante
(d'ora in poi DNA) una funzione od un programma stesso. Certo, con una
funzione la programmazione genetica lavora egregiamente: basta definire un
albero sintattico, e farlo evolvere attraverso i naturali processi di
evoluzione. L'albero e' una struttura necessaria e sufficiente che definisce
una qualsiasi funzione, da cui discende che la progettazione dell'algoritmo
di fitness che porti verso una soluzione ottima e' resa piu' semplice. La
programmazione genetica, pero', puo' riguardare interi programmi, ed in
questo ambito, forse il piu' interessante per l'IA, definire una struttura
dati come l'albero non e' altrettanto facile. Sembra improponibile usare
semplicemente un listato da modificare tramite mutazione, in quanto i
problemi da superare sono pressoche' infiniti: dalla lentezza della
convergenza (lo spazio da esplorare e' improponibilmente enorme), alla
possibilita' di errori nascosti all'interno di un programma non rilevati
dalla funzione di fitness. In che modo puo' essere risolto il dilemma?
Ciao,
     Stefano
P.S.: su questo argomento ho voglia di spendere due parole, ma prima vorrei
sapere se sto reinventando la ruota o se e' possibile dire qualcosa di
nuovo.
--
Question: If electricity comes from electrons,
does morality come from morons?

 problemi da superare sono pressoche' infiniti: dalla lentezza della
In effetti mi son trovato anchio a pensare a questo problema...(premetto che
non so una mazza riguardo alla programmazione genetica). Quello che mi e'
venuto in mente e' che forse si potrebbe ridurre parzialmente lo spazio
delle soluzioni usando un linguaggio sufficentemente povero... Se il
linguaggio di programmazione scelto e' troppo ampio (tipo c/c++, basic o
qualsiasi linguaggio comunemente usato) e' naturale che al 99,99% i
programmi "geneticamente modificati" saranno non funzionanti o non
terminanti o comunque inutili, ma se il linguaggio fosse abbastanza
ristretto (una specie di assembler) forse si potrebbe restringere la
percentuale dei programmi non funzionanti... e' solo un idea, magari sto
scoprendo l'acqua calda...
--
HariSeldon[MSS] su Starcraft
Artemis su clessidra
Roberto Previdi in r.l.
Aieie Brazo sull'autobus :-)
rpre...@dsi.unive.it

 scoprendo l'acqua calda...
Ciao,
l'argomento sulla programmazione genetica mi ha sempre interessato molto,
premetto che non ho conoscenze specifiche sull'argomento.
Tuttavia sono d'accordo con Roberto sull'idea che si debba usare
un linguaggio molto ristretto,
ma non sono riuscito a capire esattamente che tipo di programmi si possono
generare, immagino molto piccoli, che ne so'.., appunto delle funzioni.
Come faccio a capire quando uno dei "programmi" generati non è funzionante
o è da scartare?
(dico una fesseria) potrebbe darsi che il programma generato sia molto
complesso e quindi molto lento da testare, in questi casi si deve aspettare
la fine del processo o va eliminato?
Sono un po' ignorante in questo campo..,
in pratica, come faccio per testare gli algoritmi??    ;-p
E' ogni singolo algoritmo che sa quando deve evolvere
o è il programma principale?
Davide

 scoprendo l'acqua calda...
Piu' un linguaggio ristretto considero piu' opportuno un linguaggio piu' 
'rigido'. Un linguaggio funzionale secondo me meglio si adatta alle 
necessita' della programmazione genetica ( tra l'altro i primi 
esperimenti sono stati fatti il lisp ), visto che oltretutto il codice 
verrebbre rappresentato meglio da una strutture ad albero ( estendendola 
magari ad una foresta o a un grafo aciclico ). Inoltre nel caso di un 
linguaggio tipizzato staticamente si potrebbebe anche controllare che 
tagli e innesti e incroci avvengano solo tra connessioni dello stesso 
tipo ( cosi' da preservare il tipo di ritorno ), magari aggiungendo dei 
tipi particolari per rappresentare alcuni costrutti del linguaggio ( ad 
esempio l'introduzione di bindings locali ). Infine l'assenza di 
side-effects ( in particolar modo l'impossibilita' di cambiare il valore 
di una 'variabile' ) potrebbe aiutare non poco la stabilita' del codice 
risultante.
Marco

 esempio l'introduzione di bindings locali ).
Ovviamente 'staticamente tipizzato' non ha senso in questo contesto :)
Piu' corretto 'fortemente tipizzato' ( tipo ML tanto per intendersi ) 
anche se forse ripensandoci non e' poi cosi' necessario ( basta appunto 
fare i controlli )

 verrebbre rappresentato meglio da una strutture ad albero ( estendendola
ecco appunto ho scoperto l'acqua calda... A questo punto è evidente che mi
devo imparare il lisp e anche in fretta... qualcuno ha suggerimenti? buoni
tutorial, esempi per newbye ecc... Se uso il lisp di emacs va bene?


 tutorial, esempi per newbye ecc... Se uso il lisp di emacs va bene?
Per Linux c'e' l'egregio pacchetto XLISPSTAT ;)
Stefano

 o è da scartare?
E' forse il problema piu' importante della programmazione genetica, ovvero
la definizione di una "funzione di fitness" che indichi quanto e' "ben
evoluto" un determinato figlio, e se deve essergli concesso di riprodursi.
E' ovvio che la funzione di fitness, in definitiva, introduce una euristica
di ricerca che riduce l'esplosione esponenziale dello spazio delle
"soluzioni" figlie.
La parola chiave e' "euristica", che come quasi sempre significa "a muzzo"
;)
Stefano

> Piu' corretto 'fortemente tipizzato' ( tipo ML tanto per intendersi )
Secondo me un linguaggio fortemente tipizzato e' una gran sorgente di guai
per un meccanismo evolutivo del tipo che proponi !
Stefano

Raistlin wrote:

Non mi sembra che ci siano grossi problemi.
Un linguaggio fort. tipizz. finira' col rifiutare tutti quegli incroci 
che non rispettano i tipi ( ad esempio impedira  di sommare un intero ad 
una stringa per esempio ) nel momento di generare il byte-code ( per i 
linguaggi 'lazy' il discorso ovviamente e' un po' diverso ). Il mio 
dubbio era sul fatto che in fondo conviene direttamente fare gli innesti 
in punti dello stesso tipo, cosi' che si evita di generare un sacco di 
incroci inutili, che verrrebbero subito rifiutati.
Tu a che problemi pensavi ?
Marco

 
Beh, guarda che non sono il vangelo, si trattava di opinioni personali ! :)
Vanno bene anche altri linguaggi. Il problema con linguaggi tipo C e' 
come dicevate voi che e' defficile stabilire una struttura dati adatta a 
rappresentare il codice, ma non solo. Nel caso del C c'e' l'aggravante 
che devi compilare ( o provare a farlo ) per ogni porzione di codice che 
generi, e chiamare l'eseguibile risultante ( potresti pure generare dei 
moduli da 'linkare' al volo, ma non e' cosi' semplice ). Il costo di 
queste operazioni potrebbe essere rilevante e rendere il tutto piu' 
pesante che non con l'uso di un linguaggio interpretato. L'alternativa 
pseudo-assembler non e' poi cosi' male comunque: forse si potrebbero 
ottenere risultati interessanti con delle macchine virtuali, generando 
direttamente il bytecode per la JVM di Java o il CLR di C# ( tanto per 
citarne due famose ).
Marco
P.S.: personalmente odio il lisp... troppe parentesi :D

>>>"la funzione di fitness, in definitiva, introduce una euristica di ricerca"
cioe?
giusto per capirci, questo è il ciclo esecutivo dell'algoritmo di generazione degli alberi
che ho trovato su un documento:
------------------------------------------------------------------------------
(INIZIO) Generazione di alberi binari:
per ciascun albero innesta un simbolo di operazione o variabile o costante s se l'ultimo
nodo innestato contiene un simbolo d'operazione
(VALUTAZIONE) Applica agli input ciascuna delle funzioni rappresentate dagli
alberi e calcola lo scarto:  1/ E[ f(x) - target ]^2
(SELEZIONE) Sorteggia tra gli alberi valutati delle coppie e per ognuna
conserva l'albero con il valore maggiore
(RICOMBINAZIONE) scambio di porzioni tra coppie di alberi
(RIMPIAZZAMENTO) adozione dell'insieme di strutture risultato delle
ricombinazione come popolazione da avviare ad un nuovo ciclo
GOTO (valutazione)
------------------------------------------------------------------------------
Anche voi seguite questo approccio?
Il mio problema è che non ho mai capito bene cosa
si intende per "(VALUTAZIONE) Applica agli input...."
cioe?, devo applicare gli input di cosa??  forse dell'algoritmo principale?
tu sai darmi qualche spiegazione?
In questo ciclo non è presente la funzione di fitness che introduce una euristica di ricerca.
grazie
Ciao
Davide

 che non rispettano i tipi
Si', ma credo che questo andrebbe gestito DENTRO il codice in qualche modo,
e non riesco molto bene a capire come... dovrei pensarci un po' su.
Stefano

Raistlin wrote:

Penso tu abbia ragione: devo aver detto una gran boiata.
Nella mia idea originale pensavo di distinguere un pezzo di codice di un 
tipo rispetto a quello di un altro. Due 'pezzi' con tipo di ritorno 
differente sarebbero stati considerati di tipo differente ( tanto per 
capirsi il risultato sarebbe stato l'equivalente dei template del C++ ). 
Questo pero' mi impedirebbe di trattare i vari pezzi alla stessa stregua 
nel momento di trovare un punto da tagliare.
Marco

 nel momento di trovare un punto da tagliare.
Gia'... sai che piu' ci penso su e piu' mi convinco che le uniche due
alternative praticabili siano l'assembler o linguaggi funzionali alla lisp ?
Stefano

 
Un metodo applicabile in generale puo' essere quello di utilizzare una 
struttura dati intermedia: in ogni nodo dell'albero possiamo indicare in 
un campo il tipo di funzione 'primitiva'. Analogamente il tipo di 
ritorno ( cosi' come il tipo degli argomenti della funzione ) verrebbe 
rappresentato in un campo. Al momento dell'esecuzione il tutto verrebbe 
valutato da una funzione apposita ( cosi' di fatto avremmo una sorta di 
VM grossolana) oppure trasformato in codice da una funzione apposita.
Questo potrebbe anche essere implementato anche in linguaggi imperativi 
come il C. Non sarebbe difficile. Piu' altro risulterebbe noioso, per il 
fatto che per ogni tipo primitivo devi riempire una struttura dati 
iniziale ( a meno dei puntatori ai figli e realizzare una funzione 
apposita per la esecuzione/generazione del codice. E inoltre una 
funzione separata per ogni tipo di ritorno. Se vuoi posso provare a 
farti un esempio
Marco

 ha scritto nel messaggio
news:cpQP7.252951$sq5.12...@news.infostrada.it...

Era anche la mia idea. Limitare inoltre l'assembler ad un risc, peraltro, in
modo da minimizzare il numero di errori. Anzi, mi piacerebbe scoprire qual
e' il linguaggio assembler minimo per una data macchina. Scommetto che
c'entra il lambda calcolo.
Ciao,
     Stefano


 e' il linguaggio assembler minimo per una data macchina.
Per una macchina computazionalmente equivalente alla MdTuring ?
Penso read, store, add (se gestisci i numeri relativi, magari in complemento
a 2).
Teoricamente tutte le altre funzioni possono essere realizzate a partire da
queste, credo.
Stefano

 queste, credo.
Metteteci almeno il salto condizionale, per pietà. ;)))
Ciao,
  GiO che non ne può più dei Vertex Programs senza JMP ;)))

> Metteteci almeno il salto condizionale, per pietą. ;)))
Ups, svista mia, ovviamente tst, beq, e bgt :)
Stefano

Ecco un esempio abbastanza banale che mi e' venuto in mente in C++
enum value_type { INT , FLOAT , CHAR , STRING  /* etc ... */ };
enum func_type { SUM , SUB , NTH /* etc... */ }
struct node
{
   value_type result;
   func_type fun;
   vector<node*> arg;
   void* data;
};
int INTeval( node* n )
{
   switch( m->fun ) {
   case SUM: return SUMeval( n );
   case SUB: return SUBeval( n );
   /* ... */
}
int SUMeval( node* n )
{
   int x = INTeval( n->arg[0] );
   int y = INTeval( n->arg[1] );
   return x+y;
}
char NTHeval( node* n )
{
   string x = STRINGeval( n->arg[0] );
   char y = CHAReval( n->arg[1] );
   return x[y];
}
/* etc */
Tutto questo presuppone che tutti gli elementi che elaboriamo abbiamo lo 
stesso valore di ritorno alla radice, cosa comunque ragionevole se 
vogliamo confrontarli.
L'unica vera porcheria e' quel "void* data", che d'altra parte e' 
indispensabile visto che abbiamo la necessita di memorizzare ad esempio 
il valore di una costante ( che avra' un flag apposito e la cui funzione 
relativa provvedera' a fare il cast ).
Il resto non dovrebbe avere grossi problemi: l'unica cosa importante e' 
stare attenti a mantenere la "consistenza" del codice durante la 
generazione del codice iniziale e durante le mutazioni incroci.
Rispetto alla soluzione tipo assembler mi sembra che questa sia molto 
piu' adattabile al singolo problema, visto che si possono agevolmente 
creare delle funzioni specifiche, in particolare per effettuare delle 
operazioni concrete ( ad esempio, se volessi farne uno per risolvere il 
classico problema della torre di Hanoi potrei aggiungere una funzione 
che sposta dalla colonna del I' arg a quella del II' e ritorna 
vero/falso a seconda se l'esito e' possibile ),  ma anche per ridurre 
drasticamente lo spazio di ricerca: usando un assembler i "mattoni" 
costitutivi del codice potrebbero essere troppo piccoli per il compito ( 
senza contare che dovrebbero reinventare funzioni di piu' alto livello 
gia' note ). Altri vantaggi che mi vengono in mente sul momento: se le 
funzioni che fornisco sono tutte "funzionali" ( niente side-effects ) 
posso memorizzare il risultato di ogni singolo nodo: in caso di incroci 
o mutazioni dovro ricalcolare solo il risultato dei "padri" del taglio o 
dell'incrocio; Vista la semplicita' del codice un passo ulteriore 
potrebbe essere quella di fornire uno "schema" delle funzioni ( valore 
di ritorno , tipo e numero di argomenti, codice della funzione ) al 
programma che poi "sputerebbe" in out il codice condito dei necessari 
switch , case e funzioni ausiliarie per limitare il numero di errori.
Per alcuni linguaggi dotati di VM si potrebbe invece generare il codice 
eseguibile a run-time invece che il sorgente.
Ciao,
Marco
P.S. : scusate la pesantezza del post :)
P.P.S. : Non sara' forse la soluzione migliore ( non sono un esperto del 
campo ) ma mi sembra una strada piu' che percorribile

PPPS: Non so se il codice sia corretto. L'ho buttato giu in pochi minuti 
tanto per dare un'idea. Potrei pure averci messo costrutti di altri 
linguaggi senza accorgermente :D
Marco

 (d'ora in poi DNA) una funzione od un programma stesso. [...]
Ciao Stefano,
avevo introdotto l'argomento qualche tempo fa perche', come dicevo,
lo ritengo un campo di ricerca da tenere sott'occhio...
Il pioniere come sai e' John Koza e i sui libri (Genetic Progr. I, II e
III),
per non parlare dei video, rimangono IMHO delle vere perle del campo.
Oltre alle applicazioni 'serie' che avevo citato, e' incredibile, e non sono
l'unico a pensarla cosi', l'implementazione del pac-man attraverso GP...
e' un gioco, ma l'innovazione che ci sta sotto, vista da persone
'del campo' come noi, fa venire la pelle d'oca  :-)
Ok, nulla di piu' di quello che avete gia' detto....
posso solo consigliarvi di dare uno sguardo a questi:
-per chi voleva sbizzarrirsi con implementazioni C/C++/Java ecc...
http://www.frc.ri.cmu.edu/~mcm/chapt.html
http://www.cis.upenn.edu/~hollick/genetic/paper2.html
https://sourceforge.net/projects/jgprog/
- per qualche interessante applicazione:
http://www.demo.cs.brandeis.edu/pr/buildable/evocad/aid00/
http://www.demo.cs.brandeis.edu/golem/
- e ovviamente:
le conferenze GECCO (2000,2001 e pross. 2002)
http://www-illigal.ge.uiuc.edu:8080/GECCO-2002/
e
http://www.genetic-programming.org
Ciao.
--
Fabrizio
http://microservo.webhop.org
----------------------------------------------------------
 " Abbiamo preso sul serio qualcosa
     con cui ci e' permesso solo giocare
       o viceversa ? "
                              <Albert Hofmann>
----------------------------------------------------------

 queste, credo.
Si, ci sono le operazioni elementari della macchina di Turing, ma io pensavo
a qualcosa come calcolare il minimo insieme di istruzioni computazionalmente
completo su una macchina qualsiasi, strutturata in modo diverso (e.g. una
JVM). Mi pare di ricordare qualcosa sulle funzioni primitive ricorsive, ma
devo aver la voglia di tirare fuori il libro di informatica teorica.
A presto,


 creare delle funzioni specifiche,
8<
Volevo partire proprio da questo spunto per discutere i vantaggi e gli
svantaggi relativi alla programmazione genetica negli approcci
"assembler-like" e "lisp-like". E' molto probabile che non esista un
linguaggio assolutamente adatto per il compito della programmazione
genetica, e di fatto lisp ed assembler sono molto simili in quanto a
"consistenza interna" e "tagliabilita'" nell'albero del codice, ma hanno
comunque alcuni pregi e difetti. Ho iniziato a compilare una lista di
differenze.
Approcci assembler-like: la mutazione e' facile, un programma si puo'
tagliare in qualsiasi punto (l'unico punto critico puo' essere il salto
condizionale);
Approcci lisp-like: la convergenza e' rapida (piu' rapida di quella
dell'assembler, se non altro), piu' facile adattarla ai problemi (negli
approcci a-l bisogna adattare la soluzione di un problema ad un certo stato
della macchina virtuale);
a voi ulteriori aggiunte e commenti.
Ciao,
     Stefano
