Dalle Catene di Markov al Simulated Annealing: Fondamenti, Algoritmi e Applicazioni

This thesis analyzes the Simulated Annealing algorithm, a probabilistic technique for global optimization inspired by the physical process of metal annealing. In this process, a metal is heated above its recrystallization temperature, held at high temperature to allow atomic migration and the reduction of structural defects, and then slowly cooled to increase its ductility. After a brief introduction to Markov chains and the Monte Carlo algorithm, the functioning of Simulated Annealing is presented in detail, with particular emphasis on the role of the cooling schedule and the concept of optimal annealing. In the final part, the algorithm is applied to the Travelling Salesman Problem, a classic combinatorial optimization problem in which one seeks the shortest possible route that visits a series of cities exactly once and returns to the starting point. Simulated Annealing proves to be an effective approach for producing high-quality approximate solutions, even in the presence of numerous local minima.

Questa tesi analizza l’algoritmo di Simulated Annealing, una tecnica probabilistica per l’ottimizzazione globale ispirata al processo fisico della ricottura dei metalli. In tale processo, un metallo viene riscaldato al di sopra della temperatura di cristallizzazione, mantenuto ad alta temperatura per consentire la migrazione atomica e la riduzione dei difetti strutturali, e infine raffreddato lentamente per aumentarne la duttilità. Dopo una breve introduzione alle Catene di Markov e all’algoritmo Monte Carlo, viene presentato nel dettaglio il funzionamento del Simulated Annealing, con particolare attenzione al ruolo della cooling schedule e al concetto di annealing ottimale. Nella parte finale, l’algoritmo viene applicato al problema del commesso viaggiatore, un classico problema combinatorio in cui si cerca il percorso più breve che consenta di visitare una serie di città una sola volta ciascuna e di ritornare al punto di partenza. Il Simulated Annealing si dimostra un approccio efficace nel fornire soluzioni approssimate di alta qualità anche in presenza di numerosi minimi locali.