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. L’i-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 dell’oggetto i. Vogliamo ovviamente massimizzare il profitto lavorando all’interno 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 nell’i-esima posizione al valore 1 cioè xi=1 allora l’i-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 dall’ammissibilità, 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” , l’istanza 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 l’ammissibilità 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 l’effetto 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.
L’algoritmo è 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. L’indice 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 dall’algoritmo. 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 l’ottimo. Il valore di fitness medio per ogni esecuzione diventa ragionevolmente vicino all’ottimo 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 l’approccio 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 l’exploitation  della diversità del genotipo iniziale come raccomandato, mentre la seconda caratterizza una ricerca basata principalmente sulla mutazione. Questa osservazione è in accordo con l’uso ibrido del GA e con i metodi di ottimizzazione locale, dove il primo è usato per produrre soluzioni che sono punti iniziali per l’ottimizzazione locale.