Immagina lo scenario seguente: sei un commesso viaggiatore che deve visitare un grande numero di città che sono connesse da una rete di strade. Devi visitare ogni città solo una volta. Per spendere meno soldi e tempo possibile vuoi percorrere la strada più efficiente trascorrendo il meno tempo possibile sulla strada. Che tipo di procedura decisionale puoi utilizzare per arrivare al piano di viaggio migliore? Questo scenario comunemente chiamato "il problema del commesso viaggiatore", uno di quella classe di puzzles matematici conosciuti come problemi di ottimizzazione. Per il problema del venditore ambulante, come per molti altri problemi di opttimizzazione, non esiste un algoritmo generale che ti garantirà la migliore soluzione in un tempo ragionevole. Vari metodi sono stati sperimentati con diverse quantità di successo. Per esempio, potresti semplicemente misurare ogni possibile strada di collegamento fra tutte le città e poi semplicemente scegliere quella che ha coperto la distanza minore. Sicuramente, questa soluzione di "brutta forza" diventerà impraticabile per più di una manciata delle città in quanto il numero delle strade possibili aumenta molto rapidamente quando si aggiungono più città. Il parallelizzare il problema, prendendo dei computers e facendogli cercare a ciascuno una strada per comparare in seguito i risultati, è un modo possibile per migliorare i vantaggi di questo approccio.

Un secondo approccio molto più comune è rappresentato da una discesa di grado su una "superficie di errore" generata da una soluzione particolare e le sue soluzioni vicine. L’idea sarebbe di prendere l’errore della soluzione corrente e compararlo con l’errore della soluzione accanto (ciòè simile) per spostarsi alla soluzione con il grado di errore più basso. La discesa per gradi è una tecnica fondamentale per gli algoritmi di reti neurali, in particolare per quanto riguarda la retroazione. Vedi il mio articolo Neurocomputer 3 contenuto in Extropy n.6 e le relative referenze per maggiori informazioni.

Ora considera come la Natura affronta tali problemi. Puoi considerare l’obiettivo del venditore ambulante come una specie di nicchia ecologica, cos" che una buona soluzione è rappresentata da un organismo che può raggiungere l’obiettivo senza morire di stanchezza o essere sorpassato da competitori che hanno più successo. Invece, a differenza della maggior parte di algoritmi per computer, le soluzioni sviluppate dalla Natura non sono il risultato della pianificazione deliberata fatta da un agente munito di coscienza. A differenza di questo la natura usa mutazioni casuali e selezione naturale come è stato descritto per la prima volta da Charles Darwin in "L’origine della specie" e più recentemente da Richard Dawkins in "The Blind Watchmaker" (recensito nel corrente numero di Extropy). Le buone soluzioni si propongono per mutazione - ovvero cambiamenti accidentali minimi nei geni - sono favorite dall’ambiente, permettendo all’organismo che contiene i geni mutati di soppravvivere, riprodursi e passare questi geni ai suoi discendenti. La riproduzione sessuale, nella quale un discendente ottiene la metà dei suoi geni da un organismo e l’altra metà da un altro, fa si che le buone soluzioni hanno l’opportunità di combinarsi producendo discendenti che potranno essere migliori di entrambi i genitori.

Gli algoritmi genetici, sviluppati per la prima volta da John Holland all’Università di Michigan esplorano questo ciclo di mutazione, sesso e selezione naturale nel tentativo di dare soluzioni ai problemi di ottimizzazioni. La procedura generale è delizia pura e semplice che può essere descritta nei passi seguenti:

(1) Inizia con un insieme di soluzioni possibili per il tuo problema. Se non sai quale sarà una buona soluzione fai generare queste prime soluzioni in modo casuale.

(2) Prendi ogni soluzione possibile, applicala al problema e esamina i risultati. Se sei soddisfatto con alcune soluzioni/e, smetti quà, diversamente vai al passo (3)

(3) Basandoti su un criterio stabilito all’inizio, rigetta le soluzioni che cadono al di sotto di un certo livello di successo per la soluzione del problema.

(4) Crea soluzioni nuove combinando insieme le parti di una buona soluzione con le parti di un’altra.

(5) Ogni tanto "muta" (casualmente) delle parti di alcune soluzioni.

(6) Vai al (2).

Come sempre penso sia una buona idea di illustrare questa procedura con un esempio. Non ho la carta (ho la pazienza) necessaria per giocare con il problema del commesso viaggiatore, cos" mi occuperò di qualcosa un pò meno complicata e cioé una implementazione a rete neurale della funzione boleana XOR, un esempio che ho utilizzato anche per Neurocomputer 3. Questa funzione prende due input, ognuno dei quali può essere "zero" o "uno", e restituisce come output un "uno" se gli inputs sono diversi. Se gli inputs sono uguali, restituisce come output uno "zero". In altre parole...

Input 1 0011

Input 2 0101

Output 0110

Ora, un problema interessante è come educare una rete neurale per farla "diventare" questa funzione. Cioè, dato il diagramma che segue, dove gli "I" sono inputs, i "W" sono dei pesi di connessioni multiple, i "sigma" sono delle somme, e i "Teta" sono dei nodi, vogliamo ottenere dei "W" e dei "Teta" tali da soddisfare tutte le relazioni di input/output della funzione.

Come i lettori di Extropy n.6 ricorderanno, uno schema per ottenere dei buoni parametri di rete è la retroazione, dove l’output attuale della rete viene comparato con l’output che si desidera, e la differenza tra l’output attuale e quello desiderato è restituita indietro attraverso la rete per aggiustare i "pesi" e i "Teta".

Sicuramente, la nostra preoccupazione per il momento sono gli algoritmi genetici, cosicché la questione è relativa al far "crescere" la cella (??? traduzione non certa ???) di una rete in un XORganismo - per impostare il problema XOR. Per esaminare questa questione, io scrissi un piccolo programma in C che lavorava come segue. (Come al solito questo programma è disponibile gratis per i lettori di Extropy, mandando una lettera alla mia attenzione presso la rivista). Ogni organismo era rappresentato, naturalmente, da cinque "pesi" e due "Teta". Questi erano i sette "geni" dell’organismo. "L’accoppiamento" consisteva nel produrre un nuovo organismo con la metà dei geni di un genitore e metà dei geni di un altro. Poiché gli organismi hanno sette geni ciascuno, il programma lanciava una moneta per determinare da quale genitore proveniva il settimo gene. Il programma iniziava con una collezione di cento organismi con geni presi a caso. Per ogni generazione il programma calcolava i punteggi di ogni organismo in relazione al problema XOR e uccideva ogni organismo che otteneva meno di tre delle quattro soluzioni corrette del problema. Poi, il programma ha fatto crescere gli organismi ottenuti seguendo lo schema di accoppiamento appena descritto. Inoltre, il programma ha mutato (casualmente) un gene preso a caso in alcuni degli organismi presi a caso ogni poche generazioni. I parametri del programma erano (1) il numero di accoppiamenti per generazione, (2) il punteggio minimo necessario per la sopravvivenza, (3) il numero di generazioni tra le mutazioni, e (4) il numero di organismi da mutare in una generazione mutante.

Non ho avuto tempo per esplorare delle possibilità che sarebbero risultate mescolando tutti i parametri ma alcune cose relative agli XORganismi sono sembrate evidenti dopo varie sequenze delle cento generazioni. Primo, il numero di organismi con pieno successo (punteggio = 4/4) è sempre stato minore del numero degli organismi che hanno ottenuto un punteggio di ¾. Questo risultato è quello che ci aspettavamo perché la nicchia che avevamo definito era un punteggio di ¾ e questo significava che quegli organismi che hanno ottenuto 4/4 erano superiori alla media. Secondo, l’emergenza di questi "sovra-organismi" superiori alla media sembrava dipendesse molto dalle condizioni iniziali. Se l’iniziale creazione casuale dei cento organismi ne produceva uno con un punteggio perfetto, quell’organismo tendeva a riprodurre se stesso creando molti altri organismi superiori alla media, ma se nessun organismo superiore alla media esisteva dall’inizio, c’erano delle possibilità molto alte che nessuno ne sarebbe risultato.

Infine mutazioni aggiunte sembravano ottenere un effetto benefico sul numero degli organismi superiori prodotti. Per esempio, ho fatto la comparazione fra dieci cicli di cento generazioni, tutte caratterizzate da un organismo singolo che mutava ad ogni generazione, contro dieci cicli di cento generazioni senza mutazioni. Il numero medio dei sovra-organismi prodotti attraverso la mutazione era circa 32, mentre il numero prodotto senza mutazioni era all’incirca 9.

Applicare gli algoritmi genetici (o reti neurali) al modello delle funzioni Booleane potrebbe sembrare esagerato quanto ottenere un Philosophy Doctor in matematica per fare i calcoli del proprio conto in banca. Nonostante ciò, l’esempio dell’XORganismo è istruttivo poiché mostra come un problema di semplice rete neurale possa essere risolto dalle tecniche degli algoritmi genetici, dimostrando cos" una strada in cui gli algoritmi genetici rientrano nel settore del neurocomputing (neuroscienze).

Gli algoritmi genetici hanno potenzialità applicative anche nel "mondo reale". Un uso, non sorprendente, è la soluzione di problemi di ottimizzazione simili a quello del commesso viaggiatore descritto sopra. Questo include il disegno di aeroplani e chip VLSI. Altre implicazioni comprendono un programma di riconoscimento dell’immagine che controlli molti sotto-programmi, connettendo quelli che funzionano meglio, e un programma per lo studio delle abitudini delle formiche attraverso la simulazione.

Nel prossimo articolo, discuterò un problema che sembra interessare molti membri dell’indirizzario di Extropy, più precismente l’idea del modellare computazionalmente l’economie o del modellare i computers economicamente.

A.K. Dewdney. The Armchair Universe. NewYork: W.H. Freeman. 1988 (See especially the chapter entitled "The Evolution of Flibs")

J. Holland. Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press. 1975.

Articles

M. Antonoff. "Genetic Algorithms: Software by Natural Selection." Popular Science, October 1991.

R. Morin. "A Look at Genetic Algorithms." SunExpert Magazine, November 1990.

P. Wayner. "Genetic Algorithms." BYTE, January 1991.