Ora parliamo di un approccio leggermente differente all'algoritmo
genetico chiamato programmazione genetica che è stato sviluppato da John
negli anni '90, la programmazione genetica
invece di usare stringhe di numeri
come abbiamo fatto per il robot Robby usa programmi rappresentati come
quelli che vengono chiamati alberi sintattici. Tra un attimo vi dico meglio
Qui c'è un'immagine di una presentazione di Jon Koza sulla programmazione genetica
Egli ha scritto uno dei tre libri sul tema diventato una sottoarea
molto grande dell'algortimo genetico.
Questa l'idea: consideriamo di nuovo il problema del robot Robby
sulla strategia del controllo
Qui invece di rappresentare la sua strategia del controllo come
stringa di numeri che rappresenta le azioni
in ogni possibili situazione, qui rappresenteremo
una strategia del controllo come una sorta di albero.
Ecco fatto, ma quello che nella computer science è chiamato albero dove
abbiamo gli elementi per rappresentare il programma
in termini di questi nodi e questi e i rami
quindi questo particolare programma non segue le istruzioni "se"
"allora" "altrimenti" alla lettera e dice
se questa è l'affermazione da considerare
se c'è una lattina ad est e
il nord è vuoto allora
il robot dovrebbe muovere ad est altrimenti
il robot dovrebbe muovere a sud. Questo è quello che rappresenta l'albero e potete guardarlo
come
una specie di programma regolare: se est == lattina e nord == "vuoto", vai ad est
da solo.
Ora immaginate che Robby
sia in questa situazione e che questa sia la sua strategia, quindi quello che dovrebbe fare
dovrebbe guardare al "se", direste
c'è una lattina nel mio est e è il mio nord
vuoto, ci sono altre lattine ad est e il nord è vuoto, quindi
seguirebbe il primo ramo, muoverebbe ad est
eccoci.
E ora è in una nuova strategia quindi segue questa strategia di nuovo si domanda
c'è una lattina al mio est nel nord vuoto
no quindi seguo il secondo ramo
e di nuovo
non c'è una lattina ad est e il mio nord quindi vado a sud
quindi non c'è una strategia molto buona, questa è quella per lui, quella che segue
è un diverso tipo di rappresentazione rispetto a quanto visto prima.
Ovviamente, quest'albero è un modo molto simplice per una buona strategia
non riguardando la raccolta di alcuna lattina
Considerate una strategia più complicata che è rappresentata come
un albero più lungo. Allora è più difficile dare un senso
ma qui possiamo avere Robby a seguire questa strategia. Ok
dice se il nord è vuoto e c'è una lattina nel mio est
allora è vero, quindi seguo il primo ramo
ma ora il primo ramo ha un'altra istruzione "se", quindi guarda
al se entrambi sono vere non c'è una lattina nel mio ovest
non c'è una lattina ad oves e c'è una lattina ad est
allora bene è vero se tutto il primo ramo è questo
va' ad est, sì.
Ora è in una nuova situazione, quindi inizia
dice, c'è un nord vuoto
e c'è una lattina ad est, non oltre il ramo finale
c'era una del tipo: se c'è una lattina nell'attuale spazio
c'è, raccogli
lo fa, ok, ora è in una situazione dove
questo primo: se l'affermazione fallisce allora non è vera
quindi andiamo oltre qui, non c'è una lattina in questo sito
quindi muove a sud. Spero abbiate afferrato l'idea che è solamente un modo diverso
di esprimere
una strategia. É difficile trovare un albero
che sia una buona strategia ma questo sarà il compito dell'algoritmo genetico
lo sola differenza da quanto fatto prima è che l'algoritmo genetico
porta all'evoluzione di questi alberi
invece di stringhe quindi ecco come funziona
la popolazione iniziale invece di avere stringhe casuali è solo un insieme
di alberi casuali
con quello che chiamiamo limiti sintattici
per esempio, abbiamo bisogno di "se" "altrimenti" alla radice dell'albero
e altri limiti di cui non parlerò in dettaglia qui
voglio solo darvi l'idea generale
per calcolare la fitness, è la stessa procedura già vista, Robby
prova ogni strategia in diversi ambienti
computa lo score della media di ogni strategia e poi abbiamo
l'adattamento individuale per creare più discendenti, ciò nonostante preparino gli individui
che implementano la selezione al il crossover per l'inventivo di scambio per la riproduzione
in parti di stringhe scambiamo sottoalberi
quindi qui c'è un esempio di possibili genitori
per alberi e possiamo creare un bambino
prendendo questo sottoalbero
dal secondo genitore e metterlo qui
invede di questo, muove ad est, guarda, e metterebbe
questo sottoalbero lì per creare un bambino
che sembra questo quindi è esattamente la stessa cosa
del primo genitore eccetto per quella mossa ad est
rimpiazzata da questo se altrimenti fermati
è ancora sintatticamente corretto è ancora una strategia
e questo è come un algoritmo genetico è capace di prendere parte, serve
per preparare i genitori e combiniamo quelli
le mutazioni che iniziano a rimpiazzare un valore casuale scelto con un altro valore casuale
sostituiamo un sottoalbero con un sottoalbero generato casualmente
per poterlo fare, possiamo prendere questo sottoalbero qui
e rimpiazzarlo con un sottoalnero generato casualmente
non ho implementato la versione della programmazione genitca di Robby
che qualcosa che i pià avanzati programmatori tra di voi possono
essere interessati a fare
ma voglio dirvi di un progetto reale di programmazione genetica
a quelli che potrebbero essere piuttosto interessati
il primo è l'applicazione della programmazione genetica alla computer grafica
che è stato fatto da molte persone, l'esempio più famoso è stato fatto da Karl
Sims
curioso che negli anni '90 fosse un artista di computer grafica
e ha deciso che voi stessi poteste evolvere i programmi per produrre computer grafiche
che sono esteticamente piacevoli. Ecco come funziona.
Gli individui nella popolazione sono alberi prorpio come vi ho mostrato
nella rappresentazione delle strategie per
robot virtuali, rappresentano equazioni
che generano un colore per ogni pixel in un'immagine
ok, quindi questi sono solo alcuni esempi e
ci sono alcuni programmi che non vi spiegherò come funzionano
potete leggere i saggi di Carl Sims se foste interessati
ma vi resta impressa solo l'idea che potete rappresentare
questi programmi come alberi
e ogni programma genera un colore per ogni pixel dell'immagine
ok, quindi potete immaginare di generare un insieme di programmi casuali
che casulamente colrano i pixel di un'immagine
la domanda è come definireste una funzione di fitness, cioè come
definireste il fiteness di un particolare
pixel. Allora questo è qualcosa che
ora è oltre il computer di per sé
per farlo bene Karl Sims ha aggiunto gli umani nel ciclo
quello che ha fatto era di avere gli umani stessi come esempio
che guardano alle immagini che il computer ha creato immagini casuali
e prendono quella che gli piace di più
questa sarà usata come un genitore e crossover
con altri programmi casuali e mutazioni produrrebbe nuovi programmi
che produrrebbero nuove immagini collegate a quella scelta.
Ripetetelo pià volte e l'algoritomo genetico emerge con
meravigliosi risultati
qui eccone un esempio, un'immagine
e qui un programma che l'ha creata
questa è stata una collaborazione in un certo senso tra
l'algoritmo genetico e l'essere umano
dove questo non ha scritto davvero il programma, ma dice solo
cosa gli piace e poi l'algoritmo genetico
parte e evolve il programma ulteriormente
qui un altro esempio
e un altro
qui c'è uno particolarmente bello, che ricorda alcune pitture giapponesi
penso
un altro e
così via. Qui 2
KRL non potete andare al primo, è il sito di Karl Sims dove potete trovare tutte
queste immagini e molti altri diversi progetti
il secondo è un'applet che
vi dà la possibilità di evolvere tipi di immagini del cielo da soli
una cosa molto interessante che ha fatto Karl Sims
inoltre a quello già descritto è
la mostra in un museo. Era il Center George Pompidou a Parigi
dove aveva alcuni schermi come potete vedere
ognuno che mostra un'immagine diversa di quella che abbiamo appena visto
e sul pavimento, giù, ci sono dei sensori
e le persone nell'installazione possono andare e rimanare sui sensori
se gli piace una particolare immagine e poi quella
viene scelta ed evolte ulteriormente grazie all'algoritmo genetico
forse insieme ad altri immagini scekte
così in questo modo non c'è una singola persona ma un intero gruppo che
stava interpretando
in un certo senso il ruolo di amare la selezione di un algoritmo per
l'algoritmo genetico.
Quello che Sims ci ha detto a riguardo: «Gli osservatori alla mostra possono osservare
un'evoluzione simulata a computer nel progresso
di un'immagine evolutiva ma in questa evoluzione gli osservatori non sono solo
osservatori
sono la causa dell'evoluzione e ne dirigono il percorso».
Continua poi così: «Una popolazione di immagini viene vista sul computer
in un archivio di 16 monitor, gli osservatori determinano quali immagini sopravviverà
stando sui sensori e per quelli che penso siano le immagini più interessanti esteticamente
che non sono selezione vengono rimosse e rimpiazzate dalle discendenti
delle immagini sopravvissute
le nuove immagini vengono copiate e le cobinazioni sono i loro genitori ma quando
alterazioni varie
questa è un'evoluzione artificiale che gli osservatori stessi in maniera interattiva
essi determinano la fitness dell'immagine scegliendo dove stanno
come il ciclo continua la popolazione, le immagini che vanno avanti in
sempre più interessanti effetti visivi
questa installazione interattiva è un'insolita collaborazione
tra esseri umani e macchine. L'essere umano fornisce le decisioni come estetica visiva
e il computer fornisce l'abilità di calcolo per generare
combaciamenti e mutazioni di texture e modelli complessi
Agli osservatori non è richiesto di comprendere le equazioni tecniche considerate
il computer può solo sperimentare in maniera casaule senza alcun senso dell'estetica
ma la combinazione di abilità umane e della macchina permette la creazione
di risultati che nessuno dei due produrrebbe da solo.