Un Algoritmo Immunologico
Ibrido con Information Gain
per il Problema della
Colorazione dei Grafi.
dott. Mario Pavone
[email protected]
www.dmi.unict.it/mpavone
Overview
• Artificial Immune System;
• Graph Coloring Problem;
• A Hybrid Immune Algorithm with
Information Gain for the Graph
Coloring Problem;
• Results;
• Conclusions.
Introduzione
I Sistemi Immunitari Naturali
rappresentano
un’eccellente strategia intelligente “Bottom Up”,
dove l’adattamento delle cellule e delle molecole
avviene
localmente,
invece
un
utile
comportamento emerge a livello globale (risposta
immunitaria).
Immune System: sistemi di apprendimento
Ag: problema da risolvere
Ab: soluzione generata
Graph Coloring Problem (GCP)
• Migliori risultati per il GCP vengono spesso
ottenuti con Hybrid EAs.
• L’operatore di Crossover, nei SGA, ottiene scarse
prestazioni in problemi di ottimizzazione
combinatoria.
• In generale, deve essere progettato ad hoc.
• Lo sviluppo di un Operatore di Crossover è
cruciale per le prestazioni globali di un EAs.
• IA non fa uso ne di un operatore di Crossover ne
di alcuna specifica conoscenza del problema.
Definizione del GCP
Dato un Grafo non diretto G=(V, E), una
colorazione dei vertici di G è una funzione c:
V  |V|, tale che
c(u)  c(v),  (u, v)  E
{1,…,|V|} è detto insieme dei colori.
Il più piccolo intero k, tale che G è k-colorabile è
detto numero cromatico di G ((G)).
GCP è NP-Complete (Garey e Johnson:79)
Proprietà del GCP
Dalla definizione di (G) seguono le seguenti
proprietà (Bollobas: 98, Diestel: 97):
1. Poiché max{H  G}{(H)}  (G), dove 
indica il grado minimo e  il grado massimo,
segue un upper bound per il GCP:
(G) (G)
2.Il problema della colorazione è strettamente
collegato con la definizione di clique (sottografo
completo). Ne segue un lower bound per il GCP:
(G)  (G)
Approcci per la Colorazione
• Assegnazione dei
definizione);
• Classi di Colori:
colori
(come
in
– Una configurazione è considerata come un
partizionamento dei vertici, dove ciascuna
partizione rappresenta un Independent Set (due
vertici adiacenti appartengono a partizioni
diverse). Quindi, una k-colorazione di G
equivale a partizionare V in k sottoinsiemi.
Algoritmo Immunologico
Utilizzo di due entità: Ag (problema) e B cells
(soluzione candidata di lunghezza =|V|).
P(t) = popolazione di d individui, i quali
rappresentano un sottoinsieme dello spazio
delle soluzioni (S )di lunghezza  ottenute al
time step t.
Interazione
In tale fase viene valutata la popolazione P(t).
f(x)=m indica il valore della funzione fitness
del recettore della B cells x.
Nel caso del GCP, la funzione fitness indica
che esiste una colorazione di G con m colori,
cioè:
V = S 1  S2  …  Sm
tale che Si  V è un Independent Set, i.
Espansione Clonale
La fase di Espansione Clonale è composta da due
passi: cloning e hypermutation.
Potenziale di Clonazione: V(f(x)) = e –k(-f(x))
Numero di Mutazione:
M(f(x)) = 1- (/f(x))
L’operatore di mutazione sceglie M(f(x)) volte
due vertici i e j in x e li scambia.
Le rispettive popolazioni vengono indicate con
P(clo) e P(hyp).
Aging
Dopo aver valutato la nuova popolazione P(hyp) al time
step t, l’operatore di Aging elimina le B cells vecchie,
attraverso un processo stocastico.
La Probabilità di rimuovere una B cells è determinato da
una legge esponenziale negativa con parametro B:
Pdie(B) = (1 - e (– ln(2) / B ))
dove B rappresenta il tempo di vita media previsto per le
cellule B.
Non utilizziamo l’operatore della Birth poiché produce
un alto numero di valutazioni della fitness.
Assegnazione dei colori
L’assegnazione dei vertici avviene seguendo uno
schema deterministico, basato sull’ordine di visita
dei vertici del grafo.
Facciamo uso di una semplice procedura di
colorazione poiché vogliamo investigare la
capacità di apprendimento e di risoluzione del
nostro IA.
Criterio di Arresto mediante
Information Gain
Information Gain (Kullback Information) è una
funzione entropica associata alla quantità di
informazione che il sistema scopre durante la fase
di apprendimento.
Funzione di distribuzione:
f m( t ) 
Information Gain: K (t , t 0 ) 
f
m
Bmt
t
B
m0 m
(t )
m
h
log( f
Bmt

d
(t )
m
/f
( t0 )
m
)
L’Information Gain cresce monotonicamente fino
a raggiungere uno stato finale costante.
Maximum Information Gain principle: dK/dt  0.
Quando l’apprendimento del sistema finisce
avremo dK/dt = 0.
Può quindi essere utilizzato tale rapporto come
condizione di arresto per IA.
Ricerca Locale
Gli algoritmi di ricerca locale per problemi di
ottimizzazione combinatoria si basano sulla
definizione di intorno.
In tale approccio i vicini vengono generati
scambiando i valori dei vertici.
Scambiare tutte le coppie dei vertici risulta essere
computazionalmente costoso.
Utilizziamo l’idea del “vicino più vicino”.
A tal proposito definiamo unvicinato con raggio R.
Ricerca Locale (cont.)
La procedura di ricerca locale ha come vantaggio
quello di incrementare il success rate e come
svantaggio quello di incrementare il numero di
valutazioni della funzione fitness.
Se omettiamo tale procedura IA necessita di un
numero maggiore di generazioni e quindi più
calcoli della fitness per ottenere lo stesso risultato,
ma con un SR più piccolo.
Ricerca Locale (cont.)
È possibile utilizzare la differenza fra Phyp e P(t+1),
come una misura standard della diversità della
popolazione:
| avgfitness(Phyp) – avgfitness(P(t+1)) | = Popdiv
Quando Popdiv decresce rapidamente ci troviamo
di fronte ad una prematura convergenza.
Istanza DSCJ250.5.col con |V|=250, |E|=15668. Parametri
utilizzati: d=500, dup=5, B=10 ed R=5. Best Known 28.
Istanza flat_300_20_0.col con |V|=300, |E|=21375. Parametri
utilizzati: d=1000, dup=10, B=10 ed R=5. Best Known 20.
Settaggio dei Parametri mediante
Information Gain
Per capire come settare i parametri
dell’algoritmo eseguiamo alcuni esperimenti
sull’istanza del GCP QUEEN6_6.col.
Fissiamo i seguenti parametri: d=100,
dup=2, R=2 e gen=100.
Per ciascun esperimento eseguiamo 100 runs
indipendenti.
Vita Media delle B cellule, B
Vita Media delle B cellule, B
Parametro di Duplicazione dup
Fissato B=25.0, facciamo variare dup.
Da risultati sperimentali si ottiene che IA a
ciascuna generazione ottiene una maggiore
informazione (Information Gain) per
dup=10, mentre raggiunge più velocemente
il miglior valore della fitness per dup=5.
dup e B
Abbiamo quindi ottenuto che per dup=2 il
miglior valore di B è 25.0, mentre le
performance migliori si ottengono per dup=5.
Settiamo allora dup=5 e facciamo variare B .
dup e B
Information Gain per B{15, 10, 25, 50}.
dup e B
Fitness media della popolazione Phyp e della popolazione P(t) per
B{15, 10, 25, 50}.
Raggio dell’intorno R, d e dup
Numero medio di valutazioni per determinare la soluzione (AES)
al variare del raggio del vicinato.
Raggio dell’intorno R, d e dup
Grafico 3D dei valori d e dup rispetto SR.
Risultati
I risultati sperimentali sono stati ottenuti sui
classici benchmark: MYCIELSKI, QUEEN,
DSJC e LEIGHTON.
Parametri utilizzati: d=1000, dup=15, R=30 e
B=20.0.
È stato utilizzato l’operatore Elitist Aging.
I migliori valori ottenuti da IA sono sempre
ottenuti per SR=100.
Conclusioni
• Abbiamo sviluppato un nuovo IA che incorpora
una semplice procedura di ricerca locale al fine
di migliorare le performance globali;
• IA utilizza la funzione di Information Gain per
settare correttamente i quattro parametri;
• Scegliamo i parametri che massimizzano
l’informazione scoperta e che incrementano in
maniera monotona l’Information Gain.
• A nostra conoscenza questa è la prima volta che
Ias, e in generale EAs, vengono caratterizzati in
termini di Information Gain.