Gli algoritmi genetici consentono a generazioni di regole di convergere verso la soluzione di un problema, mostrando una capacità veramente interessante: sono in grado di apprendere dall'esperienza.

Gli algoritmi genetici si basano su alcuni concetti tipici della teoria dell'evoluzione:

1) Le regole buone hanno maggiore probabilità di riprodursi;

2) avviene casualmente un miscuglio di configurazioni;

3) esiste una funzione di valutazione della bontà di una regola.

Prendiamo ad esempio un sistema semplice, un animale si muove in un mondo in cui sono presenti alberi e cibo; quando una regola produce un movimento che porta l'animale su un albero questa viene penalizzata, quando una regola porta l'animale sul cibo viene premiata; premi e penalizzazioni producono l'effetto che le regole premiate si riproducono maggiormente delle regole penalizzate, inoltre vengono generate anche delle regole miscuglio, ovvero con mutazioni nella configurazione.

Un sistema del genere può essere simulato al calcolatore e presenta le seguenti interessanti caratteristiche:

1) L`animale impara a dirigersi sul cibo;

2) Le regole tendono a stabilizzarsi dopo un certo tempo;

3) Il sistema è completamente analizzabile nelle sue parti e nelle regole che genera.

È possibile migliorare le prestazioni di tali algoritmi introducendo il concetto di somiglianza. Il concetto di somiglianza consente di costruire delle classi che, ad un maggiore livello di astrazione, consentono di attribuire globalmente i premi e le penalizzazioni. Il concetto di somiglianza consente di costruire livelli successivi di astrazione sui dati originari.

Altri metodi di apprendimento si basano sulle reti neurali in cui ogni elemento della rete è collegato ad altri tramite “pesi” che vengono calibrati dall`esperienza. Anche questi metodi possono essere simulati al calcolatore.

Ma torniamo agli algoritmi genetici. Gli algoritmi genetici funzionano utilizzando una funzione che misura la bontà delle regole relativamente ad un certo obiettivo, ovviamente l'informazione contenuta in tale funzione è di estrema rilevanza. Per fare un esempio istruttivo, consideriamo un piano inclinato e delle palline sul piano stesso. Come prima considerazione si può immaginare che le palline rotoleranno lungo il piano inclinato da una posizione più alta ad una posizione più bassa conformemente alla legge di gravità. Introduciamo ora nuove considerazioni: supponiamo che il piano inclinato sia formato da una serie di microscopici avvallamenti concavi in cui le palline, anch'esse microscopiche, possano alloggiare; supponiamo inoltre che tutto il sistema sia immerso in un gas che fornisce, tramite urti casuali, una certa energia alle singole palline. Se gli urti a cui sono soggette le palline è sufficiente, per esempio in almeno in un terzo dei casi, a spostare una pallina da una posizione più a valle ad una posizione più a monte, allora un certo numero di palline si sposteranno nella direzione opposta alla legge di gravità, verosimilmente un numero di palline, proporzionale ad 1/3 elevato al numero di passi necessari, raggiungerà la cima del piano inclinato.

Questo numero appare estremamente esiguo, ma consideriamo il caso in cui, per una qualche legge particolare, le palline si possano riprodurre, e che si riproducano in maniera proporzionale all'altezza raggiunta sul piano in ragione maggiore di 1/3; cioè, una pallina che sale di un gradino ne genera più di tre. In tal caso le palline che salgono aumentano di numero e l'effetto complessivo finale consisterà in una percentuale significativa di palline che risalgono il piano inclinato. Per convincersi di questo fatto è sufficiente considerare una pallina che sale casualmente di un gradino, la probabilità di essere soggetta ad un nuovo urto positivo, che produce, cioè, l'effetto di farla salire di un ulteriore gradino è di 1/3, per ipotesi; ma essa genera più di tre palline, pertanto almeno una di esse - statisticamente parlando -, si trova nella condizione in cui un urto la farà salire di un ulteriore gradino, e il ciclo si ripeterà; se, di più, imponiamo che il numero di palline complessive in ogni generazione si debba mantenere costante, allora come effetto finale otterremo che la maggioranza delle palline, dopo successive generazioni, si trova in cima al piano inclinato. Il meccanismo descritto presenta alcune caratteristiche tipiche delle funzionalità degli algoritmi genetici.

In un algoritmo genetico, tipicamente, una configurazione viene associata ad una azione; la correttezza di tale regola rispetto ad un problema da risolvere viene premiata sia a livello di “peso” della regola, sia con maggiori probabilità di riproduzione della regola stessa. Elementi importanti sono le mutazioni, variazioni casuali delle regole, che consentono di sondare regole casualmente migliori rispetto alle regole generatrici.

Le regole vengono attivate in un determinato ambiente con caratteristiche tali da “premiare” o “punire” le regole stesse: la bontà di una azione rispetto ad una determinata configurazione avviene tramite una funzione di valutazione. È possibile tenere conto di vincoli presenti sul sistema; tali vincoli possono essere inglobati nella funzione di valutazione stessa.

Il meccanismo con cui il sistema procede verso una soluzione del problema risulta relativamente semplice.

È dimostrato che il sistema converge in maniera esponenziale: teorema fondamentale degli algoritmi genetici. È interessante affrontare con questi algoritmi problemi concreti; per esempio, la preparazione di un orario scolastico. Il problema degli orari scolastici è relativamente ben definito: si tratta di determinare una particolare combinazione di ore di insegnamento distribuite su un certo numero di classi.

Il problema è quindi un problema combinatoriale in cui il numero di permutazioni che si possono analizzare è enorme, in particolare è tale per cui una scansione di tutte le possibili combinazioni non può essere effettuata nella pratica nemmeno da potenti elaboratori.

Dal punto di vista degli algoritmi genetici il problema si pone nel modo seguente:

1) analisi di una generazione iniziale di permutazioni;

2) valutazione delle configurazioni sulla base dei vincoli imposti;

3) premiazione e riproduzione delle configurazioni migliori;

4) analisi della generazione prodotta;

5) nel caso in cui venga trovata una soluzione compatibile con tutti i vincoli, il processo si arresta, altrimenti viene ripetuto.

Occorre analizzare la velocità di convergenza del metodo, in particolare, le probabilità ed i premi relativi affinché l'algoritmo si presenti come un “gioco equo”. In altri termini, i “premi” debbono essere una funzione della probabilità legata alla creazione di una configurazione “buona”. In ogni caso, non è detto che le famiglie che si riproducono maggiormente contengano la soluzione cercata. Certamente evolveranno verso configurazioni con alti valori della funzione di valutazione; questo non è sufficiente a garantire che la combinazione cercata appartenga alle famiglie selezionate. Inoltre, il processo, fondamentalmente casuale, di creazione delle configurazioni non promette il sostanziale miglioramento sperato nei tempi di esecuzione.

Occorre introdurre criteri aggiuntivi legati alla struttura delle configurazioni medesime, in particolare:

1) una creazione di configurazioni che sia fin dall'inizio compatibile con i principali vincoli (locali);

2) una stabilità maggiore per configurazioni che sono soluzione in sottosistemi per il problema completo;

3) una sostanziale “estinzione di massa” per configurazioni buone che, dopo una determinato tempo, non producono la soluzione cercata.

Analizzando questi punti è possibile arrivare alle seguenti considerazioni:

1) il principio di generazione casuale delle configurazioni, anche se pilotato da “regole locali”;

2) il principio di risoluzione tramite utilizzo di soluzioni a sottoproblemi;

3) il principio di ritorno su scelte prese in precedenza (back-tracking).

È facile riconoscervi alcuni criteri solitamente utilizzati nella programmazione di sistemi di intelligenza artificiale. Approcci differenti portano a medesimi criteri.

Data articolo: luglio 2007