Il metodo delle direzioni coniugate

Il metodo basato sulla minimizzazione lungo direzioni coniugate prevede che nella scelta delle direzioni si possa:

• includere alcune direzioni molto efficienti che permettano di muoversi rapidamente lungo un’eventuale “valle” stretta entro la quale si trova il minimo;

• includere un certo numero di direzioni che “non interferiscano” tra loro, cio`e tali che la minimizzazione lungo una di esse non venga inficiata da successive minimizzazioni lungo le altre, in modo da evitare interminabili cicli lungo le direzioni dell’insieme. Quest’ultimo approccio quello adot- tato nel metodo delle direzioni coniugate (conjugate directions descent method), presentato da Powell nell’articolo [6]: le direzioni coniugate in- fatti sono definite in modo da soddisfare il requisito di “non interferenza” reciproca.

Si analizzano ora gli aspetti teorici e la definizione matematica del concetto finora descritto solo in modo qualitativo.

L’idea del metodo di Powell [14] `e che, se il minimo di una funzione quadratica viene trovato lungo ciascuna di p (p < n) direzioni in uno stadio della ricerca, eseguendo, poi, un passo lungo ciascuna direzione, lo spostamento finale dal- l’inizio fino al passo p-esimo `e coniugato rispetto a tutte le p sottodirezioni di

ricerca.

Il procedimento `e il seguente: Considerate in RN

m direzioni si coniugate rispetto alla matrice A, partendo da un vettore x0₀ in RN

si prendono i vettori s0₁, s0₂, . . . , s0_n paralleli agli assi coordinati.

• Il primo passo `e nella direzione di s0

n, cio´e si minimizza F (x0₀+ λs0_n) rispetto a λ .

• Detto λ0

0 il valore corrispondente al minimo, si pone

x0₁ = x0₀+ λ0₀s0_n • Successivamente si minimizza F (x0₁+ λs0₁) trovando λ0₁; • posto x0 2 = x01+ λ01s01 = x00+ λ00s0n+ λ01s01 si minimizza F (x0 2+ λs02) trovando λ02 ; • si pone quindi x0 3= x02+ λ02s02= x00+ λ00s0n+ λ01s01+ λ02s02

In generale si ha x0_m= x0₀+ Σm−1_i=0 λ0_isi0, avendo posto s0₀ = sn0.

Si pu´o dimostrare [13] che, partendo dal punto x0₀ si arriva al punto xa nella direzione s, e, se iniziando dal punto x1 si arriva al punto xb nella stessa direzione s, se F (xb) < f (xa) allora la direzione xbxa ´e coniugata ad s. Possiamo ora enunciare l’algoritmo di Powell nella sua generalit´a. Al passo k-esimo la procedura ´e la seguente:

3.8. Ottimizzazione di funzioni di pi`u variabili 67 1. Si inizia a xk

0 = xk−1n+1 Da xk

0 si determina λk1, minimizzando F (xk1+ λ2sk2), e si pone xk

2 = xk1+λ2sk2e si prosegue fino a determinare tutti i λki ,per i = 1, . . . , n. La ricerca di λk₀ per minimizzare F (x) nella direzione sk−1_n sar´a discussa al punto 4).

2. Si esegue un passo xk

n− xk0 , che a partire dal punto xkn porta al punto 2xk

n, subordinatamente al verificarsi della condizione al passo 3). 3. Indichiamo con _△k_{la massima riduzione di F (x) in una qualunque di-}

rezione di ricerca al passo k, cio´e

△k_{= maxF (x}k

i−1)− f(xki), i = 1, . . . , n Si pone F1= F (x0k), F2= F (xnk) , F3= F (xkn− xk0) , dove xk 0 = xk−1n ,xkn= xk+1n−1+ λknskn. Se si ha F3 ≥ F1 e/o (F1− 2F2+ F3)(F1− F2− △k)2 ≥ 1₂△k(F1− F3)2, si utilizzano al passo (k +1) esattamente le stesse direzioni di ricerca del passo k-esimo, cio´e si pone

sk+1_i = sk

i i = 1, . . . , n e si inizia a xk+1₀ = xk

n (o da xk+10 = 2xnk− xk0 = xn+1k , a seconda del pi´u basso valore di F(x)).

4. Se la condizione di 3) non `e verificata, si indica con skm la direzione di ricerca che corrisponde a_△k_{; sia s}k_{la direzione corrispondente a x}k

n−xk0 ; tale direzione viene utilizzata per la ricerca di xk+1₀ .

Le nuove direzioni di ricerca al passo k +1 sono allora:

(sk+1₁ , . . . , sk+1 n

5. Il criterio di terminazione `e il seguente: |xk

n− xk0| < ε

Capitolo 4

ALGORITMI DI RICERCA STOCASTICA

Le strategie evolutive furono sviluppate all’Universit`a di Berlino da Ingo Rechen- berg (1973) e Hans Peter Schwefel (1981) [15], per risolvere problemi di ot- timizzazione in alternativa ai metodi classici. In questo capitolo cominceremo con l’introdurre i parametri che sono alla base della teoria evolutiva, e poi esamineremo i diversi algoritmi proposti in letteratura. A partire dai pi`u sem- plici, che considerano strategie a singolo genitore, e quindi una riproduzione asessuata, fino ai pi`u complessi, che invece si basano su strategie con pi`u genitori.

4.1

ES-(µ/ρ

λ) Algorithm

Data un generica funzione di fitness F, definita nello spazio dei parametri N-dimensionale, Y, e con valori nello spazio M-dimensionale, Z:

F : y∈ Y → F(y) ∈ Z. (4.1)

Un problema di ottimizzazione pu`o essere formulato come segue:

determinare il vettore dei parametri ˆy _{∈ Y in cui la funzione assuma il suo} valore ottimo:

dove:

y = (y1, . . . , yN) y = (ˆˆ y1, . . . , ˆyN) (4.3) Le componenti yi di y sono dette variabili oggetto, mentre F rappresenta la funzione obiettivo o funzione di fitness. La natura delle variabili oggetto, e dunque lo spazioY a cui appartengono, dipendono dal tipo di problema di ot- timizzazione in esame. Non ci sono restrizioni all’applicabilit`a dell’algoritmo ES, cio`e le alternative, y_{i ∈ R, oppure yi ∈ N, sono possibili [15]. In seguito,} assumeremo che F sia una una funzione reale con valori reali.

L’ES opera su una popolazione _{B di individui, ognuno dei quali pu`o essere} schematizzato come un punto nello spazio di ricerca, definito completamente da tre parametri: un vettore dei parametri y, un set di strategy parameters s e il corrispondente valore di fitness F (y):

a = (y, s, F(y)). (4.4)

Lo spazio degli stati A `e dato, dunque, dal seguente prodotto tensoriale:

A = Y × S × Z (4.5)

Il set di parametri s, s_{∈ S, `e endogeno, cio`e pu`o variare all’evolvere dell’al-} goritmo, e, come vedremo, gioca un ruolo fondamentale per la self-adaptation dell’ES [15], [16]. Esso non prende parte al calcolo della fitness dell’individuo, ma viene trasmesso agli individui selezionati per la generazione successiva.

Gli individui a, che costituiscono una popolazione, consistono di µ genitori, am, con m = 1, . . . , µ, e λ discendenti, ˜al, con l = 1, . . . , λ.

I parametri µ e λ sono esogeni, cio`e non variano durante l’evoluzione.

Indichiamo, rispettivamente, le popolazioni dei genitori e dei figli al tempo g, con_Bµ(g) e ˜B(g)_λ : B(g)µ ={a(g)m } = (a (g) 1 , . . . , a(g)µ ) B˜ (g) λ ={˜a (g) l } = (˜a (g) 1 , . . . , ˜a (g) λ ) (4.6)

4.1. ES-(µ/ρ +_, λ) Algorithm 71

ES-(µ/ρ +_, λ)-Algorithm line

Begin 1 g = 0; 2 initialize  Bµ(0)= n y(0)m , s(0)m , F(y(0)m )  o  ; 3 Repeat 4 For l=1 To λ Do Begin 5 Cl=reproduction B(g)µ , ρ
; 6 sl =s_recombination Cl, ρ
; 7 ˜sl =s_mutation sl
; 8 y_l=y_recombination _Cl, ρ
; 9 ˜ y_l=y_mutation yl, ˜sl
; 10 ˜ Fl =F(˜yl); 11 End 12 ˜ Bλ(g)= n ˜ y_l, ˜sl, ˜Fl o ; 13

Case selection−type Of 14

(µ, λ) : B(g+1)µ =selectionFµ ˜B (g) λ  ; 15 (µ + λ) : _B(g+1)µ =selectionFµ ˜B (g) λ ,B (g) µ  ; 16 End 17 g = g + 1; 18

Until stop−criterion 19

End 20

Usando queste notazioni, possiamo schematizzare l’algoritmo ES-(µ/ρ +_, λ) come mostrato in fig.4.1 [15].

Oltre λ e µ, un altro parametro esogeno che compare nella notazione (µ/ρ +_, λ) `e ρ. Esso determina il numero dei genitori che partecipano alla riproduzione di un singolo figlio, ricombinando opportunamente il loro patrimonio genetico. Questi genitori formeranno l’insiemeC:

C = (am1, am2, . . . , amr. . . , amρ) (4.7)

Essendo 1≤ ρ ≤ µ, se ρ = 1 si ha una riproduzione asessuata, cio`e l’operatore di ricombinazione sar`a unario, e l’informazione genetica trasmessa non cam- bier`a.

Il caso ρ = 2 rappresenta, invece, la riproduzione biologica standard. Per ρ > 2 si ha una multiricombinazione.

Nell’algoritmo mostrato in fig.4.1 si parte da una popolazione iniziale di indi- vidui,_Bµ(0), ossia da un insieme di possibili soluzioni generate in modo pseudo- casuale, rispettando i costraints dello spazio di ricerca. Segue il ciclo evolutivo, basato su applicazioni successive di operatori genetici alla popolazione_Bµ. Gli operatori genetici usati nell’ES sono: riproduzione, ricombinazione, mu- tazione, e selezione.

Dalla linea 4 alla 19 `e rappresentato il ciclo generazionale: per ogni gener- azione, g, si parte da una popolazione di genitori B(g)µ , da cui deriveranno λ figli, che a loro volta formeranno la popolazione ˜_B(g)_λ , (linee 5-13). Ogni discendente ´e creato passo dopo passo. Prima sono selezionati i suoi genitori (linea 6), poi se ρ > 1 si ha la ricombinazione dei geni (linee 7 e 9), e quindi la mutazione (linee 8 e 10). Invece, per la riproduzione asessuata si passa direttamente all’operatore di mutazione.

L’operatore di ricombinazione, detto crossover, a differenza di quello di mutazione, non `e controllato dall’insieme dei parametri di strategia, ˜sl. Il risultato sar`a un nuovo insieme di parametri, ˜yl, su cui `e valutata la fitness (linea 11).

4.1. ES-(µ/ρ +_, λ) Algorithm 73 i”. Alla fine, a seconda del criterio di selezione usato, ((µ, λ) o (µ + λ)) si avr`a la nuova popolazione di genitoriB(g+1)µ , a cui sar`a associata il valore di fitness Fµ.

Il ciclo generazionale continuer`a fino a quando non si raggiunge un criterio di stop predefinito.

L’azione degli operatori genetici in un EA `e molto importante, visto che dalla loro azione dipendono le performance dell’algoritmo.