Partitioning di Grafi e Assegnazione Ottimale di Frequenze con Ricottura Simulativa (SA)

Questo studio esamina l'applicazione dell'algoritmo di Ricottura Simulativa (Simulated Annealing, SA) come euristica efficace per risolvere due problemi fondamentali di ottimizzazione combinatoria: il Partitioning di Grafi e l'Assegnazione Ottimale delle Frequenze (FAP). Entrambi i problemi sono caratterizzati da superfici energetiche complesse e numerosi minimi locali. Nel Partitioning di Grafi, l'SA è impiegato per bilanciare l'esigenza di minimizzare il Cut-Set (archi che attraversano il confine) con il vincolo rigido di mantenere il bilanciamento dimensionale delle partizioni. Analogamente, nell'Assegnazione delle Frequenze (FAP), l'SA gestisce un sistema di vincoli complessi (interferenze Co-Canale e Canale Adiacente) per trovare l'allocazione che minimizza l'interferenza e massimizza il riutilizzo dello spettro. L'efficacia dell'SA risiede nella sua fase di Esplorazione stocastica. Sfruttando il Criterio di Boltzmann, l'algoritmo accetta, in modo probabilistico, variazioni di stato che aumentano temporaneamente il costo, permettendo così di sfuggire ai minimi locali. Questo meccanismo assicura una convergenza verso soluzioni globalmente quasi-ottimali che soddisfano in modo efficiente i vincoli contrastanti richiesti dall'ingegneria e dalle telecomunicazioni.