3SAT - Dipartimento di Matematica e Informatica

Un Algoritmo Immunologico per
il Riconoscimento di Caratteri
e per il Problema 3-SAT
In questa
presentazione
descriverò il
lavoro
di tesi dal
Giuseppe
titolo
Nicosia
Dipartimento di Matematica e Informatica
Università di Catania
In particolare vedremo
tre sezioni:nella prima
descriverò
brevemente: la
metafora utilizzata, i
meccanismi che da
essa abbiamo estratto
e lo sviluppo
dell’algoritmo che
abbiamo creato,nella
seconda vedremo che
questo mantiene le
proprietà di
apprendimento
ereditate dal SI
naturale, e nella terza
osserveremo il
comportamento
dell’algoritmo nel
risolvere istanze difficili
di un problema NPcompleto quale il 3SAT
Indice della presentazione
Computazione Evolutiva: Metafora SI, Selezione
Clonale ed Algoritmo immunologico
Learning e riconoscimento di caratteri mediante un
Algoritmo Immunologico (AI).
Risoluzione di istanze difficili del problema 3-SAT
con un AI.
Algoritmi Evolutivi
Nascono dal “paradigma” della evoluzione
biologica della specie
Gli operatori principali:
 Selezione
 Ricombinazione
 Mutazione
Questi algoritmi vengono
utilizzati in applicazioni
quali riconoscimento di
patterns ed ottimizzazioni
di funzioni.
Sistema Immunitario Naturale
Il SI naturale è un sistema di riconoscimento e difesa
dell’organismo da agenti patogeni esterni.
Ci siamo posti la seguente domanda :
E’ possibile utilizzare i meccanismi del SI per costruire
un algoritmo evolutivo capace di risolvere problemi di
riconoscimento ed ottimizzazione ?
Il lavoro della tesi è una prima risposta a questa domanda.
Il SI Naturale
Il SI naturale riconosce ed elimina gli
agenti patogeni esterni (Antigeni) con un
sistema complesso, basato sul
matching, anche non perfetto,
tra i recettori dei linfociti B (Cellule B) e gli
antigeni.
Meccanismo della Selezione
Clonale, produzione di
plasma cellule e cellule
memoria
La cellula che supera
la soglia di
attivazione viene
clonata, i cloni
vengono sottoposti a
mutazione alcuni
evolveranno in
Plasma cellule altri
in Cellule memoria
caratterizzate da un
tempo di vita media
molto lungo.
All’interno di questo
mecc. È presente
anche un processo
chiamato affinity
loop
Affinity loop: Le cellule
prodotte da clonazione
vengono a loro volta
sottoposte a selezione
Algoritmo Immunologico
Basandoci su questi modelli del
SI abbiamo costruito un
algoritmo evolutivo che utilizza i
seguenti operatori:
Gli Operatori Immunologici
Selezione mediata dall’antigene: L’incontro tra
recettore ed Antigene genera informazione che
serve al processo evolutivo della Selezione
Clonale.
Clonazione: La cellula viene duplicata un numero di
volte prestabilito.
Ipermutazione: Inserisce diversità nella
popolazione garantendo la copertura di spazi di
ricerca molto ampi.
L’Algoritmo Immunologico
Procedura AI;{
Initpop P(0);
Evaluate P(0);
until(done) {
t=t+1;
CloningSelection P(t);
Hypermutation();
Birth();
Evaluate P(t);
Survive P(t);
}
}
/* Generazione casuale di P */
/* Valutazione livelli affinità */
/* Selezione in base ad affinità */
/* Mutazione B cells */
Qui
è Nascita
mostrata la B cells */
/*
pseudo codifica
dell’algoritmo da
noi presentato.
Sono ben visibili
gli operatori
precedentemente
menzionati
/* Secondo passo di selezione */
Dario:
Forse è meglio:
Osservando i
comportamenti di
due diverse
implementazioni
Applicazioni
L’algoritmo descritto è stato verificato su
due classici problemi computazionali:
Il riconoscimento di caratteri
Testato su due implementazioni diverse:
Riconoscimento sequenziale e parallelo.
Il 3-SAT
Mediante l’uso di un meccanismo chiamato SAW.
I Applicazione
Riconoscimento di Caratteri
I caratteri in input
vengono
presentati come
una matrice di bit
12x10;
Riconoscimento di Caratteri
Definizione del problema:
Gli antigeni e i
recettori delle
cellule B vengono
codificati
Ag
mediante
un
vettore di interi di
Recettore
dim. 120, la
metrica che
abbiamo utilizzato
per definire la
distanza tra rec.
ed antig. è la DH
uguale alla
Dhdi( Btutti
, Ag
somma
i bit)
diversi, La
funzione di fitness
associata alle
cellule è quindi un
numero compreso
tra 0 ed 1 1 perf.
Match 0 entità
opposte
codificati mediante un
vettore di interi di dim. L = 120
Distanza di Hamming
l 1
 
i 0
1 se Bi  Agi
dove   
0 Altrimenti
Funzione di Fitness
Dh ( B, Ag )
F ( B, Ag )  1 
L
12 x 10
Lanciata la
versione
sequenziale
osservando
l’evoluzione della
popolazione di
cellule, si
800
possono
notare
gli spike che
700 ai
corrispondono
vari
600
riconoscimenti,
Nel grafico
500
piccolo è
evidenziato
400 un
particolare
relativo300
al primo
step di
200
riconoscimento
per meglio
100
apprezzare
l’espansione in
prossimità0del
0
perfect match
Evoluzione di una singola
popolazione di cellule B
individui nella popolazione
numero di cellule
200
150
100
50
0
0
5
10
15
20
25
30
35
40
Spike
50
100
150
200
250
time steps
300
350
400
Variazione sul numero di cellule B durante il riconoscimento di
tutti i caratteri. Gli spike corrispondono ai riconoscimenti
Un’altra quantità
da tenere in
considerazione è
la misura di
affinità. Dalla
quale otteniamo
1
la certezza dei
riconoscimenti,
0.9 sulla
informazioni
sequenza di
questi e
0.8
sull’andamento
dei valori di
0.7
fitness
Andamento della Fitness Function
Valori di Fitness
0.6
0.5
0.4
valore medio
valore migliore
0
50
100
150
200
250
Time Steps
300
350
400
Valori medio e massimo della misura di affinità delle cellule
B
La seconda
versione
dell’algoritmo
permette 1.
Riconoscimento Parallelo
Un’altra differenza
consiste nella 2.
1. Coevoluzione di n popolazioni che
contemporaneamente tendono agli n caratteri in input
2. Seconda fase della selezione : Abbiamo utilizzato un
meccanismo chiamato ranking selection (Selezione
Ordinata) secondo il quale vengono selezionati per
sopravvivere solo m individui per ogni popolazione.
La popolazione i-esima sarà formata, quindi, dai primi m elementi
della lista ordinati rispetto all’i-esimo elemento dell’array F (fitness
function).
Questa seconda
implementazione ha
evidenziato aspetti
interessanti: nei
primi steps del
riconoscimento
abbiamo osservato
delle cellule
che le Totalità
popolazioni
contengono alcuni
individui in comune
che vengono via via
rimpiazzati da
cellule più
specializzate,
questo fenomeno,
nel SIN è appunto
chiamato
specializzazione.
Durante il
Specializzazione
riconoscimento la
diminuzione del
numero di cellule è
dovuta al fatto che si
devono isolare
sempre meno
popolazioni man
mano
10
20 che i caratteri
30
40
vengono
Time Steps
riconosciuti.
Coevoluzione di più popolazioni di
cellule B
100
Numero cellule B
80
60
40
20
0
0
B
Riconoscimento
dei Caratteri
50
60
Grafico sulla dinamica del Numero di Cellule B durante il
Riconoscimento Parallelo
.
70
L’andamento
della fitness dei
migliori elementi
di ogni
popolazione ci
mostra la 1
effettiva
coevoluzione
0.95 il
verso
riconoscimento
0.9di tutti i
completo
caratteri
Andamento della Fitness Function
Valori di Fitness degli Individui Migliori
Fitness
0.85
0.8
patt 0
patt 1
patt 2
patt 3
patt 4
patt 5
patt 6
patt 7
patt 8
patt 9
0.75
0.7
0.65
0.6
0.55
0
10
20
30
Time Steps
40
50
60
Visualizzazione del valore di affinità migliore per ogni sotto popolazione relativa a tutti i patterns in input.
Learning Cascade
n popolazioni
Una ulteriore verifica di questo riconoscimento è visibile dallo spostamento della distribuzione delle
Spostamento
della distribuzione
delle verso
cellule
albit di
cellule
da una aggregazione
con molti bit di mismatch
una relativamente
aggregazione senza
mismatch. L’osservazione dinumero
questi spostamenti
ha permesso
di Matching
Bits di capire meglio l’operatore di
ipermutazione.
Single vs Multiple
Multiple converge più velocemente ed è
insensibile al numero di caratteri in input
Confronto di prestazioni
350
Sequenziale
Parallelo
300
250
200
150
100
50
0
1
2
3
4
5
6
7
Numero pattern in input
8
Il confronto tra le
due
implementazioni
ha evidenziato
che il
9
10
riconoscimento
parallelo
II Applicazione
Il Problema 3-SAT
Il problema 3-SAT
Istanza:
C  {c1 , c2 ,..., cl }
Una collezione di clausole
Un insieme finito U di variabili tali che :
| ci | 3 per 1  i  l
Problema:
Esiste un assegnamento di verità per U che
soddisfa tutte le clausole in C
In questo problema si
ha
CNF
F1  ( X 1  X 2  Z1 )  (Z1  X 3  Z 2 )...
Noi abbiamo
considerato formule
proposizionali in CNF
Istanze difficili del problema
3-SAT (Mitchell 1992)
Di queste
abbiamo
considerato le
istanze che
presentano un
rapporto clausole
/ variabili uguale a
4.3. Mitchell ha
dimostrato che
queste sono le
Le
istanze
con
istanze
più difficili
di tale problema,
rapporto
ovvero quelle per
clausole/variabili
le quali sono
4,3necessarie il
maggior numero
di chiamate alla
procedura
ricorsiva DP
Numero medio di chiamate ricorsive alla procedura DP in
funzione del rapporto tra clausole e variabili.
SAW
Lo Stepwise adaptation weight è uno dei
meccanismi più usati per incrementare le
prestazioni degli AE riguardo i (CSP) Constraint
Satisfaction Problem, cioè i problemi dove
esistono vincoli da soddisfare. Esso consiste
nell’assegnare un peso ad ogni clausola ed
incrementarlo se la clausola, dopo un certo
numero di Time Steps, non è stata ancora
verificata. Mediante tale metodo, quindi, abbiamo
informazioni sulla semantica del problema.
Codifica per il problema 3SAT



Ag = Formula proposizionale in cnf soddisfacibile,
codificata mediante un vettore di interi di
dimensione l · 3, dove l è il numero di clausole.
Recettore della Cellula B = Assegnamento di
verità codificato mediante un vettore di interi di
dimensione n, numero di variabili.
Funzione di Fitness (penalità) è una somma
pesata delle clausole insoddisfatte:
l
F(B)   Wi  Sati ( A)
t
i 1
Dove Wi è il peso della clausola i al tempo t,
Sati(A)=0 se essa non è soddisfatta
dall’assegnamento A proposto dalla Cellula B
Confronto con altri algoritmi evolutivi
Il nostro algoritmo (AI) è stato confrontato con i migliori
algoritmi - nell’ambito delle strategie evolutive e degli algoritmi
genetici - per il problema del 3SAT :
• La strategia evolutiva (15,100)-SE
• l’algoritmo genetico WGSAT
[vedi 7th Annual Conference on Evolutionary Programming, LNCS, n.1477, pp. 125136. Springer Berlin, 1998]
Il confronto è basato su due parametri:
• SR = success rate, percentuale degli esperimenti con successo
•AES = average number of evaluation to solution, numero di
valutazioni necessarie per ottenere la soluzione.
I risultati ottenutiPercentuale di
sono stati esperimenti con
confrontati con successo
quelli ottenuti da
altri
2 AE una SE
Numero
(15,100)-SE
ed un AG
Variabili
entrambi
Caso
SR AES
selezionati come
i
migliori del loro
1
0.92 18725
gruppo nella
risoluzione del2
l=30
0
problema in
esame, l’AG 3
0
inoltre usa dei
parametri 4
0.70 10145
ottimizzati per le
l=40
5
0.66 11795
diverse istanze.l’
AI di contro usa
0
parametri 6
minimali
7
0.80 22269
ottenendo risultati
soddisfacenti.
EA vs. IA
l=50
l=100
8
9
10
0.34
0
0
Numero medio di
valutazioni
(1+1)-Saw AI
SR AES
WGSat Opt. Fixed
SR
AES
1
0.92
1
1
2912
40918
1705
13676
1
0.96
1
1
6063
78985
31526
13328
0.76
1
0.32
74374
15036
98644
1
0.94
1
2899
82031
28026
8183 0.98
- 0.18
- 0.36
46006
149323
122218
1
0.32
0.06
60160
147718
192403
Conclusioni
Nuovo algoritmo evolutivo: l’algoritmo
immunologico.
Learning mediante algoritmo immunologico
coevolutivo.
Soluzioni di istanze difficili del problema
3-SAT.
Abbiamo creato un nuovo...
Abbiamo dimostrato che questo è
capace di apprendere e di risolvere
problemi difficili