SlashCode

Programmazione Genetica: Le Origini

Posted on 12. Nov, 2009 by THeK3nger in AI e Neuroscienze

Se state pensando ad orrori tipo cani a due teste oppure ad un esercito di super-soldatigeneticamente modificati siete completamente fuoristrada. In informatica, e in particolare nell’intelligenza artificiale, per programmazione genetica si intende una metodologia di programmazione automatizzata ispirata dall’evoluzione biologica. Ma cosa significa? La selezione naturale si basa sulla sopravvivenza e la capacità di un essere vivente di avere capacità migliori rispetto ad un altro se sottoposto ad alcune pressioni naturali quali le caratteristiche dell’ambiente e la presenza di particolari predatori. Com’è possibile quindi trasportare tutto questo a livello di programmazione?

Ovviamente le parti in gioco sono diverse ma analoghe. Il codice genetico di un animale diventa semplicemente il codice di un particolare programma o funzione e la selezione naturale si riduce ad “avere le caratteristiche migliori”.

Così semplice? Almeno grossolanamente si. Ma se andiamo ad analizzare attentamente questi due aspetti possiamo trovarci di fronte a problematiche più sottili. Ad esmpio: come si può portare il codice di un programma ad assomigliare ad un codice genetico?

La risposta è altrettanto apparentemente semplice. Ci sono alcune caratteristiche che un programma, o meglio la sua rappresentazione, deve rispettare. Innanzitutto il programma deve poter essere “riprodotto” secondo una riproduzione sessuata, ovvero tramite crossover. Inoltre tale codice deve essere sottoposto a mutazioni casuali.

Spiegare come possano avvenire queste due cose su un programma o un algoritmo è qualcosa di piuttosto complesso che non ho la pretesa di poter spiegare qui. Forse lo farò un in qualche articolo separato. Sappiate però che l’approccio più semplice è quello di utilizzare  una struttura ad albero per rappresentare i programmi e simulare crossover e mutazioni come scambi e variazioni di sotto-alberi scelti casualmente all”interno del programma.

La cosa da fare, una volta che sappiamo come rappresentare i programmi, è di generare una popolazione iniziale. L’algoritmo procede in linea di massima così:

• Viene generata casualmente una popolazione di programmi iniziale.
• Vengono fatti funzionare tutti questi programmi e vengono raccolti i risultati.
• I risultati vengono valutati con una funzione di FITNESS.
• Il programma che ottiene il maggior punteggio di fitness passa immutato alla seconda generazione e inoltre viene utilizzato per “riprodurre” una nuova generazione di programmi usando crossover e mutazioni.
• Si torna al punto due e così via finché non viene estrapolato un programma sufficentemente valido.

La funzione di fitness è una funzione che prende in ingresso il codice genetico di un programma, lo avvia e confronta il risultato con il risultato “ideale”. Il concetto di risultato ideale è piuttosto complesso: molto spesso, infatti, non abbiamo chiara l’idea di quale sia il risultato ideale. Ma anche questo, da solo, potrebbe essere argomento di un libro. Il concetto di fondo della funzione di fitness rimane comunque valida.

Come vedete sia i termini che il procedimento ricorda molto quello che avviene in natura. Un interessante esempio di proto-programmazione genetica è narrata infatti anche nel libro di Richard Dawkins L’orologiaio cieco del 1989 in cui questo processo di selezione “informatica” viene usato dall’autore per mostrare la potenza della selezione cumulativa.

L’argomento è, onestamente, uno dei miei prefetiti e da tempo cerco di perfezionare un ambiente di programmazione genetica in Python chiamato Galapagos e spero con questo articolo di aver incuriosito qualcuno riguardo questa fascinosa metodologia di programmazione. Mi spiace parlarne così frettolosamente ma lo spazio è quello che è.

Vi lascio perciò un link nel quale potete approfondire l’argomento (in attesa che ci pensi io )

http://www.genetic-programming.org/

Tags: ai, featured, genetic programming