Cutting stock bidimensionale

21
Contents 1 Cutting stock bidimensionale vii 1.1 Descrizione del problema ....................... viii 1.2 Risoluzione del problema con algoritmo genetico .......... x 1.2.1 Rappresentazione genetica del problema .......... xii 1.2.2 Scelta della funzione di fitness ................ xii 1.2.3 Strutture dati ......................... xii 1.2.4 Cromosoma in dettaglio ................... xii 1.3 Operazioni genetiche ......................... xiii 1.3.1 Fase di creazione ....................... xiii 1.3.2 Fase di riproduzione ..................... xiv 1.3.3 Fase di visualizzazione .................... xvii Bibliography xx i

description

Nel problema del taglio del vetro (conosciuto come cutting stock bidimensionale o TDC), dato uno stock rettangolare di materia prima di dimensioni (L,W), e dato un insieme P di pezzi rettangolari desiderati a ciascuno dei quali e` associata una coppia di dimensioni (l,w), si deve trovare l’insieme di pezzi, sottoinsieme di P, estraibile dallo stock che massimizzi la somma dei profitti dei pezzi in esso contenuti (Figure 1.1). Un insieme S di pezzi estraibile `e definito in letteratura come “feasible pattern”. Un esempio di pezzi non estraibile, nel caso di stock con dimensioni (5, 5) `e S = (3, 3), (4, 4). Se piu` pezzi sono identici essi costituiscono un “tipo” di pezzo ed il numero ne rappresenta la domanda. Un caso particolare di TDC `e classificato come guillotine e riguarda tutte le problematiche di taglio di sagome a partire da un unico pezzo e si prefigge come obiettivo quello di minimizzare lo sfrido (scarto) con alcuni vincoli operativi.

Transcript of Cutting stock bidimensionale

Page 1: Cutting stock bidimensionale

Contents

1 Cutting stock bidimensionale vii

1.1 Descrizione del problema . . . . . . . . . . . . . . . . . . . . . . . viii

1.2 Risoluzione del problema con algoritmo genetico . . . . . . . . . . x

1.2.1 Rappresentazione genetica del problema . . . . . . . . . . xii

1.2.2 Scelta della funzione di fitness . . . . . . . . . . . . . . . . xii

1.2.3 Strutture dati . . . . . . . . . . . . . . . . . . . . . . . . . xii

1.2.4 Cromosoma in dettaglio . . . . . . . . . . . . . . . . . . . xii

1.3 Operazioni genetiche . . . . . . . . . . . . . . . . . . . . . . . . . xiii

1.3.1 Fase di creazione . . . . . . . . . . . . . . . . . . . . . . . xiii

1.3.2 Fase di riproduzione . . . . . . . . . . . . . . . . . . . . . xiv

1.3.3 Fase di visualizzazione . . . . . . . . . . . . . . . . . . . . xvii

Bibliography xx

i

Page 2: Cutting stock bidimensionale

ii CONTENTS

Page 3: Cutting stock bidimensionale

List of Tables

iii

Page 4: Cutting stock bidimensionale

iv LIST OF TABLES

Page 5: Cutting stock bidimensionale

List of Figures

1.1 Esempio di TDC . . . . . . . . . . . . . . . . . . . . . . . . . . . viii

1.2 TDC ghigliottinato . . . . . . . . . . . . . . . . . . . . . . . . . . ix

1.3 Corner-left . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x

1.4 Schema di funzionamento di un GA . . . . . . . . . . . . . . . . . xi

1.5 Esempio di Reverse . . . . . . . . . . . . . . . . . . . . . . . . . . xvi

1.6 Esempio di Spin . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii

1.7 Stock con sfrido . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii

1.8 Stock senza sfrido . . . . . . . . . . . . . . . . . . . . . . . . . . . xix

v

Page 6: Cutting stock bidimensionale

vi LIST OF FIGURES

Page 7: Cutting stock bidimensionale

Chapter 1

Cutting stock bidimensionale

Autori:Manfucci AndreaCiambelli Davide

vii

Page 8: Cutting stock bidimensionale

viii CHAPTER 1. CUTTING STOCK BIDIMENSIONALE

Figure 1.1: Esempio di TDC

1.1 Descrizione del problema

Nel problema del taglio del vetro (conosciuto come cutting stock bidimensionale

o TDC), dato uno stock rettangolare di materia prima di dimensioni (L, W ), e

dato un insieme P di pezzi rettangolari desiderati a ciascuno dei quali e associata

una coppia di dimensioni (l, w), si deve trovare l’insieme di pezzi, sottoinsieme

di P , estraibile dallo stock che massimizzi la somma dei profitti dei pezzi in esso

contenuti (Figure 1.1). Un insieme S di pezzi estraibile e definito in letteratura

come “feasible pattern”. Un esempio di pezzi non estraibile, nel caso di stock con

dimensioni (5, 5) e S = (3, 3), (4, 4). Se piu pezzi sono identici essi costituiscono

un “tipo” di pezzo ed il numero ne rappresenta la domanda. Un caso particolare

di TDC e classificato come guillotine e riguarda tutte le problematiche di taglio

di sagome a partire da un unico pezzo e si prefigge come obiettivo quello di

minimizzare lo sfrido (scarto) con alcuni vincoli operativi di seguito elencati:

• lo stock iniziale ha forma rettangolare, e limitato in altezza e larghezza con

dimensioni rispettivamente di (30, 20) e con area pari a 600;

• i tagli eseguiti sono tutti “a ghigliottina” vale a dire tagli che cominciano

e terminano su punti perimetrali (Figure 1.2);

• i pezzi hanno dimensioni variabili e forme rettangolari.

I tagli a ghigliottina paralleli realizzati sullo stock iniziale sono definiti di primo

livello (first-stage). Quelli ad essi perpendicolari e realizzati sui rettangoli ottenuti

sono definiti di secondo livello (second-stage). Il programma carica le coordinate

dei pezzi leggendo un file .txt memorizzato nella directory data. Gli oggetti ven-

gono piazzati a livelli e sono a!ancati sulla base di ogni livello. L’altezza di un

Page 9: Cutting stock bidimensionale

1.1. DESCRIZIONE DEL PROBLEMA ix

Figure 1.2: TDC ghigliottinato

livello e quella dell’oggetto piu alto che va a determinare i tagli di primo livello.

Il primo oggetto viene inserito partendo sempre dall’angolo in basso a sinistra di

ogni livello (Figure 1.3). Ogni volta che viene inserito un oggetto viene decre-

mentata la larghezza dello stock e il valore viene salvato in un variabile chiamata

larghezza rimasta. Da questo punto in avanti, ciascun oggetto successivo al primo

viene inserito solo se soddisfa le seguenti condizioni:

• la sua altezza e minore o uguale a quella del primo oggetto del livello;

• la sua larghezza e minore o uguale di larghezza rimasta.

In caso negativo l’oggetto viene inserito in un nuovo livello partendo dall’angolo

in basso a sinistra e si ricomincia la valutazione dei pezzi successivi. Ciascun

pezzo puo essere ruotato sia verticalmente che orizzontalmente (free orientation)

e i pezzi non possono essere sovrapposti. L’insieme puo contenere un set di pezzi

con la stessa dimensione ma nessuno dei pezzi puo avere una dimensione mag-

giore dello stock iniziale. Tutti gli oggetti hanno lo stesso valore di profitto e non

esiste nessun vincolo di priorita. Dato un set di oggetti l’obiettivo e quello di

minimizzare lo sfrido per cui l’area totale degli oggetti inseriti determina il val-

ore della soluzione. Non e detto quindi che tutti gli oggetti dell’insieme iniziale

facciano parte della soluzione e in tal caso non vengono presi in considerazione

per la soluzione finale. Il problema TDC e NP-hard infatti esso diventa equiva-

Page 10: Cutting stock bidimensionale

x CHAPTER 1. CUTTING STOCK BIDIMENSIONALE

Figure 1.3: Corner-left

lente al problema dello zaino mono-dimensionale che e noto essere NP-hard. In

letteratura sono stati proposti di"erenti approcci al problema TDC, ad esempio

in termini di schemi di programmazione dinamica (Gilmore e Gomory, 1966; Hifi

e Zissimopoulos, 1996), di meta-euristiche (Alvarez-Valdes, Parajon e Tamarit,

2002; Puchinger, 2005), di programmazione lineare (Lodi e Monaci, 2003; Belov,

2003). Molti lavori scientifici propongono algoritmi ad hoc classificabili, rispetto

alla versione a ghigliottina, in tre classi: top-down, bottom-up e strip heuristics.

In questo lavoro e stata sfruttata una tecnica euristica basata sugli algoritmi

genetici.

1.2 Risoluzione del problema con algoritmo ge-netico

Non esiste una tecnica rigorosa di algoritmo genetico. Gli algoritmi genetici

(AG) sono tecniche euristiche atte a risolvere problemi di ricerca e di ottimiz-

zazione. Holland, inventore e sviluppatore degli AG, aveva come scopo lo studio

del fenomeno dell’adattamento, come avviene in natura, e dei suoi meccanismi

tipici all’interno dei sistemi informatici. In biologia lo sviluppo di idee mod-

erne relative ai processi coinvolti nell’evoluzione e iniziato con Charles Darwin.

Darwin dedusse che la maggior parte degli individui muore prima di potersi ripro-

durre e cio avviene per il possesso di caratteri sfavorevoli. Questa e la selezione

naturale Darwiniana. Dato che le esigenze ambientali cambiano continuamente,

la selezione naturale favorisce caratteri via via diversi infatti nella lotta per la

sopravvivenza quelli che hanno sviluppato un miglior adattamento all’ambiente

sono quelli che riescono a riprodursi.

Page 11: Cutting stock bidimensionale

1.2. RISOLUZIONE DEL PROBLEMA CON ALGORITMO GENETICO xi

Popolazione di base

Valutazione

Selezione

Reverse e Spin

Terminato?No

Risultati

Si

Figure 1.4: Schema di funzionamento di un GA

In perfetta analogia con gli eventi descritti, gli AG partendo da un’iniziale

popolazione di cromosomi, ognuno dei quali rappresenta una possibile soluzione

del problema, associano ad ognuno di questi un certo livello di adattamento, il

“fitness score”, dipendente dalla bonta della soluzione del problema. Gli indi-

vidui migliori, in altre parole con maggior fitness, si riproducono combinandosi

con altri individui e si ottiene cosı una nuova popolazione di possibili soluzioni,

prodotta dalla selezione degli individui migliori della generazione corrente. In

questo modo, dopo molte generazioni, le buone caratteristiche vengono prop-

agate a tutta la popolazione. Favorendo l’accoppiamento fra gli individui piu

adatti vengono esplorate le aree piu promettenti dello spazio di ricerca. Per com-

prendere maggiormente quanto detto sopra e necessario dare alcune indicazioni.

Page 12: Cutting stock bidimensionale

xii CHAPTER 1. CUTTING STOCK BIDIMENSIONALE

1.2.1 Rappresentazione genetica del problema

Gli AG risolvono un determinato problema ricorrendo ad una popolazione di

soluzioni che, inizialmente casuali e quindi con fitness bassa, vengono fatte evol-

vere per un certo numero di generazioni successive, sino all’apparizione di almeno

una soluzione con fitness elevata. Per poter applicare l’algoritmo genetico occorre

anzitutto codificare numericamente le soluzioni e individuare una opportuna fun-

zione di fitness.

1.2.2 Scelta della funzione di fitness

La funzione di fitness si occupa di misurare la bonta di una soluzione. Nel TDC la

bonta corrisponde alla somma delle aree dei pezzi ricavati dallo stock. Si deduce

che piu e alto il valore di fitness e piu basso sara lo scarto. Lo stock iniziale e

un rettangolo le cui dimensioni sono (30, 20) e l’area e pari a 600. Una soluzione

ottima per il problema si ottiene quando la funzione di fitness coincide con l’area

dello stock.

1.2.3 Strutture dati

Taglio: classe che contiene tutto quello che riguarda la creazione, manipolazione

e visualizzazione dei cromosomi.

Shape: classe che contiene la definizione di oggetto.

Cromosoma: classe che contiene la definizione di cromosoma.

Piece: vector di tipo shape che contiene l’insieme iniziale dei pezzi.

Chromosome: vector di tipo cromosoma che contiene tutte le possibili soluzioni.

Solution: vector che contiene il cromosoma con il fitness migliore.

1.2.4 Cromosoma in dettaglio

Ogni individuo della popolazione e codificato mediante un cromosoma la cui strut-

tura si compone di tre parti:

Page 13: Cutting stock bidimensionale

1.3. OPERAZIONI GENETICHE xiii

• nella prima vengono memorizzati i pezzi. Ciascun pezzo viene codificato

come coppia di coordinate, in cui le posizioni con indice dispari corrispon-

dono alla larghezza mentre le posizioni con indice pari corrispondono all’altezza;

• la seconda parte rappresenta il cromosoma vero e proprio ed e specifi-

cato mediante una codifica numerica. Questa risulta essere una stringa

di lunghezza costante formata da geni. I geni sono binari, con valori di

0 o 1, e sono utilizzati per e"ettuare le operazioni di reverse e spin. Piu

precisamente, ciascuna delle operazioni utilizza un range di bit contenuto

fra due indici (iniziale e finale) specificati da ogni operazione;

• l’ultimo elemento del cromosoma, invece, memorizza il valore della funzione

di fitness associato a quel cromosoma. Si tenga presente che inizialmente

ogni cromosoma avra come valore di fitness zero.

In seguito verranno spiegate le funzioni utilizzate per ottenere cromosomi “figli”

dalla manipolazione di cromosomi “genitrici”.

1.3 Operazioni genetiche

La popolazione che evolve ha un numero N di individui che viene mantenuto

costante da una generazione all’altra. Ad ogni generazione vengono eseguite

opportune operazioni genetiche che producono nuovi individui. Per mantenere

costante N, occorre riprodurre nella generazione successiva solo N individui, pre-

miando quelli dotati di maggiore fitness. Le operazioni genetiche utilizzate sono

la reverse e la spin.

1.3.1 Fase di creazione

La funzione creation serve per generare i cromosomi in maniera casuale. Inizial-

mente ogni cromosoma contiene una possibile configurazione di pezzi (generata

con la funzione mix), i geni (generati casualmente) e un valore di fitness pari

a zero. Prima del termine della funzione tutti i cromosomi generati vengono

raddoppiati in modo da avere uno spazio doppio rispetto ai cromosomi iniziali.

Page 14: Cutting stock bidimensionale

xiv CHAPTER 1. CUTTING STOCK BIDIMENSIONALE

Questo passaggio serve per favorire la sopravvivenza dei cromosomi migliori. In-

fatti, nei passaggi successivi, i cromosomi saranno ordinati in maniera decrescente

e quelli peggiori (che si trovano in fondo) verranno rimpiazzati da cromosomi

migliori e questi diventeranno la base delle successive mutazioni. In questo modo,

sfruttando la bonta dei cromosomi genitori, verra favorita la generazione di figli

con caratteristiche piu performanti.

1.3.2 Fase di riproduzione

La funzione riproduction genera nuovi cromosomi a partire da quelli gia es-

istenti. In questa funzione vengono richiamate con il 50% di probabilita o la

reverse o la spin.

Reverse

Questa operazione sceglie due punti k e l (k < l) nelle stringhe binarie “genitrici”

< A1, A2, . . . , Ak, . . . , Al, . . . , An >

< B1, B2, . . . , Bk, . . . , Bl, . . . , Bn >

ed e"ettua lo scambio (Figure 1.5)

< A1, A2, . . . , Ak, Bk+1, Bk+2, . . . , Bn >

< B1, B2, . . . , Bk, Ak+1, Ak+2, . . . , An >

Al termine di questa operazione si ottengono nuovi cromosomi figli che rispetto

ai genitori presentano alcuni pezzi invertiti. Supponiamo di aver ottenuto un

cromosoma figlio di questo tipo:

1 0 0 1 0 0 0 0 1 0

con questa configurazione di pezzi:

(10, 5), (20, 10), (5, 10), (20, 5)

Questo e quello che avviene in dettaglio:

Page 15: Cutting stock bidimensionale

1.3. OPERAZIONI GENETICHE xv

• si considerano i geni compresi tra l’indice di reverse iniziale e quello finale

(nell’esempio 1 0 0 1)

• la stringa ottenuta viene convertita in base 2 e da questa operazione si

ottiene un intero (nell’esempio 20 + 23 = 9). L’operazione reverse lavora

sulle x di ogni pezzo. Queste si trovano in posizioni dispari quindi si deve

ottenere un valore dispari, percio:

1. se il valore dell’intero e pari si aggiunge 1

2. se il valore dell’intero e dispari non viene modificato

• il valore ottenuto viene diviso in modulo per il numero di coordinate dei

pezzi (nell’esempio 9 mod 8 = 1)

• il resto della divisione rappresenta la coordinata x del pezzo da scambiare

con il pezzo successivo (nell’esempio x1 = 10)

• a questo punto il pezzo indicato dalla coordinata (nell’esempio (10, 5)) viene

scambiato con il successivo (nell’esempio (20, 10))

La soluzione suggerita dal cromosoma e la seguente

(20, 10), (10, 5), (5, 10), (20, 5)

e attraverso la funzione fitness verra valutata.

Spin

Questa operazione coinvolge 2 stringhe binarie “genitrici”

< A1, A2, . . . , An >

< B1, B2, . . . , Bn >

ed e"ettua lo scambio dei geni compresi tra k e la fine del cromosoma producendo

le stringhe “figlie” (Figure 1.6)

< A1, A2, . . . , Ak, Bk+1, Bk+2, . . . , Bn >

< B1, B2, . . . , Bk, Ak+1, Ak+2, . . . , An >

Page 16: Cutting stock bidimensionale

xvi CHAPTER 1. CUTTING STOCK BIDIMENSIONALE

Figure 1.5: Esempio di Reverse

I nuovi cromosomi figli presentano alcuni pezzi ruotati rispetto ai genitori. Sup-

poniamo che il cromosoma ottenuto sia quello dell’esempio precedente:

1 0 0 1 0 0 0 0 1 0

con la configurazione di pezzi vista in precedenza:

(10, 5), (20, 10), (5, 10), (20, 5)

Questo e quello che avviene in dettaglio:

• si considerano i geni compresi tra l’indice di spin iniziale e quello finale

(nell’esempio 0 0 0 0 1 0)

• la stringa ottenuta viene convertita in base 2 e da questa operazione si

ottiene un intero (nell’esempio 21 = 2). L’operazione spin lavora sulle x di

ogni pezzo. Queste si trovano in posizioni dispari quindi si deve ottenere

un valore dispari, percio:

1. se il valore dell’intero e pari si aggiunge 1 (nell’esempio 2 + 1 = 3)

2. se il valore dell’intero e dispari non viene modificato

Page 17: Cutting stock bidimensionale

1.3. OPERAZIONI GENETICHE xvii

Figure 1.6: Esempio di Spin

• il valore ottenuto viene diviso in modulo per il numero di coordinate dei

pezzi (nell’esempio 3 mod 8 = 3)

• il resto della divisione rappresenta la coordinata x del pezzo da ruotare

(nell’esempio x3 = 20)

• a questo punto il pezzo indicato dalla coordinata viene ruotato (nell’esempio

(20, 10) diventa (10, 20))

La soluzione suggerita dal cromosoma e la seguente

(10, 5), (10, 20), (5, 10), (20, 5)

e attraverso la funzione fitness verra valutata. Mentre la reverse assicura il man-

tenimento di buoni individui per migliorare le soluzioni, la spin mantiene la di-

versita nella popolazione e permette di ampliare l’esplorazione.

1.3.3 Fase di visualizzazione

Le funzioni appena descritte vengono richiamate all’interno di un ciclo iterativo.

L’iterazione avanza nel caso in cui la di"erenza tra il miglior valore di fitness

Page 18: Cutting stock bidimensionale

xviii CHAPTER 1. CUTTING STOCK BIDIMENSIONALE

Figure 1.7: Stock con sfrido

attuale e il precedente e uguale a zero. Nel caso in cui la di"erenza e diversa da

zero il ciclo torna all’inizio. Questo serve a garantire che la soluzione finale sia

la migliore possibile. Quando termina il ciclo vengono richiamate due funzioni:

la visualize e la draw. La prima stampa il cromosoma soluzione con il relativo

valore di fitness. La seconda richiama la classe disegna visualizzando in output

la rappresentazione grafica relativa al cromosoma soluzione.

Un esempio di output del programma e quello in Figure 1.7 e rappresenta la

soluzione migliore con soli 6 degli 8 oggetti dell’insieme iniziale. Si puo notare che

una parte dello stock non e stata riempita (sfrido). Un altro esempio di output

e quello in Figure 1.8 dove lo stock iniziale e stato riempito completamente.

Anche in questo caso sono stati utilizzati 6 degli 8 oggetti dell’insieme iniziale

ma a di"erenza del precedente esempio non c’e stato spreco e la soluzione risulta

essere la migliore possibile. I numeri che a!ancano le rette verticali e orizzontali

rappresentano l’ordine in cui i tagli devono essere e"ettuati.

Page 19: Cutting stock bidimensionale

1.3. OPERAZIONI GENETICHE xix

Figure 1.8: Stock senza sfrido

Page 20: Cutting stock bidimensionale

xx CHAPTER 1. CUTTING STOCK BIDIMENSIONALE

Page 21: Cutting stock bidimensionale

Bibliography

[1] J. Holland, ”Genetic Algorithms”.

[2] http://en.wikipedia.org.

[3] http://www.obitko.com.

xxi