Treffer: Colonie di formiche artificiali e ottimizzazione combinatoria

This thesis analyzes, experiments with, and develops algorithms inspired by the behavior of ant colonies, known as Ant Colony System (ACS), for solving combinatorial optimization problems. A central case study is the Traveling Salesman Problem (TSP), a classic in the field of operations research. The work examines the natural dynamics of ant colonies, focusing on their cooperative behavior and the use of pheromones as a mechanism to reinforce optimal paths. This behavior is translated into an artificial system based on autonomous agents that simulate ant behavior to identify optimal solutions. In addition to describing and analyzing the ACS algorithm, the thesis proposes variations to enhance performance and provides detailed comparisons with other optimization methods, including Simulated Annealing, Genetic Algorithms, and Neural Networks. A significant emphasis is placed on the experimental analysis of results using a custom simulation environment developed for this research. The thesis concludes by introducing a new algorithm in the ACS family, whose effectiveness is tested through a series of case studies. This work represents a significant contribution to the study of bio-inspired techniques for solving complex problems. Author: Vladimiro Borsi Supervisor: Dr. Luca Maria Gambardella Co-supervisors: Dr. Stefania Bandini, Prof. Giancarlo Mauri Academic Year: 1994-1995 University: Università degli Studi di Milano, Faculty of Mathematical, Physical, and Natural Sciences ; Questa tesi di laurea affronta l'analisi, la sperimentazione e lo sviluppo di algoritmi ispirati al comportamento delle colonie di formiche, denominati ACS (Ant Colony System), per la risoluzione di problemi di ottimizzazione combinatoria. Uno degli esempi principali trattati è il Problema del Commesso Viaggiatore (Traveling Salesman Problem, TSP), un classico nel campo della ricerca operativa. La tesi esplora il funzionamento delle colonie di formiche naturali, modellando le loro dinamiche cooperative e l'uso del feromone come mezzo per ...