Sezione di Simulazioni ad agenti

A cura di: Dott. A.Cappellini, Dott. P.Mezzera , Dott. A.Vanara

Algoritmi genetici

Un classifier system è un sistema di apprendimento automatico che impara regole sintatticamente semplici, denominate classifier, per guidare le sue azioni in un ambiente arbitrario.
Tale metodologia, che viene frequentemente applicata allo studio di sistemi dinamici e all'analisi del comportamento di agenti economici, è composta - come affermato in Margarita (1992) - dai seguenti elementi:
a) un insieme di stringhe di lunghezza fissa che rappresentano le regole di comportamento; tali regole, costruite sulla base di un alfabeto ternario, sono composte da una condizione - rappresentata sotto forma di una sequenza di caratteri scelti tra i simboli {1, 0 , #}- e da una azione - costituita da una sequenza dei caratteri {1, 0}. Al valore 0 o 1 presente in ogni posizione corrisponde un particolare significato; il simbolo # viene, invece, usato come carattere jolly, con il significato di "don't care"; ad ogni classifier è associato, inoltre, un valore rappresentativo della propria forza (fitness); tale valore dipende dai risultati ottenuti effettuando l'azione suggerita dalla regola;
b) un sistema di sensori che riceve le informazioni provenienti dall'ambiente e determina quali sono i classifier da attivare; l'attivazione di una particolare regola avviene se ogni carattere della condizione è uguale a quello del messaggio proveniente dall'esterno (oppure al carattere #); in uno stesso momento più regole possono 'unire' la descrizione delle informazioni provenienti dall'ambiente con la propria condizione;
c) un sistema di asta che determina quale dei classifier attivati agisce effettivamente; i classifier che vengono eseguiti possono a loro volta attivare altri classifier oppure produrre un'azione rivolta all'esterno; il classifier che viene selezionato per 'attuare' la propria azione paga un importo, proporzionale al proprio patrimonio, che viene ripartito tra i classifier che lo hanno attivato, contribuendo così ad aumentarne il valore (bucket brigade algorithm); in questo modo ciascuna regola può aumentare il proprio patrimonio sia perché ha potuto agire sull'ambiente in modo giudicato positivo, sia perché ha permesso l'attivazione di un'altra regola.
d) un sistema contabile che aggiorna il valore del patrimonio dei singoli classifier sulla base dei premi che vengono percepiti in seguito alle decisioni prese;
e) un algoritmo genetico che introduce nel sistema nuovi set di regole in sostituzione di quelle vecchie; l'algoritmo, che viene generalmente attivato quando un messaggio in entrata non corrisponde a nessuno dei classifier presenti nel sistema, consente di operare sull'insieme di regole le seguenti operazioni:
- diversificazione: se in risposta ad un messaggio proveniente dall'ambiente tutti i classifier rispondono con la medesima azione, viene creato una nuova regola con stessa condizione e diversa azione in sostituzione di un classifier a bassa fitness allo scopo di mantenere un adeguato livello di diversità delle azioni da compiere in una data situazione;
- creazione: quando nessuna condizione "unisce" il messaggio ricevuto dall'ambiente, viene creata un nuova regola che ha per condizione il messaggio ricevuto; l'azione, invece, viene scelta casualmente; tale regola va a sostituire un classifier, già esistente, con un basso valore di patrimonio;
- generalizzazione: attivata con probabilità decrescente nel tempo, determina la nascita di due nuovi classifier, mediante crossover applicato a due regole scelte casualmente tra quelle a più elevata fitness; alle regole generate viene assegnato un patrimonio pari alla media di quello delle regole "generatrici". I classifier così creati, prendono il posto nella popolazione di due classifier, scelti casualmente tra quelli a bassa fitness;
- specializzazione: quando è stata determinata la regola da attivare, con probabilità decrescente nel tempo, si applica - allo scopo di creare una regola più specializzata - una mutazione dei caratteri # della condizione, in modo da trasformarli, con una certa probabilità in 0 o 1.

Le capacità di adattamento del classifier system dipendono dallo sviluppo di individui semplici e diversi tra loro specializzati nell'affrontare situazioni particolari. Rispetto agli algoritmi genetici, tali modelli evolutivi producono strategie - consistenti nell'insieme di regole che vengono fatte evolvere - in modo maggiormente esplicito.
Come affermato in Ferraris (2000), i classifier system possono essere utilizzati per descrivere i processi mentali degli agenti nell'ambito delle simulazioni ABM; questa impostazione si basa sulla considerazione che ogni individuo possa avere nella sua mente con riferimento ad uno stesso problema diverse strategie di soluzione reputate praticabili ; i metodi evolutivi intervengono sia nella scelta della strategia migliore che nella produzione di nuove strategie.

torna alla pagina principale della sezione

torna alla home...