2.5 Struttura di base degli algoritmi genetici
2.5.2 Funzione di fitness
In un EA la funzione di fitness viene introdotta, in accordo al modello darwiniano per quantificare la capacità di un individuo di sopravvivere e riprodursi nel proprio ambiente. Solo gli individui con il migliore fenotipo hanno la possibilità di sopravvi- vere e di avere degli eredi.
La funzione di fitness misura, pertanto, quanto sia buona la soluzione rappresentata dal genoma di un individuo e mappa l’insieme dei cromosomi in uno spazio scalare R, come espresso dalla (2.8)
ψ : Γnz −→ R (2.8)
dove Γ rappresenta il tipo di dato dei cromosomi γi del genoma ¯γ.
Nei problemi di ottimizzazione a singolo obiettivo la funzione di fitness dipende dalla funzione obiettivo e in molti casi coincide con essa. Nei problemi multi-obiettivo la funzione di fitness è distinta dalle funzioni obiettivo ed è possibile definire a parità di obiettivi fi x
diverse funzioni di fitness.
In generale la rappresentazione del genoma ¯γ differisce dalla rappresentazione delle
variabili di decisione xi che determinano i valori delle funzioni obiettivo, e la funzione di fitness dipende dal vettore (2.1) dei valori fi x. La funzione di fitness è espressa
formalmente dalla (2.9),
38 2. Tecniche euristiche di Ottimizzazione Multiobiettivo
dove Ω rappresenta lo spazio di ricerca per il vettore delle funzioni obiettivo, φ la funzione di decodifica del genoma, F le funzioni obiettivo e Υ la funzione di ridimensionamento.
La funzione di fitness fornisce una misura assoluta della qualità della soluzione, ma in alcuni casi ( algoritmi coevolutivi) è utilizzata una misura relativa quantificando le prestazioni della fitness di un individuo rispetto agli altri individui.
La definizione specifica della funzione di fitness dipende dalla particolare tipolo- gia del problema di ottimizzazione. Nei problemi di ottimizzazione non vincolati a singolo obiettivo per i quali Ω coincide con Γnz, solitamente la funzione di fitness
coincide con la funzione obiettivo.
Nei problemi di ottimizzazione multiobiettivo non vincolati, spesso la funzione di fitness è ottenuta dalla scalarizzazione dei valori delle funzioni obiettivo, ovvero dell’aggregazione lineare dei valori obiettivo fi x:
ψ =
k
X
i=1
wifi x (2.10)
dove wi ≥ 0 con i = 0, . . . , k sono coefficienti che tengono conto dell’importanza
delle k funzioni obiettivo.
Nei problemi di ottimizzazione multiobiettivo vincolati la funzione di fitness viene in molti casi calcolata come somma ponderata delle componenti del vettore delle funzioni obiettivo e del valore di una funzione di penalità SVC che tiene conto del soddisfacimento dei vincoli, eq.(2.13). La funzione di penalità è spesso definita [102] come: SV C x, t = (γ × t)α m+p X v=1 pv x, t β (2.11) dove pv x, t= nmax 0, gi x α se i ∈ 1, 2, . . . , m | hj x|α se j ∈1, 2, . . . , p (2.12)
con α, β e γ costanti positive. Nella eq. (2.11) t è l’indice di iterazione, per cui più è lunga la ricerca e più aumenta la penalità. Una scelta comunemente adottata per
2.5 Struttura di base degli algoritmi genetici 39 i parametri è α = β = 2 e γ = 0.5 ψ x, t = k X i=1 wifi x, t+ λ · SVC (2.13)
Un approccio alternativo per il calcolo della fitness dei MOP è quello introdotto da Goldberg [103] e basato sul concetto di ottimalità di Pareto. L’obiettivo è quello introdurre una classificazione (ranking) delle soluzioni della popolazione corrente attraverso una procedura iterativa.
Inizialmente si identificano gli individui non dominati all’interno della popolazione e si assegna ad essi un certo valore del rank rs. Successivamente, si separano gli individui con rank rs dalla popolazione e si rieffettua il ranking della popolazione
rimanente. Il procedimento viene iterato più volte fino a classificare tutti gli individui della popolazione.
Il valore del rank può essere assegnato in più modi:
• calcolando il numero di individui da cui un certo individuo è dominato +1 (dominance ranking), ovvero rank ¯γu= 1 + psu,con psu numero di individui
che dominano ¯γu;
• determinando il numero di individui dominati da un certo individuo (dominance
count) ovvero rank ¯γu= piu, con piu numero di individui dominati da ¯γu.
Per assegnare la fitness sulla base del ranking esistono varie tecniche. Alcuni approcci usano il valore del dominance rank, altri quello del dominance count. In [104] dopo aver proceduto al dominance ranking della popolazione il valore della fitness viene computato in due passi :
• si assegna ad ogni individuo ¯γu un valore iniziale di fitness ψ0 ¯γu ottenuto
dall’interpolazione del rank ( con una funzione lineare o esponenziale) a partire dal valore assunto per l’individuo migliore (non dominato) fino al valore assunto per l’individuo peggiore;
• si effettua la media dei valori di fitness ψ0 γ¯ per gli individui nella stessa
classe di ranking in modo che la fitness globale di tutta la popolazione rimanga costante e gli individui di una stessa classe di ranking vengano selezionati con la stessa frequenza.
40 2. Tecniche euristiche di Ottimizzazione Multiobiettivo
In [105] la fitness di ogni individuo è un valore che dipende dalla profondità di dominanza e dalla densità di affollamento all’interno del sottoinsieme dei vicini; tale valore si ricava eseguendo i seguenti passi:
• si identificano dapprima gli individui non dominanti nella popolazione corrente per costruire il fronte a rank 1;
• si assegna a tutti gli individui del fronte uno stesso valore fittizio di fitness ψi0;
• si calcola per gli individui del fronte il valore della funzione di sharing espressa dalla (2.14) Sh(di,j) 1 −di,j σsh α se di,j ≤ σsh 0 se di,j > σsh (2.14)
dove ¯γi e ¯γj sono due individui sullo stesso fronte, di,j la distanza tra i due
fenotipi, σsh un parametro che misura la massima distanza ammessa per
considerare due individui vicini nello spazio obiettivo;
• si modifica il valore iniziale della fitness degli individui del fronte ponendola pari al valore(2.15), com m numero di individui sul fronte;
ψi=
ψi0 Pm
j=1Sh di,j
(2.15)
• si separano gli elementi del fronte dalla popolazione e si reitera il procedimento sugli individui rimanenti della popolazione avendo cura di scegliere come valore iniziale della funzione di fitness del nuovo fronte di individui non dominanti un valore che sia inferiore al valore minimo di shared fitness del fronte precedente. Un metodo ulteriore di determinazione della fitness è quello proposto in [106] in cui si prende in considerazione sia il numero di individui dominati (dominance
2.5 Struttura di base degli algoritmi genetici 41