IL PROBLEMA DELLO ZAINO
Trattiamo ora di un altro problema molto conosciuto e nel quale sono stati applicati con successo gli algoritmi genetici. Nel problema classico, 0/1 simple Knapsack Problem, è dato uno zaino di capacità C e n oggetti ciascuno dei quali ha un peso wi , e profitto pi siamo interessati a riempire lo zaino con gli oggetti che danno il massimo profitto col vincolo di non superare la capacità. Noi ci occupiamo di una generalizzazione di questo, il 0/1 multiple knapsack, dove si hanno m zaini di capacità c1 cm e n oggetti ciascuno dei quali ha un profitto pi . Diversamente dalla versione classica, nella quale il peso degli oggetti è fissato, il peso del i-esimo oggetto nella versione multipla prende j valori, 1 < j < m. Li-esimo oggetto pesa wij quando è candidato ad entrare nel j-esimo zaino di capacità Cj . Dobbiamo trovare un vettore x di n componenti che rispetti il vincolo delle capacità:
Si wijxi<Cj i=1 n ; j= 1 m
e che massimizzi il profitto: P(x)= Si xipi
Possiamo notare che può essere pensato come un problema di
allocazione di risorse dove abbiamo n risorse (lo zaino) e n
oggetti. Ciascuna risorsa ha un proprio budget (la capacità
dello zaino), e wij rappresenta il
consumo della risorsa j da parte delloggetto i. Vogliamo
ovviamente massimizzare il profitto lavorando allinterno di
un certo budget. La popolarità di questo problema è alta sia
tra i teorici che tra i pratici. I primi lo usano
come sottoproblema per risolverne altri più complicati data la
sua semplice struttura; gli altri per modellare molte
applicazioni industriali come il taglio del tessuto, il
caricamento dei cargo e problemi di distribuzione del budget.
Diamo adesso la definizione formale del problema:
Istanza del problema
Zaini: 1 2
m
Capacità: C1 C2
Cm
Capacità e profitto degli oggetti devono essere positivi, mentre i pesi degli oggetti sono non negativi.
Oggetti: 1 2
n
Profitti: P1 P2
Pn
Pesi: w1j w2j
wnj
Soluzione Ammissibile
Vettore x tale che Si wijxi<Cj i=1 n ; j= 1 m
Funzione Obiettivo
P(x)=Si xipi dove x è un vettore ammissibile
Soluzione Ottima
Un vettore ammissibile che dà il massimi profitto cioè un vettore che massimizza la funzione obiettivo.
Il problema deve essere codificato in maniera da essere
risolto tramite un GA. I vettori sono usati nel passo di codifica,
ciascuna stringa x1
xn nella popolazione rappresenta un
possibile soluzione se nelli-esima posizione al valore 1
cioè xi=1 allora li-esimo oggetto è in tutti gli zaini,
al contrario no.
In altre parole, ciascuna stringa x appartenente a (0,1) è una
possibile soluzione. Ribadiamo che una stringa potrebbe
rappresentare una soluzione non ammissibile, quando ad esempio
esiste un vettore x tale che wx supera la capacità di almeno uno
degli zaini (cioè non rispetta almeno uno dei vincoli).
Noi permettiamo alle stringhe non ammissibili di entrare nella
popolazione, ma riduciamo il loro fitness aggiungendogli un punto
di penalità. Più la soluzione è lontana dallammissibilità,
più alto è il corrispondente grado di penalità. Dobbiamo
allora massimizzare la seguente funzione fitness:
f(x)= Si pi xi - s max{pi}
dove s = |{ j: Si wijxi>Cj
}|. In altre parole s indica il numero tra 0 e n degli zaini
pieni.
La funzione fitness usa un termine di penalità max{pi}, che
appare tutte le volte che una stringa non è ammissibile.
E stato usato il programma GENEsYS con la funzione
fitness di sopra e alcuni problemi test e riporteremo i risultati
nella sezione successiva. Significanti porzioni dello spazio di
ricerca di alcuni istanze del problema sono regioni di non
ammissibilità. Questa situazione si nota in modo particolare nel
problema test weing8-105 , listanza del
problema consiste di 105 oggetti e due zaini. E un problema
abbastanza complicato perché le regioni di ammissibilità nello
spazio di ricerca sono molto sparse. A causa degli alti valori
dei pesi in rapporto alle capacità degli zaini, molte delle 2105
stringhe rappresentano soluzioni non ammissibili. Siamo di fronte
a una situazione dove ogni stringa generata a caso nella
popolazione produce uno zaino stracarico. Per affrontare questi
casi estremi, bisogna controllare che le stringhe della
popolazione iniziale non siano tutte inammissibili.
Abbiamo inoltre aggiunto al programma un flag che segnala lammissibilità
della soluzione finale. Se dopo alcune esecuzioni sulla stessa
istanza del problema o un numero alto di individui nella
popolazione iniziale sono stringhe inammissibili,
suggeriamo di intraprendere le seguenti azioni:
- forzare il generatore di stringhe della popolazione
iniziale a produrre stringhe con un numero di 0 maggiore del
numero di 1. Se questo non produce leffetto desiderato,
invertire il procedimento: fare in modo di produrre più 1 di 0.
- Usa qualche altro metodo euristico, come il greedy per generare
la popolazione Includi nella popolazione iniziale stringhe che
sono minori variazioni della soluzione ottenuta con il greedy.
Questa tecnica è stata usata con successo in altri problemi.
Anche la funzione fitness può causare la comparsa di soluzione inammissibile se non fa abbastanza pressione verso la ricerca in porzioni di spazio ammissibili.
Risultati Sperimentali
Gli esperimenti riportati sono stati ottenuti utilizzando i
seguenti parametri: grandezza della popolazione m=50, tasso di mutazione pm= 1/n, tasso di
crossover pc= 0.6, selezione proporzionale, e one point crossover.
Per applicare questo algoritmo al problema non è stato
necessario modificare niente tranne la funzione fitness e questo
fatto è una prova della robustezza e adattabilità degli
algoritmi genetici.
Lalgoritmo è valutato su nove problemi test presi dalla
letteratura. Gli oggetti vanno da 15 a 105 e gli zaini da 2 a 30.
Le tabelle 1 e 2 mostrano i dati di ciascun test, le esecuzioni
sono N=100. Il valore della prima riga delle tabelle corrisponde
al massimo globale, e la soluzione media finale f in 100
esecuzioni è mostrata, per ogni esperimento, in fondo alle
tabelle. Per esempio, 33 esecuzioni producono la soluzione
ottima 6120 per knap20 mentre 20 nel
problema knap20 producono 6110. Solo gli 11 migliori
risultati sono mostrati. Per knap39 e knap50
il numero di giri non supera 100 perché alcune producono
soluzioni sotto 10561 e 16463 rispettivamente. Lindice ft(x)
rappresenta un numero totale di stringhe processate, cioè il
valore di t è il prodotto del numero di individui per
generazione e il numero di generazioni per ogni esecuzione.
Solo in una percentuale estremamente bassa dei 2n
punti dello spazio è processato dallalgoritmo. Per esempio
con knap28 solo il 0.018% dello spazio è esplorato,
e solo 4.9 10-25% delle stringhe con knap105 sono
processate.
Come entrambe le tabelle chiaramente mostrano, il GA è in grado
di localizzare il massimo globale esattamente per tutti i
problemi tranne uno. Questa eccezione è il weing7-105,
per il quale tutte le esecuzioni si inceppano prima di trovare lottimo.
Il valore di fitness medio per ogni esecuzione diventa
ragionevolmente vicino allottimo in tutti i test. Questo
risultato indica che il GA può servire come una veloce e robusta
approssimazione euristica del problema.
Nel weing8-105 viene forzata la popolazione iniziale,
come detto nel paragrafo precedente, con probabilità di generare
0 di 0.95,e questa semplice ed elegante soluzione migliora lapproccio
del nostro algoritmo.
In figura 1 è mostrato per il sento1-60 lo svolgersi
di alcune esecuzioni. Il grafico mostra il miglior valore di
fitness per cinque differenti esecuzioni.
Tabella 1
Tabella 2
Figura 1: sento1.60, alcune esecuzioni.
Come osservazione generale, ricordiamo che molti progressi sono stati fatti durante le prime 200 generazioni, seguite da una stagnazione con pochi miglioramenti occasionali. La prima fase rispecchia lexploitation della diversità del genotipo iniziale come raccomandato, mentre la seconda caratterizza una ricerca basata principalmente sulla mutazione. Questa osservazione è in accordo con luso ibrido del GA e con i metodi di ottimizzazione locale, dove il primo è usato per produrre soluzioni che sono punti iniziali per lottimizzazione locale.