Ottimizzazione Combinatoria con Reti Tensoriali

Un nuovo studio esplora l'applicazione di reti tensoriali per risolvere il problema del commesso viaggiatore (TSP), un classico esempio di ottimizzazione combinatoria. Il metodo, denominato TN-GEO (Tensor Network Generator-Enhanced Optimization), si basa su una macchina di Born a rete tensoriale che utilizza stati di prodotto matriciali (MPS) automaticamente differenziabili come modello generativo.

Formulazione e Vantaggi

A differenza degli approcci basati sulla codifica binaria, che richiedono un numero quadratico di variabili e termini di penalità per garantire soluzioni valide, questo metodo adotta una formulazione basata sulla permutazione con variabili intere. L'utilizzo del campionamento autoregressivo con mascheratura assicura che ogni soluzione generata sia un percorso valido.

Modellazione Efficiente con k-grammi

Lo studio introduce anche una variante MPS a k-siti che apprende le distribuzioni su k-grammi (sottosequenze consecutive di città) utilizzando un approccio a finestra scorrevole. Questo permette una modellazione efficiente in termini di parametri per istanze più grandi.

Performance e Validazione

La validazione sperimentale su benchmark TSPLIB con istanze fino a 52 città dimostra che TN-GEO può superare le euristiche classiche, come gli algoritmi di swap e 2-opt hill-climbing. Le varianti a k-siti, che si concentrano maggiormente sulle correlazioni locali, mostrano risultati migliori rispetto al caso MPS completo.