06 Guida alla sistemistica

Ottimizzazione:
cercare meglio, non indovinare.

Quando le combinazioni possibili sono troppe per provarle tutte, serve una strategia di ricerca. Ottimizzare significa confrontare soluzioni secondo un obiettivo misurabile, migliorandole finché il tempo, il budget o la pazienza lo consentono. Quest’ultima, nei computer, viene chiamata più elegantemente “limite di calcolo”.

Problemaspazio enorme

Obiettivocopertura e costo

Ricercasoluzione confrontabile

Prima la domanda

“Migliore” non è un numero finché non dici migliore in che senso.

Un sistema può coprire più gruppi, costare meno, distribuire meglio i simboli oppure essere più semplice da spiegare. Spesso queste qualità si aiutano; altre volte litigano. Ridurre una colonna può abbassare il costo e aprire un buco nella copertura.

L’ottimizzazione comincia quindi dalla funzione obiettivo: una regola che assegna un punteggio a ogni soluzione. Senza obiettivo, l’algoritmo non cerca; passeggia. E anche con un ottimo passo, resta una passeggiata.

Definizione semplice

Ottimizzare significa trovare una soluzione con il miglior valore possibile — o ragionevolmente buono — rispetto a criteri dichiarati e vincoli rispettati.

Famiglie di metodi

Esatti, euristici e metaeuristici: tre modi diversi di promettere.

Metodo esatto

Dimostra l’ottimo

Esplora lo spazio con regole che consentono di certificare la soluzione migliore. È prezioso, ma può richiedere molto tempo.

Euristica

Costruisce una buona soluzione

Usa una regola pratica, come scegliere ogni volta la colonna con il guadagno maggiore. Rapida e leggibile, senza certificato di perfezione.

Metaeuristica

Esplora molte alternative

Algoritmi genetici, annealing e ricerca tabu provano a evitare soluzioni locali. Hanno parametri, semi e nessun mantello da mago.

Un metodo esatto che impiega tre settimane può essere meno utile di un’euristica che produce in dieci secondi una soluzione quasi identica. Ma “quasi” va misurato: non basta pronunciarlo con voce fiduciosa.

Simboli nella base · n

Simboli per colonna · k

Gruppo da coprire · t

Budget in colonne

Confronto valido: 12 colonne per metodo, obiettivi da 3 simboli.

Integrale252colonne candidate

Obiettivi120gruppi da 3

Metodo miglioreGreedy di coperturain questo confronto

Prime colonne48,3%

Prende l’inizio dell’ordine lessicografico: semplice, ma tende a ripetere i simboli più piccoli.

Campione distribuito66,7%

Preleva posizioni distanti nell’integrale. Migliora la varietà senza conoscere gli obiettivi scoperti.

Greedy di copertura83,3%

Sceglie ogni volta la colonna che aggiunge più gruppi ancora assenti.

#11 · 2 · 3 · 4 · 5

#21 · 2 · 6 · 7 · 8

#31 · 3 · 6 · 9 · 10

#42 · 4 · 7 · 9 · 10

#53 · 5 · 7 · 8 · 9

#64 · 5 · 6 · 8 · 10

Il metodo greedy

Prende il guadagno migliore adesso. Sul domani, mantiene un prudente silenzio.

Il greedy sceglie la colonna che copre il maggior numero di obiettivi ancora assenti. Poi aggiorna l’elenco dei buchi e ripete. È veloce, deterministico e facile da spiegare: tre qualità molto utili quando qualcuno dovrà controllare il lavoro.

Il limite è nel nome stesso della strategia: una scelta ottima al passo corrente può rendere meno felici i passi successivi. Il metodo può fermarsi in una soluzione buona ma non globale. Non è un difetto morale; è una proprietà dell’algoritmo.

Una buona pratica: usa il greedy come base di confronto. Qualunque metodo più complesso dovrebbe batterlo in qualità, tempo o stabilità; altrimenti ha soltanto portato più bagagli.

Più obiettivi insieme

Copertura, costo, equilibrio: quando i numeri iniziano a negoziare.

Punteggio pesato

Una formula, più criteri

Si assegna un peso a copertura, costo, ripetizioni e uniformità. È pratico, ma i pesi sono una scelta umana e devono essere dichiarati.

Frontiera di Pareto

Più soluzioni non dominate

Mostra alternative in cui non puoi migliorare un criterio senza peggiorarne un altro. Non sceglie al posto tuo; almeno ha l’onestà di dirlo.

Quando due obiettivi confliggono, non esiste sempre una sola soluzione “migliore”. Esistono compromessi diversi. Il lavoro tecnico produce alternative misurate; la scelta finale dipende dalle priorità e dal budget.

Come fidarsi

Un algoritmo va confrontato, ripetuto e contraddetto con educazione.

Conserva una baseline

Una soluzione semplice permette di capire se la complessità aggiunta produce un beneficio reale.

Registra parametri e seme

Per i metodi casuali, senza questi dati il risultato non è riproducibile.

Ripeti più volte

Una singola esecuzione fortunata non descrive la stabilità del metodo.

Verifica indipendentemente

Il codice che genera una soluzione non dovrebbe essere l’unico a certificarla.