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

Partitioning di Grafi e Assegnazione Ottimale di Frequenze con Ricottura Simulativa (SA) Amelia Carolina Sparavigna1 e Gemini (Modello Linguistico di Google)2 1 DISAT, Politecnico di Torino, 2 Gemini AI DOI: 10.5281/zenodo.17511989 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. Partitioning Grafi Il Partitioning di Grafi è un problema fondamentale nell'informatica e nell'ingegneria (es. bilanciamento del carico di rete, progettazione di chip) che mira a suddividere i nodi di un grafo in $k$ sottoinsiemi, ottimizzando due obiettivi contrastanti: 1. Minimizzare il Cut-Set: Ridurre il numero di archi che attraversano il confine delle partizioni. 2. Mantenere il Bilanciamento: Assicurare che le partizioni abbiano dimensioni approssimativamente uguali. La Ricottura Simulativa è ideale perché gestisce efficacemente questa duplice esigenza. 1. Elementi di Ottimizzazione con SA Elemento SA Definizione nel Partitioning Note Stato L'assegnazione di ciascun nodo del grafo a una partizione (es. 0 o 1). Rappresentato da una lista o tupla di N elementi. Mossa Spostare un nodo casuale da una partizione all'altra (invertire l'appartenenza: 0 \ leftrightarrow 1). È il meccanismo di esplorazione locale. Obiettivo Trovare lo stato che minimizza l'Energia (E) totale. 2. La Funzione di Costo (Energia, E) L'Energia E è definita come una somma di due termini, che trasformano i due obiettivi contrastanti in costi da minimizzare: Componente del Costo Descrizione Tipo E_{Cut-Set} Il numero di archi del grafo che collegano due nodi appartenenti a partizioni diverse. Costo Soft (Prioritario) E_{Sbilanciamento} Una penalità (spesso quadratica) basata sulla differenza tra la dimensione attuale della partizione e la dimensione ideale (N/k). Costo Rigido 3. Ruolo Cruciale della Ricottura Simulativa L'SA è essenziale per sfuggire ai Minimi Locali in questo problema.  Il Dilemma del Minimo Locale: Spesso, una partizione perfettamente bilanciata può avere un cut-set molto alto. Un algoritmo di ricerca locale ingenuo si bloccherebbe in una soluzione leggermente peggiore ma più bilanciata.  Fase di Esplorazione (Alta T): L'SA, grazie al Criterio di Boltzmann, accetta temporaneamente mosse che aumentano il cut-set o sbilanciano leggermente le partizioni. Questo permette al nodo "bloccato" di attraversare il confine e raggiungere una configurazione che, nel lungo periodo, consente un miglioramento radicale del cut-set mantenendo un bilanciamento accettabile. In sintesi, l'SA bilancia efficacemente il compromesso tra la qualità del taglio e il bilanciamento delle partizioni, trovando l'optimum globale in cui il cut-set è minimo senza penalità eccessive per lo sbilanciamento. Proponiamo ora un esempio di partitioning. Assegnazione Ottimale delle Frequenze (FAP) con Ricottura Simulativa L'Assegnazione delle Frequenze (FAP) è un problema cruciale nelle telecomunicazioni (TV, radio, telefonia mobile). L'obiettivo è assegnare frequenze radio limitate a diverse stazioni o trasmettitori (celle), in modo da minimizzare le interferenze e massimizzare il riutilizzo delle frequenze. Il FAP è un problema di colorazione di grafi vincolato. 4. Elementi di Ottimizzazione con SA Elemento SA Definizione nel FAP Note Stato L'insieme delle frequenze assegnate a ciascun trasmettitore/cella. Una frequenza è un "colore" assegnato a un nodo. Mossa Cambiare la frequenza di un singolo trasmettitore/cella in una frequenza disponibile. Corrisponde al cambio di colore di un nodo. Obiettivo Trovare lo stato che minimizza l'Energia (E) totale (l'interferenza). 5. La Funzione di Costo (Energia, E) La Funzione di Energia (E) in questo contesto è dominata dal costo di interferenza e dai vincoli operativi. A. Costo Soft: Interferenza Questo costo è definito dalla violazione di due tipi principali di vincoli di interferenza: 1. Vincolo di Co-Canale: Due trasmettitori vicini non possono usare la stessa frequenza. 2. Vincolo di Canale Adiacente: Due trasmettitori vicini non possono usare frequenze troppo vicine (es. Frequenza 100 MHz e 100.1 MHz) per evitare lo "sconfinamento" del segnale. B. Costo Rigido Include penalità altissime se vengono violati requisiti assoluti, come l'assegnazione di frequenze al di fuori dello spettro disponibile o la violazione di requisiti di servizio fondamentali. 6. Ruolo della Ricottura Simulativa Il FAP ha una superficie energetica estremamente irregolare, piena di minimi locali (configurazioni con interferenza non ottimale).  Esplorazione (Alta ): L'SA sfrutta il Criterio di Boltzmann per accettare, ad alta temperatura, un temporaneo aumento delle interferenze. o Perché? L'algoritmo potrebbe aver bisogno di cambiare la frequenza di una stazione (aumentando temporaneamente l'interferenza) per liberare la frequenza ideale necessaria a una stazione critica, permettendo così un riaggiustamento globale che riduce l'interferenza totale finale.  Sfruttamento (Bassa ): Mentre la temperatura scende, l'SA si concentra sull'eliminazione delle ultime violazioni, convergendo verso l'assegnazione con la minima interferenza complessiva. L'uso dell'SA permette di trovare un'allocazione delle frequenze che è quasi ottimale in termini di riutilizzo dello spettro, garantendo al contempo la qualità del servizio per gli utenti. https://colab.research.google.com/drive/1ZdoP6000oE8FD5exhxdHBXvZ7EIbCykO?usp=sharing PROGRAMMI PYTHON Esempio Partitioning GRAFI Esempio Partitioning Frequenze