Programmazione Genetica e Strategie di Pianificazione (prima puntata)

VBJ — n. 77 — settembre-ottobre 2007

Programmazione Geneticae Strategie di Pianificazionedi Fabio Fabozzi

Sono sempre stato affascinato dall’Intelligenza Artificiale e dagli Algo-ritmi Genetici. La Programmazione Genetica (PG), e il frutto di un’ap-plicazione degli Algoritmi Genetici (AG) da parte di John Koza. I risultatiottenuti da Koza e dagli altri studiosi in questa disciplina sono stupefacenti.

Fabio FabozziFabio Fabozzi e pro-gettista software pertecnologie .NET e JA-VA e di integrazioni tradifferenti piattaforme.Attualmente, colla-bora con la ICM ItaliaS.p.A. sede di Roma. Trai suoi principali interessivi sono l’IntelligenzaArtificiale e le ScienzeCognitive. E laureandoin Scienze dei ProcessiCognitivi, presso l’uni-versita “La Sapienza”di Roma. E autore dellibro “Intelligenza Arti-ficiale con VB” editodal Gruppo Infome-dia, con cui collaborada diversi anni.

pubblicato suWWW.INFOMEDIA.IT

!stampa digitale da

Lulu Enterprises Inc.stores.lulu.com/infomedia

InfomediaInfomedia e l’impresa editoriale che da quasi venti an-ni ha raccolto la voce dei programmatori, dei sistemi-sti, dei professionisti, degli studenti, dei ricercatori e deiprofessori d’informatica italiani.Sono piu di 800 gli autori che hanno realizzato per le te-state Computer Programming, Dev, Login, Visual BasicJournal e Java Journal, molte migliaia di articoli tecnici,presentazioni di prodotti, tecnologie, protocolli, strumen-ti di lavoro, tecniche di sviluppo e semplici trucchi e stra-tagemmi. Oltre 6 milioni di copie distribuite, trentamilapagine stampate, fanno di questa impresa la piu grande edinfluente realta dell’editoria specializzata nel campo dellaprogrammazione e della sistemistica.In tutti questi anni le riviste Infomedia hanno vissuto del-la passione di quanti vedono nella programmazione nonsolo la propria professione ma un’attivita vitale e un verodivertimento.Nel 2009, Infomedia e cambiata radicalmente adottandoun nuovo modello aziendale ed editoriale e si e organiz-zata attorno ad una idea di Impresa Sociale di Comunita,partecipata da programmatori e sistemisti, separando leattivita di gestione dell’informazione gestite da un boardcomunitario professionale e quelle di produzione gesti-te da una impresa strumentale. Questo assetto e in lineacon le migliori esperienze internazionali e rende Infome-dia ancora di piu parte della Comunita nazionale deglisviluppatori di software.Infomedia e media-partner di manifestazioni ed eventi inambito informatico, collabora con molti dei piu impor-tanti editori informatici italiani come partner editoriale efornitore di servizi di localizzazione in italiano di testi inlingua inglese.

L’impaginazione automatica di questa rivista e realizzata al100% con strumenti Open Source usando OpenOffice,Emacs, BHL, LaTeX, Gimp, Inkscape e i linguaggi Lisp,Python e BASH

For copyright information about the contents of VisualBasic Journal, please see the section “Copyright” at theend of each article if exists, otherwise ask authors. In-fomedia contents is © 2007 Infomedia and released asCreative Commons 2.5 BY-NC-ND. Turing Club contentis © 2007 Turing Club released as Creative Commons2.5 BY-ND.

Le informazioni di copyright sul contenuto di Visual Ba-sic Journal sono riportate nella sezione “Copyright” al-la fine di ciascun articolo o vanno richieste direttamenteagli autori. Il contenuto Infomedia e © 2007 Infomediae rilasciato con Licenza Creative Commons 2.5 BY-NC-ND. Il contenuto Turing Club e © 2007 Turing Club erilasciato con Licenza Creative Commons 2.5 BY-ND. Siapplicano tutte le norme di tutela dei marchi e dei segnidistintivi.

E in ogni caso ammessa la riproduzione parziale o tota-le dei testi e delle immagini per scopo didattico purchevengano integralmente citati gli autori e la completaidentificazione della testata.

Manoscritti e foto originali, anche se non pubblicati, nonsi restituiscono.

Contenuto pubblicitario inferiore al 45%.

La biografia dell’autore riportata nell’articolo e sulsito www.infomedia.it e di norma quella disponibi-le nella stampa dell’articolo o aggiornata a cu-ra dell’autore stesso. Per aggiornarla scrivere [email protected] o farlo in autonomia all’indirizzohttp://mags.programmers.net/moduli/biografia

http://www.infomedia.it

http://stores.lulu.com/infomedia

30 VBJ N. 77 - Settembre/Ottobre 2007 31VBJ N. 77 - Settembre/Ottobre 2007

INTELLIGENZA ARTIFICIALE INTELLIGENZA ARTIFICIALE

Programmazione Genetica e Strategie di Pianificazione

di Fabio Fabozzi

Sono sempre stato affascinato dall’Intelligenza Ar-tificiale e, soprattutto, dagli Algoritmi Genetici. In particolare, chi ha letto il mio primo libro e gli arti-coli scritti in passato, ha potuto apprezzare la bel-lezza di queste aree tematiche, naturalmente non grazie a me, ma al contributo dei grandi scienziati che vi hanno lavorato. La Programmazione Geneti-ca (PG), è il frutto di un’applicazione degli Algorit-mi Genetici (AG) da parte di John Koza. I risultati ottenuti da Koza e dagli altri studiosi in questa di-sciplina sono stupefacenti. Vi consiglio di visitare il sito della Genetic Programming Foundation [1], per seguire gli ultimi aggiornamenti e le novità. In questo articolo parleremo della PG e dei problemi

legati alle strategie di pianifica-zione, riproponendo un classico problema proposto (e risolto) da Koza: UNIVERSAL (Figura 1).

Tale gioco – o problema – con-siste nell’impilare dei cubi con delle lettere, disposti casualmen-te su un tavolo, finché non sia composta la parola “UNIVER-SAL”, appunto. Un problema che può sembrare banale, ma in realtà non lo è. Si tratta, in-fatti, di un problema riguardan-te le strategie di pianificazione, successivamente la presa di de-cisione e, naturalmente, la rela-tiva generazione di programmi che risolvano il problema.

Per ciò che concerne le basi del-la PG si consiglia di consultare la bibliografia alla fine di que-sto articolo.

Fabio Fabozzi è progettista software per tecnologie .NET e JAVA e di integrazioni tra differenti piattaforme. Attualmente, collabora con la ICM Italia S.p.A. sede di Roma. Tra i suoi principali interessi vi sono l’Intelligenza Artificiale e le Scien-ze Cognitive. È laureando in Scienze dei Processi Cognitivi, presso l’università “La Sapienza” di Roma. È autore del libro “Intelligenza Artificiale con VB” edito dal Gruppo Infomedia, con cui collabora da diversi anni. Può essere contattato al-l’indirizzo [email protected]

Prima puntata



rentetica di un albero. Tale peculiarità rende tale linguaggio partico-larmente adatto a rap-presentare le forme di pensiero deduttivo, sotto forma appunto di alberi decisionali e aiuta altresì a rappre-sentare la popolazione di un Algoritmo Gene-tico per l’applicazione di operatori come l’in-crocio. Cosa succede quando si vuole uti-lizzare un linguaggio diverso dal LISP, non funzionale quindi, ma procedurale e/o ad og-getti? La direzione in cui indagheremo è pro-prio questa.

L’idea di Koza

Il problema dell’impilamento dei blocchi ser-ve per sviluppare e verificare metodi di pia-nificazione. Koza per risolvere questo proble-ma utilizzò un insieme di tre terminali e cin-que funzioni. I terminali erano rappresenta-ti da sensori collegati ad una sorta di robot e controllato dal programma LISP. Ognuno di questi sensori rileva un insieme di informa-zioni (Tabella 1).

Le cinque funzioni erano quelle riportate nella Tabella 2.

Considerazioni iniziali

Koza ha sempre scelto la generazione di pro-grammi in LISP. La scelta è in questo caso giustificata: il LISP ha infatti a disposizione un’ampia scelta di primitive che consentono di effettuare operazioni immediate su liste, pile e code con estrema semplicità rispetto ad al-tri linguaggi. Inoltre il LISP consente di rap-presentare le operazioni sotto forma di alberi decisionali, ossia come rappresentazione pa-

Figura 1

PA Restituisce il nome del blocco in cima alla pila, altrimenti, se la pila è vuota, restituisce NIL, il corrispettivo in LISP dell’istruzione null, presente in altri linguaggi.

BS Restituisce il nome del Blocco Superiore Corretto; NIL se non corretto.

PN Restituisce il nome del blocco che è necessario per completare la parola UNIVERSAL; NIL se non è necessario nessun altro blocco.

Tabella 1

32 VBJ N. 77 - Settembre/Ottobre 2007

INTELLIGENZA ARTIFICIALE

gramma vada fatto “girare” prima di conosce-re la sua Idoneità.

Il resto, come nella PG, in generale segue le regole d’Incrocio, cioè i più idonei vengo-no incrociati tra loro.

I soggetti della popolazione erano rappre-sentati direttamente come espressioni LISP

La generazione della Popolazione partiva da questi due insiemi. Koza generò casualmen-te 300 individui.

L’Idoneità era calcolata in base al numero di casi prova che risultavano impilati in modo corretto.

Ciò implica, in parole povere, che ogni pro-

Figura 2

SP(x) Sposta un blocco x dal tavolo, sulla pila

ST(x) Sposta un qualsiasi blocco x dalla pila al tavolo

RF(espressione1, espressione2) Esegue l’espressione1 finche l’espressione2, un predicato, non restituisce True.

NOT(espressione1) Restituisce True se l’espressione1 è NIL, altrimenti NIL

EQ(espressione1, espressione2) Restituisce True se l’espressione1 e l’espressione2 sono equivalenti, NIL altrimenti.

Tabella 2



come e quanto impegnativo e relativamente oneroso sia scrivere queste primitive. Il “pre-mio finale” è comunque allettante.

Come procedere?

Per chi predilige la parte puramente tecni-ca, arriveremo a costruire questa applicazio-ne in C# per .NET Framework 2.0. L’ambiente di sviluppo usato sarà SharpDevelop 2.2, un IDE open source, scaricabile liberamente. Ad ogni modo, andrà bene qualsiasi versione di Visual Studio a vostra disposizione.

Laddove sono presenti diagrammi UML, vi segnalo che sono stati creati con Star UML, un Modeler open source.

I dati per risolvere il problema (l’insieme del-le informazioni e delle funzioni e l’obiettivo)

piuttosto che alberi nelle popolazioni PG clas-siche:

(EQ(ST PA)PN)

Ancora una volta la PG ha entusiasmato per i risultati raggiunti, soprattutto per ciò che concerne la complessità delle soluzioni can-didate e per il fatto che tale complessità au-menti con l’evoluzione, piuttosto che rimane-re prefissata come negli AG classici. Tuttavia le caratteristiche del LISP, che possono esse-re considerate ottimali per le caratteristiche della PG, potrebbero rappresentare proprio una sua limitazione se trasposte in un altro linguaggio di programmazione. Questo pro-blema potrebbe essere risolto scrivendo delle “primitive” ad hoc; il problema è di scrutare

Listato 1

private void MescolaLettere() { for (int i = 0; i < _blocchiLettere.Length; i++) { int tempIdx = _mescolatore.Next(0, _blocchiLettere.Length);

string tmpStr = _blocchiLettere[tempIdx]; _blocchiLettere[tempIdx] = _blocchiLettere[i]; _blocchiLettere[i] = tmpStr; }

}

Figura 3



li abbiamo già. Non resta che pianificare la progettazione

di questo software. La nostra ipotesi di partenza è di vedere

qual è il risultato che si può raggiungere, co-struendo delle primitive in C# per risolvere questo problema.

Funzioni e Terminali, specificati in questo problema, non sono altro che funzioni.

L’ assunzione da cui si può partire, ossia la più semplice, è di andare ad implementare delle primitive molto semplici. Tuttavia, pri-ma di effettuare questa operazione, sarà ne-cessario definire la classe che definisce il sog-getto della popolazione e le relative operazio-ni per generare la popolazione.

La classe “soggetto” e la classe “istruzioni”

Prima di analizzare Attributi, Proprietà e Me-todi della classe Soggetto e della classe Istru-zioni, vediamo i relativi Class Diagram per una panoramica più generale (Figura 2 e 3):

Tralasciando attributi, proprietà e meto-di di ordine generale, andiamo ad analizza-re le caratteristiche più salienti della classe Soggetto.

Iniziamo dai costruttori della classe. Il co-struttore parametrico lo tralasciamo perché più semplice. Per ciò che concerne il costrut-tore parametrico, troveremo che esso riceve

in ingresso 3 parametri:

- la lunghezza del programma- l’insieme dei terminali- l’insieme delle funzioni

Ciò è abbastanza semplice da intuire: la lun-ghezza del programma viene selezionata in modo random, dal programma principale, così come l’insieme dei terminali e delle funzioni ha già dimensioni predefinite. Ciò ci dice che ogni soggetto genererà il suo programma in modo autonomo. La prima operazione che il costruttore esegue è un metodo privato, ossia, “MescolaLettere()”. Tale metodo ha l’effetto di effettuare il mescolamento dei blocchi che compongono la parola UNIVERSAL.

Ogni generazione, dunque, mescolerà i bloc-chi da impilare in modo diverso (Listato 1).

Il metodo successivo lanciato dal costrutto-re si occuperà di generare il programma re-lativo ad un determinato soggetto, con i pa-rametri passati al costruttore. Naturalmen-te, l’avvicendarsi tra terminali e funzioni è regolato totalmente da generazioni random (Listato 2).

Noterete che il programma è un Array di tipo Istruzioni. Nello specifico, la classe istru-zioni consente di memorizzare dei parametri che sono, praticamente, dei terminali e/o fun-zioni. In tal modo, sarà possibile eseguire il flusso del programma senza troppe complica-

Figura 4



zioni. Per ciò che concerne la classe istruzioni la sua implementazione è abbastanza sempli-ce, come avete potuto già constatare dal suo class diagram.

Infine, il metodo “EseguiProgramma()” ese-gue il programma per il soggetto e produce il risultato in termini di blocchi impilati, che rappresentano la soluzione che il programma stesso è riuscito a risolvere (Listato 3).

Come noterete, al verificarsi di alcune con-dizioni, “EseguiProgramma()”, richiama altri metodi al suo interno, che non sono altro che le primitive di cui avevamo bisogno.

Questa tematica verrà affrontata in modo più approfondito, in quanto dall’ implementazio-ne delle primitive dipende il successo di riso-luzione del problema di pianificazione.

Strategie di definizione delle primitive all’interno della classe soggetto

Probabilmente qualcuno si sarà posto la se-guente domanda: “È possibile scrivere un AG, nell’ambito della PG, che possa scrivere un programma corretto seguendo la logica della scimmia che preme a caso i tasti su una ta-stiera e compone un’opera letteraria?” I risul-tati dicono che ciò è possibile.

Pur pensando o credendo che questi risul-tati siano oltremodo oltraggiosi ed irriveren-ti nei confronti di tutti i nostri anni di studio nel campo dell’ingegneria del software, non è possibile ignorarli.

Tuttavia, il progettista del software ha anco-ra un ruolo: definire le procedure attraverso le quali la “scimmia” possa scrivere il program-

PUNTI DI FORZA PUNTI DI DEBOLEZZA

- Risparmio tempo sulla definizione delle primitive- Realizzo una soluzione comunque robusta

- La soluzione che raggiungo è completa solo al 89% circa

OPPORTUNITA’ MINACCE

- Arrivo ad una soluzione, per approssimazione, pressoché completa

- I presupposti della mia progettazione mi portino su una “strada sbagliata”

Figura 5

Tabella 3



ma o l’opera letteraria in modo corretto.Un modo corretto e completo sarebbe di pro-

gettare un parser che ricostruisca il flusso del programma in modo corretto.

Nonostante ciò, le primitive possono essere costruite in modo molto più semplice, ma non solo: il flusso può essere anche considerato come lineare, cioè eseguendo il programma dalla prima istruzione fino all’ultima. Cosa si

perde e cosa si guadagna comportandosi così? Questo comportamento progettuale potrebbe essere riassunto attraverso un quadro di ana-lisi S.W.O.T. (Tabella 3).

Per non lasciare il lettore perplesso e, so-prattutto, per dimostrarvi che il mio ragiona-mento presentato nel quadro S.W.O.T. non è errato, vi mostrerò (solo in parte, per non ro-vinarvi il finale) due condizioni, attraverso le

Listato 2

private void GeneraProgramma(string[] insiemeTerminali, string[] insiemeFunzioni) { _programma = new Istruzioni[_lunghezzaProgramma]; for (int i = 0; i < _programma.Length; i++) {

int tmpSel = _selettoreTF.Next(0,2); if (tmpSel == 1) { int tmpSelT = _selettoreT.Next(0, 2); _programma[i] = new Istruzioni(); _programma[i].Istruzione = insiemeTerminali[tmpSelT];

} else { _programma[i] = new Istruzioni(); int tmpSelF = _selettoreF.Next(0, 4); _programma[i].Istruzione = insiemeFunzioni[tmpSelF]; if (_programma[i].Istruzione == “RF(espressione1, espressione2)”) { int tmpSelP1 = _selettorePar1.Next(0,1); _programma[i].Parametro1 = insiemeFunzioni[tmpSelP1]; int tmpSelP2 = _selettorePar2.Next(0, 2); _programma[i].Parametro2 = insiemeTerminali[tmpSelP2]; }

if (_programma[i].Istruzione == “NOT(espressione1)”) { int tmpSelP1 = _selettorePar1.Next(0, 1); _programma[i].Parametro1 = insiemeFunzioni[tmpSelP1]; }

if (_programma[i].Istruzione == “EQ(espressione1, espressione2)”) { int tmpSelP1 = _selettorePar1.Next(0, 1); _programma[i].Parametro1 = insiemeFunzioni[tmpSelP1]; int tmpSelP2 = _selettorePar2.Next(0, 2); _programma[i].Parametro2 = insiemeTerminali[tmpSelP2]; }

} } }



Listato 3

public void EseguiProgramma() { int spostaBloccoDaTavolo = 0; int spostaBloccoDaPila = 0; int maxBlocchi = 8; int minBlocchi = 0; bool _scelta = true; for (int i = 0; i < _programma.Length; i++) { ... if (_programma[i] == “SP(X)”) { SP(ref spostaBloccoDaTavolo, ref spostaBloccoDaPila, ref maxBlocchi); } if (_programma[i] == “ST(X)”) { ST(ref spostaBloccoDaTavolo, ref spostaBloccoDaPila, ref minBlocchi); } ... } }

quali posso sapere che le “cose” sono andate, tutto sommato, bene.

Condizione 1

Faccio girare il mio AG con questi parame-tri :

- popolazione max = 300 individui- fitness bersaglio da raggiungere = 8

Nonostante le condizioni un po’ pretenziose, cioè popolazione esigua e fitness abbastanza alta da raggiungere, questo è il risultato ot-tenuto (Figura 4).

Ossia, in 3 epoche su 1.000 in cui il program-ma ha ciclato, ho ottenuto un certo numero di soggetti che hanno realizzato un program-ma che si è avvicinato alla soluzione di circa il 89%, cioè i programmi relativi ad ogni sog-getto hanno impilato 8 blocchi su 9 corretta-mente. Non male direi.

Condizione 2

- popolazione max = 300 individui- fitness bersaglio da raggiungere = 9

Tuttavia, come avevo già annunciato nel qua-dro S.W.O.T, nel voler raggiungere una fitness bersaglio = 9, con una popolazione di n sog-getto ho raggiunto dei risultati piuttosto scar-si (Figura 5).

Ho ottenuto una fitness pari a 6 ed i pro-grammi sono stati accurati al 67% circa, os-sia, hanno impilato 6 blocchi su 9.

Questo punto è importante, perché in questo modo, che in seguito potrete testare anche voi, so già che il mio programma è in grado di rag-giungere sempre un’accuratezza, al minimo, del 89% circa. Cercheremo, naturalmente, in seguito di migliorare questa prestazione.

Ora, se vi rivelassi che ho raggiunto questi risultati implementando due sole primitive, ci credereste?

Beh! Dovete crederci perché è proprio così.

38 VBJ N. 77 - Settembre/Ottobre 2007

INTELLIGENZA ARTIFICIALE

Listato 4

private void SP(ref int spostaBloccoDaTavolo,ref int spostaBloccoDaPila,ref int maxBlocchi) { if (spostaBloccoDaTavolo < maxBlocchi) { _blocchiDaImpilare[spostaBloccoDaPila] = _blocchiLettere[spostaBlocco DaTavolo]; spostaBloccoDaPila++; spostaBloccoDaTavolo++; } } private void ST(ref int spostaBloccoDaTavolo,ref int spostaBloccoDaPila,ref int min Blocchi) { if (spostaBloccoDaPila > minBlocchi) { _blocchiDaImpilare[spostaBloccoDaPila] = “”; spostaBloccoDaPila--; spostaBloccoDaTavolo--; } }

Come mai?Per inciso, a mio avviso, le primitive più im-

portanti sono quelle che riguardano lo spo-stamento dei blocchi dal tavolo e, successi-vamente, vengono impilati per formare la pa-rola UNIVERSAL. Due di queste, tra quelle che troverete nel codice sorgente, sono SP() e ST() (Listato 4).

Per fare una digressione sulla “scimmia”, menzionata precedentemente, i risultati rag-giungibili sono molto alti, seppur semplifica-ti. Nonostante la nostra ricerca in questo ar-ticolo sia focalizzata sullo scrivere delle pri-mitive in C#, che emulino il comportamento delle primitive in LISP, in realtà il meccani-smo più grande lo gioca proprio l’ AG stesso. Naturalmente, se le primitive sono progetta-te ed implementate bene, allora tutto andrà “per il verso giusto”.

Conclusioni

In questa prima parte abbiamo analizzato alcune tematiche per risolvere questo pro-blema. I primi risultati sono stati abbastan-za promettenti.

Nella seconda parte analizzeremo la per-

formance globale di tutto l’algoritmo rispet-to alle primitive delineate, per vedere se, e soprattutto quanto, ci siamo avvicinati al no-stro obiettivo.

Bibliografia

[1] Genetic Programming Foundation – “http://www.geneticprogramming.org”

[2] Fabio Fabozzi – “Predizione di flussi dati in sistemi caotici attraverso gli algoritmi ge-netici”, Computer Programming, Febbraio 2006, Gruppo Editoriale Infomedia

[3] Fabio Fabozzi – “Intelligenza Artificiale con Visual Basic”, Dicembre 2004, Gruppo Ed-itoriale Infomedia, ISBN 8881500183

[4] Fabio Fabozzi – “Programmazione Genetica in Visual Basic”, VBJ n°50, Marzo/Aprile 2003, Gruppo Editoriale Infomedia

[5] Melanie Mitchell – “Introduzione agli Al-goritmi Genetici”, Apogeo Scientifica, 1998, ISBN 8873035000

[6] Kenneth Lange – “Mathematical and Statistical Methods for Genetic Analysis” Springer, 1997, ISBN 0387949097

[7] Ilya Prigogine – “Le Leggi del Caos”, Laterza Editore

Programmazione Genetica e Strategie di Pianificazione (prima puntata)

Documents

Transcript of Programmazione Genetica e Strategie di Pianificazione (prima puntata)