Fondamenti e metodi progettazione

EMOSSOVER

I

V L’algoritmo genetico permette di implementare la teoria di Pareto nella selezione. La

MUTAZIONE

U selezione serve a determinare le configurazioni migliori per poi incrociarle tra loro.

POPOLAZLONE Invece di selezionare le configurazioni migliori seleziono le configurazioni con

dominanza secondo Pareto. Non posso utilizzare la selezione a Roulette (lavorerei con

i valori delle funzioni obiettivo) ma la selezione locale (mi muovo nella griglia e creo

delle isole di configurazioni). Adesso invece che selezionare la configurazione con la f

più elevata si seleziona la configurazione che domina le altre. AL

BASTA

E MINIMA COBKCE

MODIFICA

UNA ghatior

al

lame

Seheirinett

METIENDO mis

M 3M.

bione

aringnda I

munti

il magiqiene

a cons

104

FONDAMENTI NUMERICI DELLA PROGETTAZIONE

Gianluca Caizzi – n. matricola 85300110 A.A. 2009/2010

Csompoche fore tra femalise

maditiche de PAMETO

Il Cross-over classico non dovrà essere modificato perché prende semplicemente le

stringhe delle variabili e le incrocia tra loro (il valore della funzione non viene preso in

considerazione). Se utilizzo un Cross-over direzionale devo fare un piccolo

cambiamento perché in questo caso ho: oneri 1

Nel 2

sab

mon abhattio e

( ) ( ) ( )

( n ) ( i ) ( i ) ( j ) ( i ) ( k )

v v s segno F F v v t segno F F v v

( )

= + ⋅ − ⋅ − + ⋅ − ⋅ − inmera fevern

que over

m m i j m m i k m m crass agi

ser

compomente

Supponendo di avere le tre configurazioni i,j e k selezionate. Devo modificare questa

funzione perché c’è la presenza dei valori delle funzioni. Nel caso multiobiettivo gli F

sono dei vettori con dimensione uguale a n (n componenti). Per modificare il Cross-

over direzionale nel caso multiobiettivo semplicemente faccio un Cross-over

direzionale per ogni obiettivo e metto insieme tutte le informazioni:

n n

ABBa pon

∑ ∑

r n ( ) ( ) ( ) ( )

( R ) ( R ) ( i ) ( j ) ( R ) ( R ) ( i ) ( k )

s segno F F v v t segno F F v v

⋅ − ⋅ − + ⋅ − ⋅ −

R i j q q R i k q q

( n ) ( i )

v v R 1 R 1

= =

= +

q q m

Dove R sono le diverse componenti della funzione obiettivo.

Unico limite in questo caso è che non posso utilizzare variabili di categoria.

mutazione semprE VOVALE

Rimane PERCHE

ANNI CESTATA

20 ALTRIMETODI

O

PARETO

ESPEOSIONE NONANDAVANO BENE

O0 2I

PER MVITIOBBIETIVO E

QUINDI IAPLEMENTATO

HANNO IL TENETICO ROBUSTO

.

NASH

La teoria di Nash è una teoria multiobiettivo che può essere implementata con

qualunque tipo di algoritmo di ottimizzazione. caO

Consideriamo sempre il caso: m 2

IRM

IRÃ = bibimensionale

->

Secondo la teoria di Nash divido le n variabili in due set: alcune variabili vanno

nell’insieme A ed alcune nell’insieme B. ℝ

A B Senei le

× → varóll

.

Per cui mi dà tutto il dominio della funzione. Poi abbiamo due componenti e

A B

∪

divido il campo in tante parti quante sono le componenti: IÎ he

ℝ

f x , y : A B Disid dis

( ) quidi sine

'in port

M che

× → Domiwro imabine

A

OTIMIZZA SOLO 'v

A ℝ

f x , y : A B

( ) × →

13

" B

Le variabili x fanno parte del primo gruppo mentre le variabili y fanno parte del

secondo gruppo. 105

FONDAMENTI NUMERICI DELLA PROGETTAZIONE

Gianluca Caizzi – n. matricola 85300110 A.A. 2009/2010

Il punto ottimale secondo Nash (punto di equilibrio) sarà:

 ( ) ( )

* * * *

f x , y inf f x , y

=



da

A aY B A x A A

de

xTrovaTa ∈

( )

* *

x , y : NASH

PUNTO BIEQUILIBRIO BI .

( ) ( )

* * * *

f x , y inf f x , y

 UNA

= NETROVA SOLO

B y B B

∈

Il punto di equilibrio è un punto in cui, se fisso le variabili y, non posso migliorare la

prima componente lavorando solo sulle variabili x; se fisso y non posso ottimizzare la

MM

seconda componente variando solo le variabili y. È un gioco competitivo perché

ottimizzo la prima componente utilizzando solo le variabili x e la seconda componente

solo utilizzando le variabili y. Ogni giocatore (A e B) può utilizzare solo la variabile x o

solo la variabile y. Il punto ottimale sarà un punto in cui, fissate per il secondo

giocatore le seconde variabili, il primo giocatore non riesce più a migliora la prima

funzione; il secondo giocatore, quando il primo ha fissato le proprie variabili non può

più ottimizzare la seconda funzione.

Siamo nel caso multiobiettivo perché le n componenti sono indipendenti tra loro.

IMPLEMENTAZIONE DELLA TEORIA DI NASH

Siamo sempre nel caso di 2 obiettivi. Dividiamo il set di variabili in due set. Quindi

avrò il giocatore A che lavora solo sulle variabili x e ottimizza solo ; avrò il

f A

giocatore B che lavora solo sulle variabili y e ottimizza solo .

f B se fesseo

è doe mono

cone attimino toni obbeltivo

Le delle shridare

sesonerime quertore

mendlit selidoi

iune

all le sh

impartant

Niin li

VAR h VAR

euguale

'A B mese une

,

litt

importante 2?

è sen a

bere

fremcione d

lo pini

2 ad

Si OBBIETIN 10 OBB

se

ma

com me as .

onive semmre ,

,

own facrir diridere

? fe

Qid o selteri

20 VAR

Im 2-3 01

come a B

finale

qsilihni

d

runto ol attiminar

Comedo

4. he

multidispl

Uh casi

max VAR

nere

de focle

lar

cantiono tre ldi disidate

ron

Parto dalla prima configurazione inizializzando . Il giocatore A può giocare solo

x , y

( )

0 0

con mentre le sono fissate. Quindi ottimizzerà utilizzando solo le variabili x e

y f

x 0 A

troverà che massimizzano .

x f

1 A y mentre le sono fisse a . Ottimizza e

Il giocatore B può giocare solo con x f

x 0 B

troverà che massimizza .

y f

1 B 106

FONDAMENTI NUMERICI DELLA PROGETTAZIONE

Gianluca Caizzi – n. matricola 85300110 A.A. 2009/2010

A questo punto scambio le informazioni e il giocatore A si troverà con e

x , y

( )

1 1

ottimizzerà utilizzando solo le per cui troverà . Analogamente per il

f x x y

,

( )

A 2 1

giocatore B.

Posso scambiare le informazioni più volte fino a trovare un punto nel quale

x y

,

( )

n n

non potrò più ottimizzare nessuno degli obiettivi.

DIFFERENZE PARETO-NASH

1) il risultato di Pareto sono tutte configurazioni ideali, con Nash si trova un unico

punto.

2) La teoria di Nash può essere implementata con qualunque algoritmo di

ottimizzazione perché il primo giocatore ottimizza solo mentre il secondo

f A

giocatore ottimizza solo . Posso usare anche l’algoritmo del gradiente. Quindi

f B

è falsa l’affermazione che solo l’algoritmo genetico può fare un’ottimizzazione

multiobiettivo.

ALCUNE AFFERMAZIONI INDISPENSABILI

1) Pareto trova un set di configurazioni mentre Nash trova un’unica

configurazione. La configurazione di Nash non potrà essere migliore di quella di

Pareto perché Pareto trova tutte le configurazioni migliori dominanti. Facendo

un grafico semplificativo él

Poo Quello che tran

Pn Casita

PARETO OTIMALE che aveitidN NASH

, sie mighire

privrcv

No al

" massibile

Nr 11

. ,

Abbiamo indicato con e il fronte di Pareto o la configurazione di Nash

P N

∞ ∞

che troverei se avessi un algoritmo di ottimizzazione perfetto, cioè se trovassi

sempre il massimo assoluto delle mie funzioni. Nash potrà o appartenere a

Pareto o essere minore di Pareto.

Teoricamente con Pareto ottengo più soluzioni e sicuramente o sono uguali o

migliori rispetto quella di Nash. Tuttavia conviene utilizzare Nash perché

nell’implementazione di Pareto utilizzo l’algoritmo genetico mentre

nell’implementazione di Nash posso usare l’algoritmo del gradiente che è molto

veloce. Poi in Pareto ho sempre tutti gli obiettivi sotto mano quindi l’algoritmo

genetico si troverà un problema molto complicato perché lavora parallelamente

107

FONDAMENTI NUMERICI DELLA PROGETTAZIONE

Gianluca Caizzi – n. matricola 85300110 A.A. 2009/2010

su tutti gli obiettivi. Nash lavora parallelamente ma c’è un algoritmo dedicato

per ogni obiettivo (in teoria potrei avere algoritmi diversi per diversi obiettivi).

Se fissiamo il numero di configurazioni N accade che

N P

∆ < ∆

l’approssimazione del punto di Nash è migliore dell’approssimazione del fronte

di Pareto perché in un caso lavoro con algoritmi monoobiettivo in parallelo

mentre nell’altro caso lavoro con tutti gli obiettivi paralleli tra loro.

Molte volte si fanno le prime iterazioni con la teoria di Nash in modo da trovare

il punto di Nash. Poi utilizzo questo punto nella generazione iniziale di un fronte

di Pareto.

2) Per utilizzare Nash sono costretto a dividere le variabili. Devo dare le variabili x

al primo giocatore e le variabili y al secondo. Devo dividere il campo di

definizione delle variabili stesso. Questo è un problema perché se sbaglio di

dividerle ottengo risultati diversi. In modo preventivo devo fare un’ ANALISI

STATISTICA DEI DATI in modo da dare al primo individuo le variabili che sono

più importanti per la prima funzione obiettivo ed al secondo giocatore le

variabili che sono più importanti per la seconda funzione obiettivo.

STACKELBERG Non colletti

viene solo

Wilma

ti 2

torna

sei

l CAO un

.

La teoria di Stackelberg lavora in maniera simile alla teoria di Nash. Divido le variabili

tra due giocatori con il giocatore A che lavora solo sulle variabili x e il giocatore <b

che lavora solo sulle variabili y. In questo caso però si stabilisce un ordine di

importanza tra i diversi giocatori: È

A LEADER f "

→ IR

✗ →

non :

B FOLLOWER

→ Y

un

Per questo motivo i giochi di Stackelberg vengono chiamati anche giochi gerarchici.

Dire che il giocatore A è il LEADER significa che è più importante rispetto .

f f

A B

Il punto di equilibrio secondo Stackelberg sarà:

 ( ) ( )

* * *

f x , y inf f x , y

=

 A x A