Vai al contenuto

Metaeuristiche

Parte 4 · Algoritmi euristici · Capitolo 32 · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Metaeuristiche · App: TSP: simulated annealing e tabu search

Prerequisiti

Obiettivi

Alla fine di questo capitolo saremo in grado di:

  • eseguire a mano simulated annealing, tabu search, iterated local search e variable neighbourhood search, con numeri casuali assegnati;

  • eseguire GRASP, large neighbourhood search e un algoritmo genetico o memetico su istanze piccole;

  • spiegare come ciascun metodo esce da un ottimo locale, e quali parametri lo regolano;

  • confrontare i metodi sulle stesse istanze, con più semi;

  • dire che cosa le metaeuristiche non danno: un bound duale.

32.1 Metaeuristiche

Definizione 32.1: Metaeuristica

Una metaeuristica è una strategia generale che guida una ricerca locale oltre il primo ottimo locale, per esplorare altre regioni dell'insieme delle soluzioni ammissibili.

  • Una metaeuristica è uno schema, non un algoritmo: un algoritmo si ottiene scegliendo la rappresentazione, gli intorni, la ricerca locale e i parametri.

  • Ogni metaeuristica bilancia intensificazione e diversificazione, definite nel capitolo «Algoritmi euristici: definizioni».

Una ricerca locale si ferma nel primo ottimo locale; una metaeuristica ne esce accettando soluzioni peggiori, saltando a una nuova soluzione di partenza, o combinando più soluzioni buone.

  • Panoramica

    Metaeuristiche

    Apri

  • 32.2 I problemi e le ipotesi

    Numeri casuali · Le istanze

    Apri

  • Come uscire da un ottimo locale · Simulated annealing

    Lo schema di raffreddamento e i parametri · Esempi · Soluzioni inammissibili: simulated annealing con penalità · Un esperimento sull'istanza media del TSP · Proprietà

    Apri

  • 32.5 Tabu search

    Tabu search per il TSP, e l'effetto della durata tabu

    Apri

  • 32.6 Iterated local search

    Apri

  • 32.7 Variable neighbourhood search

    Apri

  • 32.8 GRASP

    Apri

  • 32.9 Large neighbourhood search

    Adaptive large neighbourhood search

    Apri

  • 32.10 Metodi basati su popolazioni: algoritmi genetici e memetici

    Apri

  • 32.11 Confronto e conclusioni

    Intensificazione e diversificazione · Parametri e calibrazione · Che cosa questi metodi non usano

    Apri

  • Errori tipici · In sintesi

    In sintesi

    Apri

  • Bibliografia

    Apri

Avanti: 32.2 I problemi e le ipotesi

Esercizi su questo capitolo: Metaeuristiche

Nel laboratorio interattivo: TSP: simulated annealing e tabu search.