Ricerca Operativa: Tesina di · 2017. 11. 26. · Ricerca Operativa: Tesina di approfondimento...
Transcript of Ricerca Operativa: Tesina di · 2017. 11. 26. · Ricerca Operativa: Tesina di approfondimento...
-
Ricerca Operativa: Tesina di approfondimento
Dipartimento di ingegneria dell’informazione delle infrastrutture e dell’energia sostenibile
a.a. 2015/2016
Make My Match
Algoritmo Squadre Equilibrate
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice Diego Marrara Giacinto Tripodi
-
Indice
Descrizione del Contesto Pag. 1
Prima Formulazione Pag. 3
Seconda Formulazione Pag. 4
Risoluzione
Hungarian Algorithm Pag. 5
Knapsack Problem Pag. 6
Metodo del Simplesso Pag. 8
Terza Formulazione Pag. 10
Soluzione Pag. 11
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
Descrizione del Contesto
Dati N giocatori, ognuno caratterizzato da cinque valori chiave, si vuole creare un algoritmo in
grado di dividere tali giocatori in due insiemi S1, S2, tali per cui la differenza tra i due insiemi,
rispetto ad ognuno dei cinque valori caratterizzanti, sia minima.
I valori chiave che caratterizzano i cinque giocatori sono numerici ed appartengono all’intervallo
che va da 0 a 100. Possiamo indicarli mediante la denominazione: Profilo Psicologico, Profilo
Tecnico, Profilo Offensivo, Profilo Difensivo e Profilo Atletico.
I valori caratterizzanti i due insiemi corrispondono alla somma dei valori caratterizzanti dei
giocatori quando vengono assegnati all’insieme.
Una rappresentazione grafica del problema può aiutare a comprendere meglio il comportamento
richiesto all’algoritmo. Si ha dunque:
In questo caso, siano Gi con i=1,2,3,4 i giocatori (quindi N=4), si avrebbe dunque:
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
1
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
S1
Profilo Psicologico S1= Prof. PsicologG1 + Prof PsicologG3 = 20 + 74 = 94 Profilo Tecnico S1 = Prof. Tecnico G1 + Prof Tecnico G3 =87 + 91 = 178 Profilo Offensivo S1 = Prof.Offensivo G1 + Prof Offensivo G3 = 75 + 78 = 153 Profilo Atletico S1 = Prof. Atletico G1 + Prof Atletico G3 =80+ 83 = 163 Profilo Difensivo S1 = Prof. Difensivo G1 + Prof Difensivo G3 = 70 + 78 = 148
S2
Profilo Psicologico S2= Prof. PsicologG2 + Prof PsicologG4 = 18+ 74 = 92 Profilo Tecnico S2 = Prof. Tecnico G2 + Prof Tecnico G4 =65 + 91 = 156 Profilo Offensivo S2 = Prof.Offensivo G2 + Prof Offensivo G4 = 83 + 78 = 161 Profilo Atletico S2 = Prof. Atletico G2 + Prof Atletico G4 =70+ 83 = 153 Profilo Difensivo S2 = Prof. Difensivo G2 + Prof Difensivo G4= 78+ 78 = 156
La distanza, parametro per parametro, tra i due insiemi sarebbe dunque:
Profilo Psicologico S1 Profilo Psicologico S2 = 9492 = 2 Profilo Tecnico S1 Profilo Tecnico S2 = 178156 = 22 Profilo Offensivo S1 Profilo Offensivo S2 = |153 168| = 15 Profilo Atletico S1 Profilo Atletico S2 =163153 = 10 Profilo Difensivo S1 Profilo Difensivo S2 = |148156| = 8
In questo esempio costruito ad hoc, i giocatori 3 e 4 hanno parametri identici e leggermente
migliori dei giocatori 1 e 2, questo ci “obbliga” a collocarli in due insiemi separati e, a questo
punto, non fa molta differenza in quale insieme vengano collocati i primi due elementi.
E’ inoltre importante notare come, per la differenza tra il profilo Offensivo e per la differenza tra i
profili Difensivi delle due squadre sia stato necessario introdurre il valore assoluto. Eventuali
distanze negative indicherebbero che l’insieme S2 ha valori più alti di S1 ma non è quello che ci
interessa sapere.
Partendo da questo problema siamo andati a sviluppare dei modelli che ci permettessero di
arrivare ad un risultato concreto, andiamo a vedere quali.
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
2
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
Prima Formulazione
Per la primissima formulazione, abbiamo adottato come linea guida il modello fornito dal
“Problema di Assegnazione”. In questo problema, analizzato durante il corso, si devono assegnare
n attività ad m persone, minimizzando i costi, sotto i vincoli:
● n=m
● Ogni attività deve essere assegnata ad una sola persona
● Ogni persona deve svolgere una sola attività
La formulazione ottenuta partendo da questo modello è la seguente:
Siano: Ci= Valore Profilo Psicologico del Giocatore i
Ti= Valore Profilo Tecnico del Giocatore i
Oi= Valore Profilo Offensivo del Giocatore i
Ai= Valore Profilo Atletico del Giocatore i
Di= Valore Profilo Difensivo del Giocatore i
Sia xij la variabile decisionale che indica:
Allora si vuole individuare:
Con i vincoli
Tale formulazione si è però rivelata eccessivamente complessa rispetto al problema in analisi ed al
livello di precisione richiesto per cui si è scelto di creare una versione semplificata che non ci
ponesse davanti alla risoluzione di un problema multiobiettivo.
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
3
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
Seconda Formulazione
Per semplificare il problema ottenuto mediante la prima formulazione si è scelto di analizzare
ognuno dei cinque parametri caratterizzanti i giocatori separatamente, per poter individuare un
ottimo da utilizzare in seguito come riferimento. Il problema è dunque diventato:
Ognuno di questi cinque problemi è soggetto ai vincoli:
Risolti tali problemi si hanno dunque cinque valori ideali e cinque diverse combinazioni degli
insiemi. Per ognuna di tali soluzioni è possibile calcolare, per ognuno dei cinque parametri
caratterizzanti, lo scarto con il valore ideale.
Una volta calcolato tale scarto è possibile dunque calcolare una media degli scarti e scegliere la
soluzione con il valore medio dello scarto più basso.
Sia h=1, 2, .., 5 l’indice che specifica quale delle cinque soluzioni ricavate sto analizzando (es h=3
indica che sto valutando lo scarto, per ogni parametro caratterizzante, della soluzione che da il
valore ottimo del Profilo Offensivo) e sia g=1, 2, …, 5 il parametro che indica quale, tra le cinque soluzioni ottime ricavate in precedenza, sto analizzando. Si ha:
NB: Sappiamo che b gh =0 quando g=h (sto valutando proprio la soluzione chemi da l’ottimo in quel parametro caratterizzante) quindi il calcolo potrebbe essere omesso.
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
4
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
Risoluzione
Hungarian Algorithm
Il Metodo Ungherese è un metodo di ottimizzazione combinatoria che risolve in tempo
polinomiale il problema dell’assegnamento. Il metodo è stato sviluppato nel 1955 anticipando i
successivi metodi “primaleduale” e la complessità dell’algoritmo è di O(n 3).
La prima idea è stata quella di usare questo algoritmo, specificatamente pensato per risolvere i
problemi di matching, adattandolo al nostro contesto. Ne abbiamo dunque valutato il
funzionamento:
Data una matrice n x n di costi C= cij :
1. Per ogni riga, individuare il minimo e sottrarlo a tutti gli elementi della riga;
2. Per ogni colonna, individuare il minimo e sottrarlo a tutti gli elementi della colonna;
3. Coprire con il minor numero di linee tutti gli zeri che si sono formati con le precedenti sottrazioni; a. Determinare un assegnamento (anche incompleto, ovvero un assegnamento in cui può esistere
qualche riga non assegnata a nessuna colonna);
b. Marcare le righe non assegnate;
c. Per ogni riga marcata non ancora esaminata, marcare le colonne che presentano uno zero su
tale riga;
d. Per ogni colonna non marcata, marcare le righe che presentano un assegnamento su tali
colonne;
e. Ripetere dallo step 3 fino ad esaurimento delle righe marcate non ancora visitate;
f. Il numero minimo di linee si ottiene selezionando le colonne marcate e le righe non marcate.
4. Se il numero minimo di linee necessarie è pari a n è possibile determinare un assegnamento ottimo altrimenti procedere con lo step 5;
5. Individuare il minimo tra gli elementi non coperti da linee, sottrarlo agli elementi non coperti e
sommarlo agli elementi che sono incrocio di due linee. Tornare allo step 3.
Il problema di questo algoritmo è di essere intrinsecamente legato ai problemi di matching in cui
n=m quindi è richiesto che la matrice C sia quadrata. Dopo alcuni tentativi di adattamento si è
quindi scelto di condurre un’analisi che ci permettesse di risolvere il problema mediante gli
algoritmi valutati durante il corso.
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
5
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
Knapsack Problem
Il secondo tentativo è stato effettuato modellando il sistema in accordo a quanto indicato dal
“problema dello zaino”.
Abbiamo quindi definito degli item, ognuno di valore corrispondente al parametro caratterizzante
in analisi e, ad ognuno degli n item, è stato associato lo stesso peso (cioè 1).
Lo zaino ha invece capienza n/2 di modo che esso sia in grado di accettare la metà dei giocatori.
Nell’esempio riportato di seguito consideriamo il valore Tecnico dei giocatori:
Il codice riportato di seguito è formato da due funzioni, la prima “precalcola” le combinazioni dei
giocatori (ad esempio 12, 13, 14 ,23, 24, 34) mentre la seconda valuta, per la combinazione in
esame, il peso ( che risulta sempre uguale ad n/2), il valore, il valore della combinazione esclusa
(calcolato come differenza tra il valore totale dello zaino con tutti i 4 elementi ed il valore dello
zaino con la combinazione in analisi) e la differenza di valore tra la combinazione in analisi e quella
esclusa.
Quest’ultima differenza si rivela fondamentale. Tramite essa infatti possiamo determinare se
inserire la nuova combinazione all’interno dello zaino omeno. In particolare quando il valore dello
zaino è maggiore della differenza attualmente in esame allora vuol dire che ho migliorato tale
differenza e posso considerare la nuova combinazione come appartenente allo zaino.
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
6
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
Questa versione dell’algoritmo funziona e riesce a produrre il risultato desiderato (anche nel caso in cui n = dispari) tuttavia, essendo basata su un approccio di tipo brute force, va in difficoltà al crescere del numero di item da collocare in ogni squadra.
Esempio di output del “Brute Force Knapsack Implementation” relativo al profilo Tecnico
I tentativi effettuati sfruttando algoritmi che risolvono il “knapsack problem” in modo dinamico
(vedi https://rosettacode.org/wiki/Knapsack_problem/01#Dynamic_programming_solution ) non si sono rivelati altrettanto semplici da gestire e si è quindi scelto di virare sul metodo del
simplesso.
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
7
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
Metodo del Simplesso
Il primo passo, per poter risolvere il problema tramite il metodo del simplesso, è stato quello di
esplicitare la funzione obiettivo ed i vincoli per poter andare a definire con precisione la matrice A
e il vettore b.
Sia x i il generico parametro caratterizzante preso in esame, sia m=4 il numero dei giocatori e sia n=2 il numero delle squadre da creare, si ha dunque:
> C 1x 11 + C 2x 21 + C 3x 31 + C 4x 41 ( C 1x 12 + C 2x 22 + C 3x 32 + C 4x 42)
Subject to:
x 11 + x 12 = 1 x 21 + x 22 = 1
> x 31 + x 32 = 1 x 41 + x 42 = 1
x 11 + x 21 + x 31 + x 41 = 2 > x 12 + x 22 + x 32 + x 42 = 2
Che in forma matriciale diventa dunque:
min {c T x : Ax=b, x ≥ 0} con: c T = [c 1 , c 1 , c 2 , c 2 , c 3 , c 3 , c 4 , c 4 ]
x T = [x 11 , x 12 , x 21 , x 22 , x 31 , x 32 , x 41 , x 42 ] b T = [1, 1, 1, 1, 2, 2]
x 11 x 12 x 21 x 22 x 31 x 32 x 41 x 42 i=1 1 1 0 0 0 0 0 0
i=2 0 0 1 1 0 0 0 0
i=3 0 0 0 0 1 1 0 0
A = i=4 0 0 0 0 0 0 1 1
j=1 1 0 1 0 1 0 1 0
j=2 0 1 0 1 0 1 0 1
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
8
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
Possiamo inoltre notare come la matrice A sia TOTALMENTE UNIMODULARE questo, come appreso durante il corso, garantisce (per un problema di PLI) che la formulazione originale
coincide con la rappresentazione ideale e, dunque, essendo b intero allora si può dire che: “il poliedro P = {x ∈ Rn : Ax =b; x ≥ 0} ha solo vertici interi, cioè se esiste una soluzione di base ottimale, essa è intera”.
NB: Essendo i vincoli del problema espressi tutti mediante uguaglianze sarebbe stato sufficiente
avere una matrice UNIMODULARE per avere la garanzia della risolvibilità del problema.
Il problema è stato risolto sfruttando l’optimization tool di matlab:
Questa seconda formulazione del problema, seppur formalmente corretta ed adeguatamente
risolta tramite il metodo del simplesso, non tiene in considerazione che lo scarto che ci interessa
minimizzare è quello relativo al valore assoluto della differenza (come detto in fase di introduzione
sapere che l’insieme 2 ha valori maggiori dell’insieme 1 non è di nostro interesse).
Si è dovuto quindi modificare la formalizzazione arrivando ad un problema quadratico con vincoli lineari .
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
9
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
Terza Formulazione
> [C 1x 11 + C 2x 21 + C 3x 31 + C 4x 41 ( C 1x 12 + C 2x 22 + C 3x 32 + C 4x 42) ]2
I vincoli del problema restano inalterati rispetto alla formulazione precedente, abbiamo cioè:
x 11 + x 12 = 1 x 21 + x 22 = 1
> x 31 + x 32 = 1 x 41 + x 42 = 1
x 11 + x 21 + x 31 + x 41 = 2 > x 12 + x 22 + x 32 + x 42 = 2
Sappiamo che ogni problema quadratico può essere espresso in
forma:
E la matrice Q ha coefficienti: q ij è il coefficiente di x i , x j per i ≠ j ½ q jj è il coefficiente di x j 2
Nel nostro caso, non esiste alcuna parte lineare ed abbiamo quindi:
A differenza di quanto avveniva nella risoluzione tramite metodo del simplesso in questo caso
l’algoritmo richiede anche il calcolo di:
cT = [0, 0, 0 ,0] → poichè, come detto, non esiste parte lineare
C 12/2 C 1(C 1) C 1(C 2) C 1(C 2) C 1(C 3) C 1(C 3) C 1(C 4) C 1(C 4)
Q = ⋮ ⋯ ⋮ C 4(C 1) C 4(C 1) C 4(C 2) C 4(C 2) C 4(C 3) C 4(C 3) C 4(C4) (C 4) 2/2
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
10
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
Soluzione
Il problema quadratico è stato risolto mediante l’Optimization Toolbox di Matlab, che mette a
disposizione la libreria “quadprog” in grado di risolvere i problemi quadratici.
La firma del metodo è: quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
In particolare la voce “options” ci permette di specificare al tool quale metodo di risoluzione
utilizzare. Nel nostro caso è stato il tool stesso a consigliare “activeset” che sfrutta il metodo della
“Discesa di Gradiente” per arrivare al risultato.
La procedura per la soluzione del problema prevede due fasi, la prima calcola un punto
ammissibile (se ne esiste uno) e la seconda genera una sequenza di punti ammissibili fino a
convergere alla soluzione (si veda per ulteriori dettagli:
http://it.mathworks.com/help/optim/ug/quadraticprogrammingalgorithms.html#brozzpo )
Nel nostro caso siamo quindi andati a dichiarare (NB: C=Vettore dei Costi, H è la matrice Q del
problema formalizzato in precedenza mentre f=C T ):
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
11
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
Ed invocando:
Si ottiene:
Il problema viene quindi correttamente risolto e le squadre vengono equilibrate in modo
adeguato.
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
12
-
Make My Match: Algoritmo per la creazione di Squadre Equilibrate
Università Mediterranea – CdL Ingegneria Informatica e dei sistemi per le telecomunicazioni – Ricerca Operativa
Note
Professoressa: Mariantonia Cotronei
Studenti: Paolo Lo Giudice, Diego Marrara, Giacinto Tripodi
13