Rete di Hopfield applicata al
problema del TSP
Federica Bazzano 197112
Traveling Salesman Problem
Dato un numero finito di città A, B, C,..., e le distanze dij fra
esse, il problema consiste nella determinazione di un tour
ovvero una sequenza di città da visitare, in modo che ogni
città venga visitata una sola volta, minimizzando il percorso
seguito e ritornando alla città di partenza.
•
Applicazione della rete di Hopfield al
Per risolvere con la rete TSP
di Hopfield il problema del TSP
occorre stabilire una corrispondenza tra variabili di stato
della rete e variabili del problema, tra la funzione energia e
la funzione obiettivo;
• Un tour viene rappresentato tramite una matrice quadrata
V(n x n) dove la (x, i)-esima componente è pari ad 1 se la xesima città viene attraversata al i-esimo step del tour, 0
altrimenti. Indicheremo con vx,i una generica componente di
V;
• Chiameremo D ∈ ℜn×n la matrice delle distanze dove la (x,
y)-esima componente rappresenta la distanza tra la x-esima
e la y-esima città. Indicheremo con dx, y la generica
Funzione energia
L’evoluzione dinamica della rete di Hopfield, a partire dallo
stato iniziale, fa diminuire la funzione energia, fin quando non
si arriva in uno stato che rappresenta un minimo locale della
funzione energia e che, vista la corrispondenza tra funzione
energia e funzione obiettivo, potrebbe costituire una “buona”
soluzione del problema combinatorio.
• E1: Vincolo di riga, solo 1 città presente in una riga;
• E2: Vincolo di colonna, solo 1 città presente in una colonna;
• E3: Vincolo globale, tutte le n città attraversate;
• E4: Vincolo sulla distanza, la distanza totale percorsa sia
minima;
Matrice dei pesi
• Una volta trovata la funzione energia corrispondente alla
funzione obiettivo del problema del TSP, può essere
determinata la matrice dei pesi per la rete;
• Dopo vari passaggi per ricondurre la funzione energia nella
sua classica notazione, si è ottenuto:
E = - 12 × ååååvx,i × vy, j éë-D × d x,y × (d j,i-1 + d j,i+1 ) - A × dx,y × (1- di, j ) - B × di, j × (1- dx,y ) - Cùû - ååC × n × vx,i
x
y
i
j
x
i
• da cui segue che possiamo risolvere il problema del TSP
utilizzando la matrice dei pesi W che ha come (x+i, y+i)esima componente:
w(x,i)( y, j ) = éë-D × dx,y × (d j,i-1 + d j,i+1 ) - A × dx,y × (1- di, j ) - B × di, j × (1- dx,y ) - Cùû
Funzione di attivazione
• La funzione di attivazione segue anch’essa vari vincoli per
ottenere un percorso valido e può essere definita come
segue:æ
ö
é
ù
a
aij = Dt çç - tij - AåVxj - BåVyi - C êååVxj - mú - Då dxy éëVy,i+1 +Vy,i-1 ùû÷÷
êë x j
úû
j¹i
y¹x
y
è
ø
• Dove aij rappresenta l’attivazione per l’unità in riga i-esima e
colonna j-esima,  ed m rappresentano una costante di
tempo e un parametro;
• il primo termine della funzione di attivazione decresce ad
ogni iterazione, il secondo, terzo, quarto e quinto
rappresentano i vincoli per ottenere un tour valido.
Funzione di output
• La funzione di uscita invece è la seguente:
Vxi = (1+ tanh(laij )) / 2 "x,i, j
• dove Vxi è l’output del
neurone, il valore di 
determina la pendenza
della
funzione
e
la
tangente iperbolica da un
output
come
quello
mostrato in figura.
Procedura di apprendimento
1. Inizializzazione:
i. Matrice delle distanze;
ii. Matrice dei pesi;
iii. Vettore di input casuale : uxi(0) = u00 + ((rand-1)/20.0);
2. Si presenta l’input alla rete e si calcola l’attivazione iniziale
come:
aij = åå wij × uxj (i) "x
i
1. Si calcola l’output
j
Vxi = (1+ tanh(laij )) / 2 "x,i, j
Procedura di apprendimento
4. Si itera
aij(new) = aij(old ) + Daij
Vxi = (1+ tanh(laij )) / 2
finchè un criterio di stop non è soddisfatto.
Criteri di stop:
• Raggiungimento di un fissato intervallo di tempo;
• Raggiungimento di uno stato stabile;
• Raggiungimento del numero massimo di iterazioni.
5. Si trova un tour e si calcola la lunghezza del percorso.
Conclusioni
Nella risoluzione del TSP con la rete di Hopfield l'ottimalità
non è sempre garantita e il sistema potrebbe cadere in minimi
locali.
Il risultato potrebbe essere migliorato aggiungendo rumore
alle dinamiche di rete, per creare una sorta di differenziazione
nella speranza che il sistema evolva nonostante la vicinanza
ad un minimo locale.