FUTURO

[NSFW] Evolvi una macchina

Su Oggiscienza è da un po’ che nominiamo gli algoritmi genetici, cioè l’approccio darwiniano alla programmazione. Ecco una semplice dimostrazione della loro efficacia.

È poco più di un gioco, ma per vedere gli algoritmi genetici all’opera BoxCar2D è perfetto. In questo gioco scritto in flash gli algoritmi genetici devono cercare di evolvere dei veicoli bidimensionli. Tutto quello che hanno disposizione sono ruote, poligoni e ammortizzatori.

Si parte con una popolazione di “veicoli” generata totalmente a caso, per non dire a casaccio: alla generazione zero alcune macchine sono addirittura prive di ruote e non è necessaria una laurea in ingegneria per capire che non possono andare molto lontano, né farlo velocemente.

A questo punto però ci si mette la selezione naturale: per quanto poco efficienti nella popolazione iniziale alcune macchine avranno ottenuto un punteggio (dato da un rapporto tra la distanza percorsa e il tempo) più alto delle altre. Solo queste si “riprodurranno” fra loro dando origine a una progenie in cui in cui le caratteristiche dei genitori si sono mescolate grazie a una sorta di crossing-over.

A ogni nuova generazione inoltre si aggiungono delle mutazioni che arricchiscono ulteriormente la variabilità della discendenza. Ma mano che lavora il filtro della selezione, le macchine arrivano sempre più lontano prima di ribaltarsi o incastrarsi in una buca, e la loro velocità aumenta. Alcuni modelli si fanno addirittura crescere una ruota sul dorso, che spesso li rende in grado di continuare la corsa su un lato diverso quando si ribaltano. Infatti l’unico scopo dei veicoli è macinare più strada possibile: l’incolumità dei passeggeri non è tra i parametri.

BoxCar2D, che ieri è giunto alla versione 2.1, si basa sulla libreria Box2D che simula alcune leggi fisiche in un ambiente bidimensionale. La nuova versione offre al giocatore più controllo sulla “specie”: può decidere per un allevamento strettamente selettivo e modificare a tavolino gli esemplari più promettenti e creare così un “pedigree” ancora più puro. Bisogna mettere in chiaro che giochi come questo non sono di per sé prove della validità della teoria dell’evoluzione per la quale le prove, anche sperimentali, non mancano. BoxCar2D (e gli algoritmi genetici in generale) semplicemente dimostra come il principio della selezione naturale è applicabile anche all’informatica.

Attenzione però: osservare i progressi delle macchine sullo schermo, che generazione dopo generazione sperimentano una varietà di forme che difficilmente verrebbero in mente a un designer, può risultare ipnotico e assuefacente, e potreste ritrovarvi con BoxCar2D aperto per giorni in una scheda del vostro browser e a non riavviare più il computer per non perdere i progressi compiuti dai vostri pupilli.

Un altro semplice algoritmo che mostra l’efficacia del principio della selezione non casuale di mutazioni casuali è il celebre Weasel program. Ideato da Richard Dawkins, data una frase “obiettivo” (originariamente una frase del terzo atto dell’AmletoMethinks it is like a weasel“, cioè “Mi sembra una donnola”) il programma deve cercare di scriverla selezionando da sequenze di lettere generate casualmente quelle che più vi somigliano. Ecco una versione web, un po’ diversa da quella di Dawkins…

Stefano Dalla Casa
Giornalista e comunicatore scientifico, mi sono formato all’Università di Bologna e alla Sissa di Trieste. Scrivo abitualmente sull’Aula di Scienze Zanichelli, Wired.it, OggiScienza e collaboro con Pikaia, il portale italiano dell’evoluzione. Ho scritto col pilota di rover marziani Paolo Bellutta il libro di divulgazione "Autisti marziani" (Zanichelli, 2014). Su twitter sono @Radioprozac

7 Commenti

  1. In origine era solo il famosissimo “Game of Life” dove l’ evolveva generando forme di “vita” (quasi) sempre diverse e (talora) anche complesse, oltre che (sovente) oscillare in stati di “flip-flop” e “imparare” dall’esperienza!!! Ora siamo a abbastanza più complesse, almeno mi pare così!
    Non essendo uno specialista in informatica, mi domando se (per i due giochi) si possa parlare di automi a numero di stati finiti non deterministico (ASFND) o se si tratti di automi a numero di stati finiti deterministico (ASFD). In ogni caso, siamo in presenza di una Macchina di Turing Universale? A me pare di sì! Qualcuno mi può rispondere? Grazie.

  2. In origine era solo il famosissimo “Game of Life” dove l'”automa” evolveva generando forme di “vita” (quasi) sempre diverse e (talora) anche complesse, oltre che (sovente) oscillare in stati di “flip-flop” e “imparare” dall’esperienza!!! Ora siamo a “macchine” abbastanza più complesse!
    Non essendo uno specialista in informatica, mi domando se (per i due giochi) si possa parlare di automi a numero di stati finiti non deterministico (ASFND) o se si tratti di automi a numero di stati finiti deterministico (ASFD). In ogni caso, siamo in presenza di una Macchina di Turing Universale. Almeno mi pare così! Qualcuno mi può rispondere? Grazie.

    1. @Mario

      Per dire che sono Turing completi (penso tu intendessi questo) ci sarebbe da dimostrarlo, bisogna formalizzarli come modello di calcolo e vedere se sono in grado di calcolare le funzioni mu-ricorsive.

      Ad ogni modo i giochi vengono elaborati su computer deterministici quindi, ammesso che possano essere considerati modelli di calcolo, sono comunque automi deterministici, es. un input del sistema può essere dato da rand() che su un computer è una funzione deterministica.

    2. Comunque Life di Conway da te citato, non impara dall’esperienza: è deterministico, fissate le configurazioni iniziali la sua evoluzione e lo stato finale (se esiste[1]) è già “scritto” nelle regole.

      (Forse lo sapevi, ma qualcuno leggendo il tuo commento potrebbe farsi un’idea sbagliata).

      [1] non è detto che ci sia ed in generale, essendo Turing completo, non possiamo saperlo a priori per il problema della fermata.

    3. in quanto programma calcolabile questo si puo’ sempre riportare ad una macchina di turing . per quanto riguarda invece il punto se sia deterministico o non deterministico cio’ dipende dalla tipologia di mutazioni: se queste sono calcolabili allora sara’ deterministico, se queste sono totalmente casuali allora l’automa sara’ non deterministico.

  3. Argomenti molto interessanti? Qualche fonte (libro o sito) dove un profano possa approfondire? Grazie!

Rispondi

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.

%d blogger hanno fatto clic su Mi Piace per questo: