Problema del commesso viaggiatore: un punto di vista basato sul feedback positivo = Travel salesman problem: a model based on positive feedback

In questo testo verranno presentate strategie meta-euristiche applicate a un noto problema di ottimizzazione stocastica: il problema del commesso viaggiatore. La dimensione dello spazio di ricerca rende difficile l'adozione di tecniche più analitiche, orientando il percorso verso metodi intuitivi che agiscano attraverso il rilevamento di soluzioni sub-ottime via via più accurate. Alla base degli algoritmi vi è l’interazione tra agenti semplici, ovvero dotati di un numero limitato di operazioni e di scelte, i quali procedono per tentativi che vengono progressivamente raffinati tramite le informazioni che ciascun agente riceve dagli altri. Tale processo di comunicazione viene integrato da un'euristica base che permette di indirizzare la ricerca nelle prime fasi. Infine, una strategia di calcolo distribuito è utile nell’ostacolare il processo dalla convergenza a un ottimo locale. I primi cinque capitoli prendono spunto dal paper "Positive Feedback as a Search Strategy'' ad opera di M.Dorigo, V.Maniezzo, A.Colorni, nei modelli utilizzati e nel tipo di analisi svolte. In particolare, nel capitolo 1 viene definito il problema e vengono presentati alcuni possibili approcci a esso, tra cui quello ad agenti che è stato effettivamente utilizzato per risolverlo. Nel capitolo 2 vengono descritte nel dettaglio le dinamiche del modello e quindi il funzionamento dell'algoritmo. Nel capitolo 3 sono riportati alcuni risultati relativi a una topologia regolare di griglia 4 x 4. Nel capitolo 4 sono presentati risultati relativi a una topologia irregolare, il problema Oliver30. Nel capitolo 5 viene presentata una variante dell'algoritmo classico con i relativi risultati di convergenza. Nel capitolo 6 vengono introdotte nuove varianti dell'algoritmo e diverse analisi sui modelli che ne risultano. Nel capitolo 7 l'algoritmo viene applicato ad altre topologie. Nel capitolo 8 sono presentate le conclusioni. In appendice sono riportati i codici utilizzati.