6 x 9 = 42

“Ho sempre detto che c’era qualcosa di fondamentalmente sbagliato nell’universo…” (Arthur Dent)

Prendendo Ispirazione

Posted by scardax su dicembre 21, 2008

Prima di tutto, non sono sparito. Semplicemente, di questi tempi sto male un giorno si e gli altri due pure, quindi non é sempre facile mettersi davanti al pc ad aggiornare il blog. Per rimediare, oggi un post che farà felici un sacco di informatici (perché io nerd non lo dico) che passano di qua. Post che, per inciso, volevo pubblicare per festeggiare le 2000 visite, ma mi sono distratto trenta secondi ed abbiamo praticamente sorpassato le 2200. Ma quanti siete là fuori?

Qualche settimana fa, in A Ciascuno I Propri Sogni, avevamo visto molto rapidamente la distinzione fra problemi P, ovvero problemi che si sanno risolvere in un tempo polinomiale (e quindi accettabile), e problemi NP, ovvero per i quali non si conosce un algoritmo di risoluzione polinomiale, pero’ non avevamo avuto il tempo di vederne uno da vicino. Il fatto é che spesso si pensa che questi “problemi” siano cose tremendamente complesse anche solo da esporre, ma la verità é che spesso si tratta di problemi facilmente riconducibili alla vita reale: ad esempio, il celeberrimo “Problema del Commesso Viaggiatore” (o, per essere cool, the Traveling Salesman Problem). L’idea di base é molto semplice: abbiamo un certo numero di città connesse fra di loro da una rete di strade, ciascuna di una certa lunghezza (per gli esperti, o per chi mi segue dai primi post, un grafo pesato) e vorremmo scoprire il cammino più corto che ci permetta di visitare tutte le città (in modo da vedere il numero maggiore di clienti nel minor tempo possibile). Bene: un problema del genere é NP, ed in alcune sue versioni addirittura NP-COMPLETO.

La cosa divertente é che, in generale, l’unico metodo per trovare la soluzione migliore é anche il più semplice che si possa pensare: si prendono tutti i cammini possibili, e li si valuta uno per uno. Per comprendere l’inefficienza di un simile metodo, di solito si considera il caso in cui ogni città sia collegata ad ogni altra città: due rapidi calcoli ci mostrano che, considerando n città, dovremo passare in rassegna n! cammini (n fattoriale, ovvero n*(n-1)*(n-2)*…*1). Giocherellando un po’ con la calcolatrice si scopre quanto rapidamente crescono i cammini: per 100 città tutte connesse fra loro, abbiamo circa 10158 cammini. 101 città, e siamo già a 10160 (ovvero 100 volte tanti). Questi sono i casi peggiori, chiaramente, ma anche se non tutte le città sono connesse fra loro questi ordini di grandezza tendono a rimanere.

Questo é, praticamente, tutto quello che si puo’ dire su questo problema se cerchiamo la soluzione migliore. Ma (e finalmente entriamo nel vivo del post) cosa succederebbe se, al posto di quella migliore, cercassimo semplicemente un’ottima soluzione (ovvero, non il cammino migliore, ma qualcosa che ci vada vicino)? Ed ecco l’idea geniale: visto che sono due settimane che discutiamo solo di genetica, perché non ispirarci alla Natura per risolvere il problema? Perché non cercare di sfruttare il meccanismo della selezione naturale? Approfondiamo quest’idea: dobbiamo trovare una maniera di far evolvere una “popolazione” di possibili soluzioni in modo che le migliori sopravvivano meglio, in modo da ritrovarci, dopo qualche “generazione”, con le migliori soluzioni molto più numerose all’interno della popolazione.

Andiamo per piccoli passi: prima di tutto, come primo passo, bisogna trovare un modo di rappresentare l’informazione genetica. In questo caso é semplice: come sequenza di geni possiamo considerare una sequenza di città da visitare in un dato ordine. Ad esempio, supponendo di avere 6 città che identifichiamo con le lettere maiuscole da A ad F, un dato individuo potrebbe essere identificato dal genoma FCBADE. La nostra popolazione iniziale, quindi, sarà data da un certo numero di individui con un genoma completamente casuale. Chiaramente, non é detto che questo genoma identifichi un percorso che passi per tutte le città: potremmo avere, ad esempio, ACEBED, ovvero un percorso che passa due volte dalla città E e mai dalla F. Meglio tenerlo a mente.

Ora che abbiamo la popolazione iniziale, dobbiamo farla evolvere: ciclicamente, tutti gli individui, a coppie, danno vita ad uno o più figli, il cui corredo genetico, ad esempio, puo’ essere dato dall’unione dei corredi dei due genitori tramite un semplice meccanismo di crossing over (visto nel post precedente): le due sequenze di DNA si spezzano in un dato punto, e la prima parte del primo genitore si unisce alla seconda parte del secondo genitore, dando vita al figlio. Un punto essenziale da ricordarsi in questo passo é includere una qualche mutazione: ogni tanto alcuni figli hanno la possibilità di ricevere un genoma cambiato in un dato punto in maniera completamente casuale. Per concludere, poi, dobbiamo ricordarci di dare una sfoltita alla nostra popolazione (eventualmente partendo dai più anziani).

Il nostro “algoritmo genetico” (ed il nome ufficiale é proprio questo) é quasi completo: ci manca solo un modo per far si che gli individui che rappresentano le soluzioni migliori sopravvivano di più e facciano più figli. Ricordandoci che la selezione non opera direttamente sul genoma, ma sui suoi effetti a livello macroscopico, dobbiamo trovare un qualche indice che ci permetta di distinguere soluzioni buone da soluzioni cattive. In questo caso ne possiamo trovare addirittura due, e li dobbiamo usare insieme: il primo deve misurare la lunghezza del percorso identificato dal genoma, mentre il secondo la percentuale di città visitate (questo é semplice: facciamo il rapporto tra le città presenti nel DNA ed il numero totali di città). Ogni volta che deve nascere un figlio o morire un individuo, usiamo questi coefficienti per favorire quelli che preferiamo. In conclusione (e lo so che adorate queste due parole):

  1. Generiamo casualmente un certo numero di individui.
  2. Ciascuna coppia genera un figlio con una probabilità che dipende dai coefficienti di “adattabilità” visti prima (con mutazioni casuali).
  3. Gli individui più anziani hanno una probabilità di morire proporzionale agli stessi coefficienti.
  4. Si ritorna al punto 2.

E si va avanti per un certo numero di generazioni. La cosa sorprendente é che la soluzione trovata (la sequenza genetica più presente nella popolazione finale) sarà, in media, del 2/3% distante dalla soluzione migliore! A questo punto manca solo di implementare l’algoritmo in un vero linguaggio di programmazione. Ma non voglio fare tutto io. 😀

Annunci

3 Risposte to “Prendendo Ispirazione”

  1. vfede said

    e questo è sicuramente il post più interessante del blog…mi ero completamente dimenticato di quella volta che me ne avevi parlato. ora chi se lo scorda più invece!
    domanda:la coppia di genitori è scelta casualmente? e se come in natura si implementassero…i “corteggiamenti”? 😀 XD

    vf

  2. scardax said

    Grazie!
    La coppia di genitori é a scelta dell’implementazione, puoi anche prendere il primo ed il secondo, il terzo ed il quarto e cosi via! 😉

  3. vfede said

    con corteggiamenti intendevo che le coppie si scelgono in base alla loro “forza” genetica…cioè le femmine si accoppiano solo con maschi che hanno vinto i corteggiamenti, cioè sono migliori dei perdenti…ma forse è gia implementato in qualche modo in quell’algoritmo..

    vf

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

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