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, dellordine
di 50. Se il grafo è più grande, è necessario un algoritmo non
lineare. Un GA è una delle alternative.
Per limplementazione abbiamo usato GATSS, un Algoritmo
Genetico basato sul problema del Commesso Viaggiatore scritto in
GNU C++ e collegato a uninterfaccia HTML tramite un
CGI-script. Non è niente di nuovo nella scienza dei GA, è solo
un algoritmo rinchiuso in uninterfaccia grafica che
permette di modificare i parametri di funzionamento dellalgoritmo
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 uninterfaccia
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