Bin Packing Problem Gruppo 7 Gruppo 7 Claudio Graffone Claudio Graffone Giovanni Peditto Giovanni...

Bin Packing ProblemBin Packing Problem

Gruppo 7Gruppo 7

Claudio Graffone Claudio Graffone Giovanni PedittoGiovanni Peditto Yary RiberoYary Ribero

Best Bins LastBest Bins Last


Valutazione dell'OttimoValutazione dell'Ottimo Abbiamo definito uno scarto percentuale Abbiamo definito uno scarto percentuale

dall'ottimodall'ottimo

Ed abbiamo calcolato media e varianza Ed abbiamo calcolato media e varianza su tutte le istanze a meno dei tre risultati su tutte le istanze a meno dei tre risultati migliori e peggiori.migliori e peggiori.


InizializzazioneInizializzazione

Dopo aver provato inizializzazioni basate sul Dopo aver provato inizializzazioni basate sul volume, la migliore è risultata quella che volume, la migliore è risultata quella che prevede score crescenti in base alla prevede score crescenti in base alla posizione dell'oggetto nella soluzione.posizione dell'oggetto nella soluzione.


Il codice d'inizializzazioneIl codice d'inizializzazione


La funzione di Short Term UpdateLa funzione di Short Term Update

• Il metodo Best Bins Last prevede di scegliere per Il metodo Best Bins Last prevede di scegliere per ultimi i bins più promettenti e di decrementarne lo ultimi i bins più promettenti e di decrementarne lo score di un valore alpha.score di un valore alpha.

• Abbiamo deciso di provare anche altre Abbiamo deciso di provare anche altre combinazioni (bin peggiori e scores crescenti ...), combinazioni (bin peggiori e scores crescenti ...), fino a scoprire che, nel nostro caso la migliore è fino a scoprire che, nel nostro caso la migliore è quella che corrisponde al metodo Worst Bin First.quella che corrisponde al metodo Worst Bin First.


Il valore di kIl valore di k Abbiamo trovato che il metodo dà soluzioni Abbiamo trovato che il metodo dà soluzioni

ottimali per una finestra di ampiezza k ottimali per una finestra di ampiezza k compresa tra 3 ed un quinto dei bins compresa tra 3 ed un quinto dei bins disponibili per l’istanza del problema.disponibili per l’istanza del problema.

Valori superiori cambiano gli scores di molti Valori superiori cambiano gli scores di molti oggetti mescolando eccessivamente le carte oggetti mescolando eccessivamente le carte in tavola.in tavola.


Il valore alfa (I)Il valore alfa (I)

Con alfa statico o monotono non Con alfa statico o monotono non riuscivamo a scendere al di sotto di una riuscivamo a scendere al di sotto di una soglia ragionevole (~1,51%).soglia ragionevole (~1,51%).


Il valore alfa (II)Il valore alfa (II)Imponendo alfa casuale tra 0,05 e 1 i risultati Imponendo alfa casuale tra 0,05 e 1 i risultati sono migliorati di molto.sono migliorati di molto.

0

1

2

3

4

5

6

25

50

100

500

25

50

200

500

25

100

200

500

25

100

200

500

50

100

500

25

50

100

500

numero di oggetti

fun

zio

ne o

bie

ttiv

o


Il codice della Short Term UpdateIl codice della Short Term Update


La Long Term UpdateLa Long Term Update

L'aggiornamento a lungo termine assegna L'aggiornamento a lungo termine assegna scores tendezialmente migliori agli oggetti scores tendezialmente migliori agli oggetti nei primi posti della soluzione attuale, a nei primi posti della soluzione attuale, a meno di una variabile casuale che aumenta meno di una variabile casuale che aumenta le possibilità di trovare nuovi ottimi nel caso le possibilità di trovare nuovi ottimi nel caso ci trovassimo in un buon intorno.ci trovassimo in un buon intorno.


Reverse Simulated AnnealingReverse Simulated Annealing

L'inversione sta nel fatto che, nel nostro L'inversione sta nel fatto che, nel nostro caso, la temperatura si alza ponendo rimedio caso, la temperatura si alza ponendo rimedio al congelamento degli scores a lungo al congelamento degli scores a lungo termine.termine.

Per introdurre un po' di varianza nelle Per introdurre un po' di varianza nelle reinizializzazioni, abbiamo fatto nostra la reinizializzazioni, abbiamo fatto nostra la filosofia dell'algortimo simulated annealing.filosofia dell'algortimo simulated annealing.


La Temperatura del sistemaLa Temperatura del sistema

Abbiamo scoperto sperimentalmente che il valore Abbiamo scoperto sperimentalmente che il valore iniziale da imporre è 0 e l’incremento ottimo è iniziale da imporre è 0 e l’incremento ottimo è 0,2. 0,2.

Questo permette alla temperatura di non salire Questo permette alla temperatura di non salire mai oltre il valore 20, soglia sopra il quale le mai oltre il valore 20, soglia sopra il quale le soluzioni si allontanano dalla soluzione ottimasoluzioni si allontanano dalla soluzione ottima


Il codice della Long Term UpdateIl codice della Long Term Update


Criteri di Stop (I)Criteri di Stop (I)

N. max di iterazioni: 10000N. max di iterazioni: 10000 N. max di iterazioni non miglioranti: N. max di iterazioni non miglioranti:

25002500 Temperatura massima: 20Temperatura massima: 20


Criteri di Stop (II)Criteri di Stop (II)

Questi tre criteri, combinati assieme, Questi tre criteri, combinati assieme, riducono notevolmente il numero di riducono notevolmente il numero di iterazioni a vuoto e permettono di iterazioni a vuoto e permettono di continuare a lungo l'analisi dei soli continuare a lungo l'analisi dei soli problemi che producono, di tanto in problemi che producono, di tanto in tanto, nuove soluzioni ottime.tanto, nuove soluzioni ottime.


Risultati (I)Risultati (I) Il nostro algoritmo tende ad essere Il nostro algoritmo tende ad essere

particolarmente efficace con istanze del particolarmente efficace con istanze del problema che hanno numerosi oggetti.problema che hanno numerosi oggetti.

3 istanze non sono mai scese al di sotto del 3 istanze non sono mai scese al di sotto del 5% dall'ottimo: 3_A_0_3, 3_A_0_4 e 5% dall'ottimo: 3_A_0_3, 3_A_0_4 e 3_A_0_5 e sono state sempre scelte per 3_A_0_5 e sono state sempre scelte per essere scartate dalla media finale.essere scartate dalla media finale.


Risultati (II)Risultati (II)

Il programma, al netto della Long Term Il programma, al netto della Long Term Update, ha una distanza dal LB pari a Update, ha una distanza dal LB pari a

~1,65%~1,65% Valore dal quale ci siamo allontanati poco Valore dal quale ci siamo allontanati poco

prima di introdurre l'algoritmo del Reverse prima di introdurre l'algoritmo del Reverse Simulated Annealing.Simulated Annealing.


Risultati (III)Risultati (III)

Aggiungendo l'algoritmo Reverse Aggiungendo l'algoritmo Reverse Simulated Annealing, abbiamo ottenutoSimulated Annealing, abbiamo ottenuto

ottimi oscillanti tra i valori ottimi oscillanti tra i valori

1,26-1,30%1,26-1,30%

Con un minimo assoluto pari a Con un minimo assoluto pari a 1,252%1,252%

Con una varianza di circa Con una varianza di circa 0,90,9

FINEFINE

Bin Packing Problem Gruppo 7 Gruppo 7 Claudio Graffone Claudio Graffone Giovanni Peditto Giovanni...

Documents

Transcript of Bin Packing Problem Gruppo 7 Gruppo 7 Claudio Graffone Claudio Graffone Giovanni Peditto Giovanni...