31.10 KP: ammissibilità e penalità¶
Parte 4 · Algoritmi euristici · Capitolo 31 · Capitolo 31: Ricerca locale · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Ricerca locale · App: TSP: nearest neighbour e 2-opt
-
La rappresentazione del KP con un vettore binario \(x\) descrive anche oggetti non ammissibili, il cui peso supera la capacità. Ci sono due modi di trattarli:
-
restare ammissibili: l'intorno contiene solo i vicini ammissibili, come fatto finora;
-
penalizzare: i vettori non ammissibili sono ammessi, e la ricerca massimizza una funzione che sottrae dal profitto una penalità proporzionale al peso in eccesso.
-
-
Restare ammissibili può rendere la ricerca miope. Nel capitolo «Algoritmi euristici: definizioni», \(x=(1,0,1,0)\) è un ottimo locale per flip: per raggiungere la soluzione ottima \((1,1,0,0)\) con i flip occorre aggiungere l'oggetto \(2\) e togliere l'oggetto \(3\), e il vettore intermedio è o \((1,1,1,0)\), non ammissibile, o \((1,0,0,0)\), di profitto \(10<16\). L'intorno swap risolve questo caso eseguendo i due flip insieme; le penalità lo risolvono lasciando che la ricerca passi attraverso il vettore non ammissibile.
-
Con le penalità, lo spazio di ricerca è l'intero insieme \(\{0,1\}^n\), e la funzione da massimizzare è
dove \(\alpha>0\) è la penalità per ogni unità di peso in eccesso. Per un \(x\) ammissibile, \(g_\alpha(x)\) è il profitto di \(x\).
31.10.1 Restare ammissibili¶
La ricerca locale flip+swap per il KP esamina i flip e poi gli swap della soluzione corrente, scarta quelli che superano la capacità, ne applica uno migliorante scelto con la regola first improvement o best improvement, e si ferma quando nessun vicino ammissibile ha un profitto maggiore.
Algoritmo: Passo flip+swap per il KP
- Con la regola first improvement, se si trova un flip migliorante gli swap non vengono esaminati. Solo i flip che aggiungono un oggetto possono migliorare il profitto; i flip che tolgono un oggetto restano nell'intorno per uniformità. Un'iterazione costa tempo \(O(n^2)\), a causa degli swap.
31.10.2 Penalizzare il peso in eccesso¶
La ricerca locale penalty flip per il KP esamina i flip del vettore corrente, ammissibile o no, li valuta con \(g_\alpha\), ne applica uno migliorante scelto con la regola first improvement o best improvement, e si ferma quando nessun flip aumenta \(g_\alpha\).
Algoritmo: Passo penalty flip per il KP
- L'ottimo locale può essere non ammissibile. La ricerca deve quindi ricordare la migliore soluzione ammissibile visitata, che è la soluzione che restituisce.
Esempio 31.8: Penalità sull'istanza di riferimento del KP
Partiamo dalla soluzione di \(GR\), \(x=(1,0,1,0)\), di peso \(8\) e profitto \(16\), che è un ottimo locale per l'intorno flip ristretto alle soluzioni ammissibili. I valori \(g_\alpha\) dei suoi quattro flip sono
| flip | vettore | peso | eccesso | \(\alpha=1\) | \(\alpha=2\) | \(\alpha=\frac94\) | \(\alpha=3\) |
|---|---|---|---|---|---|---|---|
| \(1\) | \((0,0,1,0)\) | \(3\) | \(0\) | \(6\) | \(6\) | \(6\) | \(6\) |
| \(2\) | \((1,1,1,0)\) | \(12\) | \(3\) | \(20\) | \(17\) | \(\frac{65}{4}\) | \(14\) |
| \(3\) | \((1,0,0,0)\) | \(5\) | \(0\) | \(10\) | \(10\) | \(10\) | \(10\) |
| \(4\) | \((1,0,1,1)\) | \(11\) | \(2\) | \(18\) | \(16\) | \(\frac{31}{2}\) | \(14\) |
Le due regole eseguono le stesse mosse:
-
\(\alpha=1\): la ricerca aggiunge l'oggetto \(2\) (\(g_1=20\)), poi l'oggetto \(4\) (\(g_1=27-6=21\)), e si ferma in \((1,1,1,1)\), di peso \(15\): ogni suo flip toglie un oggetto e dà \(16\), \(18\), \(18\) o \(20\). La penalità è troppo piccola: l'ottimo locale non è ammissibile, e la migliore soluzione ammissibile visitata è quella di partenza, di profitto \(16\).
-
\(\alpha=2\): la ricerca aggiunge l'oggetto \(2\) (\(g_2=17>16\)) e si ferma in \((1,1,1,0)\), non ammissibile: togliere l'oggetto \(3\) dà \((1,1,0,0)\) con \(g_2=17\), non strettamente migliore.
-
\(\alpha=\frac94\): la ricerca aggiunge l'oggetto \(2\) (\(g=\frac{65}{4}=16.25>16\)) e poi toglie l'oggetto \(3\), raggiungendo \((1,1,0,0)\), di profitto \(17\): la soluzione ottima, attraverso un vettore non ammissibile (si veda la figura).
-
\(\alpha=3\): nessun flip migliora, e la ricerca si ferma subito in \((1,0,1,0)\), come la ricerca ammissibile.
Proposizione 31.7
Siano i dati interi e sia \(\alpha>\max_{j\in\mathscr{I}} p_j\). Allora:
-
da un vettore ammissibile, nessun flip che produce un vettore non ammissibile aumenta \(g_\alpha\);
-
ogni vettore non ammissibile ha un flip che aumenta \(g_\alpha\).
Dimostrazione
(1) Se aggiungere l'oggetto \(k\) a un vettore ammissibile produce un eccesso \(e\ge1\), allora \(g_\alpha\) varia di \(p_k-\alpha e\le p_k-\alpha<0\). (2) Sia \(x\) non ammissibile, con eccesso \(e\ge 1\), e sia \(j\) un oggetto selezionato. Togliere \(j\) diminuisce l'eccesso di \(\min\{w_j,e\}\ge 1\), quindi \(g_\alpha\) varia di \(-p_j+\alpha\min\{w_j,e\}\ge -p_j+\alpha>0\). □
- Con una penalità grande gli ottimi locali sono ammissibili, ma la ricerca non lascia mai la regione ammissibile; con una penalità piccola attraversa la regione non ammissibile, ma può fermarsi lì. I valori utili dipendono dall'istanza (qui \(\frac94\) funziona, \(1\), \(2\) e \(3\) no), quindi in pratica \(\alpha\) si regola durante la ricerca: si aumenta finché la ricerca resta fra vettori non ammissibili, si diminuisce finché resta fra vettori ammissibili.