IL PROBLEMA DEL COMMESSO VIAGGIATORE
 
 

Il problema del commesso viaggiatore (Traveling Salesman problem) è uno dei problemi classici che possono essere risolti utilizzando un algoritmo genetico. Riguarda un commesso viaggiatore che deve visitare ogni città in una data rete prima di tornare al punto iniziale, e completare il suo viaggio. Il problema richiede il percorso più economico, cioè un percorso chiuso che passa attraverso ciascun nodo nel grafo (città) e il cui costo totale (cioè la distanza totale percorsa) sia minimo.
Le sue varianti sono il disegno di linee telefoniche e circuiti integrati, o la programmazione robot industriali. In tutte queste applicazioni, la capacità di trovare un percorso economico nel grafo in questione può essere abbastanza cruciale.
TS è un problema NPC (Non deterministico Polinomiale - tempo Completo) che è  in pratica è irrisolvibile con un algoritmo lineare standard se la complessità del problema è abbastanza elevata. Il TSP può essere risolto con un computer molto veloce quando il numero di nodi è, ad esempio, dell’ordine di 50. Se il grafo è più grande, è necessario un algoritmo non lineare. Un GA è una delle alternative.
Per l’implementazione abbiamo usato GATSS, un Algoritmo Genetico basato sul problema del Commesso Viaggiatore scritto in GNU C++ e collegato a un’interfaccia HTML tramite un  CGI-script. Non è niente di nuovo nella scienza dei GA, è solo un algoritmo rinchiuso in un’interfaccia grafica  che permette di modificare i parametri di funzionamento dell’algoritmo genetico e mostra graficamente i risultati. Può essere usato come tool per insegnare i concetti degli Algoritmi Genetici.

Il  TSP è un buon esempio per mostrare come funzionano i GA. E’ un problema grafico-teorico ben conosciuto e i risultati possono essere  facilmente visualizzati.
GATSS è molto simile a  DOUGAL. Le differenze principali sono che GATSS è implementato  in C++ e ha un’interfaccia utente HTML.
 
 

Algoritmi GATSS
System Overview
Analisi dei test 1-7
Analisi dei test 8-10

Sito di GATSS: permette di utilizzare il programma in linea e scaricare i codici