1) Ottimizziamo!
Ed ottimizzazione sia. In principio è il nulla, o quantomeno è una lunghissima catena di basi nucleiche ACTG che si accoppiano a due a due. Come fossero istruzioni di montaggio, questa chilometrica stringa caratterizza fin nei minimi dettagli ciò che sarà dell?organismo che da queste istruzioni prenderà vita: la capacità di produrre certi enzimi digestivi, la capacità di spostarsi e a che velocità , il colore degli occhi ammesso che ne abbia?

1) Ottimizziamo!
Ed ottimizzazione sia. In principio è il nulla, o quantomeno è una lunghissima catena di basi nucleiche ACTG che si accoppiano a due a due. Come fossero istruzioni di montaggio, questa chilometrica stringa caratterizza fin nei minimi dettagli ciò che sarà dell?organismo che da queste istruzioni prenderà vita: la capacità di produrre certi enzimi digestivi, la capacità di spostarsi e a che velocità , il colore degli occhi ammesso che ne abbia?

Più o meno, tutti ormai sappiamo cosa sia il DNA e a cosa serva. Sappiamo anche che è meccanismo e tramite per l??evoluzione?, ma forse non ci siamo mai chiesti esattamente cosa questo significhi. Infatti il meccanismo evolutivo naturale è soprattutto una forma di ottimizzazione, anche se questa non è la prima cosa che ci viene in mente quando ne parliamo.

Però, che cosa si intende per ottimizzazione? Si prenda una scatola nera con tanti ingressi ed una uscita, ovvero un modo più visuale di rappresentare una funzione ad N variabili. ?Ottimizzare? la funzione vuol dire scoprire per quale configurazione dei valori di ingresso l?uscita sia massima (o minima, a seconda del problema).
Ad esempio, potrebbe essere un circuito elettrico del quale non sappiamo nulla tranne che, applicando delle tensioni agli N ingressi, all?uscita abbiamo una tensione che dipende da questi. Oppure un complesso software che progetta automobili in base a migliaia di parametri che gli vengono forniti. Orbene, nel caso del nostro circuito elettrico la matematica classica ci insegna che ci sono un sacco di tecniche per scoprire che tensioni applicare in ingresso per ottenere una tensione massima in uscita, ma solitamente bisogna avere almeno una vaga idea di cosa ci sia nella scatola. Nel secondo caso, quello del programma che progetta automobili, l?idea di ottenere ?la migliore automobile possibile? sembrerebbe addirittura paradossale, vista la variabilità di tutti i possibili parametri?

Insomma, ottimizzare un sistema di funzioni lineari vincolate mediante il metodo cosiddetto ?del simplesso? è estremamente diverso dal trovare massimi e minimi di una funzione differenziale N-dimensionale o di una funzione armonica, che non ha massimi assoluti ma ne ha infiniti relativi?

D?altro canto, se consideriamo una formica, un gatto, un pipistrello o l?uomo stesso come il risultato di una ottimizzazione, ovvero di un adattamento evolutivo durato milioni di anni, ci rendiamo conto del brulicare di un processo dalla potenza pressoché inimmaginabile: le forme di vita che popolano la terra ? anche le più semplici ? mediante l??evoluzione? si sono adattate a climi, lavori, situazioni estreme, in base a migliaia di parametri e senza formalismi matematici a proposito della loro ?struttura interna?. Ci deve essere qualcosa di molto interessante in questo ?meccanismo evolutivo??

2) Ladies and Gentlemen, the Genetic Algorithm!
E allora proviamo a rifarlo con un calcolatore. Prendiamo una funzione qualsiasi a patto di essere in grado, dati i valori di ingresso, di calcolarne il valore in uscita. Generiamo casualmente degli input, calcoliamo quanto vale la nostra funzione e diamo un voto (chiamato ?fitness?) a questa configurazione: più la funzione è ottimizzata rispetto alle nostre esigenze, maggiore è il voto di questa sequenza di valori casuali di ingresso, che altro non sono se non una sorta di DNA virtuale.

Ripetiamo questo procedimento svariate volte, in modo da avere una ?popolazione? di sequenze di input, ognuna con il suo voto.
Chiamiamo ?individuo? ognuna di queste sequenze. Infine lasciamo che gli ?individui? migliori si accoppino e generino dei figli. Ben presto vedremo il voto medio della popolazione crescere.

Stiamo massimizzando la nostra funzione, senza avere alcuna idea a proposito della complessità della stessa. Il risultato è abbastanza sorprendente, se si considera che l?ottimizzazione di funzioni non lineari ? prima che arrivassero questi benedetti computer ? è stata una delle bestie nere dei matematici di tutti i tempi. No?

Ma cosa vuol dire ?generare dei figli?? Molto semplicemente, si prendono due individui ? i genitori ? e si imita la Natura, Primo Calcolatore Immobile: come con il DNA, si sceglie un punto a caso e si scambia la ?testa? della prima sequenza di valori con la ?testa? della seconda.

Si ottengono così due ?figli?: il primo ha una sequenza di valori iniziale uguale a quella del primo genitore e una sequenza finale ? una ?coda? ? uguale a quella dell?altro genitore; il secondo figlio è speculare. Non tutti gli individui generano dei figli: come in natura, i genitori figliano con una probabilità direttamente proporzionale alla propria fitness.

Gli individui con un basso voto molto difficilmente procreeranno: il loro pessimo DNA si perderà nel nulla. In natura questi individui spesso sono addirittura sterili. Gli individui migliori al contrario tenderanno ad avere una prole numerosa e i loro figli si scambieranno vicendevolmente pezzi di ottimo materiale genetico.

Occasionalmente, potranno essere introdotti altri ?operatori genetici? oltre al Crossover appena descritto; ad esempio, la Mutazione cambia un valore a caso in un punto a caso del codice genetico ed è utilissima per uscire da situazioni stagnanti come il ?cretinismo valligiano? che, tecnicamente, è un minimo locale di funzione dovuto ai continui accoppiamenti tra parenti (lo facevano anche i nobili, comunque? non si può dire che il Principe Carlo sia un bell?uomo, no?).

Ed ora che tutto è più chiaro, le presentazioni: questo procedimento è noto come Algoritmo Genetico (Genetic Algorithm, GA, o a volte al plurale ?Algorithms?) e lo incontreremo molte volte, qui su Ghost In The Machine.

3) Applicazioni?
Senza stare a tediare il lettore con noiose argomentazioni matematiche volte a dimostrare quanto il sopraccitato meccanismo sia inaspettatamente efficiente (possibile che dal caso scaturisca un simile miracolo?) diamo il via al brainstorming ? siamo o no su Idearium? ? e, ricordandoci che possiamo ottimizzare pressoché qualsiasi cosa, andiamo ad incominciare:

Design Evolutivo e Cucina Creativa: se davvero tutto quello che dobbiamo essere capaci di fare per ottimizzare una funzione mediante algoritmi genetici è poter dare un voto ad una certa configurazione dei parametri di ingresso, possiamo pensare di utilizzare addirittura le funzioni di giudizio più elevate ? la percezione estetica umana, ad esempio, o i sensi come olfatto e gusto ? ed ipotizzare il seguente procedimento: descriviamo parametricamente una sedia, una conchiglia, la forma della carrozzeria di una automobile o un profumo e applichiamo i GA; otterremo una popolazione inizialmente casuale di sedie, conchiglie, carrozzerie e puzze tremende generate da un computer. A questo punto, per ogni individuo noi decidiamo quanto è bello o piacevole? ovvero operiamo a livello soggettivo la valutazione della funzione di fitness, lasciando all?algoritmo genetico il compito di generare istanze sempre nuove che, per loro natura, evolveranno via via verso qualcosa di sempre più appagante per i nostri sensi.

Non può funzionare? Allora non funzionano neanche Gliftic, su www.ransen.com, o generatori di textures come AlienSkin, mentre tutti i paper sul Design Evolutivo che potete trovare facilmente in Rete sono improbabili invenzioni.

In una applicazione che potemmo chiamare EEC (Extreme Evolutionary Cooking) si potrebbero generare geneticamente delle ricette di cucina, dove i parametri di ingresso sarebbero ingredienti, tempi e modi di cottura, ed il risultato sarebbero centinaia di manicaretti. Il problema in questa applicazione consisterebbe probabilmente nell?assaggiare e votare ad una ad una centinaia di pietanze per la maggior parte non molto appetitose? ma non è da escludersi che il pane, la birra, il vino e molti altri cibi siano stati inventati in un modo simile a questo.

Robotica e Simpatici Animaletti: non vogliamo bruciare le tappe, ma usare gli Algoritmi Genetici per fare evolvere forme di vita virtuale all?interno (?) di un computer è cosa ormai ampiamente nota e collaudata.

Nella prossima puntata (FILES) di Ghost In The Machine vedremo come ricreare tra le mura domestiche gli animali virtuali di Karl Sims, forse una delle più impressionanti dimostrazioni della potenza delle tecniche di Soft Computing mai sviluppate.
Per ora basti sapere che gli Algoritmi Genetici sono stati utilizzati con successo per fare evolvere i sistemi di controllo di robot più o meno antropomorfi in grado di camminare, saltare, nuotare, strisciare? la Scuola Superiore Sant?Anna di Pisa è in questo ambito un orgoglio nazionale.

Orari: sembrerebbe semplice stilare un orario scolastico, o una tabella di orari dei trasporti? invece sussistono centinaia di vincoli, date le risorse intrinsecamente limitate di questo ambito di problemi. Numero fisso di aule, laboratori, palestre, professori senza il dono dell?ubiquità , turni da gestire, giorni di riposo da rispettare, numero di classi variabile di anno in anno? se si considera la matrice classi/tempo di un orario scolastico e la si immagina esplosa per righe, si ottiene una stringa di valori suscettibili di essere utilizzati come DNA in un algoritmo genetico, dove la funzione di fitness da ottimizzare è la minimizzazione del numero degli errori?ancora una volta, alcuni minuti di calcolo possono farci passare da una popolazione di orari inaccettabili ad orari con pochissimi errori.
Qui si rivela il Tallone di Achille dei GA: al contrario dei metodi formali-matematici di ottimizzazione, che tipicamente forniscono soluzioni esatte dopo un certo tempo di calcolo, un GA aumenterebbe la fitness di un simile problema non-continuo molto velocemente ma potrebbe non trovare mai una soluzione con zero errori? anche perché questa soluzione potrebbe non esistere. In queste applicazioni discrete è quindi spesso richiesto un intervento finale da parte di un umano per mettere le cose a posto definitivamente usando l?intelligenza che, ancora, alle macchine manca.

Hands On!
E per l?Idearium Reader che non si accontenta di leggere ma vuole anche sperimentare, ecco il consiglio di Ghost In The Machine: trovate, scaricatevi e installatevi il GA Playground di Ariel Dolan (http://www.aridolan.com/ofiles/ga/gaa/gaa.aspx - NB: dovete avere installato Java). Contiene decine di esempi commentati, dai più semplici fino ai classici della teoria della complessità (come il Problema del Commesso Viaggiatore: date N città da visitare e date le distanze tra una e l?altra, quale è la strada migliore?) risolti mediante Algoritmi Genetici. Se nutrite ancora qualche dubbio, questo è il momento di fugarlo? anche perché quello che vedremo nella prossima puntata richiede una fede cieca nella potenza degli Algoritmi Genetici!

Happy Breeding!