Ricerca Tabù Stocastica — Metaeuristica Randomizzata con Memoria
- Introdotto da
- Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
- Anno
- 1990s
- Tipo
- Stochastic metaheuristic optimizer
- Famiglia
- Simulation / optimization
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
La Ricerca Tabù Stocastica (STS) è un'estensione della Ricerca Tabù classica che introduce casualità nelle fasi di esplorazione del vicinato e selezione delle mosse.
Combinando la memoria tabù — che vieta le soluzioni visitate di recente — con l'accettazione probabilistica o il campionamento casuale dei candidati, la STS sfugge più efficacemente ai minimi locali ed esplora paesaggi di soluzioni accidentati che la TS deterministica potrebbe non riuscire ad attraversare.
L’intuizione alla base del metodo
La Ricerca Tabù classica naviga uno spazio di soluzioni muovendosi sempre verso il miglior vicino consentito, utilizzando una memoria a breve termine (la lista tabù) per prevenire il ciclaggio. In pratica, tuttavia, la migliore mossa consentita può comunque intrappolare l'algoritmo in una regione del paesaggio. La Ricerca Tabù Stocastica inietta casualità controllata: la mossa successiva viene scelta probabilisticamente da un insieme di vicini candidati piuttosto che avidamente, e occasionalmente vengono introdotte perturbazioni casuali per diversificare la ricerca. Ciò preserva la disciplina guidata dalla memoria della TS, aggiungendo il potere esplorativo che manca alla pura discesa deterministica.
Storia
La Ricerca Tabù è stata introdotta formalmente da Fred Glover nel 1986 ed elaborata in articoli fondamentali tra il 1989 e il 1990. Estensioni stocastiche sono emerse negli anni '90 quando i ricercatori hanno riconosciuto che la valutazione deterministica del vicinato era un collo di bottiglia nei problemi su larga scala. Campionamento casuale dei candidati, accettazione probabilistica delle mosse e iniezione di rumore sono stati incorporati per migliorare la diversificazione, dando origine a quella che viene ampiamente chiamata Ricerca Tabù Stocastica. La tecnica è ampiamente applicata nella ricerca operativa, nella progettazione ingegneristica e nell'ottimizzazione degli iperparametri del machine learning.
Quando usarlo
Utilizzare la Ricerca Tabù Stocastica quando si risolvono problemi di ottimizzazione combinatoria o continua a scatola nera con paesaggi accidentati e multimodali dove la ricerca locale deterministica rimane costantemente intrappolata (es. scheduling, routing, selezione di caratteristiche). È particolarmente prezioso quando la valutazione completa del vicinato è computazionalmente costosa, rendendo necessario il sottocampionamento casuale. NON utilizzare la STS quando il problema è convesso o unimodale — metodi basati su gradiente o esatti sono più veloci e ottimali. Evitarla quando si necessita di ottimalità globale garantita, poiché la STS non offre garanzie di convergenza oltre le migliori soluzioni euristiche trovate. Evitarla anche quando la funzione obiettivo è economica da valutare completamente e una TS deterministica con ricerca esaustiva dei vicini è fattibile.
Limiti e considerazioni
- Nessuna garanzia teorica di trovare l'ottimo globale; la qualità della soluzione dipende fortemente dalle impostazioni dei parametri.
- La permanenza tabù e la dimensione della lista candidati richiedono una taratura specifica per il problema; scelte errate portano a convergenza prematura o progresso lento.
- Le esecuzioni stocastiche non sono riproducibili senza un seme casuale fisso, complicando il benchmarking e l'audit.
- L'overhead di memoria cresce con la dimensione della lista tabù; sono necessarie rappresentazioni tabù basate su attributi per ampi spazi di soluzione.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Sfuggire ai minimi locali più efficacemente della Ricerca Tabù deterministica combinando memoria con esplorazione probabilistica.
- Scalare a strutture di vicinato ampie sottocampionando i candidati, riducendo il costo computazionale per iterazione.
- La memoria tabù previene il ciclaggio, una modalità di fallimento comune dei metodi puramente stocastici come l'hill climbing a riavvio casuale.
- Framework flessibile: la probabilità di perturbazione e la permanenza tabù possono essere regolate per bilanciare intensificazione e diversificazione.
- Applicabile sia a problemi combinatori (TSP, scheduling) che a ottimizzazione continua con adattamenti minori.
Applicazioni
- Routing di veicoli e ottimizzazione logistica sotto domanda incerta
- Scheduling job-shop e open-shop con tempi di elaborazione stocastici
- Selezione di caratteristiche in dataset di machine learning ad alta dimensionalità
- Progettazione di reti e ottimizzazione della topologia
- Ottimizzazione di portafoglio con vincoli combinatori sulla selezione degli asset
- Tuning degli iperparametri per modelli di simulazione complessi
Come funziona
Come funziona
Generare una soluzione iniziale x0 (casualmente o euristicamente). Impostare la lista tabù T a vuota, definire la permanenza tabù tau, il limite di iterazioni I_max e i parametri stocastici (es. dimensione della lista candidati k, probabilità di perturbazione p_perturb).
Ad ogni iterazione, campionare casualmente un sottoinsieme N_s del vicinato completo N(x_attuale) piuttosto che valutare tutti i vicini. Ciò riduce il costo per iterazione e introduce stocasticità nelle regioni dello spazio che vengono esplorate.
Selezionare la soluzione successiva x_successiva da N_s: o (a) scegliere il miglior candidato non tabù con probabilità 1-p_perturb, o (b) con probabilità p_perturb scegliere un candidato non tabù casuale per diversificare. I criteri di aspirazione possono sovrascrivere lo stato tabù se x_successiva migliora la migliore soluzione nota.
Aggiungere x_attuale (o l'attributo della mossa) alla lista tabù T. Rimuovere la voce più vecchia se |T| > tau. Aggiornare la migliore soluzione incudine x_migliore se f(x_successiva) < f(x_migliore).
Ripetere neighborhood_sampling fino a tabu_update fino al raggiungimento di I_max iterazioni, un valore obiettivo target, o nessuna miglioria si è verificata per una finestra di pazienza. Restituire x_migliore come soluzione finale.
Errori comuni
- Impostare la permanenza tabù troppo corta permette il ciclaggio nonostante la lista tabù; troppo lunga blocca regioni promettenti inutilmente.
- Usare una lista candidati troppo piccola (sottocampionamento aggressivo) può far sì che la ricerca manchi costantemente di buoni vicini.
- Trascurare i criteri di aspirazione fa sì che l'algoritmo rifiuti mosse globalmente migliorative che risultano essere tabù.
- Riportare una singola esecuzione senza riavvii multipli o semi fornisce un'immagine fuorviante della tipica qualità della soluzione.
- Confondere la Ricerca Tabù Stocastica con il Simulated Annealing: entrambi sono stocastici ma differiscono fondamentalmente — la STS usa memoria esplicita mentre SA usa accettazione probabilistica basata sulla temperatura senza memoria.
Domande frequenti
In che modo la Ricerca Tabù Stocastica differisce dal Simulated Annealing?
Entrambe sono metaeuristiche stocastiche, ma la STS utilizza una memoria tabù esplicita per proibire mosse visitate di recente, prevenendo il ciclaggio. SA non ha memoria — accetta soluzioni peggiori con una probabilità che diminuisce nel tempo (programma di temperatura). La STS è generalmente più forte su problemi combinatori dove rivisitare mosse è un pericolo evidente.
Quante iterazioni (I_max) dovrei eseguire?
Non esiste una regola universale. Una pratica comune è eseguire più prove indipendenti (es. 10-30 riavvii) con un budget proporzionale alla dimensione del problema, quindi riportare i risultati migliori e medi. Per il benchmarking, far corrispondere il budget totale di valutazione delle funzioni utilizzato dai metodi concorrenti.
La Ricerca Tabù Stocastica può gestire variabili continue?
Sì, ma richiede la definizione di un vicinato continuo (es. perturbazione Gaussiana attorno alla soluzione corrente) e un attributo adatto per la lista tabù (es. una regione o una direzione). La maggior parte della letteratura STS si concentra su problemi combinatori; per spazi continui, Differential Evolution o CMA-ES sono spesso alternative più naturali.
Qual è il ruolo dei criteri di aspirazione?
I criteri di aspirazione sovrascrivono lo stato tabù di una mossa se accettarla produce una soluzione migliore della migliore trovata finora. Senza aspirazione, l'algoritmo potrebbe rifiutare permanentemente mosse globalmente migliorative che risultano essere tabù, limitando gravemente la qualità della soluzione.
Dovrei fissare il seme casuale per la riproducibilità?
Sì, fissare il seme quando si riportano risultati nella ricerca per garantire la riproducibilità. In pratica, eseguire con semi multipli e riportare statistiche (media, migliore, deviazione standard) per dare un quadro affidabile delle prestazioni dell'algoritmo nel paesaggio stocastico.
Metodi correlati
Fonti
Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.
Apri il riferimento DOICopiato.Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.
Apri il riferimento DOICopiato.