6
1978) o mantengono solo legami molto labili, più che altro nominali. E'
questo il caso dell'apprendimento automatico (AA), un vettore in rapida
crescita, intrinsicamente multidisciplinare, ammettendo contributi che
vanno dall'ottimizzazione combinatoria alla teoria dei sistemi, dal controllo
automatico alle logiche non-standard, ma che ha vissuto un legame con la
psicologia cognitiva principalmente di riflesso, inserendosi nei grandi temi
tipici dell'IA della rappresentazione e dell'elaborazione della conoscenza.
I continui contributi all'AA di natura cognitiva infatti hanno finora
avuto ben pochi riferimenti applicativi (Schank, 1977; Nosofsky, 1992),
soprattutto per quanto riguarda l'attualissimo tema dell'apprendimento di
sequenze senso-motorie e più in generale dell'apprendimento tramite
rinforzo (o non supervisionato: URL, unsupervised reinforcement learning).
L'URL infatti è cresciuto e ha proposto principalmente due approcci
algoritmici: uno derivato dalla programmazione dinamica (Q-learning,
Watkins, 1989; Differenze Temporali, Sutton,1990) e uno da
ottimizzazione globale/regole di produzione (LCS, Holland, 1986).
Entrambi questi algoritmi si sono dimostrati efficaci nel risolvere compiti
semplici, ma hanno prestazioni sempre meno soddisfacenti al crescere della
complessità del problema affrontato (Maltoni, 1994). Questo è in parte
dovuto alle difficoltà intrinseche a questi algoritmi nell'individuazione di
lunghe catene decisionali (Matthew, McDonald, Hingston, 1995) e quindi
nel gestire sistemi non vicini allo schema Stimolo/Risposta (S/R). Alcuni
ben noti problemi riguardano infatti la difficoltà di costruzione e
mantenimento di catene decisionali, la necessità di rinforzare esplicitamente
i sotto-obiettivi e quindi di decomporre a priori i compiti da risolvere.
L’apprendimento rinforzato deriva dagli studi fatti
sull'apprendimento animale nella psicologia comportamentale. L'idea di
base di questo termine e il corrispondente paradigma di apprendimento, è
che, se un'azione è seguita da una situazione soddisfacente o da un
miglioramento dello stato attuale, allora la tendenza a scegliere quell'azione
è maggiore, cioè rinforzata (Barto, 1992). Come vedremo in seguito, il
senso di "essere seguita da una situazione soddisfacente" è esteso per
includere le conseguenze a lungo termine delle azioni. In figura 1.1 viene
illustrato uno schema del paradigma del reinforcement learning.
7
figura 1.1-paradigma dell'apprendimento rinforzato
L'agente ottiene informazioni sullo stato dell'ambiente tramite i
propri sensori, ed esegue le azioni attraverso gli attuatori. Ad ogni passo, di
un tempo discreto, l'agente osserva il corrente stato dell'ambiente e genera
un'azione in accordo con la sua politica decisionale. Di conseguenza
l'agente riceve un premio, anche chiamato payoff o reward, e viene eseguita
una transizione di stato. Il premio è usato per modificare la politica
decisionale dell'agente in accordo con alcuni algoritmi RL. In generale, sia i
premi che le transizioni di stato possono essere stocastici. L'agente non
conosce nè le probabilità di transizione, nè i valori di rinforzo attesi per una
qualsiasi combinazione stato-azione. Le azioni eseguite dall'agente
influenzano non solo i premi immediati, ma anche gli stati successivi quindi
tutti i reward futuri. L'obiettivo dell'apprendimento è di generare una
politica decisionale (una corrispondenza tra gli stati e le azioni) che
massimizzi valori di rinforzo ricevuti dall'agente a lungo termine.
Tutto ciò che l'agente conosce del mondo esterno è contenuto in una
serie di variabili di stato e premi. Non è detto che le azioni effettuate in un
particolare stato siano le migliori in quella situazione. L'agente non conosce
Algoritmo RL
Politica decisionale
Sensori
Meccanismo di
rinforzo
Attuatori
Stato
informativo
modifiche
agente
azioni
premio
8
se (e quanto) le azioni passate influenzino i premi ricevuti. Questo rende
l'apprendimento rinforzato complicato e stimolante.
I rewards sono generati in base alle azioni dell'agente e in base agli
stati nei quali le azioni sono eseguite, secondo alcuni meccanismi di
rinforzo. Si suppone, generalmente, che il meccanismo di rinforzo è una
parte dell'ambiente, cioè l'agente è premiato o punito dal suo ambiente. Tale
punto di vista enfatizza certe analogie con l'apprendimento animale. Per
programmare un agente con apprendimento rinforzato in modo che svolga
un compito, è necessario:
• progettare un'appropriata rappresentazione delle azioni e degli input
(strutture dati nella programmazione tradizionale),
• progettare un meccanismo di rinforzo specificando l'obiettivo del
compito (algoritmo).
Il RL richiede meno sforzo di altri approcci, dato che non ritiene
necessario fornire all'agente una teoria del suo dominio (ambiente). Questa
è una buona ragione affinché il reinforcement learning venga utilizzato
nella progettazione dei sistemi intelligenti. Un'altra caratteristica attraente è
la natura incrementale del RL: l'agente apprende continuamente mentre
esegue il suo compito. Gli agenti nell'apprendimento rinforzato si adattano
e si auto-migliorano, e sono quindi meglio adattabili a domini complessi e
sconosciuti.
In questa tesi presentiamo l’evoluzione di un precedente lavoro
1
,
una ricerca preliminare volta a studiare l'utilizzabilità del principale
modello teorico finora proposto nell'ambito della psicologia cognitiva, la
psicogenetica e in particolare la teoria di J.Piaget,.
La ricerca citata modellava alcuni concetti di base presi dalla teoria
di Piaget e mostrava come questi possano essere usati nella progettazione di
un algoritmo. Il risultato finale però consisteva in un algoritmo che non era
in grado di raggiungere l’obiettivo desiderato se non aiutato da un apposito
meccanismo di vicinanza.
1
V.Maniezzo, A.Navarra (1996) “A psychogenetic model for behavior
sequence learning”
9
L’obiettivo di questa tesi è sviluppare questa prima modellizzazione
e creare un nuovo algoritmo che migliori quelli già esistenti in campo di
apprendimento automatico per la costruizione di sequenze senso - motorie.
La tesi è strutturata come segue.
Il secondo capitolo descrive i principali paradigmi di apprendimento
non supervisionato. Dopo un breve excursus sull'apprendimento rinforzato
vengono analizzati i componenti principali dei sistemi a classificatori
(LCS): l'interfaccia con l'ambiente, il sistema di gestione delle regole di
comportamento, il sistema di valutazione delle regole di comportamento, il
sistema di creazione di nuove regole. L’ultima parte spiega gli algoritmi
Temporal-Difference e Q-Learning, due esempi di tecniche di
programmazione dinamica per risolvere un problema scomponendolo in
fasi successive.
Nel terzo capitolo viene esposta una sintesi della teoria di Piaget
sullo sviluppo dell'intelligenza. Secondo Piaget, le strutture mentali non
sono strutture innate, ma costruite attraverso l'azione nell’ambiente. Per
Piaget conoscere significa agire sulla realtà, cioè concepire delle
trasformazioni. Nello sviluppo delle strutture mentali dell'intelligenza si
notano delle tappe fondamentali le quali, secondo Piaget, sono 4; esse sono
rappresentate da diversi tipi di intelligenza:
1. Stadio dell'intelligenza senso-motoria (fino ai due anni).
2. Stadio dell'intelligenza simbolica o pre-operatoria (da 2 a 7-8 anni).
3. Stadio dell'intelligenza operatoria concreta (da 7-8 anni a 11-12 anni).
4. Stadio dell'intelligenza operatoria formale (a partire dai 12 anni).
Nella prima parte di questo capitolo analizzeremo in dettaglio le
tappe fondamentali dell'intelligenza senso-motoria nei primi mesi di vita
che è quella di interesse per questa tesi. Nella seconda parte verrà presentata
una breve rassegna degli sviluppi cognitivi proposti da Piaget per i periodi
successivi a quello senso-motorio che descrivono lo sviluppo
dell'intelligenza del bambino fra i 2 e i 14 anni.
Il quarto capitolo presenta il nuovo modello e relativa
implementazione dei primi tre stadi dell'intelligenza senso-motoria secondo
Piaget, vengono quindi sottolineati gli aspetti innovativi di questa tesi.
10
Viene analizzato lo schema definito da Piaget come unità di
comportamento e di conoscenza, di seguito le successive fasi che portano
alla costruzione degli schemi in accordo con il primo e il secondo stadio
dell'intelligenza senso-motoria
Nel quinto capitolo presentiamo i risultati ottenuti dalla
sperimentazione del nuovo sistema. Viene descritto come si costruiscono
gli schemi e come l'agente risolve il compito assegnatogli concatenando gli
stessi schemi. Gli esempi riportati sono gli stessi di Maniezzo, Navarra
(1996), in questo modo vedremo le differenze di comportamento dei due
algoritmi, l’ultima parte mostra il confronto con un algoritmo di
apprendimento automatico assestato come LCS.
Nel sesto capitolo esponiamo le considerazioni conclusive.
11
APPRENDIMENTO NON SUPERVISIONATO
In questo capitolo viene fatta una veloce introduzione agli elementi
dell’ apprendimento automatico non supervisionato con rinforzo, settore
dell’intelligenza artificiale in cui si colloca l’algoritmo di questa tesi.
2.1 Apprendimento rinforzato
Uno dei più recenti e discussi paradigmi della ricerca nell'ambito
dell'apprendimento automatico è il paradigma di apprendimento non
supervisionato rinforzato (unsupervised reinforcement learning).
L'apprendimento rinforzato è sia un nuovo che vecchio argomento
dell'intelligenza artificiale. Il termine reinforcement learning sembra sia
stato coniato da Minsky (1961), e indipendentemente nella teoria sviluppata
da Waltz e Fu (1965). La prima ricerca sul machine learning, ancora
considerata rilevante, fu il giocatore di dama di Samuel (1959), il quale usò
l'apprendimento per differenze temporali per elaborare reward ritardati,
come è usato oggi. L'apprendimento rinforzato è simile ai modelli usati in
12
alcuni studi psicologici del comportamento appreso negli animali e nelle
persone (Skinner, 1974).
Il reinforcement learning fu largamente dimenticato negli anni
sessanta e settanta, finchè negli anni ottanta esso divenne una attiva area di
ricerca (Barto, et al., 1981, 1983; Hapson, 1983). La ricerca in
reinforcement learning è diventata una parte importante dell'AA.
L'apprendimento non supervisionato viene applicato a sistemi il cui
obiettivo è quello di individuare le azioni o le sequenze di azioni o di
decisioni che meglio risolvono un problema dato. L'apprendimento è non
supervisionato in quanto non viene fornito un nucleo di azioni corrette, ma
si lascia che il sistema generi delle azioni possibili fornendogli un premio o
una punizione proporzionali a quanto l'azione proposta è funzionale alla
soluzione del problema. L'apprendimento rinforzato inoltre ha come unico
obiettivo di scegliere le azioni che massimizzano i premi nel tempo. Questo
tipo di apprendimento è di tipo incrementale in quanto i premi vengono
assegnati uno alla volta e l'algoritmo cerca di raggiungere la soluzione
finale mediante tentativi ripetuti.
L'apprendimento rinforzato studia come un agente possa scegliere
ottimamente un'azione (fra un insieme finito) basandosi sul valore dei suoi
sensori di input attuali e passati, in modo da massimizzare nel tempo una
funzione premio. Questo è un approccio particolarmente interessante in
quanto permette ad un agente di apprendere in un ambiente sconosciuto, di
adattare il suo apprendimento alle particolarità di un compito, e di scegliere
le azioni basandosi sull'attuale stato percettivo.
Si ha quindi un continuo "mapping" di dati sensoriali in azioni che si
susseguono in un ciclo dove l'agente riceve informazioni sensoriali e
possibilmente un premio in seguito all'azione effettuata.
Un generico algoritmo per l'apprendimento rinforzato è il seguente.
Sia S lo stato interno dell'agente, U una funzione di aggiornamento
che modifica S, e V una funzione di valutazione per la scelta delle azioni:
1. Inizializza lo stato S interno dell'agente a S0.
2. Ripeti:
a) Osserva l'attuale stato del mondo I.
b) Scegli un azione a = V(I, S) usando la funzione di valutazione V.
c) Esegui l'azione a.
13
d) Sia r il reward immediato per l'esecuzione dell'azione a nel mondo
allo stato I (può essere r=0).
e) Aggiorna lo stato interno dell’agente S
new
= U(S
old
, I, a, r) usando
la funzione U.
Nella forma più semplice di questo paradigma, il sistema di
apprendimento osserva una sequenza temporale di stati di input che porta
alla fine ad un premio. Il compito del sistema di apprendimento è in questo
caso di predire un reward atteso data una osservazione di uno stato di input
o di una sequenza di stati di input. Il sistema può essere anche utilizzato in
modo da poter generare segnali di controllo che influenzino la sequenza
degli stati. In questo caso l'apprendimento è di solito quello di generare
segnali di controllo ottimi che porterà al massimo rinforzo.
L'apprendimento con rinforzo ritardato è difficile per due motivi:
• non c'è un esplicito segnale guida che indica l'output corretto
ad ogni intervallo di tempo;
• il ritardo di tempo del segnale di reward implica che il sistema
di apprendimento deve risolvere un problema di assegnamento di un
credito, cioè deve ripartire premio e punizione ad ognuno degli stati ed
azioni che risultano nella sequenza del risultato finale.
A dispetto di queste difficoltà, l'apprendimento con rinforzo ritardato
ha attirato un interesse considerevole per molti anni nella comunità dell'AA.
(Watkins, C.J.C.H. (1989)). La nozione di un sistema di apprendimento che
interagisce con un ambiente e impara a risolvere da solo dal risultato della
sua esperienza nell'ambiente infatti è molto attraente. Esso potrebbe avere
anche numerose applicazioni pratiche nelle aree riguardanti controlli di
processi industriali, navigazione e nello studio dei percorsi.
Ad un agente RL viene richiesto di massimizzare il suo reward a
lungo termine. Una misura corrispondente di tale performance,
comunemente studiata, è il reward atteso scontato cumulativo:
Er
t
t
t
γ
=
∞
0
14
dove r
t
è il premio ricevuto al passo t, γ∈[0,1] è un fattore di sconto,
ed E è il valore atteso. Perciò non è immediato individuare il reward che
deve essere massimizzato, e l'agente deve tener conto delle conseguenze
"distruttive" (in quanto il fattore di sconto diminuisce il premio assegnato)
delle sue azioni. I premi o le punizioni non seguono necessariamente le
azioni, che li hanno causati, essi possono essere ricevuti parecchi passi
dopo l'esecuzione dell'azione. Questo viene chiamato apprendimento con
rinforzo ritardato (Sutton, 1984; Watkins, 1989).
Il fattore di sconto γ aggiusta le conseguenze delle azioni a lungo
termine contro quelle a breve termine: per 0<γ<1 i premi distanti nel tempo
sono pesati meno di quelli ricevuti ad ogni scadenza temporale. Ciò
corrisponde all'idea che le punizioni sono meno scoraggianti e i premi sono
meno attraenti se vengono ricevuti in un futuro remoto. Per diversi valori di
γ si ottengono differenti politiche ottime. In particolare, γ≈0 corrisponde
alla massimizzazione del premio immediato, mentre γ≈1 alla
massimizzazione del premio non scontato totale che l'agente riceve per tutte
la sua vita. Il valore atteso della somma è usato a causa della stocasticità
delle transizioni di stato e dei rewards. L'utilizzo di un premio scontato
totale atteso, come criterio attimo per la performance di un agente RL, è in
qualche modo una scelta arbitraria, quindi può essere criticata. Ci sono state
altre proposte di criteri ottimi. Per esempio Herger (1994) ha proposto
l'ottimizzazione dei casi peggiori piuttosto che il valore atteso di reward.
Schawartz (1993) ha presentato recentemente un algoritmo, chiamato R-
learning, per ottimizzare i valori di rinforzo non scontati.
I paragrafi che seguono descrivono principali algoritmi di
apprendimento rinforzato il sistema a classificatori, il temporal-difference e
Q-learning,
2.2 Sistemi a classificatori
I sistemi a classificatori (LCS: Learning Classifier System) sono un
paradigma di calcolo proposto da J.Holland (1986) il cui obiettivo è quello
di imparare a correlare entità di due insiemi. Ne è stato fatto un largo
utilizzo nell'area della robotica autonoma e Artificial Life, in cui viene dato
ai LCS il compito di creare una rappresentazione interna che permetta ad un
agente computazionale (un animat, secondo la terminologia di Wilson
15
(1987) intendendo con questa parola sia un robot autonomo che una sua
simulazione) di sopravvivere in un ambiente a lui sconosciuto. L'algoritmo
LCS modifica il comportamento dell'animat in funzione dei premi/punizioni
ottenuti dal supervisore all'apprendimento a seguito dell'interazione che
l'animat ha con l'ambiente. Il supervisore all'apprendimento fornisce premi
e punizioni a seguito di ogni azione tentata dall'animat, valutando così
l'efficacia dell'azione, o della sequenza di azioni, per il soddisfacimento del
compito dato.
Un sistema classificatore è un sistema parallelo, basato sulle regole
condizione/azione, designato per permettere modifiche non banali e
riorganizzazione della sua conoscenza per attuare un compito. Nella
versione più semplice tutti i messaggi, che danno la descrizione corrente del
problema, sono stringhe binarie di lunghezza fissata. L'insieme dei
messaggi per essere trattato ad ogni momento viene memorizzato in una
struttura dati denominata message list (ML). Il sistema classificatore tratta
questi messaggi usando una popolazione finita di classificatori. Ogni
classificatore è una regola avente la struttura:
if (t
1
, t
2
, ..., t
n
) then m
dove t
i
, sono le condizioni e m il messaggio (azione).
Un classificatore può essere attivato solamente se sono soddisfatte
tutte le condizioni (solitamente congiunzione di predicati). Una volta che un
classificatore è stato attivato esso genera il messaggio m e lo pone nella
message list. Le regole sono contenute in un insieme, chiamato Conflict Set
(CS). Ad ogni ciclo dell'algoritmo vengono confrontate le condizioni di
ciascuna regola in CS con ciascuno degli elementi contenuti nella ML per
determinare quale regola verrà attivata. Le regole con tutte le condizioni
soddisfatte vengono inserite in una struttura dati temporanea e le azioni di
tutte o di alcune di loro, opportunamente scelte, verranno inserite nella
message list. Per poter migliorare le proprie prestazioni col tempo è
necessario che il sistema sia in grado di modificare la base di regole
adattandola alle caratteristiche dell'ambiente in cui il sistema è inserito e al
compito da soddisfare. A ciascuna regola viene associata una forza che
rappresenta il suo grado di utilità. Tale forza consente la selezione delle
regole in conflitto per l'attivazione. La forza delle regole viene anche
16
utilizzata per la creazione di nuove regole scartando (eventualmente in
probabilità) le regole peggiori e generandone di nuove modificando o
ricombinando quelle migliori.
Il Sistema a classificatore, descritto sopra brevemente, è costituito in
genere da diversi moduli in particolare possiamo individuare:
1. l'interfaccia con l'ambiente,
2. il sistema di gestione delle regole di comportamento,
3. il sistema di valutazione delle regole di comportamento,
4. il sistema di creazione di nuove regole.
figura 1.2 - Moduli principali di un sistema a classificatori
Analizziamo ora qui di seguito i moduli principali di un LCS (figura
2.1).
2.2.1 Il sistema di gestione delle regole
Il sistema gestore delle regole è un sistema a regole di produzione.
Un classificatore è una stringa di lunghezza fissata l definita sull'alfabeto
{0,1, #}. In essa sono individuabili una parte condizione ed una parte
AMBIENTE
Input Output
Gestore delle
regole
Gestore della
valutazione
delle regole
Generatore
delle
regole
17
azione, la parte condizione è formata da una sottostringa di lunghezza lc
mentre la parte azione è costituita da una stringa di lunghezza la (la può
essere sia uguale che diversa da lc; solitamente è uguale). La sintassi del
classificatore è:
‹classificatore› = ‹condizione›...‹condizione› : ‹messaggio›
I due punti separano la parte condizione dalla parte azione. Ogni
condizione viene soddisfatta unificandola con una stringa definita su {0,1}
lc
avente gli zeri e gli uni nelle stesse posizioni e indifferentemente zero od
uno in corrispondenza dei # della condizione.
Ad ogni classificatore viene associata una forza (numero reale) che
può essere aggiornata ad ogni ciclo del sistema. I classificatori sono
contenuti nella struttura dati CS; ogni classificatore può comparire più volte
in tale struttura con forze diverse.
I messaggi definiti sull'alfabeto {0,1}
la
sono contenuti nella message
list in numero superiormente limitato dal valore di un parametro del
sistema.
L'algoritmo che presiede al sistema di gestione delle regole funziona
come segue. Il sistema viene inizializzato generando, casualmente o in altri
modi, un insieme di classificatori Ci, ad ognuno dei quali viene attribuita
una forza S(Ci). A questo punto vengono letti i sensori ambientali e
vengono inseriti i corrispondenti messaggi nella message list (inizialmente
vuota).
Si identificano poi le regole con la parte condizione completamente
soddisfatta e memorizzati in una struttura dati temporanea ConflSet. Nel
caso in cui | ConflSet | è maggiore di un valore predefinito ConfMax nasce
un problema di conflitto, che viene risolto estraendo utilizzando il metodo
di Monte Carlo da ConflSet, con probabilità proporzionali alle loro forze un
numero di classificatori attivabili.
A questo punto si cancellano tutti i messaggi dalla message list e
vengono attivati, in parallelo, i classificatori in ConflSet. Le parti azione dei
classificatori attivati vengono memorizzate nella message list. Si analizza
quindi la lista dei messaggi per vedere se contiene messaggi diretti agli
attuatori, se ve ne sono li esegue. Dopodiché vengono letti i sensori, i
18
corrispondenti messaggi esterni vengono appesi alla lista dei messaggi e si
rinizia il processo appena descritto.
2.2.2 Il sistema di valutazione delle regole
Il compito del sistema di valutazione delle regole consiste
nell'attribuire ad ogni classificatore una forza proporzionale al suo
contributo alla buona risoluzione del compito. Viene affrontato quindi il
problema di assegnazione del credito in cui si premiano sia le regole
direttamente utili sia le regole stage setting, che hanno permesso a quelle
utili di attivarsi.
Per risolvere questo problema esistono diversi algoritmi il più
utilizzato va sotto il nome di Buket Brigade proposto da Holland
(1986).Tale algoritmo permette di premiare solo le regole che propongono
azioni utili, ridistribuendo comunque ad ogni ciclo i premi/punizioni
all'indietro nella catena di classificatori e permettendo quindi di valutare
adeguatamente anche le regole stage setting. Il buket brigade può essere
visto come un sistema economico di acquisizione di informazioni dove il
diritto di ottenere informazioni è comprato e venduto dai classificatori.
L'algoritmo si articola nei seguenti passi. Ogni volta che viene
eseguita una azione a tutti i classificatori che l'avevano proposta viene
assegnato un premio/punizione. Il premio viene sommato alla forza del
classificatore che lo riceve.
La ridistribuzione del credito viene fatta implicitamente ad ogni
ciclo; quando un classificatore è attivabile paga parte della sua forza per
poter impostare il proprio messaggio nella message list. Ogni classificatore
Ci attivabile al tempo t fa un'offerta B(Ci) proporzionale alla sua forza
S(Ci) per avere il privilegio di impostare il proprio messaggio. I
classificatori attivabili vengono accettati in ConflSet sulla base del metodo
Monte Carlo con probabilità di estrazione proporzionale alle offerte fatte.
Quando una regola viene accettata, la sua forza viene diminuita di
una quantità pari all'offerta B(Ci) fatta. La sua offerta viene distribuita fra
tutti i classificatori che al ciclo precedente avevano impostato i messaggi
che hanno reso possibile l'attivazione della regola in esame. In questo modo
ogni classificatore ridistribuisce parte della propria forza ai classificatori
19
che permettono la sua attivazione, mettendo in azione un meccanismo di
ridistribuzione all'indietro del credito temporalmente locale e che tende a
premiare le catene di classificatori che portano ad azioni utili.
2.2.3 La generazione di regole nuove
Per modificare la composizione della base delle regole viene
generalmente utilizzato un Algoritmo Genetico (Holland 1975; Goldberg
1989). Gli algoritmi genetici (GA) costituiscono un procedimento di ricerca
del massimo di una funzione data che si ispira alla metafora della genetica
delle popolazioni. In analogia con la genetica delle popolazioni, ogni
soluzione è vista come un individuo e l'insieme di soluzioni considerate
all'istante t viene detto popolazione. Le idee che dirigono il processo di
ricerca sono l'equivalente della selezione naturale, della ricombinazione
genetica (crossover) e della mutazione. Gli operatori genetici principali
sono quindi: selezione, crossover, mutazione.
L'algoritmo genetico utilizzato dai sistemi a classificatori lavora su
stringhe ternarie il cui valore di fitness (funzione che misura la bontà della
soluzione considerata) è costituito dalla relativa forza. Gli operatori genetici
utilizzati sono sempre selezione, crossover, mutazione.
Per poter selezionare efficientemente le regole utili è necessario che
la relativa forza sia effettivamente una misura del loro livello di utilità alla
soluzione del problema, è quindi necessario che il sistema di valutazione sia
arrivato a definire un livello temporalmente stabile per ogni classificatore.
La selezione fatta non genera una intera nuova popolazione sulla base di
quella vecchia, ma ne tiene inalterata una larga parte scartando
deterministicamente le regole con fitness più bassa e sostituendole con
rielaborazioni genetiche di regole scelte fra quelle della popolazione
vecchia.
2.2.4 Interfaccia con l'ambiente
Questo metodo è ovviamente specifico al problema e quindi non è
compreso nel modello generale dei sistemi a classificatori. Le funzionalità