Gli algoritmi genetici fanno parte della classe più grande di algoritmi evolutivi, ossia sistemi per la risoluzione di alcuni tipi di problemi mediante l‘uso del calcolatore. In questo articolo si presenterà questa classe di algoritmi, ponendo l‘attenzione sulla comparazione tra essi e gli algoritmi genetici stessi.

 

Introduzione

Gli algoritmi genetici costituiscono un sottoinsieme degli algoritmi evolutivi, termine generico che indica una gamma di sistemi di risoluzione dei problemi basati sull’utilizzo del calcolatore, affini ai processi evolutivi. Oltre agli algoritmi genetici, gli algoritmi evolutivi comprendono la Programmazione Evolutiva, le Strategie Evolutive, i Sistemi Classificatori e la Programmazione Genetica.

Algoritmi evolutivi

Gli algoritmi evolutivi sono strategie euristiche che imitano i processi di evoluzione naturale per risolvere i problemi di ricerca globale e si caratterizzano per la capacità di risolvere problemi anche con scarsa conoscenza del dominio. Tuttavia, la loro diffusione è limitata dalle difficoltà di progettazione dovute all’elevato numero di parametri da impostare e dalla necessità di utilizzare una dimensione di popolazione elevata per ottenere una buona convergenza dell’euristica in problemi di una certa difficoltà. Ne conseguono tempi elevati sia in fase di tuning dei parametri che durante l’esecuzione dell’algoritmo. Per migliorare le prestazioni degli algoritmi evolutivi possono essere usate una serie di strategie di progetto e varie tecniche di parallelizzazione.

In genere gli algoritmi utilizzati nelle discipline di Intelligenza Artificiale operano la ricerca di un massimo o di un minimo globale in uno spazio finito sulla base di vincoli sullo spazio delle soluzioni.

 

 

Da un punto di vista formale possiamo dire che, dato un elemento X appartenente a uno spazio cartesiano D (nel caso in cui n sia la cardinalità di D, allora X sarà un vettore), e data una funzione

detta funzione obiettivo, allora la ricerca dell’ottimo globale è la ricerca di un X’ che massimizza tale funzione. Fattori come la presenza di più punti di massimo locale, vincoli sul dominio D, la non linearità, possono rendere la ricerca molto difficoltosa, per cui il problema non è risolvibile in tempi accettabili. Allora si fa uso di algoritmi di tipo euristico che, pur risolvendo il problema con gradi di incertezza e non assicurando la convergenza della ricerca alla soluzione solo in casi particolari, richiedono tempi di convergenza molto minori.

 

 

Questa caratteristica porta ad una distinzione tra i metodi:

• metodi forti: sono orientati alla soluzione di un problema specifico, sulla base della conoscenza del dominio particolare e della rappresentazione interna del sistema in esame. Le buone soluzioni ottenute sono difficilmente adattabili ad altri compiti e con risultati non soddisfacenti.
• metodi deboli: utilizzano invece poca conoscenza del dominio, non sono orientati a un target specifico e risolvono una vasta gamma di problemi.

Gli algoritmi evolutivi sono algoritmi di ricerca euristici, considerati metodi deboli. Tuttavia è stata ultimamente introdotta la nuova tipologia dei metodi deboli evolutivi, metodi che hanno inizialmente poca conoscenza del dominio ma che durante la loro evoluzione acquistano maggiore consapevolezza del problema, implementando alcune caratteristiche dei metodi forti (“intelligenza emergente”)

Programmazione evolutiva

La programmazione evolutiva è stata introdotta da Fogel, Owen e Walsh: essa nasce come approccio all’intelligenza artificiale alternativo rispetto alle tecniche basate sul ragionamento simbolico. Consiste, infatti, in una strategia stocastica di ottimizzazione, simile agli algoritmi genetici, basata sulla definizione della popolazione, della funzione di fitness e della selezione dei migliori.
Il suo scopo è di far evolvere, piuttosto che definire a priori, comportamenti intelligenti, rappresentati per mezzo di automi a stati finiti: si tratta, quindi, di predire la prossima configurazione del problema.

Il metodo di base consiste in tre passi:

1. scegliere una popolazione iniziale a caso (maggiore è il numero di individui, più velocemente si arriverà alla convergenza);
2. ogni individuo viene copiato in una nuova popolazione e a ciascun figlio viene applicata una mutazione seguendo una certa probabilità;
3. viene calcolato il fitness di ogni individuo e tramite un torneo con selezione stocastica vengono scelte N possibili soluzioni;

In particolare, ogni individuo della popolazione è una Macchina a stati finiti (FSM), formata da una serie di stati interni appartenenti a un alfabeto finito. La FSM riceve in input una serie di simboli e restituisce in output una serie di stati, sulla base degli stati correnti e dell’input ricevuto. La previsione della prossima configurazione del sistema si effettua, inoltre, non attraverso l’operatore di crossover, come nel caso degli algoritmi genetici, ma affidandosi esclusivamente alla mutazione: la mutazione, infatti, altera lo stato iniziale, modifica la transizione o cambia uno stato interno. La definizione degli operatori di mutazione e ricombinazione, inoltre, è leggermente più complessa rispetto agli algoritmi genetici, in quanto deve tener conto della struttura degli oggetti che tali operatori devono manipolare.
La caratteristica fondamentale di questo tipo di algoritmi è che i figli hanno un comportamento simile a quello dei genitori.

Strategie evolutive

Le Strategie evolutive sono tecniche simili alla precedente, ma sviluppate originariamente per problemi di ingegneria civile e strutturale. La principale differenza consiste nel fatto che, in queste strategie, gli individui sono selezionati per la mutazione con una certa probabilità proporzionale alla fitness, come accade anche negli algoritmi genetici, ma in questo caso gli individui peggiori vengono scartati deterministicamente.

Il metodo di ottimizzazione si basa sulla scelta di una strategia che viene poi applicata a una popolazione. Le due principali sono note come Strategia Plus (m+l) e Strategia Comma (m,l), in cui m rappresenta il numero di individui della popolazione, mentre l rappresenta il numero di figli concepiti per ogni generazione. Nel primo caso i genitori possono partecipare alla selezione nella generazione successiva, mentre nel secondo possono essere selezionati solo i figli, quindi i genitori muoiono: questo comporta che nella strategia Plus i migliori m individui su m+l sopravvivranno e diventeranno genitori nella generazione successiva, mentre nella Comma la selezione avviene solo tra i figli.

Un individuo nella popolazione consiste di un genotipo che rappresenta un punto nello spazio di ricerca (cioè lo spazio delle possibili soluzioni). A ciascun punto vengono associate:
•    delle variabili oggetto xi sulle quali verranno applicati gli operatori di ricombinazione (crossover) e mutazione fino a che non viene raggiunta una soluzione ottima del problema;
•    delle variabili di strategia Si che determinano la mutuabilità di xi. Esse rappresentano la deviazione standard di una distribuzione Gaussiana (0,Si);

Questa strategia funziona perchè prima o poi verranno favoriti gli individui che hanno un buon valore della funzione obiettivo e che probabilmente ricombinandosi tra loro formeranno figli migliori. Il valore della funzione obiettivo f(x) rappresenta il fenotipo (fitness) di cui si terrà conto nella selezione.

I Sistemi classificatori

I Sistemi classificatori sono modelli che simulano l’apprendimento e l’evoluzione cognitiva di agenti adattivi attraverso operatori che classificano l’input ricevuto secondo una serie di regole, generando poi un output di istruzioni da eseguire.
Si basano su tre principi:

1. la conoscenza può essere espressa in termini di strutture mentali paragonabili a regole del tipo SE – ALLORA;
2. queste regole sono in competizione fra di loro e le più forti prevalgono su quelle più deboli;
3. nuove regole vengono generate, tramite l’algoritmo genetico, dalla combinazione di regole precedenti, garantendo l’evoluzione;
4. basando un sistema su questi principi, si rileva l’emergere di capacità di transfert, cioè di applicare, in situazioni diverse, le regole imparate e di auto-organizzazione della conoscenza secondo gerarchie di default, ossia con una regola generale che governa le situazioni normali e gruppi di regole che governano le situazioni eccezionali.

La Programmazione genetica

La tecnica della Programmazione genetica è simile a quella degli Algoritmi genetici; però in questo caso, la popolazione non è costituita da stringhe di bit, ma da programmi che, quando eseguiti, si evolvono, si combinano, si riproducono o mutano per dar luogo ad altri programmi che costituiscono soluzioni migliori di un determinato problema. Questi programmi vengono codificati con una struttura ad albero in cui i nodi interni sono funzioni e le foglie sono i simboli terminali del programma

Lo spazio di ricerca è costituito da tutti i programmi composti dai terminali e dalle funzioni definite per uno specifico problema.
La Programmazione Genetica ha un grado di complessità maggiore rispetto agli Algoritmi Genetici, poichè la progettazione richiede la selezione di molti più parametri, come la generazione della popolazione iniziale, l’insieme delle funzioni e terminali di base, il tipo di selezione, la dimensione della popolazione e il numero massimo di generazioni, il criterio di terminazione.
L’operatore di crossover è la forza trainante dell’algoritmo: si prendono a caso due sotto-alberi da individui selezionati in base al loro fitness e si ricombinano dando vita a due alberi figli, con parametri che fissano limiti sulla dimensione massima degli alberi della popolazione. Altri operatori, quali la mutazione, la permutazione, l’editing, l’incapsulamento e la decimazione sono usati in casi particolari. In generale, gli operatori determinano la correttezza sintattica degli alberi generati, ma non la correttezza semantica: sarà il fitness, penalizzando gli alberi che non rispettano le condizioni semantiche, a favorire la crescita di alberi semanticamente corretti.

Se gli Algoritmi Genetici ottimizzano una soluzione definita e parametrizzata dall’utente, nella Programmazione Genetica si opera a un livello superiore, poichè l’utente definisce gli elementi di una grammatica, operatori e simboli terminali, utilizzati per generare funzioni che devono evolversi. L’ottimizzazione del fitness consiste, quindi, nella manipolazione del codice stesso delle funzioni e non solo dei parametri.
L’estensione dello spazio di ricerca, definito come lo spazio di tutte le funzioni che soddisfano la grammatica definita dall’utente, e la minore efficienza della mappatura in memoria della rappresentazione utilizzata fanno sì che la programmazione genetica richieda un elevato carico computazionale e un’elevata occupazione di memoria. Ne segue un utilizzo minore rispetto agli algoritmi genetici e la necessità di realizzare un’implementazione parallela di questi algoritmi su ambienti di tipo distribuito.

Confronto con altre tecniche

Come negli algoritmi genetici, ci sono altre tecniche general purpose che operano a partire da una funzione di fitness che deve essere massimizzata; alcune di esse sono applicabili solo a domini limitati, come la programmazione dinamica, in cui la funzione di fitness è la somma delle funzioni fitness calcolate ad ogni fase del problema e non c’è interazione tra le varie fasi.
Nel Metodo del Gradiente si utilizzano le informazioni sul gradiente della funzione per guidare la direzione della ricerca. La funzione deve essere perciò continua, altrimenti non ne può essere calcolata la derivata. In generale questi metodi sono detti di hillclimbing e vengono utilizzate nel caso di funzioni con un solo picco (unimodali), meno per funzioni multimodali, nelle quali non è detto che il primo picco scalato sia il più alto.
Un esempio è mostrato in figura, dove partendo da un punto iniziale X scelto a caso, con movimenti verso l’alto viene localizzato il picco B, ma A e C non vengono trovati.

Nella Ricerca Iterata si combina il metodo del gradiente con quello della Ricerca Casuale, in cui i punti dello spazio di ricerca sono scelti a caso; trovato il picco, la scalata riparte da un altro punto scelto a caso. La tecnica ha il pregio della semplicità e dà buoni risultati con funzioni che ovviamente non hanno molti massimi locali. Tuttavia, poichè ogni prova è isolata, non si ottiene una figura complessiva della forma del dominio e, mentre la ricerca casuale progredisce, si continuano ad allocare lo stesso numero di prove sia in regioni dove sono stati trovati alti valori di fitness, sia in regioni con basso valore di fitness. Un Algoritmo Genetico, invece, opera a partire da una popolazione iniziale casuale e compie tentativi nelle regioni con più alto fitness. Potrebbe essere uno svantaggio se il massimo si trova in una piccola regione circondata da regioni con basso fitness, ma questo tipo di funzione è difficilmente ottimizzabile con qualsiasi metodo.
La tecnica del Simulated Annealing è una versione modificata dell’hillclimbing: da un punto a caso si opera un movimento casuale: se questo porta a un punto più alto, è accettato, con una probabilità p(t), dove t è il tempo. All’inizio il valore di p(t) è vicino a 1, ma tende gradualmente a zero; inizialmente ogni movimento è accettato, ma col tempo la probabilità di accettare un movimento negativo diminuisce. A volte i movimenti negativi sono necessari per evitare massimi locali, me se sono troppi possono allontanare dal massimo. In generale, questa tecnica lavora con una sola soluzione candidata per volta, non costruisce una figura complessiva dello spazio di ricerca e non sono salvate le informazioni dei precedenti movimenti per guidare verso la soluzione.

Conclusioni

In questo articolo si è fornita una panoramica generale sugli algoritmi evolutivi e su come essi sono messi in correlazione con gli algoritmi genetici. Nei prossimi articoli verrà analizzato in dettaglio un algoritmo genetico, partendo dalla pseudocodifica e spiegando ogni passaggio.

Riferimenti

[1] D.B. Fogel, “Evolutionary computation: toward a new philosophy of machine intelligence”, IEEE Press, NewYork, 1995, ISBN 078035379X

[2] J.R Koza, “Genetic programming: on the programming of computers by means of natural selection”, MIT Press, Cambridge, MA, 1992, ISBN 0262111705

[3] Alden H. Wright, “Genetic Algorithms for Real Parameter Optimization”, 1991