AGENTI CHE RISOLVONO PROBLEMI
Ottimizzazione euristica
E.Mumolo
[email protected]
Il problema della ottimizzazione



Componenti:

Un insieme di variabili indipendenti

Un insieme di condizioni sulle variabili (vincoli)

Una funzione obiettivo
Soluzione:

I valori delle variabili che, rispettando i vincoli, portano la funzione obiettivo
ad un valore ottimo
In forma generale:
massimizza F x , x
n
Con i vincoli
ci x
0, i m' 1,... , m
ci x
0, i 1,2 , ... m'
Lo spazio di ricerca della soluzione

Descritto da:
 Numero di dimensioni
 Dominio di ciascuna dimensione




Natura della relazione tra vettori di ingresso e funzione obiettivo



Discreto
Limitato
Reale
Continua
Discontinua
Ricerca locale nello spazio di ricrca: non tiene conto delle
soluzioni precedenti
 Considera solo la soluzione corrente
 Usa un metodo per generare soluzioni alternative.
Una tassonomia approssimata delle tecniche di ottimizzazione
ottimizzazione
Tecniche
enumerative
Tecniche
euristiche
DFS
Tabu Search
Hill
Climbing
Simulated
Annealing
Programmazione
dinamica
Algoritmi
evoluzionistici
Programmazione
genetica
Algoritmi
genetici
BFS
Tecniche euristiche

Tecniche per la soluzione di problemi mediante algoritmi iterativi che
selezionano via via la soluzione più appropriata tra quelle ottenute a
ciascun passo. Tra queste:





Tabu search. Definisce come muoversi localmente da una soluzione all’altra
usando una tabella delle soluzioni visitate recentemente
Hill Climbing: parte da un punto e cerca punti con migliore funzione obiettivo
Ant colony optimization: risolve problemi che possono essere ridotti alla ricerca
di cammini ottimi in un grafo. Idea: le formiche in cerca di cibo esplorano a
caso l’ambiente e quando lo trovano ritornano alla colonia lasciando tracce
chimiche, eventualmente rinforzate da altre formiche
Simulated annealing: ricerca la soluzione generando soluzioni vicine alla
corrente. Soluzioni che portano a un valore superiore sono sempre accettate.
Soluzioni che portano a un valore inferiore sono accettate probabilisticamente
Genetic algorithms: mantiene un insieme di soluzioni che evolvono usando i
principi della evoluzione Darwiniana
Hill Climbing
varianti:



stochastic hill climbing

Non sceglie sempre il migliore
first-choice hill climbing

Prende il primo buon successore (utile se il numero di successori è grande)
random restart

Cerca il punto migliore da diversi punti di partenza

Ovviamente la probabilità di trovare il massimo aumeta con l’aumentare del numero
di tentativi
Algoritmi di ottimizzazione mediante
Simulated Annealing



Simulated Annealing: (~ tempera simulata)
Idea: imitare quello che succede nel processo di tempera
 la tempera è il processo nel quale il metallo viene
riscaldato e poi raffreddato lentamente
Il materiale temperato viene arriva ad uno stato a minore energia
nel quale le molecle si assestano su una posizione più stabile
Riassunto dell’algoritmo di minimizzazione
selezione
dei parametri iniziali
perturba i parametri
Valutazione


Se v’ < v accetta la perturbazione
Altrimenti accetta la perturbazione
con Prob(E,T)

Test di Metropolis
Ripeti
con stato e temperatura aggiornati
Test di Metropolis
Si
approssima l’allineamento delle molecole in natura consentendo le
transizioni verso l’alto con qualche probabilità
E
 Prob (nello stato ad energia E) ~ 1 kT
e


Funzione di distribuzione di probabilitàZ
di Boltzmann (Z normalizz., k cost.Boltzmann)
Anche quando T è piccola, c’è una
possibilità di accettazione
E

Prob (accettazione) = e



La
kT
Metropolis
if E2 < E1, prob () > 1
if E2 > E1, possiamo trasferirci ad uno stato ad energia maggiore
velocità alla quale si decrementa T e la quantità di decremento è
stabilito da una sequenza di tempera prestabilita (annealing schedule)
Pseudocodice del Simulated annealing
Fissa un valore iniziale del parametro T sufficientemente alto: T0
Fissa la configurazione iniziale: i0
Ripeti
Ripeti
Perturba la configurazione attuale: ij
Calcola Dc=c(i)-c(j);
Se Dc ≤ 0 Allora
Accetta la configurazione j;
Altrimenti
Se (exp(-Dc/T) ≥ Random(0,1)) Allora
Accetta la configurazione j;
FineSe
FinoAQuando(l’equilibro termico è bene approssimato);
Decrementa T;
FinoAQuando(il criterio di stop è verificato);
Proprietà





L’algoritmo può essere considerato come una successione di catene di
Markov omogenee
Si può realizzare delle catene non omogenee diminuendo la
temperatura ad ogni iterazione
Si può dimostrare che se T scende abbastanza lentamente, il processo
converge all’ottimo globale con probabilità 1
presentato in: Kirkpatrick, Gelatt and Vecchi, “Optimization by
Simulated Annealing”, Science, 220(4598):498-516, May 1983 per
problemi di routing VLSI
semplice da utilizzare per l’ottimizzazine vincolata
Sequenze di raffreddamento


La temperatura iniziale, la temperatura finale
e la sequenza di raffreddamento sono
determinate sperimentalmente
Alcuni schemi:



t = at, dove a è tipicamente intorno a 0.95
t = e-bt t, dove b è tipicamente intorno a 0.7
......
Parametri di SA

Valore iniziale di temperatura

determina l’efficienza dell’algoritmo

un valore troppo basso fà convergere l’algoritmo ad un minimo
locale

un valore troppo alto fà si che le prime catene siano superflue

possibile modo di determinare T0:
1. Si fissa un valore arbitrario
2. si esegue un certo numero di iterazioni
3. si calcola il rapporto tra il numero di transizioni accettate e il
numero di transizioni proposte
4. se il rapporto è superiore a un numero prefissato
(tipicamente 0.8), allora il valore di T0 proposto viene
accettato, altrimenti si raddoppia tale valore e si ripete da 2.
Algoritmi Genetici (GA)




Tecnica di ottimizzazione euristica; prende come modello il processo di
evoluzione biologica
NB: IL PROCESSO DI EVOLUZIONE BIOLOGICO E’
GROSSOLANAMENTE APPROSSIMATO!!!
Proposta da John Holland nel 1975
Uno sguardo sul suo modo di operare:



mantiene una popolazione di possibili soluzioni al problema
Gestisce la loro evoluzione applicando concetti di evoluzione
naturale e ereditarietà genetica
Questi concetti sono applicati mediante Operatori Stocastici:



Selezione
Ricombinazione
Mutazione
Operatori stocastici



Selezione: preferisce le soluzioni migliori nella
popolazione  definizione della qualità di una
soluzione
Ricombinazione: prende due soluzioni distinte e
genera nuove soluzioni ricombinandole a caso
Mutazione: perturba a caso una soluzione
Il processo preso a modello
Evoluzione naturale
Algoritmi genetici
Problema: adattarsi all’ambiente
Problema: trovare l’ottimo globale di una
funzione
Attori: gli individui viventi in quell’ambiente
Attori: le possibili soluzioni
Il metro di giudizio: la capacità degli
individui di adattarsi all’ambiente
Il metro di giudizio: valore della funzione da
ottimizzare, chiamata fitness
Modalità di evoluzione: selezione,
ricombinazione e mutazione genetica delle
specie viventi
Modalità di evoluzione: applicazione
iterativa degli Operatori Stocastici
Risultato: le specie viventi si adattano
all’ambiente
Risultato: la popolazione di soluzioni
cambia cercando di massimizzare la
funzione
Ottimizzazione Genetica: pseudocodice
Genera la popolazione iniziale di soluzioni;
Valuta la fitness di ogni soluzione;
while (condizione di termine non raggiunta) do
seleziona le soluzioni per la riproduzione;
ricombina le soluzioni selezionate;
mutazione delle soluzioni;
valuta la fitness delle soluzioni modificate;
genera una nuova popolazione rimpiazzando la popolazione
iniziale con le soluzioni modificate;
done
GA
for(gen=0; gen<maxgen; gen++)
{
fprintf(outfp,"\nRUN %d of %d: GENERATION %d->%d\n",run,maxruns,gen,maxgen);
application();
/*application dependent routines*/
generation();
/* create a new generation */
statistics(newpop);
/* compute fitness statistics on new populations */
report();
/* report results for new generation */
temp = oldpop;
oldpop = newpop;
newpop = temp;
}
/* advance the generation */
Evoluzione
selezione
riproduzione
Genera la
popolazione
valutazione
Esempio


massimizzare la funzione f(x)=x2 con x tra 0 e 31
struttura dati:
...
unsigned *chrom
cromosoma
double fitness
individuo i
int xsite
int *parent
genitori
int *utility
eventuali variabili utili
unsigned *chrom
individuo i+1
double fitness
int xsite
int *parent
int *utility
...
Esempio

inzializzazione a caso di una popolazione di 4
individui con cromosoma lungo 5
--------------------------------------------------------------------------------
1)
11010 v11
121.000000
2)
11101 v23
529.000000
3)
11101 v23
529.000000
4)
00011 v24
576.000000
--------------------------------------------------------------------------------
Codice:
inizializzazione
Inizializzazione della popolazione:
initpop()
{
int j, j1, k, stop;
unsigned mask = 1;
for(j = 0; j < popsize; j++)
{
for(k = 0; k < chromsize; k++)
{
oldpop[j].chrom[k] = 0;
if(k == (chromsize-1))
stop = lchrom - (k*UINTSIZE);
else
stop = UINTSIZE;
for(j1 = 1; j1 <= stop; j1++)
{
oldpop[j].chrom[k] = oldpop[j].chrom[k]<<1;
if(flip(0.5))
oldpop[j].chrom[k] = oldpop[j].chrom[k]|mask;
}
}
oldpop[j].parent[0] = 0; /* Initialize parent info. */
oldpop[j].parent[1] = 0;
oldpop[j].xsite = 0;
objfunc(&(oldpop[j])); /* Evaluate initial fitness */
}
}
Selezione
Metodo della ruota della roulette:
L’individuo ‘i’ ha una probabilità pari a
f (i )
 f (i)
di essere scelto
i
n
quest’area è proporzionale
al valore della fitness
1 2
3
4
Si ripete la selezione tante volte quanti sono gli individui che devono
avere gli stessi genitori
Codice: selezione
Selezione:
int rws(struct individual *pop)
{
float rand, partsum;
int
j,k;
float randomperc();
sumfitness=0;
for(j = 0; j < popsize; j++)
{
sumfitness = sumfitness + pop[j].fitness;
}
rand = randomperc() * sumfitness;
partsum=0.; j=0;
do
{
partsum += pop[j].fitness;
j++;
} while(!((partsum>=rand)||(j==popsize)));
return(j-1);
}
//trova la fitness totale
Esempio
Crossover.
Prima:
s1` = 1111010101
s2` = 1110110101
s5` = 0100010011
s6` = 1110111101
Dopo:
s1`` = 1110110101
s2`` = 1111010101
s5`` = 0100011101
s6`` = 1110110011
Codice: crossover
int crossover (unsigned *parent1, *parent2, *child1, *child2)
{
int j, jcross, k;
unsigned mask, temp;
if(flip(pcross))
{
jcross = rnd(1 ,(lchrom - 1));/* Cross tra 1 and l-1 */ ncross++;
for(k = 1; k <= chromsize; k++)
{
if(jcross >= (k*UINTSIZE)) {child1[k-1] = parent1[k-1]; child2[k-1] = parent2[k-1];}
else if((jcross < (k*UINTSIZE)) && (jcross > ((k-1)*UINTSIZE)))
{
mask = 1;
for(j = 1; j <= (jcross-1-((k-1)*UINTSIZE)); j++)
{ temp = 1; mask = mask<<1; mask = mask|temp; }
child1[k-1] = (parent1[k-1]&mask)|(parent2[k-1]&(~mask));
child2[k-1] = (parent1[k-1]&(~mask))|(parent2[k-1]&mask);
}
else { child1[k-1] = parent2[k-1]; child2[k-1] = parent1[k-1]; }
}
}
else
{
for(k = 0; k < chromsize; k++) { child1[k] = parent1[k]; child2[k] = parent2[k]; }
jcross = 0;
}
return(jcross);
}
Esempio
Mutazione:ogni bit è sottoposto ad una piccola probabilità
d’errore (per esempio 0.1)
Prima:
Dopo:
s1`` = 1110110101
s1``` = 1110100101
f (s1``` ) = 6
s2`` = 1111010101
s2``` = 1111110100
f (s2``` ) = 7
s3`` = 1110111101
s3``` = 1110101111
f (s3``` ) = 8
s4`` = 0111000101
s4``` = 0111000101
f (s4``` ) = 5
s5`` = 0100011101
s5``` = 0100011101
f (s5``` ) = 5
s6`` = 1110110011
s6``` = 1110110001
f (s6``` ) = 6
Codice: mutazione
mutation(child)
unsigned *child;
/* Mutate an allele w/ pmutation, count # of mutations */
{
int j, k, stop;
unsigned mask, temp = 1;
for(k = 0; k < chromsize; k++)
{
mask = 0;
if(k == (chromsize-1))
stop = lchrom - (k*UINTSIZE);
else
stop = UINTSIZE;
for(j = 0; j < stop; j++)
{
if(flip(pmutation))
{
mask = mask|(temp<<j);
nmutation++;
}
}
child[k] = child[k]^mask;
}
}
-------------------------------------------------------------------------------Generation
0
Generation
1
num
string value fitness
parents xsite string value fitness
-------------------------------------------------------------------------------1) 11010 v11
121.000000 | ( 4, 3)
0
00011 v24
576.000000
2) 11101 v23
529.000000 | ( 4, 3)
0
11101 v23
529.000000
3) 11101 v23
529.000000 | ( 2, 4)
0
11101 v23
529.000000
4) 00011 v24
576.000000 | ( 2, 4)
0
00011 v24
576.000000
-------------------------------------------------------------------------------Generation
1
Generation
2
num
string value fitness
parents xsite string value fitness
-------------------------------------------------------------------------------1) 00011 v24
576.000000 | ( 2, 1)
0
11101 v23
529.000000
2) 11101 v23
529.000000 | ( 2, 1)
0
00011 v24
576.000000
3) 11101 v23
529.000000 | ( 4, 3)
0
00011 v24
576.000000
4) 00011 v24
576.000000 | ( 4, 3)
0
11101 v23
529.000000
------------------------------------------------------------------------------Generation
2
Generation
3
num
string value fitness
parents xsite string value fitness
-------------------------------------------------------------------------------1) 11101 v23
529.000000 | ( 3, 4)
2
00101 v20
400.000000
2) 00011 v24
576.000000 | ( 3, 4)
2
11011 v27
729.000000
3) 00011 v24
576.000000 | ( 1, 2)
0
11101 v23
529.000000
4) 11101 v23
529.000000 | ( 1, 2)
0
00011 v24
576.000000
-------------------------------------------------------------------------------Generation
3
Generation
4
num
string value fitness
parents xsite string value fitness
-------------------------------------------------------------------------------1) 00101 v20
400.000000 | ( 4, 3)
3
00001 v16
256.000000
2) 11011 v27
729.000000 | ( 4, 3)
3
11111 v31
961.000000
3) 11101 v23
529.000000 | ( 2, 1)
0
11011 v27
729.000000
4) 00011 v24
576.000000 | ( 2, 1)
0
00101 v20
400.000000
-------------------------------------------------------------------------------Generation
4
Generation
5
num
string value fitness
parents xsite string value fitness
-------------------------------------------------------------------------------1) 00001 v16
256.000000 | ( 2, 2)
3
11111 v31
961.000000
2) 11111 v31
961.000000 | ( 2, 2)
3
11111 v31
961.000000
3) 11011 v27
729.000000 | ( 1, 3)
0
00001 v16
256.000000
4) 00101 v20
400.000000 | ( 1, 3)
0
11011 v27
729.000000
--------------------------------------------------------------------------------
Operatori Alternativi per il Crossover





Crossover a n punti
Scegliere a caso n punti per il crossover
Dividere i cromosomi in questi punti
incrociarli, alternano i genitori
Generalizzazione del crossover a 1 punto
Crossover Uniforme




Assegnare la testa a un genitore, la coda all’altro
Lanciare una moneta per ogni gene del primo figlio
Realizza una copia inversa per il gene del secondo figlio
L’ereditarietà è indipendente dalla posizione
Crossover o mutazione?

Lungo dibattito: qual’è migliore o necessario

Risposta:




dipende dal problema
in generale, è meglio avere entrambi
entrambi hanno il loro ruolo
generalmente, usare solo mutazione è possibile, usare solo
crossover non funziona bene
Rappresentazioni

Possibili codifiche degli individui






Bit strings
Real numbers
Permutations of element
Lists of rules
Elementi di programmi
... strutture dati ...
(0101 ... 1100)
(43.2 -33.1 ... 0.0 89.2)
(E11 E3 E7 ... E1 E15)
(R1 R2 R3 ... R22 R23)
(genetic programming)
Rappresentazioni




Alcuni problemi hanno varabili intere, per. esempio segnali
campionati
Altri problemi hanno valori da un insieme prefissato
Molti problemi sono intrinsicamente reali, tipicamente l’ottimizzazione
f:n
Esempio: la funzione di Ackley’s
Crossover tra valori reali

Discrete:



each allele value in offspring z comes from one of its
parents (x,y) with equal probability: zi = xi or yi
Could use n-point or uniform
Intermediate


exploits idea of creating children “between” parents
(hence a.k.a. arithmetic recombination)
zi = a xi + (1 - a) yi
The parameter

•
•
•
where a : 0  a  1.
a can be:
constant: uniform arithmetical crossover
variable (e.g. depend on the age of the population)
picked at random every time
Crossover aritmetico singolo
•
•
•
Genitori: x1,…,xn  e y1,…,yn
Scegliere a caso un gene (k)
il figlio è:
•
ugualmente per l’altro figlio. Esempio (a = 0.5)
x1 , ..., xk , a  yk  (1  a )  xk , ..., xn
• estensione al caso multiplo
GA: ottimizzazione vincolata


I GA sono adatti per l’ottimizzazione non
vincolata  attività in corso
i metodi proposti sono




basati sulla penalizzazione
basati sula ricerca di soluzioni fattibili
basati sulla preservazione della fattibilità
metodi ibridi