Colonie di formiche artificiali e ottimizzazione combinatoria
Creators: name: Borsi, Vladimiro
name: Borsi, Vladimiro
name: Bandini, Stefania
name: Mauri, Giancarlo
name: Gambardella, Luca Maria
Publisher: name: Zenodo
Year: 2024
Subjects: Ant Colony Optimization (ACO)
Ant Colony System (ACS)
Traveling Salesman Problem (TSP)
Combinatorial Optimization
Bio-inspired Algorithms
Optimization Algorithms
Computational Intelligence
Optimization
Combinatorial Optimization and Mathematical Modeling
Algorithm Design
Bio-inspired Systems
Behavioral Modeling of Ant Colonies
Algorithm Analysis and Computational Experiments

description: 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
description: 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 rafforzare percorsi ottimali. Questo comportamento viene tradotto in un sistema artificiale basato su agenti autonomi che simulano il comportamento delle formiche per identificare soluzioni ottimali. Oltre a descrivere e analizzare l'algoritmo ACS, vengono proposte varianti per migliorare l'efficacia e vengono condotti confronti dettagliati con altri metodi di ottimizzazione, tra cui il Simulated Annealing, gli Algoritmi Genetici e le Reti Neurali.

Particolare enfasi è posta sull'analisi sperimentale dei risultati, utilizzando un ambiente di simulazione sviluppato appositamente per questa ricerca. La tesi si conclude proponendo un nuovo algoritmo della famiglia ACS, la cui validità è testata attraverso una serie di casi studio. Questo lavoro rappresenta un contributo significativo allo studio delle tecniche bio-ispirate per la risoluzione di problemi complessi.



Autore: Vladimiro Borsi

Relatore: Dott. Luca Maria Gambardella

Correlatori: Dott.ssa Stefania Bandini, Prof. Giancarlo Mauri

Anno Accademico: 1994-1995

Università: Università degli Studi di Milano, Facoltà di Scienze Matematiche, Fisiche e Naturali