| Sezione
di Simulazioni ad agenti
A cura di: Dott.
A.Cappellini, Dott. P.Mezzera , Dott. A.Vanara
Algoritmi genetici
Gli algoritmi genetici sono algoritmi di ricerca basati sui meccanismi di selezione
naturale e sulla genetica. Integrano un principio di sopravvivenza della struttura
maggiormente adatta all'ambiente con un meccanismo di scambio di informazioni,
strutturato ma stocastico, per formare un algoritmo di ricerca che presenta
un po' dell'intuito innovativo insito nella ricerca umana.
Ispirati alla teoria evoluzionistica dei sistemi biologici, gli algoritmi genetici
sono meccanismi di calcolo, altamente paralleli, che trasformano popolazioni
di oggetti matematici individuali, in genere sequenze binarie di lunghezza fissa,
in nuove popolazioni utilizzando operatori mutuati dalle operazioni genetiche
naturali come la riproduzione sessuata e la riproduzione proporzionale al grado
di adattamento.
Il meccanismo di base tipico degli algoritmi genetici prevede le seguenti fasi:
a) generazione della popolazione: sulla base della rappresentazione del problema
che è stata definita viene creata (generalmente in modo casuale) una
popolazione iniziale composta di un certo numero di individui; ciascun individuo,
creato in modo indipendente dagli altri, viene rappresentato come una combinazione
di valori binari (stringa o genotipo), in numero sufficiente a contenere tutta
la conoscenza che risulta necessaria a descrivere un qualche tipo di processo
o di strategia;
b) valutazione degli individui: ad ogni individuo è associato un valore,
rappresentativo del grado di adattamento alla funzione da svolgere nell'ambiente
(fitness); il valore della fitness, calcolato in base ai risultati ottenuti
applicando la strategia di cui è portatore l'individuo, è di fondamentale
importanza, per la successiva selezione degli individui ai fini della riproduzione;
c) riproduzione: in questa fase avviene la selezione degli individui della popolazione
e la definizione della tecnica di riproduzione vera e propria; l'obiettivo della
selezione è di conferire maggiori probabilità di riproduzione
agli individui che hanno il più elevato grado di adattamento; la tecnica
generalmente utilizzata è la roulette wheel selection che assicura ad
ogni individuo una probabilità di riproduzione proporzionale alla propria
fitness; in questa fase vengono, anche, definiti gli aspetti quantitativi della
riproduzione; in particolare viene stabilito se è l'intera popolazione
che viene sostituita da una generazione all'altra o se, invece, sono soltanto
alcuni individui che nascono e vanno a sostituire quelli della generazione precedente;
d) applicazione degli operatori genetici: mediante le tecniche di crossover
e di mutazione vengono fatti nascere nuovi individui, non presenti nella popolazione
iniziale (viene esplorato lo spazio delle soluzioni); il crossover, spesso assimilato
alla riproduzione sessuata, agisce condizionatamente ad una data probabilità
e coinvolge due individui, denominati 'genitori', che fanno confluire il loro
patrimonio genetico creando così due nuovi discendenti; il crossover
si basa sull'individuazione, in modo casuale, di una posizione qualunque interna
alla stringa in cui avverrà la scissione del patrimonio genetico dei
due individui e sul successivo scambio delle due sottosequenze successive (o
precedenti) a tale posizione ; la mutazione, invece, simula gli errori di copia
e trasmissione del patrimonio genetico da una generazione ad un'altra e consiste
nel cambiamento condizionato ad una data probabilità del valore presente
nelle singole posizioni della stringa degli individui;
e) ripetizione del ciclo per un certo numero di generazioni.
Gli algoritmi genetici, formalizzati in Holland (1975), hanno ricevuto negli
ultimi anni una notevole attenzione da parte degli studiosi di scienze sociali
e di economia.
Il crescente interesse verso tale metodologia può essere attribuito alla
estrema generalità del loro approccio e al notevole potenziale applicativo.
Gli algoritmi genetici possono essere utilizzati, infatti - grazie all'elevato
grado di parallelismo che li caratterizza (e alla capacità di esplorazione
intelligente dello spazio delle soluzioni) - per la soluzione di problemi di
ottimizzazione numerica e di ricerca combinatoria, ma anche - data la completa
assenza di requisiti sulla natura e struttura del problema da risolvere e dell'eventuale
funzione sottostante - come un efficace strumento per la costruzione di agenti
"adattivi" nell'ambito dei modelli ABM.
torna alla
pagina principale della sezione
torna
alla home...
|
