polito.it
Politecnico di Torino (logo)

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

Luca Campanello

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

Rel. Luigi Preziosi, Marco Scianna. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Matematica, 2021

[img]
Preview
PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (2MB) | Preview
Abstract:

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.

Relatori: Luigi Preziosi, Marco Scianna
Anno accademico: 2021/22
Tipo di pubblicazione: Elettronica
Numero di pagine: 67
Soggetti:
Corso di laurea: Corso di laurea magistrale in Ingegneria Matematica
Classe di laurea: Nuovo ordinamento > Laurea magistrale > LM-44 - MODELLISTICA MATEMATICO-FISICA PER L'INGEGNERIA
Aziende collaboratrici: NON SPECIFICATO
URI: http://webthesis.biblio.polito.it/id/eprint/19864
Modifica (riservato agli operatori) Modifica (riservato agli operatori)