Ricerca Tabù

La ricerca tabù è una metaeuristica basata sulla memoria introdotta da Glover (1986, 1989, 1990); un'idea correlata fu proposta indipendentemente da Hansen (1986). Il tratto distintivo è la memoria esplicita: mentre la ricottura simulata si basa sulla casualità e gli algoritmi genetici su una popolazione, la ricerca tabù tiene una lista delle mosse o degli attributi recenti e ne vieta l'inversione. Componenti chiave: (1) struttura di vicinato e valutazione delle mosse; ad ogni iterazione si passa al miglior vicino non tabù anche se peggiora l'obiettivo (uscita dall'ottimo locale); (2) memoria a breve termine (lista tabù) di lunghezza k, chiamata tabu tenure; (3) criterio di aspirazione — una mossa tabù è ammessa se migliora la migliore soluzione nota; (4) memoria a medio termine per l'intensificazione — approfondire la ricerca attorno a soluzioni buone visitate spesso; (5) memoria a lungo termine per la diversificazione — salti verso regioni inesplorate. Le varianti includono granular tabu search, reactive tabu search (Battiti e Tecchiolli 1994, con tenure auto-regolata) e Adaptive Memory Programming. Per VRP, scheduling, sequenziamento e assegnazione è tra le metaeuristiche più potenti; i lavori di Cordeau e Laporte sui VRP sono riferimento industriale. Rispetto alla ricottura simulata è più deterministica e più intensiva in memoria, con qualità simile e minore sensibilità ai parametri. Riferimenti: Glover e Laguna (1997), Gendreau e Potvin (2010).